Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.php > #5688 > unrolled thread

FYI performance of hash algorithms

Back to article view | Back to comp.lang.php

Contents

  FYI performance of hash algorithms "M. Strobel" <sorry_no_mail_here@nowhere.dee> - 2012-04-23 21:42 +0200
    Re: FYI performance of hash algorithms Jerry Stuckle <jstucklex@attglobal.net> - 2012-04-23 16:16 -0400
      Re: FYI performance of hash algorithms "M. Strobel" <sorry_no_mail_here@nowhere.dee> - 2012-04-23 22:44 +0200

#5688 — FYI performance of hash algorithms

I am just asking myself which of the many hash algorithms performs best, so I can use
it to index my translation strings.

So I wrote a test script. It iterates over an array of 3.917.116 strings calculating
the hash of each.

Here you have the results, with run time, and run time relative to hash length
(smaller is better).
Interesting that the tiger hashes seem to perform well.

There were only collisions with adler32 (many), crc32 and crc32b.

/Str.

Name	Length	Timing	   t/Byte (skal.)
crc32	8	2,2150330544	276,9
crc32b	8	2,2309110165	278,9
adler32	8	2,4038968086	300,5
md4	32	2,9871790409	93,3
md5	32	3,0691349506	95,9
tiger128,3 32	3,4266569614	107,1
tiger160,3 40	3,5735139847	89,3
tiger128,4 32	3,6424109936	113,8
tiger192,3 48	3,6483809948	76,0
sha1	   40	3,6727621555	91,8
tiger160,4 40	3,7693319321	94,2
tiger192,4 48	3,8536069393	80,3
ripemd128  32	3,9478549957	123,4
ripemd256  64	4,2519729137	66,4
salsa20	128	4,4366490841	34,7
salsa10	128	4,4819700718	35,0
ripemd160 40	4,8140711784	120,4
sha224	56	5,2336411476	93,5
ripemd320 80	5,2477719784	65,6
sha256	  64 	5,3834650517	84,1
haval128,3 32	5,8804600239	183,8
haval160,3 40	5,9342179298	148,4
haval192,3 48	6,0202069283	125,4
haval224,3 56	6,0966057777	108,9
haval256,3 64	6,2231030464	97,2
sha384	   96	6,4372200966	67,1
sha512	128 	6,7605450153	52,8
haval128,4 32	7,0831079483	221,3
haval160,4 40	7,1777567863	179,4
haval192,4 48	7,2292518616	150,6
haval224,4 56	7,3201220036	130,7
haval256,4 64	7,4621391296	116,6
whirlpool 128	7,4762940407	58,4
haval128,5 32	7,9410018921	248,2
haval160,5 40	8,028870821	200,7
haval192,5 48	8,102463007	168,8
haval224,5 56	8,1795060635	146,1
haval256,5 64	8,3195581436	130,0
gost	   64 	12,0381391048	188,1
snefru	   64	14,0808851719	220,0
snefru256  64	14,1807420254	221,6
md2	   32	17,4794299603	546,2

[toc] | [next] | [standalone]

#5689

On 4/23/2012 3:42 PM, M. Strobel wrote:
> I am just asking myself which of the many hash algorithms performs best, so I can use
> it to index my translation strings.
>
> So I wrote a test script. It iterates over an array of 3.917.116 strings calculating
> the hash of each.
>
> Here you have the results, with run time, and run time relative to hash length
> (smaller is better).
> Interesting that the tiger hashes seem to perform well.
>
> There were only collisions with adler32 (many), crc32 and crc32b.
>
> /Str.
>

<snip>

Interesting, but only applicable on your system with your libraries and 
your data.  A different system could have different versions of the 
libraries and completely different performance figures.

As for collisions - completely dependent on your data.  While you can 
say some things with certainty (i.e. hashing 2^16+1 values with CRC-16 
is guaranteed to have at least one collision), by picking different 
strings to be hashed your collisions will come out differently.

For instance, it's not really surprising that adler32 had a lot of 
collisions.  It was designed for CRC and works better with binary data; 
it was never meant to be a general purpose hashing algorithm.  Rather it 
was designed for speed.  It's also very short.

The same is true but to a lesser extent with the CRC-32 and CRC-32b 
algorithms, so again I'm not surprised about the collisions.

But the real question here is - how much does it matter if hashing a 
string takes 2 microseconds or 2.5 microseconds?  Unless you're doing 
millions of them at one time, no one is going to notice the difference. 
  Personally, when looking at such things I always elect the fewest 
collisions over the fastest time.

-- 
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attglobal.net
==================

[toc] | [prev] | [next] | [standalone]

#5690

Am 23.04.2012 22:16, schrieb Jerry Stuckle:
> On 4/23/2012 3:42 PM, M. Strobel wrote:
>> I am just asking myself which of the many hash algorithms performs best, so I can use
>> it to index my translation strings.
>>
>> So I wrote a test script. It iterates over an array of 3.917.116 strings calculating
>> the hash of each.
>>
>> Here you have the results, with run time, and run time relative to hash length
>> (smaller is better).
>> Interesting that the tiger hashes seem to perform well.
>>
>> There were only collisions with adler32 (many), crc32 and crc32b.
>>
>> /Str.
>>
> 
> <snip>
> 
> Interesting, but only applicable on your system with your libraries and your data.  A
> different system could have different versions of the libraries and completely
> different performance figures.

Agreed. But it gives you hints.

> As for collisions - completely dependent on your data.  While you can say some things
> with certainty (i.e. hashing 2^16+1 values with CRC-16 is guaranteed to have at least
> one collision), by picking different strings to be hashed your collisions will come
> out differently.
> 
> For instance, it's not really surprising that adler32 had a lot of collisions.  It
> was designed for CRC and works better with binary data; it was never meant to be a
> general purpose hashing algorithm.  Rather it was designed for speed.  It's also very
> short.
> 
> The same is true but to a lesser extent with the CRC-32 and CRC-32b algorithms, so
> again I'm not surprised about the collisions.

Neither am I. I just did not cut the list, they are listed by hash_algos().

> But the real question here is - how much does it matter if hashing a string takes 2
> microseconds or 2.5 microseconds?  Unless you're doing millions of them at one time,
> no one is going to notice the difference.  Personally, when looking at such things I
> always elect the fewest collisions over the fastest time.

Even for this simple test I had to bump up memory_limit to 3G. And a real collision
test is difficult.

The problem is indeed that hashes are often used without collision detection, I am
running the app without as well. I made this test to have an indication about how
much longer one of the longer hashes takes to compute, for example md5 / sha1.

For me the winner is ripemd256: a very long hash, running relatively fast.

/Str.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.php

csiph-web