3
\$\begingroup\$

A few notes:

  • There is currently no non exception-based way of knowing whether a key is present in the table or not. This is intentional for my use case.

  • Unlike the lookup process, the baking process is definitely not appropriate for a real-time application. That's ok as it's meant to be run offline.

  • Obviously, this is only appropriate for storing trivial types.

What I'm particularly interested in is:

  1. I "think" I managed to pull this off without any Undefined Behavior, but I'd really want some other pairs of eyes checking for this, as I'm in dodgy territory on that front.

  2. As usual, any and all criticism on general code quality.

Thanks!

#include <cassert>
#include <cstdint>
#include <cstring>
#include <functional>
#include <type_traits>
#include <unordered_set>
#include <utility>

// The flat hash table is meant to be used when a hash table is baked once,
// typically during a build process, and then used repeatadly. It can be
// initialized by simply pointing it at a memory location containing the
// raw data.
// The table does NOT maintain ownership over the data.
template <typename ValT, typename HashT = std::uint64_t>
class flat_hash_table {
  static_assert(std::is_trivial_v<ValT>);
  static_assert(std::is_trivial_v<HashT>);

 public:
  flat_hash_table(char const* mem_loc, std::size_t mem_len)
      : mem_loc_(mem_loc) {
    if (mem_len < sizeof(bucket_count_)) {
      throw std::invalid_argument("invalid flat hash data");
    }

    char const* read_ptr = mem_loc;
    std::memcpy(&bucket_count_, read_ptr, sizeof(bucket_count_));
    read_ptr += sizeof(bucket_count_);

    if (mem_len < sizeof(bucket_count_) + bucket_count_ * sizeof(bucket_t)) {
      throw std::invalid_argument("invalid flat hash data");
    }

    if (std::uintptr_t(read_ptr) % alignof(bucket_t) != 0) {
      throw std::invalid_argument("flat hash data appears to be misaligned");
    }

    static_assert(std::is_trivially_constructible_v<bucket_t>);
    buckets_ = new (const_cast<char*>(read_ptr)) bucket_t[bucket_count_];

    for (std::uint32_t i = 0; i < bucket_count_; ++i) {
      if (buckets_[i].offset + buckets_[i].count * sizeof(elem_t) > mem_len) {
        throw std::invalid_argument("invalid flat hash data");
      }

      auto bucket_loc = mem_loc_ + buckets_[i].offset;
      if (std::uintptr_t(bucket_loc) % alignof(elem_t) != 0) {
        throw std::invalid_argument("flat hash data appears to be misaligned");
      }

      static_assert(std::is_trivially_constructible_v<elem_t>);
      new (const_cast<char*>(bucket_loc)) elem_t[buckets_[i].count];
    }
  }

  // Lookup a value from the hash table, throws if the value is not 
  // present.
  template <typename KeyT>
  ValT const& at(KeyT const& key) {
    HashT key_hash = std::hash<KeyT>{}(key);
    auto const& bucket = buckets_[key_hash % bucket_count_];

    if (bucket.count > 0) {
      elem_t const* elem_table =
          reinterpret_cast<elem_t const*>(mem_loc_ + bucket.offset);

      auto end = elem_table + bucket.count;

      // Elements within a bucket are stored as a sorted vector, so we 
      // can do a binary search.
      auto found = std::lower_bound(
          elem_table, end, key_hash,
          [](elem_t const& lhs, HashT const& rhs) { return lhs.key < rhs; });

      if (found != end && found->key == key_hash) {
        return found->val;
      }
    }

    throw std::out_of_range("element not present in flat hash table");
  }

 private:
  char const* mem_loc_;

  struct bucket_t {
    std::uint32_t count;
    std::uint32_t offset;
  };

  // This cannot be a std::pair<> because the default constructor is not trivial
  struct elem_t {
    HashT key;
    ValT val;
  };

  std::uint32_t bucket_count_;
  bucket_t const* buckets_;

  template <typename K, typename V, typename H>
  friend std::vector<char> bake_flat_hash_table(
      std::vector<std::pair<K, V>> const&);
};

// Bakes a dataset into a flat_has_table raw data chunk.
template <typename KeyT, typename ValT, typename HashT = std::uint64_t>
std::vector<char> bake_flat_hash_table(
    std::vector<std::pair<KeyT, ValT>> const& data) {
  using table_t = flat_hash_table<ValT, HashT>;
  using elem_t = typename table_t::elem_t;
  using bucket_t = typename table_t::bucket_t;

  static_assert(std::is_trivial_v<ValT>);
  static_assert(std::is_trivial_v<HashT>);

  // TODO: Better process to determine optimal bucket count.
  std::uint32_t bucket_count = data.size() / 2 + 1;
  std::vector<std::vector<elem_t>> buckets(bucket_count);

  {
    // Keep track of seen hashes since we do not tolerate true collisions.
    std::unordered_set<HashT> hash_values_set;
    for (auto const& d : data) {
      HashT hash_val = HashT(std::hash<KeyT>{}(d.first));

      if (hash_values_set.count(hash_val) != 0) {
        throw std::runtime_error(
            "True hash collision in dataset, cannot make a flat hash table out "
            "of it.");
      }
      hash_values_set.insert(hash_val);

      buckets[hash_val % bucket_count].emplace_back(elem_t{hash_val, d.second});
    }
  }

  std::size_t header_mem_size = 0;
  header_mem_size += sizeof(std::uint32_t);            // for bucket_count
  header_mem_size += sizeof(bucket_t) * bucket_count;  // bucket table

  // Make sure the actual value payloads is correctly aligned
  constexpr auto elem_align = alignof(elem_t);
  static_assert((elem_align & (elem_align - 1)) == 0);
  header_mem_size = (header_mem_size + (elem_align - 1)) & ~(elem_align - 1);

  auto mem_size = header_mem_size + sizeof(elem_t) * data.size();

  std::vector<char> result(mem_size);

  char* header_w_ptr = result.data();
  char* data_w_ptr = result.data() + header_mem_size;

  auto write = [&](char*& dst, auto const& v) {
    assert(dst + sizeof(v) <= result.data() + result.size());
    std::memcpy(dst, &v, sizeof(v));
    dst += sizeof(v);
  };

  write(header_w_ptr, bucket_count);

  for (auto& b : buckets) {
    std::sort(b.begin(), b.end(), [](auto const& lhs, auto const& rhs) {
      return lhs.key < rhs.key;
    });

    auto offset = data_w_ptr - result.data();
    bucket_t bucket_header{std::uint32_t(b.size()), std::uint32_t(offset)};

    write(header_w_ptr, bucket_header);

    for (auto const& e : b) {
      write(data_w_ptr, e);
    }
  }
  return result;
}

