On Fri, 22 Aug 2008, Arnd Bergmann wrote:
quoted text > On Friday 22 August 2008, Jared Hulbert wrote:
> > If I have an array of u64 numbers tracking small numbers (a[0] = 1;
> > a[1] = 2;) just throwing that onmedia is a big waste.
> > (0x0000000000000001; 0x0000000000000002) Having different array types
> > for different images such as arrays of u8,u16,u32,u64 becomes less
> > efficient for 3,5,6 and 7 byte numbers, 3 bytes was a particularly
> > interesting size for me.
> >
> > All I'm doing is removing the totally unnecessary zeros and aligning by bytes.
> > Take an array of u64 like this :
> > 0x0000000000000005
> > 0x0000000000001001
> > 0x00000000000a0000
> >
> > I strip off the unneeded leading zeros:
> > 0x000005
> > 0x001001
> > 0x0a0000
> >
> > Then pack them to byte alignment:
> > 0x0000050010010a0000
> >
> > Sure it could be encoded more but that would make it harder to extract
> > the data. This way I can read the data in one, maybe two, cache
> > misses. A couple of shifts to deal with the alignment and endianness
> > and we are done.
>
> So do I understand right that 3 bytes is your minimum size, and going
> smaller than that would not be helpful? Otherwise I would assume that
> storing a '5' should only take one byte instead of three.
From the paper, the minimum size (called `depth') is 1.
quoted text > I don't unsterstand yet why you store the length of each word separate
> from the word. Most variable-length codes store that implicitly in
> the data itself, e.g. in the upper three bits, so that for storing
> 0x5, 0x1001, 0xa0000, this could e.g. end up as 0x054010014a0000,
> which is shorter than what you have, but not harder to decode.
AFAIU, the length (`depth') of each word is not stored separate, as the
depth is the same for all values in the same table.
With kind regards,
Geert Uytterhoeven
Software Architect
Sony Techsoft Centre Europe
The Corporate Village
