Associative Array: reasonable limits?

[Charles Hixson]

On 11/05/2013 05:34 AM, Dmitry Olshansky wrote:
> 05-Nov-2013 02:20, Charles Hixson пишет:
>> On 11/03/2013 01:46 AM, Dmitry Olshansky wrote:
>>> 03-Nov-2013 02:37, Charles Hixson пишет:
>>>> I'm contemplating an associative array that will eventually grow to be
>>>> an estimated 64KB in size, assuming it's about half full. It would 
>>>> then
>>>> be holding around 90,000 entries.  Is this reasonable, or should I go
>>>> with a sorted array, and do binary searches?  I estimate that binary
>>>> searches would average around 15 accesses/hit, but that's still a lot
>>>> faster than disk access.  The array would be nearly full, so there 
>>>> would
>>>> be less wasted space, but, of course, insertions would become quite
>>>> expensive.  (Deletions aren't expected.)  In either case the keys 
>>>> would
>>>> be fixed length character arrays, and the values would also be simple
>>>> structs without reference types (so the garbage collector could pretty
>>>> much ignore things).
>>>
>>> 90k elements is a small AA. It would work just fine with any sane hash
>>> function (e.g. the built-in one).
>>>
>>> At around 10M+ elements it may be worth to consider space saving
>>> techniques. That said on x64 100M+ is perfectly OK, on 32bit I'd
>>> advise against it but only because of GC.
>>>
>>>> FWIW I'm expecting this array to be around the entire time the program
>>>> is running, but it would probably be rolled out most of the time, as
>>>> frequently accessed items would be pulled into a much smaller 
>>>> structure,
>>>> and if I go with the array rather than the hash table I may only do
>>>> updates as a batch.  (Since it's linear with the size of the array, 
>>>> but
>>>> essentially ignores the number of items being added.)
>>>>
>>>> My temptation is to go with the hash table...but I'm not sure of the
>>>> underlying mechanics.
>>>
>>> Think of it as a sparse array that has "holes" and takes around ~2-4
>>> times the size of normal array. It's not only because of holes but
>>> because a slot is a bit bigger.
>>> In return lookups/inserts/deletions are cheap O(1) with high 
>>> probability.
>>>
>> Thanks, I'd been assuming that it would just be around 128 bytes larger
>> (i.e., two pointers) and around a 50% fill rate.  Sounds like a bit
>> worse than I was estimating...not hugely worse though.  OTOH, that's an
>> argument in favor of using a small cache that is a hash table, and a
>> large array as a backing store, where infrequently accessed items could
>> be kept.  Probably if the cache could hold around 2,000 entries it would
>> have over a 90% hit rate (though that would need to be tested).
>
> What's your requirements for this data-structure anyway?
>
>> And the
>> array would also provide a sorted access method for traversing it.  I'm
>> not sure that's important, but it could be.  It could also be saved to
>> an externally editable file (i.e., using a standard text editor) which
>> also might be important.
>
> Oh my, that's a lot of complexity for no gain. Truth be told I tend to 
> always optimize for speed (=less power consumption) these days. What 
> you describe is sort of collision pages (like in some DB) but deployed 
> in such a small scenario I see ZERO gain in any dimension.
> You know code is also occupying some RAM ;).
>
>> This will, naturally, slow down insertions. (I don't expect any
>> deletions, as they would render historical data unintelligible.)
>>
>> Perhaps I'll batch the insertions, as the insertion is linear WRT the
>> size of the array, but is essentially independent of the number of
>> insertions.  (I.e., no matter how many insertions, it's a one pass job.)
>>
>
> Even more code. And space for batching and keeping track of if the 
> item is batched but not yet in collection.
>
I'm not sure about the batch adds.  I certainly won't do it at first, 
while the data is small.  The thing is, I want to keep as much as 
feasible rolled out most of the time.  That means that while it's active 
in "RAM" that RAM is actually pages on the disk of virtual memory.  With 
a large hash table, that's not likely to be controllable.  What I'm 
doing here is optimizing for "speed and..." where and includes active 
memory use (as opposed to rolled out virtual memory).  A part of what 
makes a hash table efficient is that it's always in RAM.  If you need to 
roll it in to access it, then you lose most of the efficiency.  A sorted 
array is a pretty straightforwards data structure.  It's reasonably 
quick to access, though not as fast as a hash table.  The real killer is 
insertion (or deletion).  And it doesn't lose anywhere near as much by 
being rolled out (for one thing, each page holds about twice as much 
data, so you don't need as many reads).  And it's easy to save to 
external disk.  (You can size it easily so that when starting up the 
program again, the array is initialized at the correct size.)

I had actually for a long time considered just using a database, but I 
can't control how the database caches things in RAM.  I want the cache 
to have a long term usage memory as well as recent use, and doing that 
with a database is just too complex.  Yes, this is sort of like a 
database, but except for some databases that store everything in RAM, 
it's not the same.

OTOH, if this were the entire program, you would be right that just 
using a hash table was a better idea.  But this is actually almost a 
side show, rather like GUI's are sideshows to what the program is 
actually doing.  This is what the program needs to interface 
intelligibly with people.  As such, it's not a heavily used part, and 
it's best if it doesn't consume excess active RAM.  (For that matter, I 
*know* my computer is too small for what I'm trying to do.  So using 
extra RAM is undesirable. I may eventually decide to have the thing that 
I'm currently calling "the array" live out on disk, but it's my 
understanding that this isn't much of a gain over having it just rolled 
out by virtual memory.)  I've also seriously considered using a sort of 
database (I'm thinking of KyotoCabinet), but doing it this way yields 
fewer external dependencies, and the hash cache is probably a better 
choice.  (Again, with KyotoCabinet I don't have as much control over 
what it decides to keep in the cache.)  I expect that the total memory 
needs of the program will edge towards the Terabyte range, so most of it 
is going to need to live on disk no matter what I do.  But I don't know 
in detail just what's going to be involved there.  I've roughed out a 
data file based around fixed length records addressable by id# which can 
be transformed into a file offset, but how to decide what should be 
removed from RAM isn't something I've figured out yet.  You could think 
of the basic datastructure of the program as a 40 dimensional cyclic 
graph with one-way links, but that's not quite right.  The links carry 
more information than is typical of graph structures (though logically 
that's no change...you could model them as nodes along the links that 
act as filters). OTOH, the file structure that supports this is quite 
simple.  Just a direct access file with fixed length blocks.

As for "to be added" being separate, that's not hard either.  That could 
be either a hash table or an array. though a hash table would probably 
be simpler.  And it's just another place I'd need to check when looking 
to see if I already recognized the code.  Still, that's something that 
should really be saved until later, as it can be added on at any time.  
(Which probably means I'll never get around to it.)

-- 
Charles Hixson