From: vmakarov@... Date: 2016-12-04T23:04:36+00:00 Subject: [ruby-core:78490] [Ruby trunk Bug#13002] Hash calculations no longer using universal hashing Issue #13002 has been updated by Vladimir Makarov. File switching_hash_removal.patch added Vladimir Makarov wrote: > Although strong/weak hash approach gave about 5-6% improvement out of 45% on Ruby hash table benchmarks, I think we should not use it for Ruby. I will provide a patch to get rid of it in 2 days. The following patch removes hash function switching. The patch also randomizes simple type hashes making them strong. The patch was successfully compiled by GCC and LLVM and tested by make check. The actual average performance decrease of the hash tables on Ruby hash table benchmarks is about 3.5% which was measured on 4.2GHz i7-4790K by ``` ruby ../ruby/benchmark/driver.rb -p hash -r 3 -e before::before/miniruby -e current::./miniruby 2>/dev/null|awk 'NF==2 && /hash/ {s+=$2;n++;print} END{print s/n}' ``` That still makes the new hash tables by about 42% faster than the old implementation. Nobuyoshi, I was not sure about adding your tests checking hash randomness. I think it is upto you to add them. The tests should pass after applying the patch. I also found that for symbols the hash is always the same in previous MRI version (I used 2.3.1). So I keep this behaviour. Martin, thank you for reporting this issue. ---------------------------------------- Bug #13002: Hash calculations no longer using universal hashing https://bugs.ruby-lang.org/issues/13002#change-61869 * Author: Martin D��rst * Status: Open * Priority: Normal * Assignee: * ruby -v: * Backport: 2.1: DONTNEED, 2.2: DONTNEED, 2.3: DONTNEED ---------------------------------------- When preparing for my lecture on hash tables last week, I found that Ruby trunk doesn't do universal hashing anymore. See http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf for background. I contacted security@ruby-lang.org, but was told by Shugo that because trunk is not a published version, we can talk about it publicly. Shugo also said that the change was introduced in r56650. Following is some output from two different versions of Ruby that show the problem: On Ruby 2.2.3, different hash value for the same number every time Ruby is restarted: C:\Users\duerst>ruby -v ruby 2.2.3p173 (2015-08-18 revision 51636) [i386-mingw32] C:\Users\duerst>ruby -e 'puts 12345678.hash' 611647260 C:\Users\duerst>ruby -e 'puts 12345678.hash' -844752827 C:\Users\duerst>ruby -e 'puts 12345678.hash' 387106497 On Ruby trunk, always the same value: duerst@Arnisee /cygdrive/c/Data/ruby $ ruby -v ruby 2.4.0dev (2016-12-02 trunk 56965) [x86_64-cygwin] duerst@Arnisee /cygdrive/c/Data/ruby $ ruby -e 'puts 12345678.hash' 1846311797112760547 duerst@Arnisee /cygdrive/c/Data/ruby $ ruby -e 'puts 12345678.hash' 1846311797112760547 duerst@Arnisee /cygdrive/c/Data/ruby $ ruby -e 'puts 12345678.hash' 1846311797112760547 ---Files-------------------------------- switching_hash_removal.patch (9.21 KB) -- https://bugs.ruby-lang.org/ Unsubscribe: