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

From: Jeff King <peff@peff.net>
Date: Jan 23, 2014, 22:26 UTC
Message-ID: <20140123222632.GA2311@sigill.intra.peff.net>
In-Reply-To: <20140123221755.GA18964@google.com>

On Thu, Jan 23, 2014 at 02:17:55PM -0800, Jonathan Nieder wrote:

Show 15 quoted lines

> Jeff King wrote:
> > On Thu, Jan 23, 2014 at 09:53:26PM +0000, 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