Re: [PATCH 4/8] add functions for memory-efficient bitmaps
On Tue, Jul 01, 2014 at 09:57:13AM -0700, Junio C Hamano wrote: > Another thing I noticed was that the definition of and the > commentary on bitset_equal() and bitset_empty() sounded somewhat > "undecided". These functions take "max" that is deliberately named > differently from "num_bits" (the width of the bitsets involved), > inviting to use them for testing only earlier bits in the bitset as > long as the caller understands the caveat, but the caveat requires > that the partial bitset to test must be byte-aligned, which makes it > not very useful in practice, which means we probably do not want > them to be used for any "max" other than "num_bits". Yeah, I added that comment because I found "max" to be confusing, but couldn't think of a better name. I'm not sure why "num_bits" did not occur to me, as that makes it completely obvious. > * take "num_bits", not "max", to clarify that callers must use them >only on the full bitset. This seems like the right solution to me. Handling partially aligned bytes adds to the complexity and may hurt performance (in fact, I think bitset_equal could actually just call memcmp, which I should fix). That's fine if callers care about that feature, but I actually don't anticipate any that do. By the way, I chose "unsigned char" as the storage format somewhat arbitrarily. Performance might be better with "unsigned int" or even "unsigned long". It means potentially wasting more space, but not more than one word (minus a byte) per commit (so about 3MB on linux.git). I'll try to do some timings to see if it's worth doing. > In either case, there needs another item in the "caller's responsibility" > list at the beginning of bitset.h: > > 4. Ensure that padding bits at the end of the bitset array are >initialized to 0. Agreed. That is definitely a requirement I had in mind, but I didn't think to write it down. I'll fix both points in the re-roll. -Peff -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 4/8] add functions for memory-efficient bitmaps
Jeff King writes:
> On Sun, Jun 29, 2014 at 03:41:37AM -0400, Eric Sunshine wrote:
>
>> > +static inline void bitset_set(unsigned char *bits, int n)
>> > +{
>> > + bits[n / CHAR_BIT] |= 1 << (n % CHAR_BIT);
>> > +}
>>
>> Is it intentional or an oversight that there is no way to clear a bit
>> in the set?
>
> Intentional in the sense that I had no need for it in my series, and I
> didn't think about it. I doubt many callers would want it, since commit
> traversals tend to propagate bits through the graph, and then clean them
> up all at once. And the right way to clean up slabbed data like this is
> to just clear the slab.
>
> Of course somebody may use the code for something besides commit
> traversals. But I'd rather avoid adding dead code on the off chance that
> somebody uses it later (and then gets to find out whether it even works
> or not!).
Another thing I noticed was that the definition of and the
commentary on bitset_equal() and bitset_empty() sounded somewhat
"undecided". These functions take "max" that is deliberately named
differently from "num_bits" (the width of the bitsets involved),
inviting to use them for testing only earlier bits in the bitset as
long as the caller understands the caveat, but the caveat requires
that the partial bitset to test must be byte-aligned, which makes it
not very useful in practice, which means we probably do not want
them to be used for any "max" other than "num_bits".
They probably would want either:
* be made to truly honor max < num_bits case, by special casing the
last byte that has max-th bit, to officially allow them to be
used for partial bitset test; or
* take "num_bits", not "max", to clarify that callers must use them
only on the full bitset.
In either case, there needs another item in the "caller's responsibility"
list at the beginning of bitset.h:
4. Ensure that padding bits at the end of the bitset array are
initialized to 0.
In the description of bitset_sizeof(), the comment hints it by using
xcalloc() in the example, but a careless user may be tempted to
implement bitset_clr() and then do:
int i;
unsigned char *bits = malloc(bitset_sizeof(nr));
for (i = 0; i < nr; i++)
bitset_clr(bits, i);
assert(bitset_empty(bits, nr));
and the implementation of bitset_empty(), even if we rename
s/max/num_bits/, will choke if (nr % CHAR_BIT) and malloc() gave us
non-zero bit in the padding.
For the sake of simplicity, I am inclined to vote for not allowing
their use on a partial-sub-bitset.
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 4/8] add functions for memory-efficient bitmaps
On Sun, Jun 29, 2014 at 03:41:37AM -0400, Eric Sunshine wrote:
> > +static inline void bitset_set(unsigned char *bits, int n)
> > +{
> > + bits[n / CHAR_BIT] |= 1 << (n % CHAR_BIT);
> > +}
>
> Is it intentional or an oversight that there is no way to clear a bit
> in the set?
Intentional in the sense that I had no need for it in my series, and I
didn't think about it. I doubt many callers would want it, since commit
traversals tend to propagate bits through the graph, and then clean them
up all at once. And the right way to clean up slabbed data like this is
to just clear the slab.
Of course somebody may use the code for something besides commit
traversals. But I'd rather avoid adding dead code on the off chance that
somebody uses it later (and then gets to find out whether it even works
or not!).
-Peff
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 4/8] add functions for memory-efficient bitmaps
On Wed, Jun 25, 2014 at 7:40 PM, Jeff King wrote:
> We already have a nice-to-use bitmap implementation in
> ewah/bitmap.c. It pretends to be infinitely long when asking
> for a bit (and just returns 0 for bits that haven't been
> allocated or set), and dynamically resizes as appropriate
> when you set bits.
>
> The cost to this is that each bitmap must store its own
> pointer and length, using up to 16 bytes per bitmap on top
> of the actual bit storage. This is a lot of storage (not to
> mention an extra level of pointer indirection) if you are
> going to store one bitmap per commit in a traversal.
>
> These functions provide an alternative bitmap implementation
> that can be used when you have a large number of fixed-size
> bitmaps. See the documentation in the header file for
> details and examples.
>
> Signed-off-by: Jeff King
> ---
> diff --git a/bitset.h b/bitset.h
> new file mode 100644
> index 000..5fbc956
> --- /dev/null
> +++ b/bitset.h
> @@ -0,0 +1,113 @@
> +#ifndef BITSET_H
> +#define BITSET_H
> +
> + * Return the number of unsigned chars required to store num_bits bits.
> + *
> + * This is mostly used internally by the bitset functions, but you may need
> it
> + * when allocating the bitset. Example:
> + *
> + * bits = xcalloc(1, bitset_sizeof(nr));
> + */
> +static inline int bitset_sizeof(int num_bits)
> +{
> + return (num_bits + CHAR_BIT - 1) / CHAR_BIT;
> +}
> +
> +/*
> + * Set the bit at position "n". "n" is counted from zero, and must be
> + * smaller than the num_bits given to bitset_sizeof when allocating the
> bitset.
> + */
> +static inline void bitset_set(unsigned char *bits, int n)
> +{
> + bits[n / CHAR_BIT] |= 1 << (n % CHAR_BIT);
> +}
Is it intentional or an oversight that there is no way to clear a bit
in the set?
> +/*
> + * Return the bit at position "n" (see bitset_set for a description of "n").
> + */
> +static inline int bitset_get(unsigned char *bits, int n)
> +{
> + return !!(bits[n / CHAR_BIT] & (1 << (n % CHAR_BIT)));
> +}
> +
> +/*
> + * Return true iff the bitsets contain the same bits. Each bitset should be
> the
> + * same size, and should have been allocated using bitset_sizeof(max).
> + *
> + * Note that it is not safe to check partial equality by providing a smaller
> + * "max" (we assume any bits beyond "max" up to the next CHAR_BIT boundary
> are
> + * zeroed padding).
> + */
> +static inline int bitset_equal(unsigned char *a, unsigned char *b, int max)
> +{
> + int i;
> + for (i = bitset_sizeof(max); i > 0; i--)
> + if (*a++ != *b++)
> + return 0;
> + return 1;
> +}
> +
> +/*
> + * Bitwise-or the bitsets in "dst" and "src", and store the result in "dst".
> + *
> + * See bitset_equal for the definition of "max".
> + */
> +static inline void bitset_or(unsigned char *dst, const unsigned char *src,
> int max)
> +{
> + int i;
> + for (i = bitset_sizeof(max); i > 0; i--)
> + *dst++ |= *src++;
> +}
> +
> +/*
> + * Returns true iff the bitset contains all zeroes.
> + *
> + * See bitset_equal for the definition of "max".
> + */
> +static inline int bitset_empty(const unsigned char *bits, int max)
> +{
> + int i;
> + for (i = bitset_sizeof(max); i > 0; i--, bits++)
> + if (*bits)
> + return 0;
> + return 1;
> +}
> +
> +#endif /* BITSET_H */
> --
> 2.0.0.566.gfe3e6b2
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 4/8] add functions for memory-efficient bitmaps
On Thu, Jun 26, 2014 at 05:15:05AM +0200, Torsten Bögershausen wrote:
> > + */
> > +static inline int bitset_sizeof(int num_bits)
> > +{
> > + return (num_bits + CHAR_BIT - 1) / CHAR_BIT;
> > +}
> Just a general question about the usage of "int" here (and at other places):
> Is there a special reason for new code to allow num_bits to be negative ?
No. I usually choose "int" when the word size is not likely to matter
(i.e., we do not expect it to overflow a 32-bit integer, nor to have so
many that I need to be careful not to waste space).
Probably "unsigned int" would be a more descriptive choice.
It may also help the compiler optimize better. Assuming CHAR_BIT is 8
(i.e., most everywhere), we get:
(num_bits + 7) / 8
Presumably the compiler implements the division with a right-shift.
Marking num_bits as unsigned should let us do just a logical shift,
without worrying about the sign. And indeed, here are the signed and
unsigned versions produced by "gcc -S -O2" (for an equivalent
non-inlined function):
[signed]
leal14(%rdi), %edx
movl%edi, %eax
addl$7, %eax
cmovs %edx, %eax
sarl$3, %eax
ret
[unsigned]
leal7(%rdi), %eax
shrl$3, %eax
ret
Much simpler, though see below for practical considerations.
> To my knowledge all the size_t definitions these days are positive,
> because a size can not be negative.
size_t is perhaps a reasonable choice for the return value, given the name
"sizeof". But if you really care about using the whole range of bits there, you
need a data type for num_bits that is CHAR_BIT times larger.
> Should we use
> "unsigned" here ?
> or "unsigned int" ?
Yes, I think so. Both are the same to the compiler. I have a vague
recollection that we prefer one over the other, but grepping seems to
find many examples of each in our code.
I'm squashing in the patch below. I couldn't measure any speed
improvement. I'm guessing because the functions are all inlined, which
means we likely get away with calculating bitset_sizeof once outside of
our loop. I think the result is still more obvious to read, though.
-Peff
---
diff --git a/bitset.h b/bitset.h
index 5fbc956..268545b 100644
--- a/bitset.h
+++ b/bitset.h
@@ -45,7 +45,7 @@
*
* bits = xcalloc(1, bitset_sizeof(nr));
*/
-static inline int bitset_sizeof(int num_bits)
+static inline unsigned bitset_sizeof(unsigned num_bits)
{
return (num_bits + CHAR_BIT - 1) / CHAR_BIT;
}
@@ -54,7 +54,7 @@ static inline int bitset_sizeof(int num_bits)
* Set the bit at position "n". "n" is counted from zero, and must be
* smaller than the num_bits given to bitset_sizeof when allocating the bitset.
*/
-static inline void bitset_set(unsigned char *bits, int n)
+static inline void bitset_set(unsigned char *bits, unsigned n)
{
bits[n / CHAR_BIT] |= 1 << (n % CHAR_BIT);
}
@@ -62,7 +62,7 @@ static inline void bitset_set(unsigned char *bits, int n)
/*
* Return the bit at position "n" (see bitset_set for a description of "n").
*/
-static inline int bitset_get(unsigned char *bits, int n)
+static inline unsigned bitset_get(unsigned char *bits, unsigned n)
{
return !!(bits[n / CHAR_BIT] & (1 << (n % CHAR_BIT)));
}
@@ -75,9 +75,10 @@ static inline int bitset_get(unsigned char *bits, int n)
* "max" (we assume any bits beyond "max" up to the next CHAR_BIT boundary are
* zeroed padding).
*/
-static inline int bitset_equal(unsigned char *a, unsigned char *b, int max)
+static inline int bitset_equal(unsigned char *a, unsigned char *b,
+ unsigned max)
{
- int i;
+ unsigned i;
for (i = bitset_sizeof(max); i > 0; i--)
if (*a++ != *b++)
return 0;
@@ -89,9 +90,10 @@ static inline int bitset_equal(unsigned char *a, unsigned
char *b, int max)
*
* See bitset_equal for the definition of "max".
*/
-static inline void bitset_or(unsigned char *dst, const unsigned char *src, int
max)
+static inline void bitset_or(unsigned char *dst, const unsigned char *src,
+unsigned max)
{
- int i;
+ unsigned i;
for (i = bitset_sizeof(max); i > 0; i--)
*dst++ |= *src++;
}
@@ -101,9 +103,9 @@ static inline void bitset_or(unsigned char *dst, const
unsigned char *src, int m
*
* See bitset_equal for the definition of "max".
*/
-static inline int bitset_empty(const unsigned char *bits, int max)
+static inline int bitset_empty(const unsigned char *bits, unsigned max)
{
- int i;
+ unsigned i;
for (i = bitset_sizeof(max); i > 0; i--, bits++)
if (*bits)
return 0;
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 4/8] add functions for memory-efficient bitmaps
On 2014-06-26 01.40, Jeff King wrote:
[]
> + */
> +static inline int bitset_sizeof(int num_bits)
> +{
> + return (num_bits + CHAR_BIT - 1) / CHAR_BIT;
> +}
Just a general question about the usage of "int" here (and at other places):
Is there a special reason for new code to allow num_bits to be negative ?
To my knowledge all the size_t definitions these days are positive,
because a size can not be negative.
As a reader of the code I always wonder if there is a special meaning with
negative values, (as the result of read() to indicate an error) but there isn't.
Should we use
"unsigned" here ?
or "unsigned int" ?
or "size_t" (Which may use 64 bits, which feels like a overkill)
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH 4/8] add functions for memory-efficient bitmaps
We already have a nice-to-use bitmap implementation in
ewah/bitmap.c. It pretends to be infinitely long when asking
for a bit (and just returns 0 for bits that haven't been
allocated or set), and dynamically resizes as appropriate
when you set bits.
The cost to this is that each bitmap must store its own
pointer and length, using up to 16 bytes per bitmap on top
of the actual bit storage. This is a lot of storage (not to
mention an extra level of pointer indirection) if you are
going to store one bitmap per commit in a traversal.
These functions provide an alternative bitmap implementation
that can be used when you have a large number of fixed-size
bitmaps. See the documentation in the header file for
details and examples.
Signed-off-by: Jeff King
---
Makefile | 1 +
bitset.h | 113 +++
2 files changed, 114 insertions(+)
create mode 100644 bitset.h
diff --git a/Makefile b/Makefile
index 07ea105..8158fd2 100644
--- a/Makefile
+++ b/Makefile
@@ -633,6 +633,7 @@ LIB_H += archive.h
LIB_H += argv-array.h
LIB_H += attr.h
LIB_H += bisect.h
+LIB_H += bitset.h
LIB_H += blob.h
LIB_H += branch.h
LIB_H += builtin.h
diff --git a/bitset.h b/bitset.h
new file mode 100644
index 000..5fbc956
--- /dev/null
+++ b/bitset.h
@@ -0,0 +1,113 @@
+#ifndef BITSET_H
+#define BITSET_H
+
+/*
+ * This header file provides functions for operating on an array of unsigned
+ * characters as a bitmap. There is zero per-bitset storage overhead beyond the
+ * actual number of stored bits (modulo some padding). This is efficient, but
+ * makes the API harder to use. In particular, each bitset does not know how
+ * long it is. It is the caller's responsibility to:
+ *
+ * 1. Never ask to get or set a bit outside of the allocated range.
+ *
+ * 2. Provide the allocated range to any functions which operate
+ * on the whole bitset (e.g., bitset_or).
+ *
+ * 3. Always feed bitsets of the same size to functions which require it
+ * (e.g., bitset_or).
+ *
+ * It is mostly intended to be used with commit-slabs to store N bits per
+ * commit. Here's an example:
+ *
+ * define_commit_slab(bit_slab, unsigned char);
+ *
+ * ... assume we want to store nr bits per commit ...
+ * struct bit_slab bits;
+ * init_bit_slab_with_stride(&bits, bitset_sizeof(nr));
+ *
+ * ... set a bit (make sure 10 < nr!) ...
+ * bitset_set(bit_slab_at(&bits, commit), 10);
+ *
+ * ... or get a bit ...
+ * if (bitset_get(bit_slab_at(&bits, commit), 5))
+ *
+ * ... propagate bits to a parent commit ...
+ * bitset_or(bit_slab_at(&bits, parent),
+ *bit_slab_at(&bits, commit),
+ *nr);
+ */
+
+/*
+ * Return the number of unsigned chars required to store num_bits bits.
+ *
+ * This is mostly used internally by the bitset functions, but you may need it
+ * when allocating the bitset. Example:
+ *
+ * bits = xcalloc(1, bitset_sizeof(nr));
+ */
+static inline int bitset_sizeof(int num_bits)
+{
+ return (num_bits + CHAR_BIT - 1) / CHAR_BIT;
+}
+
+/*
+ * Set the bit at position "n". "n" is counted from zero, and must be
+ * smaller than the num_bits given to bitset_sizeof when allocating the bitset.
+ */
+static inline void bitset_set(unsigned char *bits, int n)
+{
+ bits[n / CHAR_BIT] |= 1 << (n % CHAR_BIT);
+}
+
+/*
+ * Return the bit at position "n" (see bitset_set for a description of "n").
+ */
+static inline int bitset_get(unsigned char *bits, int n)
+{
+ return !!(bits[n / CHAR_BIT] & (1 << (n % CHAR_BIT)));
+}
+
+/*
+ * Return true iff the bitsets contain the same bits. Each bitset should be the
+ * same size, and should have been allocated using bitset_sizeof(max).
+ *
+ * Note that it is not safe to check partial equality by providing a smaller
+ * "max" (we assume any bits beyond "max" up to the next CHAR_BIT boundary are
+ * zeroed padding).
+ */
+static inline int bitset_equal(unsigned char *a, unsigned char *b, int max)
+{
+ int i;
+ for (i = bitset_sizeof(max); i > 0; i--)
+ if (*a++ != *b++)
+ return 0;
+ return 1;
+}
+
+/*
+ * Bitwise-or the bitsets in "dst" and "src", and store the result in "dst".
+ *
+ * See bitset_equal for the definition of "max".
+ */
+static inline void bitset_or(unsigned char *dst, const unsigned char *src, int
max)
+{
+ int i;
+ for (i = bitset_sizeof(max); i > 0; i--)
+ *dst++ |= *src++;
+}
+
+/*
+ * Returns true iff the bitset contains all zeroes.
+ *
+ * See bitset_equal for the definition of "max".
+ */
+static inline int bitset_empty(const unsigned char *bits, int max)
+{
+ int i;
+ for (i = bitset_sizeof(max); i > 0; i--, bits++)
+ if (*bits)
+ return 0;
+ return 1;
+}
+
+#endif /* BITSET_H */
--
2.0.0.566.gfe3e6b2
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info a