#include <iostream>
#include <string_view>
#include <vector>

int main() {
  std::vector<std::pair<std::string, float>> raw_values = {
      {"hi", 12.0f}, {"yo", 10.0f}, {"sup", 3.0f},
  };

  std::vector<char> raw_data = bake_flat_hash_table(raw_values);

  flat_hash_table<float> values(raw_data.data(), raw_data.size());

  std::cout << values.at(std::string_view("yo")) << "\n";
  std::cout << values.at(std::string_view("sup")) << "\n";
  std::cout << values.at(std::string_view("hi")) << "\n";

  return 0;
}

Obvious next steps / stuff I'm already aware of:

  • Endianness handling
  • Proper iterator-based lookup interface
  • Better bucket counting
\$\endgroup\$
  • \$\begingroup\$ Is internal layout of hashmap part of public interface? Code says yes, but I just wanted to be sure. \$\endgroup\$ – Incomputable Jun 30 '18 at 21:46
  • \$\begingroup\$ @Incomputable I'm not sure what you mean, it's definitely private. Only the baking function is friended in. \$\endgroup\$ – Frank Jun 30 '18 at 22:09
  • \$\begingroup\$ I just thought you wanted to allow other people to write their own bakers, given the constructor of the map. Structurizing the layout into class/struct would allow container-agnostic and algorithm-agnostic map construction. \$\endgroup\$ – Incomputable Jun 30 '18 at 22:10
  • \$\begingroup\$ @Incomputable The constructor is structured this way because the main way this will be used will be interpreting data loaded straight from a file. But the idea of letting people write their own baker is not bad... \$\endgroup\$ – Frank Jun 30 '18 at 22:13
  • \$\begingroup\$ Hi! I played with it a bit, but couldn't get what I wanted: constructing non-trivial types. I got the templating on container though. Link to gist. The modifications are almost trivial, so I decided not to post it as a separate question. And thanks, I got much better understanding of strict aliasing rule. Also the functions on canvas are kind of useless. \$\endgroup\$ – Incomputable Jul 12 '18 at 18:19
2
\$\begingroup\$

I'm no expert, but it seems like the code doesn't invoke UB. It is already great, but there are some small issues here and there.

Missing header

std::sort() is used in bake_flat_hash_table(), but <algorithm> is not added.

Assuming stateless std::hash

Although probably most implementations are stateless, there might be user provided specialization. And anyway, tagging 4 additional bytes along shouldn't be a problem. If stateless std::hash is required, it would be nice to put a check:

static_assert(std::is_empty_v<std::hash<KeyT>>, "Stateless std::hash is required");

Precompute instead of taking everything by ref

Pulling everything is not required in this case:

[&](char*& dst, auto const& v) {
    assert(dst + sizeof(v) <= result.data() + result.size());

This could be used instead:

[data_boundary = result.data() + result.size()](char*& dst, auto const& v) {
    assert(dst + sizeof(v) <= data_boundary);

In the worst case, it should be equally easy or easier for compiler to hoist it.

Leaking abstraction

It seems like baker function is to-be-constructor, but the need to return buffer holds it back from becoming constructor. It might be a good idea to pass buffer into constructor by non-const reference, since users need to hold on to it anyway.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the comments! The news are necessary as per the standard, otherwise the reinterpret_cast being done further down the line would be strict aliasing violations. \$\endgroup\$ – Frank Jun 30 '18 at 23:21
  • \$\begingroup\$ @Frank, thanks for the correction. I'll try to implement the idea I proposed in the comments. First thing I'd like to do is to allow std::array as underlying container. It would be pretty dope. \$\endgroup\$ – Incomputable Jun 30 '18 at 23:23
  • \$\begingroup\$ The baking function should simply take a templated pair of iterators instead of a vector<>, I admit I got lazy on that. \$\endgroup\$ – Frank Jun 30 '18 at 23:24
  • \$\begingroup\$ @Frank, resizing the container would be a problem. I could use if constexpr on ability to resize, and if too small on static containers, throw. It'll probably take a few days though, and very bad idea from engineering point of view. My main goal is to extract the lookup and layout from the code, and make everything else configurable. Should I put some particular license on it? I'd like to take your code as starting point, if you don't mind. \$\endgroup\$ – Incomputable Jun 30 '18 at 23:27
  • \$\begingroup\$ You can treat this as being Boost-licensed. Have fun! \$\endgroup\$ – Frank Jun 30 '18 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.