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

Groups > comp.lang.java.programmer > #28239 > unrolled thread

Benchmarking hashcode algorithms

Back to article view | Back to comp.lang.java.programmer

Contents

  Benchmarking hashcode algorithms Roedy Green <see_website@mindprod.com.invalid> - 2014-04-26 09:49 -0700
    Re: Benchmarking hashcode algorithms Marcel Müller <news.5.maazl@spamgourmet.org> - 2014-04-26 18:54 +0200
    Re: Benchmarking hashcode algorithms Roedy Green <see_website@mindprod.com.invalid> - 2014-04-26 12:24 -0700
      Re: Benchmarking hashcode algorithms Mike Amling <mamling@chaff.us> - 2014-05-05 11:17 -0500
        Re: Benchmarking hashcode algorithms Roedy Green <see_website@mindprod.com.invalid> - 2014-05-16 16:27 -0700
          Re: Benchmarking hashcode algorithms Silvio <silvio@internet.com> - 2014-05-20 17:32 +0200
        Re: Benchmarking hashcode algorithms Roedy Green <see_website@mindprod.com.invalid> - 2014-05-16 16:28 -0700

#28239 — Benchmarking hashcode algorithms

I have been benchmarking some hashing algorithms. The fastest and
fewest collisions are near the top.  I used real world data.

The big surprise for me is how good String.hashCode is.

Collecting 20000 filenames from drive E...
The best have the lowest elapsed times and the fewest collisions.

Benchmarking String.hashCode...
Computing 100000 String.hashCode hashes...
Time to compute 100000 iterations of String.hashCode was 12.200
seconds.
Checking 20000 String.hashCode for collisions...
There were 0 collisions.
------

Benchmarking SunCRC32...
Computing 100000 SunCRC32 hashes...
Time to compute 100000 iterations of SunCRC32 was 66.515 seconds.
Checking 20000 SunCRC32 for collisions...
There were 0 collisions.
------

Benchmarking FNV1a32...
Computing 100000 FNV1a32 hashes...
Time to compute 100000 iterations of FNV1a32 was 48.146 seconds.
Checking 20000 FNV1a32 for collisions...
There were 0 collisions.
------

Benchmarking Adler...
Computing 100000 Adler hashes...
Time to compute 100000 iterations of Adler was 45.458 seconds.
Checking 20000 Adler for collisions...
There were 39 collisions.
------

Benchmarking SunCRC16...
Computing 100000 SunCRC16 hashes...
Time to compute 100000 iterations of SunCRC16 was 215.462 seconds.
Checking 20000 SunCRC16 for collisions...
There were 2768 collisions.
------


I will be adding some more. If you want be to test your favourite,
just implement this interface:


/**
 * interface that an algorithm must provide to be benchmarked
 */
interface HashAlgorithm
    {
    /**
     * identifying info
     */
    String getAlgorithmName();

    /**
     * compute hash, must be converted to a String for collision
checking.
     * Slow version, used for collision checking.
     */
    String computeHashString( String s );

    /**
     * It need not include code to convert to string.
     * Fast version, used for timing
     */
    void computeHash( String s );
    }

If you are inventing a hashing algorithm that do not involve every
byte, keep in mind that in the real world the Strings you are hashing
often begin and end with the same strings.

e.g. E:\mindprod .... .html

You might be able to cook up some special algorithm just for absolute
filenames.
-- 
Roedy Green Canadian Mind Products http://mindprod.com
Computers are like Old Testament gods; lots of rules and no mercy. 
~ Joseph Campbell (born: 1904-03-26 died: 1987-10-31 at age: 83)

[toc] | [next] | [standalone]

#28240

On 26.04.14 18.49, Roedy Green wrote:
> I have been benchmarking some hashing algorithms. The fastest and
> fewest collisions are near the top.  I used real world data.
>
> The big surprise for me is how good String.hashCode is.
>
> Collecting 20000 filenames from drive E...
> The best have the lowest elapsed times and the fewest collisions.

Speed: no surprise. I could bet that most VMs implement String.hashCode 
as native code.

> Benchmarking SunCRC16...
> Computing 100000 SunCRC16 hashes...
> Time to compute 100000 iterations of SunCRC16 was 215.462 seconds.
> Checking 20000 SunCRC16 for collisions...
> There were 2768 collisions.

Also no surprise with 16 bits.


Marcel

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

#28241

Here are the latest set of results. There are 100 times faster than in
the previous cut. I was using 1_000_000d to convert from ns to seconds
instead of 1_000_000_000d.  Serves me right for not using TimeUnit.

1. These are all very fast. For my purposes implementing cache, the
speed is negligible.  I have to compute hashes on only 10,000 to
20,000 files.

2. Sun's code works on a string directly. Most hashing require you to
convert the String to a byte first, which is probably as much work a
computing the hash itself.

3. Any kind of benchmark code because it does nothing useful can be
optimised out of existence be a clever compiler. I took no measures to
defeat that.

4. I also discovered that Adler is not so hot for collisions.

5. I expected Sun's String.hashCode to be fast, but to have lots of
collisions. It had none.

6. The speed penalty of the cryptographic hashes is not nearly a high
as I expected.

7. Whoever writes these functions is gradually making them faster.


