clang-tools 24.0.0git
ConcurrentStringPool.h
Go to the documentation of this file.
1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file defines ConcurrentStringPool, a lock-free deduplicating string
11/// saver for clang-doc.
12///
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_DOC_CONCURRENTSTRINGPOOL_H
16#define LLVM_CLANG_TOOLS_EXTRA_CLANG_DOC_CONCURRENTSTRINGPOOL_H
17
18#include "llvm/ADT/LazyAtomicPointer.h"
19#include "llvm/ADT/SmallString.h"
20#include "llvm/ADT/StringRef.h"
21#include "llvm/ADT/Twine.h"
22#include "llvm/Support/Compiler.h"
23#include "llvm/Support/ErrorHandling.h"
24#include "llvm/Support/MathExtras.h"
25#include "llvm/Support/PerThreadBumpPtrAllocator.h"
26#include "llvm/Support/xxhash.h"
27
28#include <array>
29#include <cassert>
30#include <cstddef>
31#include <cstdint>
32#include <limits>
33#include <memory>
34#include <string>
35
36namespace clang {
37namespace doc {
38
39/// A thread-safe string pool that deduplicates strings into a
40/// PerThreadBumpPtrAllocator.
41///
42/// Keys are sharded by the upper bits of their hash. Each shard holds an array
43/// with a power-of-two number of slabs which are allocated on demand via
44/// LazyAtomicPointer. Lookups probe a small window in each slab and move to
45/// the next level when the window is full, avoiding locks and table rehashing.
46///
47/// \tparam ShardBits Number of upper hash bits used to select a shard (1..31).
48/// \tparam InitialSlabCapacity Power-of-two capacity of level 0.
49/// \tparam ProbeWindow Linear probe window per level (1..InitialSlabCapacity).
50/// \tparam NumLevels Number of doubling slab levels per shard; the largest
51/// slab (InitialSlabCapacity << (NumLevels - 1)) must not exceed
52/// 2^(32 - ShardBits), the bits of ProbeHash not consumed by ShardBits.
53template <size_t ShardBits = 10, uint32_t InitialSlabCapacity = 256,
54 uint32_t ProbeWindow = 8, size_t NumLevels = 15>
56 static_assert(ShardBits > 0 && ShardBits < 32,
57 "ShardBits must be between 1 and 31");
58 static_assert(llvm::isPowerOf2_32(InitialSlabCapacity),
59 "InitialSlabCapacity must be a power of two");
60 static_assert(ProbeWindow > 0 && ProbeWindow <= InitialSlabCapacity,
61 "ProbeWindow must fit within InitialSlabCapacity");
62 static_assert(NumLevels > 0 && NumLevels < 32,
63 "NumLevels must be between 1 and 31");
64
65 static constexpr size_t NumShards = 1ULL << ShardBits;
66 static constexpr size_t ProbeBits = 32 - ShardBits;
67 static constexpr uint64_t MaxSlabCapacity = 1ULL << ProbeBits;
68 static constexpr uint64_t LargestSlabCapacity = uint64_t(InitialSlabCapacity)
69 << (NumLevels - 1);
70 static constexpr size_t CacheLineBytes = 64;
71
72 static_assert(LargestSlabCapacity <= MaxSlabCapacity,
73 "Slab capacity must not overlap ShardBits");
74
75 // Store Size and Hash alongside Data so probe mismatches don't chase the
76 // string pointer into the arena.
77 struct Bucket {
78 llvm::LazyAtomicPointer<const char> Data;
79 uint32_t Size = 0;
80 uint32_t Hash = 0;
81 };
82 static_assert(sizeof(Bucket) <= CacheLineBytes / 4,
83 "a cache line should fit at least 4 Buckets");
84
85 // Align shards to cache lines to avoid false sharing.
86 struct alignas(CacheLineBytes) Shard {
87 std::array<llvm::LazyAtomicPointer<Bucket>, NumLevels> Slabs{};
88
89 ~Shard() {
90 for (llvm::LazyAtomicPointer<Bucket> &SlabPtr : Slabs)
91 delete[] SlabPtr.load();
92 }
93 };
94
95public:
98
102
103 /// Save string \p S in the arena.
104 /// \return a reference to the interned string.
105 llvm::StringRef save(const char *S) { return save(llvm::StringRef(S)); }
106
107 llvm::StringRef save(const std::string &S) {
108 return save(llvm::StringRef(S));
109 }
110
111 llvm::StringRef save(const llvm::Twine &S) {
112 if (S.isTriviallyEmpty())
113 return llvm::StringRef();
114 if (S.isSingleStringRef())
115 return save(S.getSingleStringRef());
116 return saveTwineSlow(S);
117 }
118
119 llvm::StringRef save(llvm::StringRef S) {
120 if (S.empty())
121 return llvm::StringRef();
122 return insert(S);
123 }
124
125private:
126 LLVM_ATTRIBUTE_NOINLINE llvm::StringRef saveTwineSlow(const llvm::Twine &S) {
127 llvm::SmallString<128> Storage;
128 S.toVector(Storage);
129 return save(llvm::StringRef(Storage.data(), Storage.size()));
130 }
131
132 llvm::StringRef insert(llvm::StringRef S) {
133 assert(S.size() <= std::numeric_limits<uint32_t>::max() &&
134 "String exceeds 32-bit size limit");
135
136 // Hash the string and select the shard.
137 uint64_t Hash = llvm::xxh3_64bits(S);
138 uint32_t HashTag = static_cast<uint32_t>(Hash);
139 uint32_t ProbeHash = static_cast<uint32_t>(Hash >> 32);
140 Shard &Sh = (*Shards)[Hash >> (64 - ShardBits)];
141
142 // Find the right bucket in the shard to intern into via probing.
143 for (size_t Level = 0; Level < NumLevels; ++Level) {
144 uint32_t SlabCapacity = InitialSlabCapacity << Level;
145 Bucket *CurSlab = &Sh.Slabs[Level].loadOrGenerate(
146 [SlabCapacity] { return new Bucket[SlabCapacity](); });
147 uint32_t Mask = SlabCapacity - 1;
148 uint32_t StartIdx = ProbeHash & Mask;
149 for (uint32_t P = 0; P < ProbeWindow; ++P) {
150 Bucket &B = CurSlab[(StartIdx + P) & Mask];
151 const char &First = B.Data.loadOrGenerate([&] {
152 B.Size = static_cast<uint32_t>(S.size());
153 B.Hash = HashTag;
154 return S.copy(Allocator).data();
155 });
156 llvm::StringRef Entry(&First, B.Size);
157 if (LLVM_LIKELY(B.Hash == HashTag && Entry == S))
158 return Entry;
159 }
160 }
161 llvm_unreachable("ConcurrentStringPool capacity exhausted");
162 }
163
164 using ShardArray = std::array<Shard, NumShards>;
165 std::unique_ptr<ShardArray> Shards = std::make_unique<ShardArray>();
166 llvm::parallel::PerThreadBumpPtrAllocator Allocator;
167};
168
170
171} // namespace doc
172} // namespace clang
173
174#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_DOC_CONCURRENTSTRINGPOOL_H
A thread-safe string pool that deduplicates strings into a PerThreadBumpPtrAllocator.
llvm::StringRef save(const char *S)
Save string S in the arena.
llvm::StringRef save(const std::string &S)
ConcurrentStringPoolImpl(const ConcurrentStringPoolImpl &)=delete
ConcurrentStringPoolImpl & operator=(const ConcurrentStringPoolImpl &)=delete
llvm::StringRef save(llvm::StringRef S)
llvm::StringRef save(const llvm::Twine &S)
ConcurrentStringPoolImpl<> ConcurrentStringPool
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//