fast_hash.cpp

#include "fast_hash.hpp"
namespace AppenDB {
  // hash64 is Thomas Wang's 64-bit integer hash (hash64shift), published
  // without an explicit license and widely treated as freely usable.
  uint64_t hash64(uint64_t key) {
    key = (~key) + (key << 21); // key = (key << 21) - key - 1;
    key = key ^ (key >> 24);
    key = (key + (key << 3)) + (key << 8); // key * 265
    key = key ^ (key >> 14);
    key = (key + (key << 2)) + (key << 4); // key * 21
    key = key ^ (key >> 28);
    key = key + (key << 31);
    return key;
  }

  // inverse_hash64 inverts the above, following the commonly circulated
  // derivation of the inverse of Thomas Wang's hash.
  uint64_t inverse_hash64(uint64_t key) {
    uint64_t tmp;

    // Invert key = key + (key << 31)
    tmp = key-(key<<31);
    key = key-(tmp<<31);

    // Invert key = key ^ (key >> 28)
    tmp = key^key>>28;
    key = key^tmp>>28;

    // Invert key *= 21
    key *= 14933078535860113213u;

    // Invert key = key ^ (key >> 14)
    tmp = key^key>>14;
    tmp = key^tmp>>14;
    tmp = key^tmp>>14;
    key = key^tmp>>14;

    // Invert key *= 265
    key *= 15244667743933553977u;

    // Invert key = key ^ (key >> 24)
    tmp = key^key>>24;
    key = key^tmp>>24;

    // Invert key = (~key) + (key << 21)
    tmp = ~key;
    tmp = ~(key-(tmp<<21));
    tmp = ~(key-(tmp<<21));
    key = ~(key-(tmp<<21));

    return key;
  }

  uint64_t hash64(const char * const b, size_t const size){
    const uint64_t volatile *as64 = reinterpret_cast<const uint64_t *>(b);
    if(size == 8) return hash64(*as64);
    size_t const num_pieces = (size >> 3);
    size_t const remainder = size & 7;
    uint64_t pieces[num_pieces];
    for(size_t i = 0; i != num_pieces; ++i) pieces[i] = hash64(as64[i]);
    uint64_t accumulator = 1 + (2 * size);
    const char *remainder_pointer = b + (8 * num_pieces);
    unsigned int shift_amount = 8;
    if(remainder & 4){
      accumulator ^= (static_cast<uint64_t>(*reinterpret_cast<const uint32_t *>(remainder_pointer)) << shift_amount);
      remainder_pointer += 4;
      shift_amount += 32;
    }
    if(remainder & 2){
      accumulator ^= (static_cast<uint64_t>(*reinterpret_cast<const uint16_t *>(remainder_pointer)) << shift_amount);
      remainder_pointer += 2;
      shift_amount += 16;
    }
    if(remainder & 1){
      accumulator ^= (static_cast<uint64_t>(*reinterpret_cast<const unsigned char *>(remainder_pointer)) << shift_amount);
      remainder_pointer += 1;
      shift_amount += 8;
    }
    accumulator = hash64(accumulator);
    assert(remainder_pointer == (b + size));
    for(size_t i = 0; i != num_pieces; ++i) accumulator += pieces[i];
    return accumulator;
  }
}

