Re: [PATCH v4 08/23] ewah: compressed bitmap implementation
Jeff King wrote: > On Thu, Jan 23, 2014 at 02:17:55PM -0800, Jonathan Nieder wrote: >> I don't think that's a big issue. A pair of 4-byte reads would not be >> too slow. > > The header is actually two separate 4-byte values, so that's fine. But > between the header and trailer are a series of 8-byte data values, and > that is what we need the 8-byte alignment for. Sorry for the lack of clarity. What I meant is that a 4-byte aligned 8-byte value can be read using a pair of 4-byte reads, which is less of a performance issue than a completely unaligned value. [...] > Anyway, this is all academic until we are designing bitmap v2, which I > do not plan on doing anytime soon. Sure, fair enough. :) Jonathan -- 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 v4 08/23] ewah: compressed bitmap implementation
On Thu, Jan 23, 2014 at 02:17:55PM -0800, Jonathan Nieder wrote: > Jeff King wrote: > > On Thu, Jan 23, 2014 at 09:53:26PM +, brian m. carlson wrote: > > >> Yes, it will. SPARC requires all loads be naturally aligned (4-byte to > >> an address that's a multiple of 4, 8-byte to a multiple of 8, and so > >> on). In general, architectures that do not support unaligned access > >> require natural alignment for all quantities. > > > > In that case, I think we cannot even blame Shawn. The ewah serialization > > format itself (which JGit inherited from the javaewah library) has 8 > > bytes of header and 4 bytes of trailer. So packed serialized ewahs > > wouldn't be 8-byte aligned > > I don't think that's a big issue. A pair of 4-byte reads would not be > too slow. The header is actually two separate 4-byte values, so that's fine. But between the header and trailer are a series of 8-byte data values, and that is what we need the 8-byte alignment for. So the _first_ ewah's data is 8-byte aligned, but then it offsets the alignment with a single 4-byte trailer. So the next ewah, if they are packed in a sequence, is will have its data misaligned. You could solve it by putting an empty 4-byte pad at the end of each ewah (and of course making sure the first one is 8-byte aligned). Anyway, this is all academic until we are designing bitmap v2, which I do not plan on doing anytime soon. -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 v4 08/23] ewah: compressed bitmap implementation
Jeff King wrote: > On Thu, Jan 23, 2014 at 09:53:26PM +, brian m. carlson wrote: >> Yes, it will. SPARC requires all loads be naturally aligned (4-byte to >> an address that's a multiple of 4, 8-byte to a multiple of 8, and so >> on). In general, architectures that do not support unaligned access >> require natural alignment for all quantities. > > In that case, I think we cannot even blame Shawn. The ewah serialization > format itself (which JGit inherited from the javaewah library) has 8 > bytes of header and 4 bytes of trailer. So packed serialized ewahs > wouldn't be 8-byte aligned I don't think that's a big issue. A pair of 4-byte reads would not be too slow. Even on x86, aligned reads are supposed to be faster than unaligned reads (though I haven't looked at benchmarks recently). -- 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 v4 08/23] ewah: compressed bitmap implementation
On Thu, Jan 23, 2014 at 09:53:26PM +, brian m. carlson wrote: > On Thu, Jan 23, 2014 at 03:26:45PM -0500, Jeff King wrote: > > Looking over the format, I think the only thing preventing 4-byte > > alignment is the 1-byte XOR-offset and 1-byte flags field for each > > bitmap. If we ever have a v2, we could pad the sum of those out to 4 > > bytes. Is 4-byte alignment enough? We do treat the actual data as 64-bit > > integers. I wonder if that would have problems on Sparc64, for example. > > Yes, it will. SPARC requires all loads be naturally aligned (4-byte to > an address that's a multiple of 4, 8-byte to a multiple of 8, and so > on). In general, architectures that do not support unaligned access > require natural alignment for all quantities. In that case, I think we cannot even blame Shawn. The ewah serialization format itself (which JGit inherited from the javaewah library) has 8 bytes of header and 4 bytes of trailer. So packed serialized ewahs wouldn't be 8-byte aligned (though of course he could have added his own padding to each when we have a sequence of them). -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 v4 08/23] ewah: compressed bitmap implementation
On Thu, Jan 23, 2014 at 03:26:45PM -0500, Jeff King wrote: > Looking over the format, I think the only thing preventing 4-byte > alignment is the 1-byte XOR-offset and 1-byte flags field for each > bitmap. If we ever have a v2, we could pad the sum of those out to 4 > bytes. Is 4-byte alignment enough? We do treat the actual data as 64-bit > integers. I wonder if that would have problems on Sparc64, for example. Yes, it will. SPARC requires all loads be naturally aligned (4-byte to an address that's a multiple of 4, 8-byte to a multiple of 8, and so on). In general, architectures that do not support unaligned access require natural alignment for all quantities. Also, even on architectures where the kernel can fix these alignment issues up, the cost of doing so is a two context switches (in and out of the kernel), servicing the trap, two loads, some shifts and rotates, and a kernel message, so many people disable alignment fixups. I know it made things extremely slow on Alpha. ARM is even more fun since if you don't take the trap, it loads the data rotated, so the load happens, it just silently returns the wrong data. -- brian m. carlson / brian with sandals: Houston, Texas, US +1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only OpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187 signature.asc Description: Digital signature
Re: [PATCH v4 08/23] ewah: compressed bitmap implementation
On Thu, Jan 23, 2014 at 03:03:11PM -0500, Jeff King wrote:
> > My main worry about the patches is that they will probably run into
> > an analagous problem to the one that v1.7.12-rc0~1^2~2 (block-sha1:
> > avoid pointer conversion that violates alignment constraints,
> > 2012-07-22) solved. By casting the pointer to (uint32_t *) we are
> > telling the compiler it is 32-bit aligned (C99 section 6.3.2.3).
>
> Yeah, maybe. We go via memcpy, which takes a "void *", so that part is
> good. However, the new code looks like:
>
> foo = align_ntohl(*(uint32_t *)ptr);
>
> I think this probably works in practice because align_ntohl is inlined,
> and any sane compiler will never actually load the variable. If we
> change the signature of align_ntohl, we can do this:
Actually, it is a little trickier than that. We actually take the
address in the macro. So even without inlining, we end up casting to
void. I still think this:
> uint32_t align_ntohl(void *ptr)
> {
> uint32_t x;
> memcpy(x, ptr, sizeof(x));
> return ntohl(x);
> }
is a little more obvious, though. It does mean that everybody has to
pass a pointer, though, and on platforms where non-aligned reads are OK,
we do the cast ourselves. That means that:
foo = align_ntohl(&bar);
will not be able to do any type-checking for "bar" (say, when we are
pulling "bar" straight out of a packed struct). I don't know how much
we care.
-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 v4 08/23] ewah: compressed bitmap implementation
On Thu, Jan 23, 2014 at 12:23:42PM -0800, Jonathan Nieder wrote: > > The memcpy solution is taken from read-cache.c, but as we noted, it > > probably hasn't been used a lot. The blk_sha1 get_be may be faster, as > > it converts as it reads. > > I doubt there's much difference either way, especially after an > optimizer gets its hands on it. According to [1] ARM has no fast > byte swap instruction so with -O0 the byte-at-a-time implementation is > probably faster there. I can try a performance test if you like. If you're curious and have time, go ahead and benchmark what I posted against what you posted (with your fix). But you'll probably need a big repo like the kernel to notice anything. But I don't mind that much if we just use the memcpy trick for now. It's nice and obvious, and we can always change it later if somebody has numbers (I doubt it will be all that noticeable anyway; this isn't nearly as tight a loop as the BLK_SHA1 code). -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 v4 08/23] ewah: compressed bitmap implementation
On Thu, Jan 23, 2014 at 12:14:03PM -0800, Shawn Pearce wrote: > > Yes, the mmap'd buffers aren't necessarily word-aligned. I don't think > > we can fix that easily without changing the on-disk format (which comes > > from JGit anyway). > > Ouch, sorry about that. JGit doesn't mmap the file so we didn't think > about the impact of words not being aligned. I should have caught > that, but I didn't. Looking over the format, I think the only thing preventing 4-byte alignment is the 1-byte XOR-offset and 1-byte flags field for each bitmap. If we ever have a v2, we could pad the sum of those out to 4 bytes. Is 4-byte alignment enough? We do treat the actual data as 64-bit integers. I wonder if that would have problems on Sparc64, for example. -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 v4 08/23] ewah: compressed bitmap implementation
Jeff King wrote:
> If we
> change the signature of align_ntohl, we can do this:
>
> uint32_t align_ntohl(void *ptr)
> {
> uint32_t x;
> memcpy(x, ptr, sizeof(x));
> return ntohl(x);
> }
>
> ...
>
> foo = align_ntohl(ptr);
>
> The memcpy solution is taken from read-cache.c, but as we noted, it
> probably hasn't been used a lot. The blk_sha1 get_be may be faster, as
> it converts as it reads.
I doubt there's much difference either way, especially after an
optimizer gets its hands on it. According to [1] ARM has no fast
byte swap instruction so with -O0 the byte-at-a-time implementation is
probably faster there. I can try a performance test if you like.
Jonathan
[1] http://thread.gmane.org/gmane.comp.version-control.git/125737
--
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 v4 08/23] ewah: compressed bitmap implementation
Jeff King wrote: > [1/2]: compat: move unaligned helpers to bswap.h > [2/2]: ewah: support platforms that require aligned reads After setting NEEDS_ALIGNED_ACCESS, Tested-by: Jonathan Nieder # ARMv5 -- 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 v4 08/23] ewah: compressed bitmap implementation
On Thu, Jan 23, 2014 at 12:12:23PM -0800, Jonathan Nieder wrote: > Jeff King wrote: > > On Thu, Jan 23, 2014 at 11:52:06AM -0800, Jonathan Nieder wrote: > > >> My main worry about the patches is that they will probably run into > >> an analagous problem to the one that v1.7.12-rc0~1^2~2 > [...] > > I think this probably works in practice because align_ntohl is inlined, > > and any sane compiler will never actually load the variable. > > I don't think that's safe to rely on. The example named above didn't > pose any problems except on one platform. All the relevant functions > were static and easy to inline. GCC just followed the standard > literally and chose to break by reading one word at a time, just like > in this case it could break e.g. by copying one word at a time in > __builtin_memcpy (which seems perfectly reasonable to me --- > optimization involves a lot of constraint solving, and if you can't > trust your constraints then there's not much you can do). I wasn't disagreeing with you. I was guessing at why it did not fail out of the box when I tested it. What do you think of the alternative I posted? -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 v4 08/23] ewah: compressed bitmap implementation
On Thu, Jan 23, 2014 at 10:33 AM, Jeff King wrote: > On Wed, Jan 22, 2014 at 06:05:36PM -0800, Jonathan Nieder wrote: > >> Jeff King wrote: >> >> > EWAH is a word-aligned compressed variant of a bitset (i.e. a data >> > structure that acts as a 0-indexed boolean array for many entries). >> >> I suspect that for some callers it's not word-aligned. > > Yes, the mmap'd buffers aren't necessarily word-aligned. I don't think > we can fix that easily without changing the on-disk format (which comes > from JGit anyway). Ouch, sorry about that. JGit doesn't mmap the file so we didn't think about the impact of words not being aligned. I should have caught that, but I didn't. -- 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 v4 08/23] ewah: compressed bitmap implementation
Jeff King wrote: > On Thu, Jan 23, 2014 at 11:52:06AM -0800, Jonathan Nieder wrote: >> My main worry about the patches is that they will probably run into >> an analagous problem to the one that v1.7.12-rc0~1^2~2 [...] > I think this probably works in practice because align_ntohl is inlined, > and any sane compiler will never actually load the variable. I don't think that's safe to rely on. The example named above didn't pose any problems except on one platform. All the relevant functions were static and easy to inline. GCC just followed the standard literally and chose to break by reading one word at a time, just like in this case it could break e.g. by copying one word at a time in __builtin_memcpy (which seems perfectly reasonable to me --- optimization involves a lot of constraint solving, and if you can't trust your constraints then there's not much you can do). -- 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 v4 08/23] ewah: compressed bitmap implementation
On Thu, Jan 23, 2014 at 11:52:06AM -0800, Jonathan Nieder wrote:
> > After my patches, t5310 runs fine for me. I didn't try your patch, but
> > mine are similar. Let me know if you still see the problem (there may
> > simply be a bug in yours, but I didn't see it).
>
> I had left out a cast to unsigned, producing an overflow.
>
> My main worry about the patches is that they will probably run into
> an analagous problem to the one that v1.7.12-rc0~1^2~2 (block-sha1:
> avoid pointer conversion that violates alignment constraints,
> 2012-07-22) solved. By casting the pointer to (uint32_t *) we are
> telling the compiler it is 32-bit aligned (C99 section 6.3.2.3).
Yeah, maybe. We go via memcpy, which takes a "void *", so that part is
good. However, the new code looks like:
foo = align_ntohl(*(uint32_t *)ptr);
I think this probably works in practice because align_ntohl is inlined,
and any sane compiler will never actually load the variable. If we
change the signature of align_ntohl, we can do this:
uint32_t align_ntohl(void *ptr)
{
uint32_t x;
memcpy(x, ptr, sizeof(x));
return ntohl(x);
}
...
foo = align_ntohl(ptr);
The memcpy solution is taken from read-cache.c, but as we noted, it
probably hasn't been used a lot. The blk_sha1 get_be may be faster, as
it converts as it reads. However, the bulk of the data is copied via
a single memcpy and then modified in place. I don't know if that would
be faster or not (for a big-endian system it probably is, since we can
omit the modification loop entirely).
-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 v4 08/23] ewah: compressed bitmap implementation
Jeff King wrote: > Here's a patch series (on top of jk/pack-bitmap, naturally) that lets > t5310 pass there. I assume the ARM problem is the same, though seeing > the failure in realloc() is unexpected. Can you try it on both your > platforms with these patches? Thanks. Trying it out now. [...] >> Hopefully it's possible to get the alignment right in the caller >> and tweak the signature to require that instead of using unaligned >> reads like this. There's still something wrong after this patch --- >> the new result is a NULL pointer dereference in t5310.7 "enumerate >> --objects (full bitmap)". > > After my patches, t5310 runs fine for me. I didn't try your patch, but > mine are similar. Let me know if you still see the problem (there may > simply be a bug in yours, but I didn't see it). I had left out a cast to unsigned, producing an overflow. My main worry about the patches is that they will probably run into an analagous problem to the one that v1.7.12-rc0~1^2~2 (block-sha1: avoid pointer conversion that violates alignment constraints, 2012-07-22) solved. By casting the pointer to (uint32_t *) we are telling the compiler it is 32-bit aligned (C99 section 6.3.2.3). Thanks, Jonathan -- 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 v4 08/23] ewah: compressed bitmap implementation
On Wed, Jan 22, 2014 at 06:05:36PM -0800, Jonathan Nieder wrote: > Jeff King wrote: > > > EWAH is a word-aligned compressed variant of a bitset (i.e. a data > > structure that acts as a 0-indexed boolean array for many entries). > > I suspect that for some callers it's not word-aligned. Yes, the mmap'd buffers aren't necessarily word-aligned. I don't think we can fix that easily without changing the on-disk format (which comes from JGit anyway). However, since we are memcpying the bulk of the data into a newly allocated buffer (which must be aligned), we can do that first, and then fix the endian-ness in place. The only SPARC machine I have access to is running Solaris, but after some slight wrestling with the BYTE_ORDER macros, I managed to get it to compile and reproduced the bus error. Here's a patch series (on top of jk/pack-bitmap, naturally) that lets t5310 pass there. I assume the ARM problem is the same, though seeing the failure in realloc() is unexpected. Can you try it on both your platforms with these patches? [1/2]: compat: move unaligned helpers to bswap.h [2/2]: ewah: support platforms that require aligned reads > Hopefully it's possible to get the alignment right in the caller > and tweak the signature to require that instead of using unaligned > reads like this. There's still something wrong after this patch --- > the new result is a NULL pointer dereference in t5310.7 "enumerate > --objects (full bitmap)". After my patches, t5310 runs fine for me. I didn't try your patch, but mine are similar. Let me know if you still see the problem (there may simply be a bug in yours, but I didn't see it). -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 v4 08/23] ewah: compressed bitmap implementation
Hi,
Jeff King wrote:
> EWAH is a word-aligned compressed variant of a bitset (i.e. a data
> structure that acts as a 0-indexed boolean array for many entries).
I suspect that for some callers it's not word-aligned.
Without the following squashed in, commits 212f2ffb and later fail t5310
on some machines[1].
On ARMv5:
expecting success:
git rev-list --test-bitmap HEAD
*** Error in `/«PKGBUILDDIR»/git': realloc(): invalid pointer:
0x008728b0 ***
Aborted
not ok 3 - rev-list --test-bitmap verifies bitmaps
On sparc:
expecting success:
git rev-list --test-bitmap HEAD
Bus error
not ok 3 - rev-list --test-bitmap verifies bitmaps
Hopefully it's possible to get the alignment right in the caller
and tweak the signature to require that instead of using unaligned
reads like this. There's still something wrong after this patch ---
the new result is a NULL pointer dereference in t5310.7 "enumerate
--objects (full bitmap)".
(gdb) run
Starting program: /home/jrnieder/src/git/git rev-list --objects
--use-bitmap-index HEAD
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/sparc-linux-gnu/libthread_db.so.1".
537ea4d3eb79c95f602873b1167c480006d2ac2d
[...]
ec635144f60048986bc560c5576355344005e6e7
Program received signal SIGSEGV, Segmentation fault.
0x001321c0 in sha1_to_hex (sha1=0x0) at hex.c:68
68 unsigned int val = *sha1++;
(gdb) bt
#0 0x001321c0 in sha1_to_hex (sha1=0x0) at hex.c:68
#1 0x000b839c in show_object_fast (sha1=0x0, type=OBJ_TREE, exclude=0,
name_hash=0, found_pack=0x2b8480, found_offset=4338) at builtin/rev-list.c:270
#2 0x00158abc in show_objects_for_type (objects=0x2b2498,
type_filter=0x2b0fb0, object_type=OBJ_TREE, show_reach=0xb834c
) at pack-bitmap.c:640
#3 0x001592d0 in traverse_bitmap_commit_list (show_reachable=0xb834c
) at pack-bitmap.c:818
#4 0x000b894c in cmd_rev_list (argc=2, argv=0xd688, prefix=0x0) at
builtin/rev-list.c:369
#5 0x00014024 in run_builtin (p=0x256e38 , argc=4,
argv=0xd688) at git.c:314
#6 0x00014330 in handle_builtin (argc=4, argv=0xd688) at git.c:487
#7 0x000144a8 in run_argv (argcp=0xd5ec, argv=0xd5a0) at git.c:533
#8 0x000146fc in main (argc=4, av=0xd684) at git.c:616
(gdb) frame 2
#2 0x00158abc in show_objects_for_type (objects=0x2b2498,
type_filter=0x2b0fb0, object_type=OBJ_TREE, show_reach=0xb834c
) at pack-bitmap.c:640
640 show_reach(sha1, object_type, 0, hash,
bitmap_git.pack, entry->offset);
(gdb) p entry->nr
$1 = 4294967295
Line numbers are in the context of 8e6341d9. Ideas?
[1] ARMv5 and sparc:
https://buildd.debian.org/status/logs.php?pkg=git&suite=experimental
diff --git a/ewah/ewah_io.c b/ewah/ewah_io.c
index aed0da6..696a8ec 100644
--- a/ewah/ewah_io.c
+++ b/ewah/ewah_io.c
@@ -110,25 +110,38 @@ int ewah_serialize(struct ewah_bitmap *self, int fd)
return ewah_serialize_to(self, write_helper, (void *)(intptr_t)fd);
}
+#define get_be32(p) ( \
+ (*((unsigned char *)(p) + 0) << 24) | \
+ (*((unsigned char *)(p) + 1) << 16) | \
+ (*((unsigned char *)(p) + 2) << 8) | \
+ (*((unsigned char *)(p) + 3) << 0) )
+
+#define get_be64(p) ( \
+ ((uint64_t) get_be32(p) << 32) | \
+ get_be32((unsigned char *)(p) + 4) )
+
int ewah_read_mmap(struct ewah_bitmap *self, void *map, size_t len)
{
- uint32_t *read32 = map;
- eword_t *read64;
+ unsigned char *p = map;
size_t i;
- self->bit_size = ntohl(*read32++);
- self->buffer_size = self->alloc_size = ntohl(*read32++);
+ self->bit_size = get_be32(p);
+ p += 4;
+ self->buffer_size = self->alloc_size = get_be32(p);
+ p += 4;
self->buffer = ewah_realloc(self->buffer,
self->alloc_size * sizeof(eword_t));
if (!self->buffer)
return -1;
- for (i = 0, read64 = (void *)read32; i < self->buffer_size; ++i)
- self->buffer[i] = ntohll(*read64++);
+ for (i = 0; i < self->buffer_size; ++i) {
+ self->buffer[i] = get_be64(p);
+ p += 8;
+ }
- read32 = (void *)read64;
- self->rlw = self->buffer + ntohl(*read32++);
+ self->rlw = self->buffer + get_be32(p);
+ p += 4;
return (3 * 4) + (self->buffer_size * 8);
}
--
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 v4 08/23] ewah: compressed bitmap implementation
From: Vicent Marti
EWAH is a word-aligned compressed variant of a bitset (i.e. a data
structure that acts as a 0-indexed boolean array for many entries).
It uses a 64-bit run-length encoding (RLE) compression scheme,
trading some compression for better processing speed.
The goal of this word-aligned implementation is not to achieve
the best compression, but rather to improve query processing time.
As it stands right now, this EWAH implementation will always be more
efficient storage-wise than its uncompressed alternative.
EWAH arrays will be used as the on-disk format to store reachability
bitmaps for all objects in a repository while keeping reasonable sizes,
in the same way that JGit does.
This EWAH implementation is a mostly straightforward port of the
original `javaewah` library that JGit currently uses. The library is
self-contained and has been embedded whole (4 files) inside the `ewah`
folder to ease redistribution.
The library is re-licensed under the GPLv2 with the permission of Daniel
Lemire, the original author. The source code for the C version can
be found on GitHub:
https://github.com/vmg/libewok
The original Java implementation can also be found on GitHub:
https://github.com/lemire/javaewah
Signed-off-by: Vicent Marti
Signed-off-by: Jeff King
---
Makefile | 11 +-
ewah/bitmap.c | 221
ewah/ewah_bitmap.c | 726 +
ewah/ewah_io.c | 193 ++
ewah/ewah_rlw.c| 115 +
ewah/ewok.h| 235 +
ewah/ewok_rlw.h| 114 +
7 files changed, 1613 insertions(+), 2 deletions(-)
create mode 100644 ewah/bitmap.c
create mode 100644 ewah/ewah_bitmap.c
create mode 100644 ewah/ewah_io.c
create mode 100644 ewah/ewah_rlw.c
create mode 100644 ewah/ewok.h
create mode 100644 ewah/ewok_rlw.h
diff --git a/Makefile b/Makefile
index 48ff0bd..64a1ed7 100644
--- a/Makefile
+++ b/Makefile
@@ -667,6 +667,8 @@ LIB_H += diff.h
LIB_H += diffcore.h
LIB_H += dir.h
LIB_H += exec_cmd.h
+LIB_H += ewah/ewok.h
+LIB_H += ewah/ewok_rlw.h
LIB_H += fetch-pack.h
LIB_H += fmt-merge-msg.h
LIB_H += fsck.h
@@ -800,6 +802,10 @@ LIB_OBJS += dir.o
LIB_OBJS += editor.o
LIB_OBJS += entry.o
LIB_OBJS += environment.o
+LIB_OBJS += ewah/bitmap.o
+LIB_OBJS += ewah/ewah_bitmap.o
+LIB_OBJS += ewah/ewah_io.o
+LIB_OBJS += ewah/ewah_rlw.o
LIB_OBJS += exec_cmd.o
LIB_OBJS += fetch-pack.o
LIB_OBJS += fsck.o
@@ -2474,8 +2480,9 @@ profile-clean:
$(RM) $(addsuffix *.gcno,$(addprefix $(PROFILE_DIR)/, $(object_dirs)))
clean: profile-clean coverage-clean
- $(RM) *.o *.res block-sha1/*.o ppc/*.o compat/*.o compat/*/*.o
xdiff/*.o vcs-svn/*.o \
- builtin/*.o $(LIB_FILE) $(XDIFF_LIB) $(VCSSVN_LIB)
+ $(RM) *.o *.res block-sha1/*.o ppc/*.o compat/*.o compat/*/*.o
+ $(RM) xdiff/*.o vcs-svn/*.o ewah/*.o builtin/*.o
+ $(RM) $(LIB_FILE) $(XDIFF_LIB) $(VCSSVN_LIB)
$(RM) $(ALL_PROGRAMS) $(SCRIPT_LIB) $(BUILT_INS) git$X
$(RM) $(TEST_PROGRAMS) $(NO_INSTALL)
$(RM) -r bin-wrappers $(dep_dirs)
diff --git a/ewah/bitmap.c b/ewah/bitmap.c
new file mode 100644
index 000..710e58c
--- /dev/null
+++ b/ewah/bitmap.c
@@ -0,0 +1,221 @@
+/**
+ * Copyright 2013, GitHub, Inc
+ * Copyright 2009-2013, Daniel Lemire, Cliff Moon,
+ * David McIntosh, Robert Becho, Google Inc. and Veronika Zenz
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
USA.
+ */
+#include "git-compat-util.h"
+#include "ewok.h"
+
+#define MASK(x) ((eword_t)1 << (x % BITS_IN_WORD))
+#define BLOCK(x) (x / BITS_IN_WORD)
+
+struct bitmap *bitmap_new(void)
+{
+ struct bitmap *bitmap = ewah_malloc(sizeof(struct bitmap));
+ bitmap->words = ewah_calloc(32, sizeof(eword_t));
+ bitmap->word_alloc = 32;
+ return bitmap;
+}
+
+void bitmap_set(struct bitmap *self, size_t pos)
+{
+ size_t block = BLOCK(pos);
+
+ if (block >= self->word_alloc) {
+ size_t old_size = self->word_alloc;
+ self->word_alloc = block * 2;
+ self->words = ewah_realloc(self->words,
+ self->word_alloc * sizeof(eword_t));
+
+ memset(self->words + old_size, 0x0,
+ (self->word_alloc - old_size) * sizeof(ew
