src/gn/string_atom.cc

// Copyright (c) 2020 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "gn/string_atom.h"

#include <array>
#include <memory>
#include <mutex>
#include <set>
#include <string>
#include <unordered_set>
#include <vector>

#include "gn/hash_table_base.h"

namespace {

// Implementation note:
//
// StringAtomSet implements the global shared state, which is:
//
//    - a group of std::string instances with a persistent address, allocated
//      through a fast slab allocator.
//
//    - a set of string pointers, corresponding to the known strings in the
//      group.
//
//    - a mutex to ensure correct thread-safety.
//
//    - a find() method that takes an std::string_view argument, and uses it
//      to find a matching entry in the string tree. If none is available,
//      a new std::string is allocated and its address inserted into the tree
//      before being returned.
//
// Because the mutex is a large bottleneck, each thread implements
// its own local string pointer cache, and will only call StringAtomSet::find()
// in case of a lookup miss. This is critical for good performance.
//

static const std::string kEmptyString;

using KeyType = const std::string*;

// A HashTableBase node type that stores one hash value and one string pointer.
struct KeyNode {
  size_t hash;
  KeyType key;

  // The following methods are required by HashTableBase<>
  bool is_valid() const { return !is_null(); }
  bool is_null() const { return !key; }
  size_t hash_value() const { return hash; }

  // No deletion support means faster lookup code.
  static constexpr bool is_tombstone() { return false; }
};

// This is a trivial hash table of string pointers, using open addressing.
// It is faster in practice than using a standard container or even a
// base::flat_set<>.
//
// Usage is the following:
//
//     1) Compute string hash value.
//
//     2) Call Lookup() with the hash value and the string_view key,
//        this always returns a mutable Node* pointer, say |node|.
//
//     3) If |node->key| is not nullptr, this is the key to use.
//        Otherwise, allocate a new string with persistent address,
//        and call Insert(), passing the |node|, |hash| and new string
//        address as arguments.
//
struct KeySet : public HashTableBase<KeyNode> {
  using BaseType = HashTableBase<KeyNode>;
  using Node = BaseType::Node;

  // Compute hash for |str|. Replace with faster hash function if available.
  static size_t Hash(std::string_view str) {
    return std::hash<std::string_view>()(str);
  }

  // Lookup for |str| with specific |hash| value.
  // Return a Node pointer. If the key was found, |node.key| is its value.
  // Otherwise, the caller should create a new key value, then call Insert()
  // below.
  //
  // NOTE: Even though this method is const, because it doesn't modify the
  //       state of the KeySet, it returns a *mutable* node pointer, to be
  //       passed to Insert() in case of a miss.
  //
  Node* Lookup(size_t hash, std::string_view str) const {
    return BaseType::NodeLookup(hash, [hash, &str](const Node* node) {
      // NOTE: Only is_valid() node pointers are passed to this function
      // which means key won't be null, and there are no tombstone values
      // in this derivation of HashTableBase<>.
      return node->hash == hash && *node->key == str;
    });
  }

  void Insert(Node* node, size_t hash, KeyType key) {
    node->hash = hash;
    node->key = key;
    BaseType::UpdateAfterInsert();
  }
};

class StringAtomSet {
 public:
  StringAtomSet() {
    // Ensure kEmptyString is in our set while not being allocated
    // from a slab. The end result is that find("") should always
    // return this address.
    //
    // This allows the StringAtom() default initializer to use the same
    // address directly, avoiding a table lookup.
    //
    size_t hash = set_.Hash("");
    auto* node = set_.Lookup(hash, "");
    set_.Insert(node, hash, &kEmptyString);
  }

  // Find the unique constant string pointer for |key|.
  const std::string* find(std::string_view key) {
    std::lock_guard<std::mutex> lock(mutex_);
    size_t hash = set_.Hash(key);
    auto* node = set_.Lookup(hash, key);
    if (node->key)
      return node->key;

    // Allocate new string, insert its address in the set.
    if (slab_index_ >= kStringsPerSlab) {
      slabs_.push_back(new Slab());
      slab_index_ = 0;
    }
    std::string* result = slabs_.back()->init(slab_index_++, key);
    set_.Insert(node, hash, result);
    return result;
  }

 private:
  static constexpr unsigned int kStringsPerSlab = 128;

  // Each slab is allocated independently, has a fixed address and stores
  // kStringsPerSlab items of type StringStorage. The latter has the same
  // size and alignment as std::string, but doesn't need default-initialization.
  // This is used to slightly speed up Slab allocation and string
  // initialization. The drawback is that on process exit, allocated strings
  // are leaked (but GN already leaks several hundred MiBs of memory anyway).

  // A C++ union that can store an std::string but without default
  // initialization and destruction.
  union StringStorage {
    StringStorage() {}
    ~StringStorage() {}
    char dummy;
    std::string str;
  };

  // A fixed array of StringStorage items. Can be allocated cheaply.
  class Slab {
   public:
    // Init the n-th string in the slab with |str|.
    // Return its location as well.
    std::string* init(size_t index, const std::string_view& str) {
      std::string* result = &items_[index].str;
      new (result) std::string(str);
      return result;
    }

   private:
    StringStorage items_[kStringsPerSlab];
  };

  std::mutex mutex_;
  KeySet set_;
  std::vector<Slab*> slabs_;
  unsigned int slab_index_ = kStringsPerSlab;
};

StringAtomSet& GetStringAtomSet() {
  static StringAtomSet s_string_atom_set;
  return s_string_atom_set;
}

// Each thread maintains its own ThreadLocalCache to perform fast lookups
// without taking any mutex in most cases.
class ThreadLocalCache {
 public:
  // Find the unique constant string pointer for |key| in this cache,
  // and fallback to the global one in case of a miss.
  KeyType find(std::string_view key) {
    size_t hash = local_set_.Hash(key);
    auto* node = local_set_.Lookup(hash, key);
    if (node->key)
      return node->key;

    KeyType result = GetStringAtomSet().find(key);
    local_set_.Insert(node, hash, result);
    return result;
  }

 private:
  KeySet local_set_;
};

thread_local ThreadLocalCache s_local_cache;

}  // namespace

StringAtom::StringAtom() : value_(kEmptyString) {}

StringAtom::StringAtom(std::string_view str) noexcept
    : value_(*s_local_cache.find(str)) {}