// this is code for testing how fast various operations are
/*
#include <cstdlib>
static size_t const BUFFER_SIZE = 128*1024;
static size_t const NUM_RUNS = 100;
int main(){
  char buffer[BUFFER_SIZE + 100];
  for(size_t i = 0; i != BUFFER_SIZE + 100; ++i) buffer[i] = (::std::rand()) & 0xFF;
  uint64_t last_hash = 0;

  timespec start_time;
  timespec end_time;
  timespec misc_time;
  unsigned int match_count;

  last_hash = ::AppenDB::hash64(buffer, BUFFER_SIZE);
  clock_gettime(CLOCK_MONOTONIC_RAW, &start_time);
  for(size_t i = 0; i != NUM_RUNS; ++i){
    uint64_t hash = ::AppenDB::hash64(buffer, BUFFER_SIZE);
    if(last_hash != hash) ::std::abort();
    last_hash = hash;
  }
  clock_gettime(CLOCK_MONOTONIC_RAW, &end_time);
  ::std::cout << (static_cast<double>(((end_time.tv_sec - start_time.tv_sec) * 1000000000ULL) + (end_time.tv_nsec - start_time.tv_nsec)) / static_cast<double>(NUM_RUNS)) << "ns to hash a 128k key" << ::std::endl;

  clock_gettime(CLOCK_MONOTONIC_RAW, &start_time);
  match_count = 0;
  for(size_t i = 0; i != NUM_RUNS; ++i){
    for(size_t j = 0; j != BUFFER_SIZE; j += 8){
      uint64_t hash = ::AppenDB::hash64(buffer + j, 8);
      if(last_hash == hash) ++match_count;
      last_hash = hash;
    }
  }
  clock_gettime(CLOCK_MONOTONIC_RAW, &end_time);
  ::std::cout << (static_cast<double>(((end_time.tv_sec - start_time.tv_sec) * 1000000000ULL) + (end_time.tv_nsec - start_time.tv_nsec)) / static_cast<double>(NUM_RUNS)) << "ns to hash 16k 64-bit keys as variable length keys, match_count: " << (match_count / NUM_RUNS) << ::std::endl;

  clock_gettime(CLOCK_MONOTONIC_RAW, &start_time);
  match_count = 0;
  for(size_t i = 0; i != NUM_RUNS; ++i){
    for(size_t j = 0; j != BUFFER_SIZE; j += 8){
      uint64_t hash = ::AppenDB::hash64(*reinterpret_cast<const uint64_t*>(buffer + j));
      if(last_hash == hash) ++match_count;
      last_hash = hash;
    }
  }
  clock_gettime(CLOCK_MONOTONIC_RAW, &end_time);
  ::std::cout << (static_cast<double>(((end_time.tv_sec - start_time.tv_sec) * 1000000000ULL) + (end_time.tv_nsec - start_time.tv_nsec)) / static_cast<double>(NUM_RUNS)) << "ns to hash 16k 64-bit keys as uint64_t, match_count: " << (match_count / NUM_RUNS) << ::std::endl;

  clock_gettime(CLOCK_MONOTONIC_RAW, &start_time);
  match_count = 0;
  for(size_t i = 0; i != NUM_RUNS; ++i){
    for(size_t j = 0; j != BUFFER_SIZE; j += 16){
      uint64_t hash = ::AppenDB::hash64(buffer + j, 16);
      if(last_hash == hash) ++match_count;
      last_hash = hash;
    }
  }
  clock_gettime(CLOCK_MONOTONIC_RAW, &end_time);
  ::std::cout << (static_cast<double>(((end_time.tv_sec - start_time.tv_sec) * 1000000000ULL) + (end_time.tv_nsec - start_time.tv_nsec)) / static_cast<double>(NUM_RUNS)) << "ns to hash 8k 128-bit keys as variable length keys, match_count: " << (match_count / NUM_RUNS) << ::std::endl;

  clock_gettime(CLOCK_MONOTONIC_RAW, &start_time);
  match_count = 0;
  for(size_t i = 0; i != NUM_RUNS; ++i){
    for(size_t j = 0; j < BUFFER_SIZE; j += 7){
      uint64_t hash = ::AppenDB::hash64(buffer + j, 7);
      if(last_hash == hash) ++match_count;
      last_hash = hash;
    }
  }
  clock_gettime(CLOCK_MONOTONIC_RAW, &end_time);
  ::std::cout << (static_cast<double>(((end_time.tv_sec - start_time.tv_sec) * 1000000000ULL) + (end_time.tv_nsec - start_time.tv_nsec)) / static_cast<double>(NUM_RUNS)) << "ns to hash 128k of keys, 7 bytes at a time, match_count: " << (match_count / NUM_RUNS) << ::std::endl;

  clock_gettime(CLOCK_MONOTONIC_RAW, &start_time);
  match_count = 0;
  for(size_t i = 0; i != NUM_RUNS; ++i){
    for(size_t j = 0; j < BUFFER_SIZE; j += 1){
      uint64_t hash = ::AppenDB::hash64(buffer + j, 1);
      if(last_hash == hash) ++match_count;
      last_hash = hash;
    }
  }
  clock_gettime(CLOCK_MONOTONIC_RAW, &end_time);
  ::std::cout << (static_cast<double>(((end_time.tv_sec - start_time.tv_sec) * 1000000000ULL) + (end_time.tv_nsec - start_time.tv_nsec)) / static_cast<double>(NUM_RUNS)) << "ns to hash 128k of keys, 1 byte at a time, match_count: " << (match_count / NUM_RUNS) << ::std::endl;

  clock_gettime(CLOCK_MONOTONIC_RAW, &start_time);
  match_count = 0;
//  for(size_t i = 0; i != NUM_RUNS; ++i){
    for(size_t j = 0; j != BUFFER_SIZE; ++j){
      uint64_t hash = ::AppenDB::hash64(buffer, j);
      if(last_hash == hash) ++match_count;
      last_hash = hash;
    }
//  }
  clock_gettime(CLOCK_MONOTONIC_RAW, &end_time);
  ::std::cout << (static_cast<double>(((end_time.tv_sec - start_time.tv_sec) * 1000000000ULL) + (end_time.tv_nsec - start_time.tv_nsec))) << "ns to hash all lengths of data from 0 to 128k-1 bytes, match_count: " << (match_count / NUM_RUNS) << ::std::endl;

  clock_gettime(CLOCK_MONOTONIC_RAW, &start_time);
  match_count = 0;
  for(size_t i = 0; i != NUM_RUNS; ++i){
    for(size_t j = 0; j != 64; ++j){
      uint64_t hash = ::AppenDB::hash64(buffer, j);
      if(last_hash == hash) ++match_count;
      last_hash = hash;
    }
  }
  clock_gettime(CLOCK_MONOTONIC_RAW, &end_time);
  ::std::cout << (static_cast<double>(((end_time.tv_sec - start_time.tv_sec) * 1000000000ULL) + (end_time.tv_nsec - start_time.tv_nsec)) / static_cast<double>(NUM_RUNS)) << "ns to hash all lengths of data from 0 to 63 bytes, match_count: " << (match_count / NUM_RUNS) << ::std::endl;

  clock_gettime(CLOCK_MONOTONIC_RAW, &start_time);
  match_count = 0;
  for(size_t i = 0; i != NUM_RUNS; ++i){
    for(size_t j = 0; j != 16; ++j){
      uint64_t hash = ::AppenDB::hash64(buffer, j);
      if(last_hash == hash) ++match_count;
      last_hash = hash;
    }
  }
  clock_gettime(CLOCK_MONOTONIC_RAW, &end_time);
  ::std::cout << (static_cast<double>(((end_time.tv_sec - start_time.tv_sec) * 1000000000ULL) + (end_time.tv_nsec - start_time.tv_nsec)) / static_cast<double>(NUM_RUNS)) << "ns to hash all lengths of data from 0 to 15 bytes, match_count: " << (match_count / NUM_RUNS) << ::std::endl;

  return 0;
}
*/