We know siphash-1-3 is fine for a hash function, but do we know for sure that halfsiphash-1-3 is?

Do not ever use HalfSipHash except for as a hashtable key function, and only
then when you can be absolutely certain that the outputs will never be
transmitted out of the kernel. This is only remotely useful over jhash as a
means of mitigating hashtable flooding denial of service attacks.

https://github.com/torvalds/linux/blob/master/Documentation/siphash.txt

I guess this fits our need... unless someone starts using #hash and publicly discloses values?

Ah, so halfsiphash's typical variant is 1-3? That makes it a lot clearer, thanks.

Also, this response by Jean-Philippe Aumasson on linux.kernel that pretty much details the above warning:
https://groups.google.com/d/msg/linux.kernel/9NxJW70-hEU/X7nWWkzDAAAJ

• use siphash-2-4 for anything that requires cryptography quality —e.g. when disclosing hashes;
• halsiphash is probably attackable;
• halsiphash is probably stronger than other solutions, even with 1-3 rounds;
• you may use halfsiphash-1-3 for mitigating hash flooding attacks —but never disclose hashes!

Perhaps the hash type should always be a UInt64, and we just cast to UInt64 on 32bit. I think changing Object#hash's type on 32bit is probably a bad idea.

I modified halfsiphash to compute 64-bit hashes, which is slower (doubles finalizations), but still faster than siphash (on 32-bit systems). Some unscientific benchmarks (Benchmark.ips, encoding 2165 random english words):

• 64-bit system (trusty host, llvm 5.0):

    Digest::SipHash(1, 3)  14.02k ( 71.34µs) (± 0.26%)       fastest
Digest::HalfSipHash(1, 3)   11.8k ( 84.77µs) (± 0.75%)  1.19× slower

• 32-bit system (precise container, llvm 3.8):

    Digest::SipHash(1, 3)   8.46k (118.15µs) (± 0.44%)  1.43× slower
Digest::HalfSipHash(1, 3)   12.1k ( 82.61µs) (± 0.21%)       fastest

CircleCI is broken: ld: library not found for -lgmp.

LGTM (but we need optimization for Slice(Primitive) anyway).

Due to how Hasher#string was implemented (iterating each byte of the slice casted to u64), the performance impact of siphash (hashing bytes directly) is contained. Around 33.5µs (siphash) vs 32.5µs (current) on a 64-bit host.

For some reason the last commit didn't appear on GitHub. I amended and force pushed it.

Find the way, we should declare

struct Hasher
  def slice(value) : self
    @siphash.update(value)
    self
  end

  def string(value)
    value.to_slice.hash(self)
  end
end

struct Slice(T)
  def hash(hasher)
    hasher.slice(self)
  end
end

and revert Hasher.string to use to_slice.
What do you think, @ysbaddaden?

Tried already, but Int32.slice(1, 2, 3).hash will fail, since SipHash#update only accepts String and Bytes aka Slice(UInt8).

We could consider a Slice to be a binary blob, and hash it as is:

struct Slice(T)
  def hash(hasher)
    hasher.bytes Bytes.new(to_unsafe.as(UInt8*), size * sizeof(T))
  end
end

But I'm not sure; what if T is Time or LibC::SockaddrIn? Shall we iterate the slice and hash each item as item.hash(hasher)? We may only optimize basic primitives:

struct Slice(T)
  def hash(hasher)
    {% if [UInt8, UInt16, UInt32, UInt64, Int8, Int16, Int32, Int64, Bool, Float32, Float64].includes?(T) %}
      hasher.bytes Bytes.new(to_unsafe.as(UInt8*), size * sizeof(T))
    {% else %}
      super hasher
    {% end %}
  end
end

But maybe we shouldn't care: a slice is a memory blob of binary data, and that's it. We can't because T maybe anything, a primitive, a struct, or a Reference (in which case we should iterate).

I prefer to think about Slice as blob (may be with stricture on T.struct? || T.is_a?(Primitive)).

Just because hash author must know where he uses slice(value) method.

I got the wrong assumption that Slice(T) only accepted primitives and structs for T, but it accepts anything, so yeah, we should filter-out references, but there doesn't seem to be T.primitive? nor T.struct? in TypeNode macro methods.

