Otto Moerbeek wrote [2012-02-19 08:49+0100]:
> while I did graduate on a theoretical computer science subject myself
I have no doubt about that. (?)
> I think this alternate hash table stuff is all overkill for ksh.
But a linear array based implementation with INT_MAX/2 is a heavy
thing. Did you sent this to me only to get some kind of
"INT_MAX/2 is probably a bit too large for a limit? Yes, using
specific hash algorithms for specific array sizes may aid in
making things better"? If so - yes, i think you're right.
And for one i've found the cause of the higher memory consumption.
The problem was simply that the variable names of the test were so
short.
If the variable name is instead "XXXXXXXXXX${i}" then the memory
overhead of the current implementation is already larger than that
of the node-based one. It thus seems as if the single pointer
that the node-based implementation adds to struct tbl causes the
memory allocator to allocate from a "larger allocation slot".
So this is the result for the shown longer variable name:
Node (400%/400% load factor):
0m14.72s real 0m14.41s user 0m0.25s system
0m5.81s real 0m5.70s user 0m0.06s system
0m5.87s real 0m5.76s user 0m0.09s system
27781 R+ 95.9 4840 3904 ttyp0 6:29PM 0:04.80 obj/ksh tt2.sh
Current (Torek):
0m14.20s real 0m13.71s user 0m0.21s system
0m5.90s real 0m5.85s user 0m0.06s system
0m5.82s real 0m5.64s user 0m0.12s system
17422 R+ 91.0 5052 4316 ttyp0 6:28PM 0:02.58 ../ksh/obj/ksh tt2.sh
That looks good!
> Added to that, the ksh code is tricky, so I'd resist big changes.
Tricky is a nice word for this code.
And i'm really sorry about that, as you surely can imagine.
But note i will post the node-based version once it is running as
it should, and maybe you'll give it a try nonetheless, then.
That would be fine.
> -Otto
Yours,
--steffen
