From d22524497a457c986a8e69824095527556936623 Mon Sep 17 00:00:00 2001 From: Nico Weber Date: Mon, 15 Jul 2019 18:56:56 +0000 Subject: [PATCH] Expand comment about how StringsToBuckets was computed, and add more entries The construction was explained in https://reviews.llvm.org/D44810?id=139526#inline-391999 but reading the code shouldn't require hunting down old reviews to understand it. The precomputed list was missing an entry for the empty list case, and one entry at the very end. (The current last entry is the last one where 3 * BucketCount fits in a signed int, but the reference implementation uses unsigneds as far as I can tell, so there's room for one more entry.) No behavior change for inputs seen in practice. Differential Revision: https://reviews.llvm.org/D64738 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@366107 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../PDB/Native/PDBStringTableBuilder.cpp | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-) diff --git a/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp b/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp index eabb9d44669..f7f36901e4d 100644 --- a/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp +++ b/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp @@ -60,7 +60,19 @@ static uint32_t computeBucketCount(uint32_t NumStrings) { // strings. Matching the reference algorithm exactly is not strictly // necessary for correctness, but it helps when comparing LLD's PDBs with // Microsoft's PDBs so as to eliminate superfluous differences. + // The reference implementation does (in nmt.h, NMT::grow()): + // unsigned StringCount = 0; + // unsigned BucketCount = 1; + // fn insert() { + // ++StringCount; + // if (BucketCount * 3 / 4 < StringCount) + // BucketCount = BucketCount * 3 / 2 + 1; + // } + // This list contains all StringCount, BucketCount pairs where BucketCount was + // just incremented. It ends before the first BucketCount entry where + // BucketCount * 3 would overflow a 32-bit unsigned int. static std::map StringsToBuckets = { + {0, 1}, {1, 2}, {2, 4}, {4, 7}, @@ -110,7 +122,8 @@ static uint32_t computeBucketCount(uint32_t NumStrings) { {229865455, 459730910}, {344798183, 689596366}, {517197275, 1034394550}, - {775795913, 1551591826}}; + {775795913, 1551591826}, + {1163693870, 2327387740}}; auto Entry = StringsToBuckets.lower_bound(NumStrings); assert(Entry != StringsToBuckets.end()); return Entry->second; -- 2.40.0