lkml.org 
[lkml]   [2008]   [Aug]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [PATCH 03/10] AXFS: axfs.h
    > This bytetable stuff looks overly complicated, both the data structure and
    > the access method. It seems like you are implementing your own custom Huffman
    > compression with this.
    >
    > Is the reasonn for the bytetable just to pack numbers efficiently, or do you
    > have a different intention?

    It looks more complicated than it is. I need a data structure that is
    64bit capable, easily read-in-place (remember this is designed to be
    an XIP fs), and highly space efficient. Because it's XIP I didn't
    want something that required a lot of calculation nor something that
    made you incur a lot of cache misses. So yes I just want to pack
    numbers in an easily read-in-place fashion.

    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.

    > Did you see a significant size benefit over simply storing all metadata as
    > uncompressed data structures like in cramfs?

    Yes. For some modest values of significant. In terms of the amount of
    space required to track the metadata it is more dramatic. For a small
    rootfs I can fit many of the data structures in an u8 array, while
    maintaining u64 compatibility. Compared to dumping u64 arrays onmedia
    that's an 8X savings. But it's an 8X savings of a smallish percentage
    of the image size. The difference is more pronounced on a smaller
    (2MB) filesystem I tested but it was only ~5% if memory serves me
    correct.

    > Have you considered storing simple dentry/inode data in node_type==Compressed
    > nodes?

    Yes, I thought a lot about that. But I choose against it because I
    wanted read-in-place data structures for minimum RAM usage in the XIP
    case and I figure the way I do it would stat() faster.


    \
     
     \ /
      Last update: 2008-08-22 00:43    [W:2.391 / U:0.032 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site