blob: fe1ef7382cdec80f504dd76d809805c32c514418 [file] [log] [blame]
// 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)) {}