[PATCH] Revert "libsepol: cache ebitmap cardinality value"

[PATCH] Revert "libsepol: cache ebitmap cardinality value"

[Ondrej Mosnacek]

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(-)

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;
 }
 
-- 
2.24.1

Re: [PATCH] Revert "libsepol: cache ebitmap cardinality value"

[Stephen Smalley]

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>

Re: [PATCH] Revert "libsepol: cache ebitmap cardinality value"

[Stephen Smalley]

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.