Associative Array: reasonable limits?

[Dmitry Olshansky]

06-Nov-2013 00:36, 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?

Still no answer. I'm asking it only because designing any data-structure 
w/o answering this first is an exercise in futility.

It seems like priority is lookup speed and data size. Search for succint 
data-structures if you really want to dive that deep. I'd recommend it 
only for fun, not for the task at hand.

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

The moment you start using data it all gets in RAM pretty soon 
(potentially with a few of page faults). After that point you may as 
well forget about page system and virtual memory.

The thing is that number of page faults is environment dependent anyway 
an is "a constant cost" compared to any operations on data.

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

I doubt you'll ever be able to measure this effect on top of OS induced 
noise. Thing is OS will keep pages forever in RAM anyway if there is 
plenty of it. And if it's paging on every call to your tiny dataset - 
you have far-far bigger problems anyway.

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

*Yawn* Anyhow you'd serialize it in some format. Maybe even text ;)

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

There is this moment through out your post - you seem to require some 
implementation details but have no high-level goals specified. It's kind 
of backwards.

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

Quoting you before that:

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

It's anyway sooo tiny compared to the rest you'd better focus on getting 
the main program efficient. Even saving say save all of that RAM (assume 
you cache weights 0 bytes) you'd save 64Kb of RAM. Now compared with at 
least 1G of ram (or what have you to work with said 1Tb?) it's 64K/1G or 
0.006% of RAM gained.

Anyhow I'd spent that time learning how memory mapped I/O works instead 
of sweating over that 0.006% (that are absolute maximum you'd never 
achieve btw). All in all the fruit to optimize is where the potential 
gain is large, something that is proportional to your dataset.

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

What I can say is it that there is never enough time to optimize every 
bit of system. Spend time wisely.

-- 
Dmitry Olshansky