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

From: "Zlatin Balevsky" <[email protected]>
> A small note on RLE - we could relatively easily modify our table reading 
> code to read directly from a RLE'd table; this alone could save us a lot 
> of memory on the leaf tables.  This seems like the easiest first step to 
> take.

It's just that I really doubt about the efficiency of RLE encoding for 
bitsets filled by QRP, whose set bits are more or less regularly distributed 
throughout the table.
Same thing about the tree encoding, for the same reason, because the tree 
structure itself will be hard and costly to compute on many levels, and a 
limited number of levels will necessarily have almost all branches filled 
with an actual node, at very moderate fill level.
For example, with a 64Kbit table, a 5% fill level means that there's one bit 
set every 20 bit (so the RLE compression will not be extremely performing, 
due to very short compressible lengths, and 20 bits will not be enough to 
avoid that all branches in a tree representation, where leaf nodes will need 
to represent some significant group of bits, will be present).

What is interesting to see first, is how many bits are set in leaf nodes 
(those for which we need the highest number of QRP tables, and so the 
highest number of large bitsets). On average it should represent 2 or 3 
times the number of shared files on each leaf node. If we expect (and 
measure) that on average, leaf nodes share about 300 files, this will set 
about 1000 bits in their bitset. To start being significantly compressible, 
a large bitset should be about 50 times this number, so this gives an 
initial bitset size of at least 50,000 bits; the current size of 64K bits is 
then very moderately compressible with RLE (I think we could gain no more 
than 10 to 20% of total size for 64K bitsets, i.e. a total size of about 80 
to 90% of an uncompressed bitset).

But if you double the size of the virtual bitset, you don't modify the 
number of total bits set, so the compression rate will be significantly 
higher, because all additional bits will be zeroes, so that the compressed 
data could be kept roughly at the same size as a 64Kbit table, effectively 
more than doubling the compression rate: suppose as above that we compressed 
the 64Kbit size at 80 to 90%, then the comrpessed data would be around 51 to 
57 Kbit; with a doubled virtual table size of 128Kbit, the compressed data 
would remain roughly at the same size of 51 to 57 Kbit, i.e. a compressed 
size at 40 to 45% of the uncompressed bitset.

The more we increase the virtual bitsize, the more the RLE compression will 
become effective to maintain (or not increase significantly the average 
compressed size).

The problem with this scheme is in its maintenance cost: now the compressed 
bitsets have dynamic size, so we need to reallocate very often each time a 
bitset needs to be updated. This can cause significant performance penalties 
due to excessive fragmentation, if we don't split the bitsets into fixed 
virtual size (I think that fragments around 16Kbits, i.e. a max of 4KB, 
should work OK to greatly limit the memory fragmentation costs in the VM.) 
Splitting fragments may also offer another opportunity to simply not store 
completely empty fragments, because their position in a table of fragments 
will be left to null, adding some memory save. Splitting is very simple to 
compute with simple bitmasks and shifts, and it limits a lot the impact of 
necessary data copies and allocations.

Also each fragment may have its own compression scheme, if fragments are 
represented as distinct objects; no need to add other fields because their 
instance's class pointer wil implement a common interface to effectively 
decode them; this allows also to temporarily compute fragments one by one in 
an uncompressed form, easy to compute and set for OR/XOR/AND operations, and 
terminate this work by computing their optimal compression scheme, before 
going to the next fragment. The temporary uncompressed fragment is easily 
reusable to compute the next actual fragment, so this limits the number of 
allocations needed to process the whole bitset.


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