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

Philippe Verdy wrote:

> 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.


The constants involved in this splitting should ideally be determined by 
some automated fashion unless through experimentation we come up to a 
set of constants which perform reasonably well.  Keep in mind that while 
we may be able to do this easily for leaves, we don't know how will the 
fill rates of ultrapeer tables change in future if we increase the 
number of leaf connections.

Compression is a little trickier to get right because of the transient 
memory usage, and the fact that routing happens on several threads - so 
we may end up decompressing the same data many times.  Only if message 
processing is serialized to a single thread (which will hopefully be the 
case with NIO) then we can be sure that uncompressing, reading and 
re-compressing each table will indeed use less memory.  Therefore I'm 
more optimistic about dynamically finding some optimal representation of 
each table in the form of a bitset tree and simply not allocating those 
fragments that are all 0s or 1s.

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.
_______________________________________________
gui-dev mailing list
[email protected]
http://www.limewire.org/mailman/listinfo/gui-dev