| Message ID | 20200225224841.2693481-1-nicolas.iooss@m4x.org (mailing list archive) |
|---|---|
| State | Changes Requested |
| Headers | show |
| Series | [1/1] libsepol: make ebitmap_cardinality() of linear complexity | expand |
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.
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
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; }
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(-)