ConcurrentHashtable.h Source File (original) (raw)

9#ifndef LLVM_ADT_CONCURRENTHASHTABLE_H

10#define LLVM_ADT_CONCURRENTHASHTABLE_H

16#include "llvm/Config/llvm-config.h"

22#include

23#include

24#include

25#include

26#include

28namespace llvm {

74template <typename KeyTy, typename KeyDataTy, typename AllocatorTy>

76public:

88 static inline const KeyTy &getKey(const KeyDataTy &KeyData) {

89 return KeyData.getKey();

90 }

96};

98template <typename KeyTy, typename KeyDataTy, typename AllocatorTy,

99 typename Info =

100 ConcurrentHashTableInfoByPtr<KeyTy, KeyDataTy, AllocatorTy>>

102public:

106 size_t InitialNumberOfBuckets = 128)

108 assert((ThreadsNum > 0) && "ThreadsNum must be greater than 0");

109 assert((InitialNumberOfBuckets > 0) &&

110 "InitialNumberOfBuckets must be greater than 0");

111

112

113 uint64_t EstimatedNumberOfBuckets = ThreadsNum;

114 if (ThreadsNum > 1) {

115 EstimatedNumberOfBuckets *= InitialNumberOfBuckets;

116 EstimatedNumberOfBuckets *= std::max(

117 1,

119 2);

120 }

121 EstimatedNumberOfBuckets = PowerOf2Ceil(EstimatedNumberOfBuckets);

123 std::min(EstimatedNumberOfBuckets, (uint64_t)(1Ull << 31));

124

125

127

131

132

136

139

143 }

144

145

147

150

151

152

153 MaxBucketSize = 1Ull << (std::min((size_t)31, LeadingZerosNumber));

154

155

157 }

158

166

167

168

169

170

171 std::pair<KeyDataTy *, bool> insert(const KeyTy &NewValue) {

172

173 uint64_t Hash = Info::getHashValue(NewValue);

176

177#if LLVM_ENABLE_THREADS

178

179 std::scoped_lockstd::mutex Lock(CurBucket.Guard);

180#endif

181

185

186 while (true) {

187 uint32_t CurEntryHashBits = BucketHashes[CurEntryIdx];

188

189 if (CurEntryHashBits == 0 && BucketEntries[CurEntryIdx] == nullptr) {

190

192 BucketEntries[CurEntryIdx] = NewData;

193 BucketHashes[CurEntryIdx] = ExtHashBits;

194

197 return {NewData, true};

198 }

199

200 if (CurEntryHashBits == ExtHashBits) {

201

202 KeyDataTy *EntryData = BucketEntries[CurEntryIdx];

203 if (Info::isEqual(Info::getKey(*EntryData), NewValue)) {

204

205 return {EntryData, false};

206 }

207 }

208

209 CurEntryIdx++;

210 CurEntryIdx &= (CurBucket.Size - 1);

211 }

212

214 return {};

215 }

216

217

219 OS << "\n--- HashTable statistic:\n";

222

223 uint64_t NumberOfNonEmptyBuckets = 0;

224 uint64_t NumberOfEntriesPlusEmpty = 0;

225 uint64_t OverallNumberOfEntries = 0;

227

229

230

233

234 BucketSizesMap[CurBucket.Size]++;

235

237 NumberOfNonEmptyBuckets++;

238 NumberOfEntriesPlusEmpty += CurBucket.Size;

240 OverallSize +=

242 }

243

244 OS << "\nOverall number of entries = " << OverallNumberOfEntries;

245 OS << "\nOverall number of non empty buckets = " << NumberOfNonEmptyBuckets;

246 for (auto [Size, Count] : BucketSizesMap)

247 OS << "\n Number of buckets with size " << Size << ": " << Count;

248

249 std::stringstream stream;

250 stream << std::fixed << std::setprecision(2)

251 << ((float)OverallNumberOfEntries / (float)NumberOfEntriesPlusEmpty);

252 std::string str = stream.str();

253

254 OS << "\nLoad factor = " << str;

255 OS << "\nOverall allocated size = " << OverallSize;

256 }

257

258protected:

261

264

265

268

269

271

272

274

275

277

278

280

281#if LLVM_ENABLE_THREADS

282

283 std::mutex Guard;

284#endif

285 };

286

287

289 assert((CurBucket.Size > 0) && "Uninitialised bucket");

291 return;

292

295

296 uint32_t NewBucketSize = CurBucket.Size << 1;

297 assert((NewBucketSize <= MaxBucketSize) && "New bucket size is too big");

298 assert((CurBucket.Size < NewBucketSize) &&

299 "New bucket size less than size of current bucket");

300

301

304

305

307 memset(DestHashes, 0, sizeof(ExtHashBitsTy) * NewBucketSize);

308

310 memset(DestEntries, 0, sizeof(EntryDataTy) * NewBucketSize);

311

312

