Associative Arrays need cleanout method or property to help garbage collection

[Michael Rynn]

On Tue, 16 Mar 2010 16:12:25 +0000, Moritz Warning wrote:

> On Tue, 16 Mar 2010 04:41:55 +0000, Michael Rynn wrote:
> 
>> The use of built in Associative Array can have deleterious effects on
>> Garbage Collection.
>  :(
> 
> 
> Fwiw, here is the original Python Dictionary implementation:
> http://svn.python.org/projects/python/trunk/Objects/dictobject.c This is
> also a nice read:
> http://svn.python.org/projects/python/trunk/Objects/dictnotes.txt
> 
> As for difference to the D impl.:
> The decision logic for table resizing is a bit different (Python uses a
> load factor of 2/3 and table doubling for more as 50K entries, *4 else).
> Python also wraps everything in Objects and attaches the hash when
> computed.
> 

I am beginning to get a headache playing around with this. There must be 
better things to do.  I have refined the test program a bit more and 
added some missing bits to aaht by calling the implementation class.

The following summary statistics were obtained.
The no-cleanup averages represent more or less the value of the middle 
run number, due to slowdown, except for aapy.   Even so, doing a cleanup 
improved the aapy results,  for which insertion times are very 
impressive. I attribute this to not needing to allocate memory for each 
insertion. Lookups for aapy are on average about 7-8% slower.

The bits I find interesting are:-

When doing cleanups, the aaht library version of the builtin AA is about 
33% faster on insertions than the builtin AA, although a few percent 
slower on lookups. Using a Tangy heap Container for node allocation 
increases performance to 60% faster than builtin, and brings the lookups 
to par. It also allows a super fast cleanup.

Since the builtin has no builtin cleanup to call, I used the following 
template to inefficiently do the task. 

The aaht version with a custom clear did the task 1.5 to 2.5 times faster 
(no TangyHeap), or really super fast (TangyHeap).



void
clear(K,V)(ref V[K] aa)
{
    K[] keyset = aa.keys;
    foreach(ks; keyset)
    {
        aa.remove(ks);
    }
}

A call to aa.clear then cleans up in reasonable time.

summary average 10 runs of size 500_000

no-cleanup uint[uint]
		insert  lookup
builtin(K,V)	4.395	0.0388
aaht(K,V)	4.5906	0.0426
aapy(K,V)	0.139	0.0423

cleaned-up uint[uint]
		insert  lookup cleanup
builtin(K,V)	0.4601	0.0376	  0.1252
aaht(K,V)	0.3021	0.0399	  0.081
aapy(K,V)	0.0957	0.0438	  0.0002


no-cleanup uint[string]
builtin(K,V)	3.4727	0.1596
aaht(K,V)	3.6453	0.1646
aapy(K,V)	0.9753	0.1735

cleaned-up uint[string]
builtin(K,V)	0.668	0.1658	 0.2609
aaht(K,V)	0.4396	0.1621	 0.1001
aapy(K,V)	0.2286	0.1717	 0.0002


After recompile with aaht version=TangyHeap
uint[uint]
aaht(K,V)	0.188	0.0387	0.0004

uint[string]
aaht(K,V)	0.3391	0.1609	0.0001



I have no empirical or logical justifications for when to resize tables. 
I just copy the previous code and hope I got it right.

 There must have been some previous research on the number of times a 
lookup or insert needs to check another slot because of hash collision, 
causing slowdown. But wether the ratio is 3/5 (60%) 2/3 (66%) or 3/4(75%) 
has not yet made for me an observable effect in pydict.

> As for your modifications to the PyDict code: Why have you changed the
> length() implementation? As far as I remember, it's wrong to just return
> "used".

Formerly 'used' field was the number of active nodes in the table itself.
The relationship is mathematically seen in the size() property: 
---
length = used + is_dummy + is_unused;
---

where is_dummy and is_unused can be 1 or 0.

I have rewritten this an equivalent form
used_entries = length_ - is_dummy - is_unused.

I have now changed the 'used' to become length_, and added a comment to 
make it plain.

This length_ variable now includes the count of the usage of the 2 extra 
nodes for unused_hash(0) and dummy_hash(1).  The length_ count will get 
bumped up or down whenever these nodes are set or unset respectively, as 
if they were normal nodes.

'used_entries' is only calculated just before readjusting the table size.
This is a computationally a trivial no difference, only preferred because 
I thought that length_ will be accessed more than 'used_entries', giving 
it the possibility of no calculation property access.


I want to add that the problems of AA with garbage collection are not 
particular to the implementation of built-in AA. The number of nodes that 
builtin AA creates will increase GC scanning, but the AA slowdowns also 
occurs using the pyDict implementation with string keys.

Original PyDictD2 slowed down for both uint and string keys, unless I set 
NO_SCAN calloc.
Then I changed the implementation to use new Entry[] instead of a calloc. 
This helped the uint[uint] test, but not the uint[string] test.

For uint[string]  the pyDict still slows progressively after each run, 
not nearly as much as the for builtin AA. The only way I can prevent this 
is to forcefully clean up the AA after each use, for whatever 
implementation.

The testhash.d command line 3rd option for the test select shows this.

option 5 -  aapy uint[string] - no cleanup. -- slows down
option 15   aapy uint[string] - cleanup     -- no slow down.

ditto for aabuiltin -1,11(except that it always slows down, because no 
cleanup possible)  and aaht - 3,13.

For immutable(char)[] keys, uint values
The AA needs to be scanned because AA node holds a reference to the key. 
If the key is not reachable and referenced elsewhere, the key array will 
be deleted by the GC, and the AA key will then reference freed memory.

The testhash program is holding references to the original string keys in 
a dynamic array. Also tested a version that makes sure all the AA values 
are 0, to help the garbage collector, but it still slows down if no 
cleanup requested.  Another version flag calls the GC.collect before each 
run. Its as if bits in the string keys are being misinterpreted as 
pointers.

With the current D garbage collector, using any AA implementation, 
builtin or otherwise, requires the ability to enforce cleanup. I do not 
expect any harm from using enforced AA memory management.  

>From my reading of Hans Boehm garbage collector, it is possible to 
provide TypeInfo hints to it has to what to interpret as pointers, in a 
structure or array. It would be nice to be able to do this from TypeInfo 
in D. I do not know if it is done to any extent at all in D.  I suppose 
there is always both a development and a performance penalty for this 
sort of thing. There also appears to be a penalty for not doing it.

While the GC cannot be fixed real soon, or cannot be replaced with a more 
descriminating or enhanced with TypeInfo hints, then for many 
applications, D and its libraries interweave manual memory management 
with garbage collection, such as this little aa project.  Applications 
are able to delete and clear things using some degree safety 
encapsulation and stack scoping, and still let the garbage collector 
worry about what it can cope with.  

Mono dev is trying to wean off the Hans Boehm and use something more 
exact and generational. Given the failing of garbage collection for most 
AA implementations, all current D AA implementations need a manual 
cleanup method. Other alternatives include using being able to specify 
non-scanned memory implementation where the programmmer deems it safe. 

Have a cleanup method for the AA, makes memory management more flexible 
and accessible, and when used will nearly always improve overall 
performace.  Improve the AA or fix the GC. Which is easier?

The aaht version with the heap node allocation and fast cleanup seems to 
be a better AA than the built-in.  The aapy has by far the best insertion 
results.

But do not take this very restricted and rather extreme sampling of 
possible test parameters to be a reliable guide to relative performance 
when used in other applications with differing environments.
---
Michael Rynn.