Carlo Sogono wrote:
With regards to Benno's code:
After trying raw mallocs and performing quite well, I think it might
have to do with the code. I have different versions of my software,
hashed linked lists, hashed binary trees, etc. With 87 million mallocs
I expect binary trees of a hash table with size 100,001 to have a 800
entries each. Testing the same code with 1 million mallocs with a hash
table of 1,001 still gives me good results (that's an average of about
1000 per tree) at less than 5 minutes. I tried to insert 87 million to
a hash of 100,001 yesterday at 4pm and it wasn't finished at 9am
today. I think that's just way too slow. By the way i just use a
simple for loop and % hash size so all trees should have the same depth.
87 million / 100,001 = 869 (4pm-9am still not complete)
1 million / 1,001 = 999 (by 5 mins)
I would attach my source but it contains proprietary code :/
If you're inserting a list of malloc'ed memory chunks into a binary
tree, you should make sure that the tree is self-balancing: inserting a
stream of sorted objects (assuming you're using the address of the
malloc'ed object as a key, a list of subsequent malloc()s will be
"ordered") will create a *very* unbalanced binary tree (i.e. worst case
performance - you're basically doing an insertion sort).
This would be where I'd start looking: the long runtime is typical
of a malformed tree.
(Oh, and 100,001 isn't prime either. Using 100,003 may make your
hash a little more efficient. Or not. :)
John
_______________________________________________
coders mailing list
[email protected]
http://lists.slug.org.au/listinfo/coders
