Project

General

Profile

Actions

Feature #5106

closed

Is MurmurHash overkill?

Added by kstephens (Kurt Stephens) over 12 years ago. Updated over 11 years ago.

Status:
Rejected
Target version:
-
[ruby-core:38548]

Description

st.c implements MurmurHash to compute hash table indexes (#hash).

Simpler hash functions may be appropriate for hash tables, esp. small tables.

Is there a particular reason this hash function was chosen? Is MurmurHash typically used for check-summing purposes?

Anybody positively adverse to changing it? If so I won't bother. Otherwise I might take a crack at it.

-- KAS

Updated by naruse (Yui NARUSE) over 12 years ago

  • Priority changed from Normal to 3

Updated by mame (Yusuke Endoh) about 12 years ago

  • Status changed from Open to Assigned
  • Assignee set to mame (Yusuke Endoh)

Updated by mame (Yusuke Endoh) about 12 years ago

  • Status changed from Assigned to Feedback

Hello,

Simpler hash functions may be appropriate for hash tables, esp. small
tables.

Please make it quantitative when talking about performance.

Please show a benchmark first.
How slow is MurmurHash? How fast will st.c be if the algoritm
is replaced with another one?
And how much the drawback? That is, how many collision will
increase in actual cases?

Anybody positively adverse to changing it? If so I won't bother. Otherwise
I might take a crack at it.

Please make your move first.

We cannot answer your question until you show a benchmark.
Even after that, we cannot promise to import your patch before
you create it. The chicken or the egg :-)

Thanks,

--
Yusuke Endoh

Updated by MartinBosslet (Martin Bosslet) about 12 years ago

With the recent changes since hashDoS I'm not sure whether
we should really aim for simplicity. It's quite easy to
become a target with a function that is algebraically as
simple as for example DJB33X. But speed on the other hand
couldn't hurt. We use Murmur 2, there is a version 3 by
the same author who claims it is generally faster than 2.
Maybe we should give that a try first?

Updated by mame (Yusuke Endoh) over 11 years ago

  • Status changed from Feedback to Rejected

I'm closing this ticket. Feel free to reopen with benchmark.

BTW: MurmurHash was replaced with SipHash which is a bit slower than MurmurHash.

--
Yusuke Endoh

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0