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");
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)
70 static constexpr size_t CacheLineBytes = 64;
72 static_assert(LargestSlabCapacity <= MaxSlabCapacity,
73 "Slab capacity must not overlap ShardBits");
78 llvm::LazyAtomicPointer<const char> Data;
82 static_assert(
sizeof(Bucket) <= CacheLineBytes / 4,
83 "a cache line should fit at least 4 Buckets");
86 struct alignas(CacheLineBytes) Shard {
87 std::array<llvm::LazyAtomicPointer<Bucket>, NumLevels> Slabs{};
90 for (llvm::LazyAtomicPointer<Bucket> &SlabPtr : Slabs)
91 delete[] SlabPtr.load();
105 llvm::StringRef
save(
const char *S) {
return save(llvm::StringRef(S)); }
107 llvm::StringRef
save(
const std::string &S) {
108 return save(llvm::StringRef(S));
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);
119 llvm::StringRef
save(llvm::StringRef S) {
121 return llvm::StringRef();
126 LLVM_ATTRIBUTE_NOINLINE llvm::StringRef saveTwineSlow(
const llvm::Twine &S) {
127 llvm::SmallString<128> Storage;
129 return save(llvm::StringRef(Storage.data(), Storage.size()));
132 llvm::StringRef insert(llvm::StringRef S) {
133 assert(S.size() <= std::numeric_limits<uint32_t>::max() &&
134 "String exceeds 32-bit size limit");
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)];
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());
154 return S.copy(Allocator).data();
156 llvm::StringRef Entry(&First,
B.Size);
157 if (LLVM_LIKELY(
B.Hash == HashTag && Entry == S))
161 llvm_unreachable(
"ConcurrentStringPool capacity exhausted");
164 using ShardArray = std::array<Shard, NumShards>;
165 std::unique_ptr<ShardArray> Shards = std::make_unique<ShardArray>();
166 llvm::parallel::PerThreadBumpPtrAllocator Allocator;