I now think that Slice's design is not good. Maybe we should only have Bytes which is a hardcoded version of Slice with UInt8. I don't think there are use cases for Slice where T isn't UInt8. So for now I wouldn't worry about optimizing this for other types of slices.

I disagree. There's plenty of times where C structs and other int primitives make sense. Please keep Slice generally generic. I'd at least need to hear some concrete arguments against it first.

Since Pointer(Struct) is possible I suppose say that Slice(Struct) makes sense too, if we consider slice to be safe pointers with bound checks.

Maybe aliasing Bytes as Slice(UInt8) is the issue? It's basically the same, but conceptually maybe there is a tiny difference: a chunk of bytes vs a collection of ordered T?

I still don't see the problem, this is simply a performance enhancement right? The typical method is simply to iterate the slice and call hash(hasher), as with any other collection. We simply perform a performance optimization in the case of primitive numeric types.

Btw, is macro system allows to know type.has_inner_pointers?? It allows full optimization of hashing on any slices.

@akzhan Why? Float doesn't have inner pointers, but it still must use hash(hasher) to ensure it's normalized.

@RX14 Slice on T without any references can be interpreted as raw byte array. It's usable for hashing too.

No, Slice is a collection of items, not a raw byte array. Sometimes those items happen to be bytes.

We can perform optimizations in some cases where we can read the slice in blocks which suit siphash, but that's all it is: an optimization.

class Test
  def ==(other : Test)
    true
  end

  def hash(hasher)
    hasher.bool(true)
  end
end

Slice(Test).new(1, Test.new).hash == Slice(Test).new(1, Test.new).hash

This should always be true even if they're different pointers to different objects because we defined them to be the same using == and hash.

The simple optimization we would perform, that @ysbaddaden already wrote the code for (without float though), preserves this property (all equal ints have one unique bit representation on a given machine), so it's valid.

Ok, lets get it merged.

@ysbaddaden you should rework https://github.com/crystal-lang/crystal/pull/5000/files#diff-ecf42db578886535ae723622017d8e95R179 code piece to keep StringPool fast.

I read more closely the issue. As I said, Slice(UInt8) is by far the most common type of slice. If we can optimize for that case then we should do it. Other slices can use a slower hash for now. That should also optimize String if we use str.to_slice.hash.

I've just profiled the compiler compiling itself: a full 10% of compiler time is spent in Slice(UInt8)#hash. This method needs to be highly optimized.

@RX14 What if you profile the compiler before we started making all these changes to hash?

