Re^4: Perl Hashes in C?

>> 76% of the pixels have unique colors! This makes your hashing algorithm rehash everything when it lands on a dup.

>Sorry, but if you mean "rehash every preexisting key", you are wrong. Why do you believe that?

As I recall, when a hash algorithm is selected, there is a tradeoff between performance and probability of uniqueness. Some fraction of the data up to and including the entire key may be used in the hash key.

If all of the distinct keys tried actually give non-colliding hash values, then the tradeoff worked. Otherwise, another algorithm must be selected which uses either more of the key or a different algorithm.

That triggers a total recalc. No?

Not even the Perl Gurus can know in advance that your data would have 8000 distinct colors and that mine would have 27 million.

And, hashing 48 bit quantomly random data has to be much more than 2.0 times as hard on a hashing algorithm as 24 bit data. There are 3300 times more buckets to keep track of.

Working in 16E6 color space does not in any way seem like it should be half as hard as 281474976710656 color space.

What I was seeing in my ill-fated C attempt was dramatically longer run times with modest increases in data volume from the ever expanding looup table. That is why I was looking for a hashing formula!

>> If you've already trimmed your OP time of "2.17 hours" to 48 seconds, why have you wasted our time

When I asked the question, the run-time was hours. Way beyond my nano-scale attention span. While The Monks were busy writing up many questions, I was beaverishly instrumenting my code to find out where all the time was being squandered. Qsort was taking 98% of the time!

Replacing <dumb old> QSort with a brilliantly conceived "Shuffle Merge" (TM :) and increasing my MAX_UNSORTED value from 200 (D'oh!) to a more workable 7920, I was able to realize the astonishingly better run time of roughly a minute. 120 X Faster? Dang!

Make your first draft the klunkiest, cloddiest, most horrendously heinous code possible because then you have no place to go but UP!

Comment on Re^4: Perl Hashes in C?

Replies are listed 'Best First'.
Re^5: Perl Hashes in C? by BrowserUk (Patriarch) on Aug 13, 2015 at 02:09 UTC
>Sorry, but if you mean "rehash every preexisting key", you are 05 wrong. Why do you believe that? 06 07 As I recall, when a hash algorithm is selected, there is a tradeoff 08 between performance and probability of uniqueness. Some fraction of 09 the data up to and including the entire key may be used in the hash 10 key. 11 12 If all of the distinct keys tried actually give non-colliding hash 13 values, then the tradeoff worked. Otherwise, another algorithm 14 must be selected which uses either more of the key or a different 15 algorithm. Perl uses the same hashing algorithm for all hashes regardless of their content; and never changes it during the life of a hash. Collisions are dealt with using bucket chains; when the fill ratio reaches a certain level (75% I think), it creates a new hash double the size of the existing one and moves the existing key/values pairs to that new hash; but it doesn't need to recalculate hash values because these are stored (the full 32-bit calculated value) in the datastructure with the keys; so to find the keys position in the new, bigger hash it has only to re-mask that value to give an index into the array of pointers that is the basis of the hash structure and then copy the pointer over. No rehashing is needed. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". I knew I was on the right track :) In the absence of evidence, opinion is indistinguishable from prejudice. I'm with torvalds on this Agile (and TDD) debunked I told'em LLVM was the way to go. But did they listen!	[reply]

Replies are listed 'Best First'.

Re^5: Perl Hashes in C?
by BrowserUk (Patriarch) on Aug 13, 2015 at 02:09 UTC

>Sorry, but if you mean "rehash every preexisting key", you are 05 wrong. Why do you believe that? 06 07 As I recall, when a hash algorithm is selected, there is a tradeoff 08 between performance and probability of uniqueness. Some fraction of 09 the data up to and including the entire key may be used in the hash 10 key. 11 12 If all of the distinct keys tried actually give non-colliding hash 13 values, then the tradeoff worked. Otherwise, another algorithm 14 must be selected which uses either more of the key or a different 15 algorithm.

Perl uses the same hashing algorithm for all hashes regardless of their content; and never changes it during the life of a hash.

Collisions are dealt with using bucket chains; when the fill ratio reaches a certain level (75% I think), it creates a new hash double the size of the existing one and moves the existing key/values pairs to that new hash; but it doesn't need to recalculate hash values because these are stored (the full 32-bit calculated value) in the datastructure with the keys; so to find the keys position in the new, bigger hash it has only to re-mask that value to give an index into the array of pointers that is the basis of the hash structure and then copy the pointer over. No rehashing is needed.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I knew I was on the right track :)

In the absence of evidence, opinion is indistinguishable from prejudice.

I'm with torvalds on this Agile (and TDD) debunked I told'em LLVM was the way to go. But did they listen!

[reply]