Re: [gui-dev] QueryRouteTable.java.patch (second version)

From: <[email protected]>
> Any container abstraction suffers from the need to very quickly be able to
> switch from one concrete representation to another.  In the specific case 
> of
> Integer array, we need to keep track of certain fill level after which the
> bitset representation becomes more efficient and be able to convert the 
> array
> to that bitset on the fly using minimal amounts of cpu. Needless to say, 
> any
> such conversion must be ultra-efficient when done both directions.
> Furthermore, the managing code which decides when to do the conversion 
> must be
> lightweight and optimal.
>
> Regarding various sub-bitset representations, we would ideally have an 
> algorithm
> which finds the optimal one for a given load factor/distribution.  My 
> hunch is
> that such algorithm would require memoization, but if anyone is aware of
> something greedy that would work, let us know.

My feeling is that we should manage large bitsets by splitting them into 
large enough (but not too much) fragments of fixed size, that could have 
each their own alternate representations, but that could each be converted 
quickly from one to the other.

Also, each fragment should be stored in a class inheriting from a common 
BitSetBased parent class. Large bitsets would also inherit from this parent 
class, but could simply be an array of small bitsets represented in one of 
the other BitSetBased derived classes.

Because, in fine, only small bitsets will be stored in the leaf nodes, it 
becomes easy to represent them in several alternate forms: uncompressed 
packed array of bits, no array at all (if all bits are set to 0 or to 1), 
RLE packing, or even a deflated form...

Which alternate form will be used will be computed by the parent node, 
performing the necessary cleanup for each fragment, without requiring too 
much work in memory (because fragments will have a maximum size, a single 
buffer can be reused to compute intermediate representations for every 
fragments)

Now some experimentation would be needed to determine which fragment size 
would be needed. If we want to be able to use the most compact forms, we 
need statistics on bitset fill rates. Immediately, it comes the fact that 
there are two types of QRP tables, with distinct fill rate averages:
- bitsets for QRP from leaf nodes, that are about 2 to 10% filled (with 64K 
tables), meaning that there's 1 bit set every 10 to 50 bits, i.e. with 
average unused gaps between 9 to 49 bits; not enough to perform a good 
compression with no array at all, but for which a Lempel-Ziv based 
compression (deflate?) would create significant compression.
- bitsets for QRP from ultrapeers, that are about 40 to 60% filled (with 64K 
tables), meaning that there's about as many bits set to 1 and to 0, in a 
pseudo-random distribution (as bits are set from a pseudo-random hash 
function), for which compression is likely to be very deceptive.

I think that byte-RLE compression of fragments will be rarely efficient, 
unless the bitset is really very sparse (fill rates below 1 bit set on 32, 
i.e. fill rates below 3%). But even at this level, a Lempel-Ziv compression 
may finally be more effective...

The choice of the compression function to use, will also affect performance: 
there's a tradeoff to find between expected compression level (to maximize 
the memory saved), and performance:

- bitsets for QRP tables from leaf nodes that share the least (lowest fill 
rates) could be maximaly compressed,

- but bitset for QRP tables from ultrapeers, or from leaf nodes that share a 
lot would probably use a lower compression level.

If we split large bitsets into small manageable fixed-size bitsets, we can 
cache for each of them a fill rate, and then determine which representation 
is the most appropriate. Additionally, when updating fragments dynamically, 
we are not required to compress these fragments to their best representation 
immediately (this can be differed and performed by a background process, 
which will need a constant and reusable maximum working memory, minimizing 
the VM memory fragmentation).


What do you think of this idea?


_______________________________________________
gui-dev mailing list
[email protected]
http://www.limewire.org/mailman/listinfo/gui-dev