313 for (uint32_t CurSrcEntryIdx = 0; CurSrcEntryIdx < CurBucket.Size;

314 CurSrcEntryIdx++) {

315 uint32_t CurSrcEntryHashBits = SrcHashes[CurSrcEntryIdx];

316

317

318 if (CurSrcEntryHashBits == 0 && SrcEntries[CurSrcEntryIdx] == nullptr)

319 continue;

320

322

323

324 while (true) {

325 uint32_t CurDestEntryHashBits = DestHashes[StartDestIdx];

326

327 if (CurDestEntryHashBits == 0 && DestEntries[StartDestIdx] == nullptr) {

328

329 DestHashes[StartDestIdx] = CurSrcEntryHashBits;

330 DestEntries[StartDestIdx] = SrcEntries[CurSrcEntryIdx];

331 break;

332 }

333

334 StartDestIdx++;

335 StartDestIdx = StartDestIdx & (NewBucketSize - 1);

336 }

337 }

338

339

340 CurBucket.Hashes = DestHashes;

341 CurBucket.Entries = DestEntries;

342 CurBucket.Size = NewBucketSize;

343

344

345 delete[] SrcHashes;

346 delete[] SrcEntries;

347 }

348

350

354

356 assert((BucketSize > 0) && "Empty bucket");

357

358 return ExtHashBits & (BucketSize - 1);

359 }

360

361

363

364

366

367

369

370

372

373

375

376

378

379

381

382

384};

385

386}

387

388#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file defines the BumpPtrAllocator interface.

Analysis containing CSE Info

This file defines the DenseMap class.

This file defines the SmallVector class.

std::pair< KeyDataTy *, bool > insert(const KeyTy &NewValue)

Insert new value NewValue or return already existing entry.

Definition ConcurrentHashtable.h:171

uint32_t getStartIdx(uint32_t ExtHashBits, uint32_t BucketSize)

Definition ConcurrentHashtable.h:355

virtual ~ConcurrentHashTableByPtr()

Definition ConcurrentHashtable.h:159

uint64_t HashBitsNum

Definition ConcurrentHashtable.h:362

std::unique_ptr< Bucket[]> BucketsArray

Definition ConcurrentHashtable.h:380

uint32_t MaxBucketSize

Definition ConcurrentHashtable.h:371

KeyDataTy * EntryDataTy

Definition ConcurrentHashtable.h:260

EntryDataTy * DataPtr

Definition ConcurrentHashtable.h:263

ExtHashBitsTy * HashesPtr

Definition ConcurrentHashtable.h:262

uint64_t ExtHashMask

Definition ConcurrentHashtable.h:368

uint32_t getBucketIdx(hash_code Hash)

Definition ConcurrentHashtable.h:349

uint64_t HashMask

Definition ConcurrentHashtable.h:365

uint32_t ExtHashBitsTy

Definition ConcurrentHashtable.h:259

uint32_t NumberOfBuckets

Definition ConcurrentHashtable.h:377

void printStatistic(raw_ostream &OS)

Print information about current state of hash table structures.

Definition ConcurrentHashtable.h:218

void RehashBucket(Bucket &CurBucket)

Definition ConcurrentHashtable.h:288

uint32_t InitialBucketSize

Definition ConcurrentHashtable.h:374

uint32_t getExtHashBits(uint64_t Hash)

Definition ConcurrentHashtable.h:351

ConcurrentHashTableByPtr(AllocatorTy &Allocator, uint64_t EstimatedSize=100000, size_t ThreadsNum=parallel::strategy.compute_thread_count(), size_t InitialNumberOfBuckets=128)

Definition ConcurrentHashtable.h:103

AllocatorTy & MultiThreadAllocator

Definition ConcurrentHashtable.h:383

ConcurrentHashTable - is a resizeable concurrent hashtable.

Definition ConcurrentHashtable.h:75

static KeyDataTy * create(const KeyTy &Key, AllocatorTy &Allocator)

Definition ConcurrentHashtable.h:93

static const KeyTy & getKey(const KeyDataTy &KeyData)

Definition ConcurrentHashtable.h:88

static bool isEqual(const KeyTy &LHS, const KeyTy &RHS)

Definition ConcurrentHashtable.h:83

static uint64_t getHashValue(const KeyTy &Key)

Definition ConcurrentHashtable.h:78

An opaque object representing a hash code.

This class implements an extremely fast bulk output stream that can only output to a stream.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

LLVM_ABI ThreadPoolStrategy strategy

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI uint64_t xxh3_64bits(ArrayRef< uint8_t > data)

uint64_t PowerOf2Ceil(uint64_t A)

Returns the power of two which is greater than or equal to the given value.

int countr_zero(T Val)

Count number of 0's from the least significant bit to the most stopping at the first 1.

int countl_zero(T Val)

Count number of 0's from the most significant bit to the least stopping at the first 1.

LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)

FunctionAddr VTableAddr Count

LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key

DataPtr Entries

Definition ConcurrentHashtable.h:279

HashesPtr Hashes

Definition ConcurrentHashtable.h:276

uint32_t Size

Definition ConcurrentHashtable.h:270

uint32_t NumberOfEntries

Definition ConcurrentHashtable.h:273