wanted: hash stress tests
Leopold Toetsch
hash structure has just one piece of malloced memory with bucket
pointers and buckets in one piece.
But before comitting I'd like to have some stress and benchmarks tests
that first show that my implementation is correct and of course that
it's faster too ;-)
I'll ci what I have so far as src/new_hash.c first, when it's usable.
Thanks,
leo
Leopold Toetsch
It's in SVN now - rev 8134
please have a look at it,
thanks
leo
Uri Guttman
LT> I'm currently rewriting the hash implementation in src/hash.c. The
LT> new hash structure has just one piece of malloced memory with
LT> bucket pointers and buckets in one piece.
here is an odd thought to add to that. since your hash is a single hunk
of ram, you could use offsets inside it instead of pointers. that means
it could be both shareable (given locks) and even writable to disk. but
that doesn't handle the issues with serializing the scalar values (and
even keys) but it does make those things easier. and yes i know there is
a core serializer but if you make the hash pointers inside that ram
chunk into offsets instead, that will speed up serializing hashes.
PL/I has a thing called AREA where you could declare one and allocate
anything from it. but all the pointers you got back were offsets from
the base of that area. it was meant just for the ability to create
binary structures in ram that could be written/read to disk and back.
just reminiscing,
uri
--
Uri Guttman ------ u...@stemsystems.com -------- http://www.stemsystems.com
--Perl Consulting, Stem Development, Systems Architecture, Design and Coding-
Search or Offer Perl Jobs ---------------------------- http://jobs.perl.org
Leopold Toetsch
>>>>>>"LT" == Leopold Toetsch <l...@toetsch.at> writes:
>
>
> LT> I'm currently rewriting the hash implementation in src/hash.c. The
> LT> new hash structure has just one piece of malloced memory with
> LT> bucket pointers and buckets in one piece.
>
> here is an odd thought to add to that. since your hash is a single hunk
> of ram, you could use offsets inside it instead of pointers. that means
> it could be both shareable (given locks) and even writable to disk.
I don't see the difference WRT shareable, but yes, the memory hunk could
be written at once for freezing, which may save some cycles. More
importantly it doesn't need relocation during hash_expand(), if offsets
are calculated from start of mem.
With some benchmarks we can see, which is better, but using offsets
seems to be a good idea.
> uri
Thanks,
leo
Bob Rogers
Date: Fri, 20 May 2005 16:07:10 +0200
I'm currently rewriting the hash implementation in src/hash.c. The new
hash structure has just one piece of malloced memory with bucket
pointers and buckets in one piece.
But before comitting I'd like to have some stress and benchmarks tests
that first show that my implementation is correct and of course that
it's faster too ;-)
Below please find an additional test case for t/pmc/hash.t that defines
>50K keys, while checking that earlier entries are still present. This
takes about 0.8 sec on my 1.8GHz AMD box, tunable by increasing I22. Is
this the sort of thing you had in mind?
I'll ci what I have so far as src/new_hash.c first, when it's usable.
Thanks,
leo
One question: Why is there a space to store computed hash codes in
struct parrot_string_t but not in HashBucket? Part of the reason I am
asking is because I have started thinking about how to implement Common
Lisp hashes, for which (a) keys can be arbitrary objects, (b) object
equivalence is not defined in terms of stringification, and (c) hash
computation is not necessarily cheap. The standard technique is
therefore to store each key's computed hash in the bucket, which seems
like it would be a win for Parrot as well.
From: Leopold Toetsch <l...@toetsch.at>
Date: Fri, 20 May 2005 19:34:27 +0200
Uri Guttman wrote:
> here is an odd thought to add to that. since your hash is a single hunk
> of ram, you could use offsets inside it instead of pointers. that means
> it could be both shareable (given locks) and even writable to disk.
I don't see the difference WRT shareable,
It sounds like Uri meant that it could be mapped at different addresses
for different processes . . . but maybe not, because then the key and
value pointers would be useless.
. . . but yes, the memory hunk could be written at once for freezing,
which may save some cycles. More importantly it doesn't need
relocation during hash_expand(), if offsets are calculated from start
of mem.
With some benchmarks we can see, which is better, but using offsets
seems to be a good idea.
This may be too obvious to be worth pointing out, but if hash internals
are made persistent, then the hash code computation needs to be
invariant from one interpreter instantiation to another. For this
reason, the "seed" member of struct _hash is probably counterproductive.
Not to mention the fact that initializing it randomly would make it
harder to test hash iteration, since the key enumeration order would
then be nondeterministic.
FWIW, Common Lisp defines an SXHASH function [1] that must exhibit
just this invariance characteristic, and must also compute a definite
answer for circular structures. Time to revive the "hash" opcode?
-- Bob Rogers
http://rgrjr.dyndns.org/
[1] http://www.lispworks.com/documentation/HyperSpec/Body/f_sxhash.htm
------------------------------------------------------------------------
Index: t/pmc/hash.t
===================================================================
--- t/pmc/hash.t (revision 8136)
+++ t/pmc/hash.t (working copy)
@@ -19,7 +19,7 @@
=cut
-use Parrot::Test tests => 35;
+use Parrot::Test tests => 36;
use Test::More;
output_is(<<CODE, <<OUTPUT, "Initial Hash tests");
@@ -273,6 +273,95 @@
0
OUTPUT
+## stuff them in, and check periodically that we can pull selected ones out.
+pir_output_is(<<'CODE', <<OUTPUT, "stress test: lots of keys");
+.sub set_multiple_keys prototyped
+ .param pmc hash
+ .param int key_index
+ .param int step
+ .param int count
+
+again:
+ if count <= 0 goto ret
+ S0 = key_index
+ S1 = concat "key", S0
+ S2 = concat "value", S0
+ hash[S1] = S2
+ key_index = key_index + step
+ count = count - 1
+ goto again
+ret:
+.end
+
+.sub print_multiple_keys prototyped
+ .param pmc hash
+ .param int key_index
+ .param int step
+ .param int count
+
+again:
+ if count <= 0 goto ret
+ S0 = key_index
+ S1 = concat "key", S0
+ print S1
+ print " => "
+ I2 = exists hash[S1]
+ if I2 goto print_value
+ print "(undef)"
+ goto print_end
+print_value:
+ S2 = hash[S1]
+ print S2
+ print "\n"
+ key_index = key_index + step
+ count = count - 1
+ goto again
+ret:
+.end
+
+.sub _main @MAIN
+ new P30, .Hash
+ print "round 1\n"
+ I29 = 1
+ I30 = 1000
+ I31 = 1000
+ set_multiple_keys(P30, I29, I30, I31)
+ I20 = 3
+ print_multiple_keys(P30, I29, I30, I20)
+ print "round 2\n"
+ I21 = 100000
+ set_multiple_keys(P30, I21, I30, I31)
+ print_multiple_keys(P30, I29, I30, I20)
+ print_multiple_keys(P30, I21, I30, I20)
+ print "round 3\n"
+ I22 = 50000
+ set_multiple_keys(P30, I22, I29, I22)
+ print_multiple_keys(P30, I29, I30, I20)
+ print_multiple_keys(P30, I21, I30, I20)
+ print "done.\n"
+.end
+CODE
+round 1
+key1 => value1
+key1001 => value1001
+key2001 => value2001
+round 2
+key1 => value1
+key1001 => value1001
+key2001 => value2001
+key100000 => value100000
+key101000 => value101000
+key102000 => value102000
+round 3
+key1 => value1
+key1001 => value1001
+key2001 => value2001
+key50000 => value50000
+key51000 => value51000
+key52000 => value52000
+done.
+OUTPUT
+
# Check all values after setting all of them
output_is(<<CODE, <<OUTPUT, "stress test: loop(set), loop(check)");
new P0, .Hash
Leopold Toetsch
> Below please find an additional test case for t/pmc/hash.t that defines
>
>>50K keys, while checking that earlier entries are still present. This
>
> takes about 0.8 sec on my 1.8GHz AMD box, tunable by increasing I22. Is
> this the sort of thing you had in mind?
Yeah. Thanks. It's OTOH failing here, I've too look at it, then it'll go
in. Another one which additionally deletes keys would be great.
> One question: Why is there a space to store computed hash codes in
> struct parrot_string_t but not in HashBucket?
Having it in the bucket is a space penalty for other objects that can
provide an hash value easily like e.g. Integer PMCs. More complicated
objects like strings can therefore cache their hash val inside their
structure.
> ... Part of the reason I am
> asking is because I have started thinking about how to implement Common
> Lisp hashes, for which (a) keys can be arbitrary objects, (b) object
> equivalence is not defined in terms of stringification, and (c) hash
> computation is not necessarily cheap.
It's like in Python. The Py PMCs already implement a hash vtable -
albeit a bit buggy one for double or complex.
> ... The standard technique is
> therefore to store each key's computed hash in the bucket, which seems
> like it would be a win for Parrot as well.
We can do that too, but that's more or less an optimization thingy which
needs some existing RL code to benchmark.
> I don't see the difference WRT shareable,
>
> It sounds like Uri meant that it could be mapped at different addresses
> for different processes . . . but maybe not, because then the key and
> value pointers would be useless.
A shared PMC exists just once there is no address mapping. Different
processes needs of course distinct PMC data, we can't share data, just code.
> This may be too obvious to be worth pointing out, but if hash internals
> are made persistent, then the hash code computation needs to be
> invariant from one interpreter instantiation to another. For this
> reason, the "seed" member of struct _hash is probably counterproductive.
Or the seed is frozen too.
> Not to mention the fact that initializing it randomly would make it
> harder to test hash iteration, since the key enumeration order would
> then be nondeterministic.
Well, the reason *is* exactly to make it nondeterministic. The perl5
archives should have a lot of discussion WRT that, keyword DOS attacks.
> FWIW, Common Lisp defines an SXHASH function [1] that must exhibit
> just this invariance characteristic, and must also compute a definite
> answer for circular structures. Time to revive the "hash" opcode?
It depends on how we define the equality of objects or aggregates, i.e
if or how deeply that might recurse. If yes then the hash *vtable* needs
a change and cooporate with the visit vtable like freeze or thaw. But
that would need a change for is_equal too.
> [1] http://www.lispworks.com/documentation/HyperSpec/Body/f_sxhash.htm
Yep.
leo
Leopold Toetsch
> + I22 = 50000
> + set_multiple_keys(P30, I22, I29, I22)
> + print_multiple_keys(P30, I29, I30, I20)
> + print_multiple_keys(P30, I21, I30, I20)
^^^
c&p typo
Small reminder: always "make test" before submitting patches
Thanks, applied.
leo
Bob Rogers
Date: Sun, 22 May 2005 17:07:48 +0200
Bob Rogers wrote:
Thanks, applied.
leo
Mea culpa. I hand-tweaked the patch after putting it into the message
in order to change I21 to I22 so that I could reference I22 from the
message text -- thinking "Gee, maybe this isn't a good idea" even as I
did so . . .
-- Bob
Uri Guttman
LT> Uri Guttman wrote:
>>>>>>> "LT" == Leopold Toetsch <l...@toetsch.at> writes:
LT> I'm currently rewriting the hash implementation in
>> src/hash.c. The
LT> new hash structure has just one piece of malloced memory with
LT> bucket pointers and buckets in one piece.
>> here is an odd thought to add to that. since your hash is a single
>> hunk
>> of ram, you could use offsets inside it instead of pointers. that means
>> it could be both shareable (given locks) and even writable to disk.
LT> I don't see the difference WRT shareable, but yes, the memory hunk
LT> could be written at once for freezing, which may save some
LT> cycles. More importantly it doesn't need relocation during
LT> hash_expand(), if offsets are calculated from start of mem.
sharing is also simpler since the hash can be mmap'ed to different
virtual addresses in different processes and with offsets they don't
have any issues with pointers into/inside that space. it is the same
advantage if has for freezing and thawing.
LT> With some benchmarks we can see, which is better, but using offsets
LT> seems to be a good idea.
it can't hurt as it is about the same amount of cpu work (1 more
addition of the chunk base address is needed) but the wins for sharing
and freeze/thaw may make that worth it. also you could declare a hash to
be offset based so the compiler/optimizer code generates offset based
code (that is if people want that 1 addtion optimized away if offsets
aren't used.
Uri Guttman
BR> Uri Guttman wrote:
>> here is an odd thought to add to that. since your hash is a single hunk
>> of ram, you could use offsets inside it instead of pointers. that means
>> it could be both shareable (given locks) and even writable to disk.
BR> I don't see the difference WRT shareable,
BR> It sounds like Uri meant that it could be mapped at different addresses
BR> for different processes . . . but maybe not, because then the key and
BR> value pointers would be useless.
i did sorta cover that a little but here are some more ideas. you can
make more of the data structure offset based but use an indirection
table attached to the main chunk. so a key bucket in the main chunk has
an offset into this table (which is not shared) and that entry points to
the real key/PMC (which could be allocated from similar chunked
memory). i know this is getting deeper and deeper away from basic
pointer code but it is something to be explored. if the wins (FSDO win)
for sharing and freeze/thaw are worth it, then the extra code and slight
slowdowns would be worth it. and as i mentioned in the other response,
this could be an optional hash (or whatever) implementation (since
multiple implementation are easy in parrot/perl) that uses offsets as
much as possible for those wins. so in perl you might declare it like
this (p6l folks, please fix this):
my OffsetHash %foo ;
and class OffsetHash offers 'does Hash' as a role (is that needed?).
BR> This may be too obvious to be worth pointing out, but if hash internals
BR> are made persistent, then the hash code computation needs to be
BR> invariant from one interpreter instantiation to another. For this
BR> reason, the "seed" member of struct _hash is probably counterproductive.
BR> Not to mention the fact that initializing it randomly would make it
BR> harder to test hash iteration, since the key enumeration order would
BR> then be nondeterministic.
it is a good point to remember and it would have to be that way in the
OffsetHash implementation. i like this way of splitting it so the
pointer based hash is the common default but if you want better
sharing/freeze/thaw, you just have to (auto)load OffetHash and change
your declarations a but. there would also be similar classes for arrays
and scalars and even a way to force/request allocation of them all from
a single ram chunk (we just reinvented PL/I's area :).
Bob Rogers
Date: Sun, 22 May 2005 16:58:00 +0200
Bob Rogers wrote:
> Below please find an additional test case for t/pmc/hash.t that defines
>
>>50K keys, while checking that earlier entries are still present. This
>
> takes about 0.8 sec on my 1.8GHz AMD box, tunable by increasing I22. Is
> this the sort of thing you had in mind?
Yeah. Thanks. It's OTOH failing here, I've too look at it, then it'll go
in. Another one which additionally deletes keys would be great.
Good idea; I'll work on that. (I assume the failure was because of the
bug I introduced into the emailed version?)
> One question: Why is there a space to store computed hash codes in
> struct parrot_string_t but not in HashBucket?
Having it in the bucket is a space penalty for other objects that can
provide an hash value easily like e.g. Integer PMCs. More complicated
objects like strings can therefore cache their hash val inside their
structure.
Hmm. Seems to me that this space penalty is proportional to the number
of keys for keeping it in the HashBucket, and proportional to the number
of objects for keeping it in the objects. Since the number of string
keys (e.g.) must be smaller than the total number of strings, and may be
much smaller, it seems like it would be better to keep them in the
HashBucket, even though that's somewhat redundant for such things as
Integer PMCs. True?
> Not to mention the fact that initializing it randomly would make it
> harder to test hash iteration, since the key enumeration order would
> then be nondeterministic.
Well, the reason *is* exactly to make it nondeterministic. The perl5
archives should have a lot of discussion WRT that, keyword DOS attacks.
If DOS attacks on hashes are a consideration, then using the seed purely
as an initializer won't be enough. In particular, I note that
key_hash_cstring produces the same hash code for the strings "cB" and
"bc" regardless of the seed value, so they would always collide. Doing
h += hash->seed + *p++;
in the iteration would make it harder to attack, IMHO. (But IANASE
("security expert"). ;-)
On the other hand, I would argue that it's way too early to apply
this kind of low-level security hardening; it's a lot of work, and it's
too easy for someone to accidentally undo it in a rapidly-evolving
system by helpfully "simplifying" the code.
In any case, I take your point that the seed will eventually need to
be initialized randomly -- as long as it can be set deterministically
for testing/debugging purposes, I'm happy.
> FWIW, Common Lisp defines an SXHASH function [1] that must exhibit
> just this invariance characteristic, and must also compute a definite
> answer for circular structures. Time to revive the "hash" opcode?
It depends on how we define the equality of objects or aggregates, i.e
if or how deeply that might recurse . . .
True. That is all set in stone [1] for Common Lisp, but other languages
may have other requirements. I imagine all languages will need to be
able to compute hashes on keys from other languages, so a universal hash
operator that treats its argument as opaque would be useful. (Since the
GC doesn't move objects, the object address may be sufficient.) But
thinking about which language operator and/or object should decide
whether to recur into a given object for purposes of equality testing
gives me a headache . . .
-- Bob
[1] http://www.lispworks.com/documentation/HyperSpec/Body/f_equal.htm
http://www.lispworks.com/documentation/HyperSpec/Body/f_equalp.htm
Leopold Toetsch
> I'm currently rewriting the hash implementation in src/hash.c. The new
> hash structure has just one piece of malloced memory with bucket
> pointers and buckets in one piece.
The code is committed now, tests are passing as before the test.
leo
Bob Rogers
Date: Sun, 22 May 2005 16:58:00 +0200
Bob Rogers wrote:
> Below please find an additional test case for t/pmc/hash.t that defines
>
>>50K keys, while checking that earlier entries are still present. This
>
> takes about 0.8 sec on my 1.8GHz AMD box, tunable by increasing I22. Is
> this the sort of thing you had in mind?
Yeah. Thanks. It's OTOH failing here, I've too look at it, then it'll go
in. Another one which additionally deletes keys would be great.
This patch adds deletion to the same case. Testing also caught a
missing label in the original version, for a branch that was never
taken.
-- Bob Rogers
http://rgrjr.dyndns.org/
------------------------------------------------------------------------
Index: t/pmc/hash.t
===================================================================
--- t/pmc/hash.t (revision 8160)
+++ t/pmc/hash.t (working copy)
@@ -312,6 +312,7 @@
print_value:
S2 = hash[S1]
print S2
+print_end:
print "\n"
key_index = key_index + step
count = count - 1
@@ -319,6 +320,23 @@
ret:
.end
+.sub delete_multiple_keys prototyped
+ .param pmc hash
+ .param int key_index
+ .param int step
+ .param int count
+
+again:
+ if count <= 0 goto ret
+ S0 = key_index
+ S1 = concat "key", S0
+ delete hash[S1]
+ key_index = key_index + step
+ count = count - 1
+ goto again
+ret:
+.end
+
.sub _main @MAIN
new P30, .Hash
print "round 1\n"
@@ -338,6 +356,10 @@
set_multiple_keys(P30, I22, I29, I22)
print_multiple_keys(P30, I29, I30, I20)
print_multiple_keys(P30, I22, I30, I20)
+ print "round 4\n"
+ delete_multiple_keys(P30, I22, I29, I22)
+ print_multiple_keys(P30, I29, I30, I20)
+ print_multiple_keys(P30, I22, I30, I20)
print "done.\n"
.end
CODE
@@ -359,6 +381,13 @@
key50000 => value50000
key51000 => value51000
key52000 => value52000
+round 4
+key1 => value1
+key1001 => value1001
+key2001 => value2001
+key50000 => (undef)
+key51000 => (undef)
+key52000 => (undef)
done.
OUTPUT
Leopold Toetsch
> This patch adds deletion to the same case. Testing also caught a
> missing label in the original version, for a branch that was never
> taken.
Thanks, applied - 8175
leo