Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-23 Thread Jonathan Nieder
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-b

Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-23 Thread Jeff King
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

Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-23 Thread Jonathan Nieder
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 a

Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-23 Thread Jeff King
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

Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-23 Thread brian m. carlson
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 eno

Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-23 Thread Jeff King
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 c

Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-23 Thread Jeff King
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, especial

Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-23 Thread Jeff King
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

Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-23 Thread Jonathan Nieder
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); > } > > ... > >

Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-23 Thread Jonathan Nieder
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

Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-23 Thread Jeff King
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 > [...] >

Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-23 Thread Shawn Pearce
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 su

Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-23 Thread Jonathan Nieder
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

Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-23 Thread Jeff King
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 un

Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-23 Thread Jonathan Nieder
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. [...]

Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-23 Thread Jeff King
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, th

Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

2014-01-22 Thread Jonathan Nieder
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

[PATCH v4 08/23] ewah: compressed bitmap implementation

2013-12-21 Thread Jeff King
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-al