Jump Consistent Hash in Haskell and C++

A paper by John Lamping and Eric Veach1 describing Jump consistent hash, a fast, minimal memory, consistent hash algorithm that can be expressed in about 5 lines of code. The accompanying C++ code is indeed short and sweet:

However, there are a lot of implicit type conversions in the above code. This becomes apparent if you implement the algorithm in a language without implicit conversions. The following implementation in Haskell is quite close to a 1:1 translation of the C++ code (but using recursion instead of a while loop), and as you can see, there are five different type conversions happening (the conversions are named in the code):

So, in the (seemingly) simple algorithm, we have the following conversions taking place:

  • The int32 to int64 conversion happens when comparing j and b and is done through sign extension.
  • The int64 to int32 conversion is the last step of the algorithm and is done when returning b, which was a 64-bit integer in the loop, to a 32-bit integer. This behaviour is actually implementation-defined(!)2 3, so the algorithm relies on the compiler doing the sensible thing here. In practice, this is probably not a problem.
  • The int64 to double and uint64 to double conversions happen when doing floating-point calculations with integer values and are “floating-integral conversions”. Loss of precision occurs if the integral value cannot be represented exactly as a value of the floating type. If the value being converted is outside the range of values that can be represented, the behavior is undefined. 4
  • The double to int64 conversion truncates, i.e. discards the fractional part, of the double. 5

This was, at least for me, an interesting case of how often “hidden” behaviour can be a crucial part of code.

  1. Lamping, J., & Veach, E. (2014). A Fast, Minimal Memory, Consistent Hash Algorithm. arXiv Preprint arXiv:1406.2294, (1), 1–12. Retrieved from http://arxiv.org/abs/1406.2294

  2. The value is unchanged if it can be represented in the destination type (and bit-field width); otherwise, the value is implementation-defined.

  3. C++11 Standard §4.7.3

  4. C++11 Standard §4.9.2

  5. C++11 Standard §4.9.1