#8 Default hash function for char * - speed

closed
None
5
2009-07-17
2008-06-25
Yves Maurer
No

I propose to slightly change the default implementation of __stl_hash_string in _hash_fun.h to improve speed. The inner loop is currently:
__h = 5*__h + *__s;
This can be changed to
__h = (__h << 2) + h + *__s;
Since __h is unsigned, this will not result in any difference in the value computed.

On my x86 machine this results in a 50% speed improvement for this hash function. Since string hashing is relatively common and this change is trivial, I don't see why it couldn't be done.

Discussion

  • Big Muscle

    Big Muscle - 2008-07-06

    Logged In: YES
    user_id=1033723
    Originator: NO

    I see this is applied in _string_hash.h as hash function for string, but not in _hash_fun.h as hash function for char*

     
  • Nigel Stewart

    Nigel Stewart - 2008-07-18

    Logged In: YES
    user_id=338692
    Originator: NO

    Or even...
    __h += (__h<<2) + *__s

     
  • Edwin Choi

    Edwin Choi - 2008-08-10

    Logged In: YES
    user_id=2166592
    Originator: NO

    I'm guessing you have a P4.
    P4's have a long instruction latency for imul/mul operation - over double to triple their predecessors. Prescott dropped the latency down to 10 cycles from Northwood's 14-18 cycle latency (PII/PIII have a latency of 4 cycles).

    This should only really affect debug builds though, when optimizations are turned off. With optimizations turned on, '5 * __h' and '(__h << 2) + __h' should both result in the same assembly level code. In GCC 3.4 and 4.1, and Visual C++ 2005 and 2008, this is the case with the O2 flag set - all perform the operation as lea reg, [reg*4+reg].

    Personally, I choose clarity over performance in a non-optimized environment.

     
  • Petr Ovtchenkov

    Petr Ovtchenkov - 2009-07-17

    Well, I check http://www.azillionmonkeys.com/qed/hash.html and don't see benefits of Hsieh's hash (SuperFastHash is Hsieh's hash) (first column is mean test time, second is dispersion):

    1.26269 0.0562612 Strings hash: english dictionary
    1.6152 0.121985 Strings hash: 16 bytes
    31.1449 3.04323 Strings hash: 256 bytes
    1.31363 0.0654169 Strings hash: english dictionary, SuperFastHash
    1.61207 0.125413 Strings hash: 16 bytes, SuperFastHash
    30.7594 2.9586 Strings hash: 256 bytes, SuperFastHash
    *** PASS STL strings hash performance tests (+6-0~0/6) ***

    Conclusion: no reasons to use more complex Hsieh's hash as default in STlport.
    But I switch to original Bernstein's hash ('33 * __h' or '(__h << 5) + __h') in STLport.

     
  • Petr Ovtchenkov

    Petr Ovtchenkov - 2009-07-17
    • assigned_to: nobody --> complement
    • status: open --> closed
     
  • Petr Ovtchenkov

    Petr Ovtchenkov - 2009-07-17

    Commit bb270ad in mainstream.

     

Log in to post a comment.