Time to compute 25,000,000 iterations of 32-bit String.hashCode was
0.393 seconds.
There were 0 collisions in 50,000 filenames
------
Time to compute 25,000,000 iterations of 32-bit FNV1a32 was 5.044
seconds.
There were 1 collisions in 50,000 filenames
------
Time to compute 25,000,000 iterations of 64-bit FNV1a64 was 4.217
seconds.
There were 0 collisions in 50,000 filenames
------
Time to compute 25,000,000 iterations of 32-bit SunCRC32 was 6.133
seconds.
There were 1 collisions in 50,000 filenames
------
Time to compute 25,000,000 iterations of 32-bit Adler was 6.327
seconds.
There were 946 collisions in 50,000 filenames
------
Time to compute 25,000,000 iterations of 128-bit MD5 was 12.967
seconds.
There were 0 collisions in 50,000 filenames
------
Time to compute 25,000,000 iterations of 160-bit SHA-1 was 23.390
seconds.
There were 0 collisions in 50,000 filenames
------
Time to compute 25,000,000 iterations of 160-bit SHA was 22.690
seconds.
There were 0 collisions in 50,000 filenames
------
Time to compute 25,000,000 iterations of 256-bit SHA-256 was 30.003
seconds.
There were 0 collisions in 50,000 filenames
------
Time to compute 25,000,000 iterations of 384-bit SHA-384 was 30.902
seconds.
There were 0 collisions in 50,000 filenames
------
Time to compute 25,000,000 iterations of 512-bit SHA-512 was 30.538
seconds.
There were 0 collisions in 50,000 filenames
------
Time to compute 25,000,000 iterations of 16-bit SunCRC16 was 34.809
seconds.
There were 14,949 collisions in 50,000 filenames
------
Time to compute 25,000,000 iterations of 128-bit MD2 was 178.489
seconds.
There were 0 collisions in 50,000 filenames
------

-- 
Roedy Green Canadian Mind Products http://mindprod.com
Computers are like Old Testament gods; lots of rules and no mercy. 
~ Joseph Campbell (born: 1904-03-26 died: 1987-10-31 at age: 83)

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

#28376

On 4/26/14 2:24 PM, Roedy Green wrote:
> Here are the latest set of results. There are 100 times faster than in
> the previous cut. I was using 1_000_000d to convert from ns to seconds
> instead of 1_000_000_000d.  Serves me right for not using TimeUnit.
>
> 1. These are all very fast. For my purposes implementing cache, the
> speed is negligible.  I have to compute hashes on only 10,000 to
> 20,000 files.
>
> 2. Sun's code works on a string directly. Most hashing require you to
> convert the String to a byte first, which is probably as much work a
> computing the hash itself.
>
> 3. Any kind of benchmark code because it does nothing useful can be
> optimised out of existence be a clever compiler. I took no measures to
> defeat that.
>
> 4. I also discovered that Adler is not so hot for collisions.
>
Yep.
 > ...
>
> Time to compute 25,000,000 iterations of 32-bit String.hashCode was
> 0.393 seconds.
> There were 0 collisions in 50,000 filenames
> ------
> Time to compute 25,000,000 iterations of 32-bit FNV1a32 was 5.044
> seconds.
> There were 1 collisions in 50,000 filenames
> ------
> ...

Did you write out the code that Java uses to compute String.hashCode, or 
did you just call s.hashCode()? s.hashCode() could have been precomputed 
and cached.

Did you implement using all 16 bits of each char of the String or only 
the low-order 8 bits?

Mike Amling
--
SmFtZXMgTWFkaXNvbiBpcyB1bmRlcnJhdGVkLg==

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

#28494

On Mon, 05 May 2014 11:17:05 -0500, Mike Amling <mamling@chaff.us>
wrote, quoted or indirectly quoted someone who said :

>Did you write out the code that Java uses to compute String.hashCode, or 
>did you just call s.hashCode()? s.hashCode() could have been precomputed 
>and cached.
>
>Did you implement using all 16 bits of each char of the String or only 
>the low-order 8 bits?

I just used String.hashCode.  I figured the caching is a bonus that
would come with in the real world too.

I wonder if anyone knows with File.hashCode does. It seems to be
implementation dependent.  I wondered if it would de safer to use
String hashCode on the filename converted to lower case and \ to / so
you get the same hash no matter how you specify minor differences in
filename.
-- 
Roedy Green Canadian Mind Products http://mindprod.com
Young man, in mathematics you don’t understand things.
You just get used to them. 
~ John von Neumann (born: 1903-12-28 died: 1957-02-08 at age: 53)

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

#28542

On 05/17/2014 01:27 AM, Roedy Green wrote:
> On Mon, 05 May 2014 11:17:05 -0500, Mike Amling <mamling@chaff.us>
> wrote, quoted or indirectly quoted someone who said :
>
>> Did you write out the code that Java uses to compute String.hashCode, or
>> did you just call s.hashCode()? s.hashCode() could have been precomputed
>> and cached.
>>
>> Did you implement using all 16 bits of each char of the String or only
>> the low-order 8 bits?
>
> I just used String.hashCode.  I figured the caching is a bonus that
> would come with in the real world too.
>
> I wonder if anyone knows with File.hashCode does. It seems to be
> implementation dependent.  I wondered if it would de safer to use
> String hashCode on the filename converted to lower case and \ to / so
> you get the same hash no matter how you specify minor differences in
> filename.
>

Don't do that. You can not convert filenames to lowercase since only 
Windows has case-insensitive filenames and treats / as \ in the File class.

Perhaps you could use the canonical name of the file?

Silvio

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

#28495

On Mon, 05 May 2014 11:17:05 -0500, Mike Amling <mamling@chaff.us>
wrote, quoted or indirectly quoted someone who said :

>
>Did you implement using all 16 bits of each char of the String or only 
>the low-order 8 bits?

I converted to a byte[] using UTF-8 encoding. So the answer is mu.
-- 
Roedy Green Canadian Mind Products http://mindprod.com
Young man, in mathematics you don’t understand things.
You just get used to them. 
~ John von Neumann (born: 1903-12-28 died: 1957-02-08 at age: 53)

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web