| Message ID | 20200303094813.142288-1-omosnace@redhat.com (mailing list archive) |
|---|---|
| State | Accepted |
| Headers | show |
| Series | Revert "libsepol: cache ebitmap cardinality value" | expand |
On Tue, Mar 3, 2020 at 4:58 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > This reverts commit 542e878690ea1e310bed9adda6dcb28ca8cd1d53. > > After 6968ea977501 ("libsepol: make ebitmap_cardinality() of linear > complexity"), the caching only saves ~0.06 % of total semodule -BN > running time (on x86_64 without using the POPCNT instruction), so it's > no longer worth the added complexity. > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> Acked-by: Stephen Smalley <sds@tycho.nsa.gov>
On Tue, Mar 3, 2020 at 2:15 PM Stephen Smalley <stephen.smalley.work@gmail.com> wrote: > > On Tue, Mar 3, 2020 at 4:58 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > > > This reverts commit 542e878690ea1e310bed9adda6dcb28ca8cd1d53. > > > > After 6968ea977501 ("libsepol: make ebitmap_cardinality() of linear > > complexity"), the caching only saves ~0.06 % of total semodule -BN > > running time (on x86_64 without using the POPCNT instruction), so it's > > no longer worth the added complexity. > > > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> > > Acked-by: Stephen Smalley <sds@tycho.nsa.gov> Applied.
diff --git a/libsepol/include/sepol/policydb/ebitmap.h b/libsepol/include/sepol/policydb/ebitmap.h index 1abfdd71..910834dd 100644 --- a/libsepol/include/sepol/policydb/ebitmap.h +++ b/libsepol/include/sepol/policydb/ebitmap.h @@ -37,7 +37,6 @@ typedef struct ebitmap_node { typedef struct ebitmap { ebitmap_node_t *node; /* first node in the bitmap */ uint32_t highbit; /* highest position in the total bitmap */ - unsigned int cardinality; /* cached value of cardinality */ } ebitmap_t; #define ebitmap_is_empty(e) (((e)->highbit) == 0) diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c index a5108b71..963b8080 100644 --- a/libsepol/src/ebitmap.c +++ b/libsepol/src/ebitmap.c @@ -67,7 +67,6 @@ int ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1) ebitmap_destroy(dst); dst->node = tmp.node; dst->highbit = tmp.highbit; - dst->cardinality = 0; return 0; } @@ -131,13 +130,9 @@ unsigned int ebitmap_cardinality(ebitmap_t *e1) unsigned int count = 0; ebitmap_node_t *n; - if (e1->cardinality || e1->highbit == 0) - return e1->cardinality; - for (n = e1->node; n; n = n->next) { count += __builtin_popcountll(n->map); } - e1->cardinality = count; return count; } @@ -201,7 +196,6 @@ int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * src) } dst->highbit = src->highbit; - dst->cardinality = src->cardinality; return 0; } @@ -317,7 +311,6 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value) free(n); } } - e->cardinality = 0; /* invalidate cached cardinality */ return 0; } prev = n; @@ -348,7 +341,6 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value) e->node = new; } - e->cardinality = 0; /* invalidate cached cardinality */ return 0; } @@ -368,7 +360,6 @@ void ebitmap_destroy(ebitmap_t * e) e->highbit = 0; e->node = 0; - e->cardinality = 0; return; }
This reverts commit 542e878690ea1e310bed9adda6dcb28ca8cd1d53. After 6968ea977501 ("libsepol: make ebitmap_cardinality() of linear complexity"), the caching only saves ~0.06 % of total semodule -BN running time (on x86_64 without using the POPCNT instruction), so it's no longer worth the added complexity. Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> --- libsepol/include/sepol/policydb/ebitmap.h | 1 - libsepol/src/ebitmap.c | 9 --------- 2 files changed, 10 deletions(-)