* [PATCH 1/1] libsepol: make ebitmap_cardinality() of linear complexity
@ 2020-02-25 22:48 Nicolas Iooss
2020-02-27 8:46 ` Ondrej Mosnacek
0 siblings, 1 reply; 3+ messages in thread
From: Nicolas Iooss @ 2020-02-25 22:48 UTC (permalink / raw)
To: selinux
As ebitmap_get_bit() complexity is linear in the size of the bitmap, the
complexity of ebitmap_cardinality() is quadratic. This can be optimized
by browsing the nodes of the bitmap directly in ebitmap_cardinality().
While at it, use built-in function __builtin_popcountll() to count the
ones in the 64-bit value n->map for each bitmap node. This seems better
suited than "count++". This seems to work on gcc and clang on x86,
x86_64, ARM and ARM64 but if it causes compatibility issues with some
compilers or architectures (or with older versions of gcc or clang),
the use of __builtin_popcountll() can be replaced by a C implementation
of a popcount algorithm.
Signed-off-by: Nicolas Iooss <nicolas.iooss@m4x.org>
---
libsepol/src/ebitmap.c | 9 +++++----
1 file changed, 5 insertions(+), 4 deletions(-)
diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c
index d23444ce5064..a5108b7184c5 100644
--- a/libsepol/src/ebitmap.c
+++ b/libsepol/src/ebitmap.c
@@ -128,14 +128,15 @@ int ebitmap_andnot(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2, unsigned int ma
unsigned int ebitmap_cardinality(ebitmap_t *e1)
{
- unsigned int i, count = 0;
+ unsigned int count = 0;
+ ebitmap_node_t *n;
if (e1->cardinality || e1->highbit == 0)
return e1->cardinality;
- for (i=ebitmap_startbit(e1); i < ebitmap_length(e1); i++)
- if (ebitmap_get_bit(e1, i))
- count++;
+ for (n = e1->node; n; n = n->next) {
+ count += __builtin_popcountll(n->map);
+ }
e1->cardinality = count;
return count;
}
--
2.25.0
^ permalink raw reply related [flat|nested] 3+ messages in thread
* Re: [PATCH 1/1] libsepol: make ebitmap_cardinality() of linear complexity
2020-02-25 22:48 [PATCH 1/1] libsepol: make ebitmap_cardinality() of linear complexity Nicolas Iooss
@ 2020-02-27 8:46 ` Ondrej Mosnacek
2020-03-01 21:32 ` Nicolas Iooss
0 siblings, 1 reply; 3+ messages in thread
From: Ondrej Mosnacek @ 2020-02-27 8:46 UTC (permalink / raw)
To: Nicolas Iooss; +Cc: SElinux list
On Tue, Feb 25, 2020 at 11:49 PM Nicolas Iooss <nicolas.iooss@m4x.org> wrote:
> As ebitmap_get_bit() complexity is linear in the size of the bitmap, the
> complexity of ebitmap_cardinality() is quadratic. This can be optimized
> by browsing the nodes of the bitmap directly in ebitmap_cardinality().
>
> While at it, use built-in function __builtin_popcountll() to count the
> ones in the 64-bit value n->map for each bitmap node. This seems better
> suited than "count++". This seems to work on gcc and clang on x86,
> x86_64, ARM and ARM64 but if it causes compatibility issues with some
> compilers or architectures (or with older versions of gcc or clang),
> the use of __builtin_popcountll() can be replaced by a C implementation
> of a popcount algorithm.
>
> Signed-off-by: Nicolas Iooss <nicolas.iooss@m4x.org>
> ---
> libsepol/src/ebitmap.c | 9 +++++----
> 1 file changed, 5 insertions(+), 4 deletions(-)
>
> diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c
> index d23444ce5064..a5108b7184c5 100644
> --- a/libsepol/src/ebitmap.c
> +++ b/libsepol/src/ebitmap.c
> @@ -128,14 +128,15 @@ int ebitmap_andnot(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2, unsigned int ma
>
> unsigned int ebitmap_cardinality(ebitmap_t *e1)
> {
> - unsigned int i, count = 0;
> + unsigned int count = 0;
> + ebitmap_node_t *n;
>
> if (e1->cardinality || e1->highbit == 0)
> return e1->cardinality;
>
> - for (i=ebitmap_startbit(e1); i < ebitmap_length(e1); i++)
> - if (ebitmap_get_bit(e1, i))
> - count++;
> + for (n = e1->node; n; n = n->next) {
> + count += __builtin_popcountll(n->map);
> + }
> e1->cardinality = count;
> return count;
> }
> --
> 2.25.0
>
Acked-by: Ondrej Mosnacek <omosnace@redhat.com>
I'll check if the cardinality caching still makes any measurable
difference and if not, I'll post a revert patch.
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH 1/1] libsepol: make ebitmap_cardinality() of linear complexity
2020-02-27 8:46 ` Ondrej Mosnacek
@ 2020-03-01 21:32 ` Nicolas Iooss
0 siblings, 0 replies; 3+ messages in thread
From: Nicolas Iooss @ 2020-03-01 21:32 UTC (permalink / raw)
To: Ondrej Mosnacek, SElinux list
On Thu, Feb 27, 2020 at 9:46 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
>
> On Tue, Feb 25, 2020 at 11:49 PM Nicolas Iooss <nicolas.iooss@m4x.org> wrote:
> > As ebitmap_get_bit() complexity is linear in the size of the bitmap, the
> > complexity of ebitmap_cardinality() is quadratic. This can be optimized
> > by browsing the nodes of the bitmap directly in ebitmap_cardinality().
> >
> > While at it, use built-in function __builtin_popcountll() to count the
> > ones in the 64-bit value n->map for each bitmap node. This seems better
> > suited than "count++". This seems to work on gcc and clang on x86,
> > x86_64, ARM and ARM64 but if it causes compatibility issues with some
> > compilers or architectures (or with older versions of gcc or clang),
> > the use of __builtin_popcountll() can be replaced by a C implementation
> > of a popcount algorithm.
> >
> > Signed-off-by: Nicolas Iooss <nicolas.iooss@m4x.org>
> > ---
> > libsepol/src/ebitmap.c | 9 +++++----
> > 1 file changed, 5 insertions(+), 4 deletions(-)
> >
> > diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c
> > index d23444ce5064..a5108b7184c5 100644
> > --- a/libsepol/src/ebitmap.c
> > +++ b/libsepol/src/ebitmap.c
> > @@ -128,14 +128,15 @@ int ebitmap_andnot(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2, unsigned int ma
> >
> > unsigned int ebitmap_cardinality(ebitmap_t *e1)
> > {
> > - unsigned int i, count = 0;
> > + unsigned int count = 0;
> > + ebitmap_node_t *n;
> >
> > if (e1->cardinality || e1->highbit == 0)
> > return e1->cardinality;
> >
> > - for (i=ebitmap_startbit(e1); i < ebitmap_length(e1); i++)
> > - if (ebitmap_get_bit(e1, i))
> > - count++;
> > + for (n = e1->node; n; n = n->next) {
> > + count += __builtin_popcountll(n->map);
> > + }
> > e1->cardinality = count;
> > return count;
> > }
> > --
> > 2.25.0
> >
>
> Acked-by: Ondrej Mosnacek <omosnace@redhat.com>
>
> I'll check if the cardinality caching still makes any measurable
> difference and if not, I'll post a revert patch.
Thanks. I applied this patch.
Nicolas
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2020-03-01 21:32 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-02-25 22:48 [PATCH 1/1] libsepol: make ebitmap_cardinality() of linear complexity Nicolas Iooss
2020-02-27 8:46 ` Ondrej Mosnacek
2020-03-01 21:32 ` Nicolas Iooss
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.