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, the

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 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,

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 any

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 p...@peff.net 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

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 [...] I think

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 jrnie...@gmail.com # ARMv5 -- To unsubscribe from this list: send the line unsubscribe git in the body

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); } ... foo =

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 didn't

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, especially

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 casting

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

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 v2, we

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 access

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 8, and so

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-byte

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 tan...@gmail.com 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