In my version I made only specialization for Bytes aka Slice(Uint8) (and String#hash used it).

I don't see reason this shouldn't be done. At least until crystal has specialized primitive "string_slice".

BTW, don't forget about hashing of HTTP headers.

I pushed a commit to optimize Bytes#hash and keep the iteration for other Slice(T), so for example:

Int32.slice(1, 2, 3).hash == Int64.slice(1, 2, 3)
Int32.slice(1, 2, 3).hash != UInt8.slice(1, 2, 3)

@ysbaddaden what about this trick:

struct Crystal::Hasher
  def slice(value) : self
    return self unless value.bytesize
    if value.first.is_a?(Int::Primitive) || value.first.is_a?(Float::Primitive)

p "fast"
      p64 = value.to_unsafe.as(UInt64*)
      size64 = value.bytesize / sizeof(UInt64)
      size64.times do |i|
        @result = @result * 31 + p64[i]
      end
      full_len = size64 * 4
      remainder = value.bytesize & 0x03
      remainder.times do |r|
        @result = @result * 31 + value.to_unsafe.as(UInt8*)[full_len + r]
      end
      self
    else
      self
    end
  end
end

p Crystal::Hasher.new.slice(Slice(UInt8).new(4)).result

Looks like code piece that checks Slice T should be rewritten.

Wow. I have this benchmark:

words = ["one", "two", "hello world", "welcome", "good bye", "さようなら"]

hash = {} of String => Int32
words.each do |word|
  hash[word] = word.bytesize
end

time = Time.now
a = 0
10_000_000.times do
  words.each do |word|
    a += hash[word]
  end
end
puts Time.now - time

In Crystal 0.23.1 it takes 0.95s. In master (because we now randomize hashes) it takes 1.69s. And with this PR it takes 4.27s!

But then, the same benchmark in Ruby takes 12.98s, so it might be ok. However, in Go it takes 0.76s, so I guess we better optimize our Hash and #hash algorithms. I checked and Go doesn't seem to use siphash.

On my laptop:

yura@dell:~/Project/crystal$ ~/tmp/bench_master
00:00:01.582613000
yura@dell:~/Project/crystal$ ~/tmp/bench_master
00:00:01.586930000
yura@dell:~/Project/crystal$ ~/tmp/bench_master
00:00:01.605560000
yura@dell:~/Project/crystal$ ~/tmp/bench_mine
00:00:00.9957240
yura@dell:~/Project/crystal$ ~/tmp/bench_mine
00:00:01.0005630
yura@dell:~/Project/crystal$ ~/tmp/bench_mine
00:00:01.0528370

bench_mine - is a hasher1 branch

yura@dell:~/Project/crystal$ ~/tmp/bench_minehash                                                                                              
00:00:02.1886980
yura@dell:~/Project/crystal$ ~/tmp/bench_minehash
00:00:02.1599750
yura@dell:~/Project/crystal$ ~/tmp/bench_minehash
00:00:02.2136030

bench_minehash version with my hash function.
(bench_mine used just my hasher with almost same hash function as master).

All is compiled with --release

yura@dell:~/Project/crystal$ ~/tmp/bench_minehash_old
00:00:01.0748730
yura@dell:~/Project/crystal$ ~/tmp/bench_minehash_old
00:00:01.0996810
yura@dell:~/Project/crystal$ ~/tmp/bench_minehash_old
00:00:01.1796260

With hash function I initially crafted for Crystal.

Here are my results (Ubuntu 14.04, 64-bit), using benchmark.ips and 2165 random english words. Master is slightly slower than 0.23.1, while this branch is twice slower:

test  10.12k (  98.8µs) (± 0.44%) fastest           [0.23.1]
test   9.13k (109.57µs) (± 0.28%) fastest           [master]
test    5.8k (172.48µs) (± 1.39%) fastest           [siphash]

Note: we can most surely tweak / rework the algorithm to enable some LLVM optimizations.

I checked and Go doesn't seem to use siphash.

Go uses as fast function as its author could made.
It is not crypto-strong even nearly (despite it uses aes-inc primitive if present).
But it is resistant to hash-flood given hash-value is not exposed.
(And Go's runtime never exposes it).
And they use per-table random seed combined with application level random seed.

So, it is your choice what to use:

• buzz-word crypto-strong but slow hash function,
• or just enough strong fast function.

I think I prefer strong enough fast function :-)

@funny-falcon can you send PR with your fastest implementation?

I'm always can get hasher1, of course.

With no normalization please

hasher1 is almost the same as current hasher, so it is as dumb.
I will prepare version with funny_hash64.

@asterite @funny-falcon I think that we

1. must incorporate fastest HashDoS defence algorithm from @funny-falcon
2. give SipHash digest algorithms as option (not used by Crystal)
3. rework hashes using open addressing, as initially designed.
4. introduce Python-inspired number normalization (optional, on the way).

Every step is by another PR.

I've made #5146 with funny_hash64 like function.
Surpisingle, I could not make faster than current dumb hasher for the benchmark above.
But it is not slower either. Looks like, with relatively fast function bottleneck is somewhere else.

Fastest result above were achieved on branch from older master commit with my hasher interface and 2*32bit state.
I don't know which factor is most significiant: older master commit, my hasher interface or 2*32bit state :-(
And my wife will bite me cause I'm still not at home. So, I'm done for today.

@ysbaddaden looks this PR should be modified to no touch Crystal::Hasher directly. Just alternative digests.

Now that the alternative hash function has been merged, I don't think there's a need for this in the standard library (it could be a useful shard, though).

It was already: https://github.com/ysbaddaden/siphash.cr