[ADT] Add TrieRawHashMap

[steven_wu]

Summary

Implement TrieRawHashMap which stores objects into a Trie based on the
hash of the object.

User needs to supply the hashing function and guarantees the uniqueness of
the hash for the objects to be inserted. Hash collision is not
supported

[steven_wu]

Update missing decl due to header cleanup in other files.

[dblaikie]

Not sure I'll be the most detailed reviewer here, if anyone else wants to chime in.

I've a generally understanding of what a trie is, but at my current level of detail looking at this code it's not entirely clear to me what this particular data structure is - maybe some more comments both in the source and in the patch description? simple example usage (in a test and/or in those comments/patch description) migth be helpful

llvm/include/llvm/ADT/HashMappedTrie.h

26

I think we can use static constexpr implicitly inline constants now, rather than enums?

35–37

Guess these could be constexpr variable templates rather than functions? But probably not a big deal either way.

64

157–161

This sort of feels a bit confusing - why are we hashing a hash?

llvm/unittests/ADT/HashMappedTrieTest.cpp

72–76

Seems unfortunate to do significant amounts of testing via the stringification of an object - any chance this could be done in a more API-centric way?

200

This is specifically to make it non-trivially destructible? should this record the execution of the dtor and check that the right number (or even instance) of destructions occur?

[dexonsmith]

[Resigning as reviewer, since I was the original author, but feel free ping me explicitly if I can be helpful for something and I'm not volunteering anything...]

In D133715#3980058, @dblaikie wrote:

Not sure I'll be the most detailed reviewer here, if anyone else wants to chime in.

I've a generally understanding of what a trie is, but at my current level of detail looking at this code it's not entirely clear to me what this particular data structure is - maybe some more comments both in the source and in the patch description? simple example usage (in a test and/or in those comments/patch description) migth be helpful

Yeah, probably more docs here would be good. Some notes that Steven might be able to use as a starting point (although feel free to ignore this an do your own thing!):

At a high-level, this is a set/map data structure that supports fast thread-safe insertion/lookup and does not support erase. (IIRC, the interface similar to a std::map, where the key is a hash?)

A hash-mapped trie is a tree of arrays where the prefix of the hash is consumed as an "index" into the array at each level of the tree. IIRC, this data structure as implemented:

• is lock-free and thread-safe
• supports "insert" and "lookup"
• does NOT detect a hash collision; first insertion wins; you want a strong-enough hash for your data set that there are no collisions, or handle collisions in the value_type somehow
• does NOT support "erase"; IIRC, that'd be hard to do in a thread-safe way, but I didn't think hard about it
• does NOT support "iteration"; IIRC, it'd be easy to implement iteration that exposed the internal layout
• array sizes are configurable (root array can be a different size from sub-trie arrays)
• each slot in an array is either empty, a sub-trie, or a value

Insertion (and lookup) works basically like the following (skipping over details that make the lock-free-thead-safety work):

1. start with the root trie's array
2. convert a prefix of the hash into an index into the current array
3. if the slot is a value with the same hash, return the existing value
4. if the slot is a value with a different hash, create a new sub-trie that contains the existing value, put the sub-trie in the slot, and continue with step (5)
5. if the slot is a sub-trie, descend and go back to step (2) with the unused suffix of the hash on the sub-trie's array
6. if the slot is empty, insert and return the new value

llvm/include/llvm/ADT/HashMappedTrie.h

157–161

This is creating a std::array<> out of an ArrayRef. std::array's constructors don't make this easy, so a wrapper function is helpful. Probably copyHash is a better name, or maybe there's a better way to do this!

llvm/unittests/ADT/HashMappedTrieTest.cpp

72–76

This is a good point. It was hard to test this way, and it's probably hard to maintain the tests.

The motivating thought was to avoid adding APIs that exposed the layout so that clients couldn't inspect/rely on it (i.e., there are no APIs for iterating through all values). But maybe that is unnecessarily restrictive.

IIRC, it would be fairly easy to change Trie::pointer to a recursive iterator, or to expose an iterator that wrapped it, or something. operator++ might be quite slow and/or be thread-unsafe, but maybe it's worth opening up just for the testing benefit.

(I'm happy either way; just chiming in in case I have more context about motivation for the currently-sparse API.)

[alexander-shaposhnikov]

llvm/include/llvm/ADT/HashMappedTrie.h

323

constexpr

[dblaikie]

In D133715#3980166, @dexonsmith wrote:

[Resigning as reviewer, since I was the original author, but feel free ping me explicitly if I can be helpful for something and I'm not volunteering anything...]

In D133715#3980058, @dblaikie wrote:

Not sure I'll be the most detailed reviewer here, if anyone else wants to chime in.

I've a generally understanding of what a trie is, but at my current level of detail looking at this code it's not entirely clear to me what this particular data structure is - maybe some more comments both in the source and in the patch description? simple example usage (in a test and/or in those comments/patch description) migth be helpful

Yeah, probably more docs here would be good. Some notes that Steven might be able to use as a starting point (although feel free to ignore this an do your own thing!):

At a high-level, this is a set/map data structure that supports fast thread-safe insertion/lookup and does not support erase. (IIRC, the interface similar to a std::map, where the key is a hash?)

A hash-mapped trie is a tree of arrays where the prefix of the hash is consumed as an "index" into the array at each level of the tree. IIRC, this data structure as implemented:

• is lock-free and thread-safe
• supports "insert" and "lookup"
• does NOT detect a hash collision; first insertion wins; you want a strong-enough hash for your data set that there are no collisions, or handle collisions in the value_type somehow
• does NOT support "erase"; IIRC, that'd be hard to do in a thread-safe way, but I didn't think hard about it
• does NOT support "iteration"; IIRC, it'd be easy to implement iteration that exposed the internal layout
• array sizes are configurable (root array can be a different size from sub-trie arrays)
• each slot in an array is either empty, a sub-trie, or a value

Insertion (and lookup) works basically like the following (skipping over details that make the lock-free-thead-safety work):

1. start with the root trie's array
2. convert a prefix of the hash into an index into the current array
3. if the slot is a value with the same hash, return the existing value
4. if the slot is a value with a different hash, create a new sub-trie that contains the existing value, put the sub-trie in the slot, and continue with step (5)
5. if the slot is a sub-trie, descend and go back to step (2) with the unused suffix of the hash on the sub-trie's array
6. if the slot is empty, insert and return the new value

Oh, this is all really useful info I didn't understand from the code - I'd assumed it was a user-visible trie (eg: something you could insert entries into, then walk the trie) - if the trie-ness is purely an implementation detail, maybe it shouldn't be tested/dumped? (like we don't test the layout of hash buckets in DenseMap tests) if it does need to be tested, maybe having a test friend in some way.

As for naming, given the functionality. I'd consider putting Trie earlier in the name rather than later, same as DenseMap - it's not a trie data structure, it's a Set data structure implemented using a trie. So TrieSet. Though adding all the features might be a bit of a mouthful - ThreadSafeHashedTrieSet?... Not sure what the right answer is here (two hard problems in computer science, amirite?).

Is it a set or a map?

Not sure how to capture all the other fairly esoteric requirements (no removal, needs perfect hashing, lock free/thread safe, - I guess that's most of/all the user-visible major requirements (as you say, non-iterable is just a minor artifact of the current implementation, not a major defining feature of the interface)). PerfectHashMap? (if we were going verbose, ThreadSafePerfectHashMap... )

[dexonsmith]

In D133715#3993178, @dblaikie wrote:

Is it a set or a map?

The interface is a map, just that the key type is restricted to look like a hash, and the client is expected to ensure the keys are well-distributed.

Not sure how to capture all the other fairly esoteric requirements (no removal, needs perfect hashing, lock free/thread safe, - I guess that's most of/all the user-visible major requirements (as you say, non-iterable is just a minor artifact of the current implementation, not a major defining feature of the interface)). PerfectHashMap? (if we were going verbose, ThreadSafePerfectHashMap... )

Both names make sense to me. "This is a map from a perfect hash to the data."

Issues I see with those names:

• I worry it's not obvious from either name *when* you'd want to use this. (The answer is, I think, you want this if you are building a set shared between multiple threads, you expect lots of concurrent lookup/insertion, and you want fast insertion/lookup nevertheless.)
• It might sound like the data structure does hashing. (It doesn't. The client is expected to provide the hash.)
• It steals the turf for more general map built on top of this. More later.

Regardless of the name, maybe the programmer's guide could use an explainer.

Note that there's an example data structure called ThreadSafeHashMappedTrieSet buried in the unit tests, which has an interface that hides the hash. Could be useful for some clients.

• Maybe it would make sense to lift up? Name could be PerfectHashSet
• You might want to build a map that also handles the hashing; name could potentially be PerfectHashMap

Maybe this could be PerfectHashSetImpl?

• Has the "guts" for implementing a client-friendly PerfectHashSet or PerfectHashMap?
• ... but can be used directly if you want to manage the hashing yourself?

llvm/unittests/ADT/HashMappedTrieTest.cpp

242–246

FYI, here, buried in the unit tests (demoted due to lack of immediate use cases), this is a set data structure built on top of the trie.

If this were lifted up again for actual use, as opposed to just a test, you'd want to template it on HasherT and then use HashBuilder (from llvm/include/llvm/Support/HashBuilder.h) to hash the value.

[dblaikie]

In D133715#3993270, @dexonsmith wrote:

In D133715#3993178, @dblaikie wrote:

Is it a set or a map?

The interface is a map, just that the key type is restricted to look like a hash, and the client is expected to ensure the keys are well-distributed.

Hmm, right.

Not sure how to capture all the other fairly esoteric requirements (no removal, needs perfect hashing, lock free/thread safe, - I guess that's most of/all the user-visible major requirements (as you say, non-iterable is just a minor artifact of the current implementation, not a major defining feature of the interface)). PerfectHashMap? (if we were going verbose, ThreadSafePerfectHashMap... )

Both names make sense to me. "This is a map from a perfect hash to the data."

Issues I see with those names:

• I worry it's not obvious from either name *when* you'd want to use this. (The answer is, I think, you want this if you are building a set shared between multiple threads, you expect lots of concurrent lookup/insertion, and you want fast insertion/lookup nevertheless.)

I think given the number of things we're trying to capture in the name, and the nuance here - not sure we can capture that in the name (even if that was the only thing we wanted to capture in the name I can't think of a punchy name - InsertOnlyFastConcurrentHashMap? :/)

• It might sound like the data structure does hashing. (It doesn't. The client is expected to provide the hash.)

Yeah, fair - I guess maybe that tends towards ConcurrentPerfectHashMap (open to Concurrent or ThreadSafe)

• It steals the turf for more general map built on top of this. More later.

Regardless of the name, maybe the programmer's guide could use an explainer.

Might be this is esoteric enough not to be worth Programmer's Manual space, but certainly some good doc comments - but either/both I'm OK with.

Note that there's an example data structure called ThreadSafeHashMappedTrieSet buried in the unit tests, which has an interface that hides the hash. Could be useful for some clients.

• Maybe it would make sense to lift up? Name could be PerfectHashSet
• You might want to build a map that also handles the hashing; name could potentially be PerfectHashMap

Maybe this could be PerfectHashSetImpl?

• Has the "guts" for implementing a client-friendly PerfectHashSet or PerfectHashMap?
• ... but can be used directly if you want to manage the hashing yourself?

I take it the current use cases you have in mind/lined up in the CAS use this directly? Maybe a Raw prefix? RawPerfectHashSet, RawConcurrentHashSet, etc... some combination/choice of those sort of things?

llvm/unittests/ADT/HashMappedTrieTest.cpp

242–246

Hmm, yeah, this looks like overkill for the test - given the data structure as-is, we don't need any hash algorithm here - the test, I would expect, would use unique array values/"hash" values hardcoded/directly.

If you've got a use for this data structure, it could come along in a subsequent patch?

[dexonsmith]

In D133715#3993311, @dblaikie wrote:

Note that there's an example data structure called ThreadSafeHashMappedTrieSet buried in the unit tests, which has an interface that hides the hash. Could be useful for some clients.

• Maybe it would make sense to lift up? Name could be PerfectHashSet
• You might want to build a map that also handles the hashing; name could potentially be PerfectHashMap

Maybe this could be PerfectHashSetImpl?

• Has the "guts" for implementing a client-friendly PerfectHashSet or PerfectHashMap?
• ... but can be used directly if you want to manage the hashing yourself?

I take it the current use cases you have in mind/lined up in the CAS use this directly? Maybe a Raw prefix? RawPerfectHashSet, RawConcurrentHashSet, etc... some combination/choice of those sort of things?

@steven_wu can confirm, but that's what I remember. (There was an early branch that used the hash-included-client-friendly set, but the use case for it was refactored IIRC.)

To summarize, seems like the patch needs:

• a new name (RawConcurrentHashSet SGTM);
• some header docs explaining how to use it / design motivation;
• a test support friend class that can inspect/test the trie layout without relying on stringification;
• unit tests rewritten to use the friend (and probably dropping the example higher-level data structure).

[dblaikie]

In D133715#3993416, @dexonsmith wrote:

In D133715#3993311, @dblaikie wrote:

Note that there's an example data structure called ThreadSafeHashMappedTrieSet buried in the unit tests, which has an interface that hides the hash. Could be useful for some clients.

• Maybe it would make sense to lift up? Name could be PerfectHashSet
• You might want to build a map that also handles the hashing; name could potentially be PerfectHashMap

Maybe this could be PerfectHashSetImpl?

• Has the "guts" for implementing a client-friendly PerfectHashSet or PerfectHashMap?
• ... but can be used directly if you want to manage the hashing yourself?

I take it the current use cases you have in mind/lined up in the CAS use this directly? Maybe a Raw prefix? RawPerfectHashSet, RawConcurrentHashSet, etc... some combination/choice of those sort of things?

@steven_wu can confirm, but that's what I remember. (There was an early branch that used the hash-included-client-friendly set, but the use case for it was refactored IIRC.)

To summarize, seems like the patch needs:

• a new name (RawConcurrentHashSet SGTM);

+1

• some header docs explaining how to use it / design motivation;

+1

• a test support friend class that can inspect/test the trie layout without relying on stringification;

This bit I'm not so sure about - we don't test the bucketing behavior of DenseHashMap so far as I know (or other similar implementation details of the various other hashing data structures - (since they're the ones with fairly complicated implementation details, they seem the best comparison)), for instance, we only test its interface - why would we do differently for this data structure?

• unit tests rewritten to use the friend (and probably dropping the example higher-level data structure).

+1

[dexonsmith]

In D133715#3993489, @dblaikie wrote:

• a test support friend class that can inspect/test the trie layout without relying on stringification;

This bit I'm not so sure about - we don't test the bucketing behavior of DenseHashMap so far as I know (or other similar implementation details of the various other hashing data structures - (since they're the ones with fairly complicated implementation details, they seem the best comparison)), for instance, we only test its interface - why would we do differently for this data structure?

IMO the layout is more complex than a flat array with quadratic probing. The logic for equal and/or nearly-equal hashes is a bit subtle, and there were hard-to-reason about bugs originally. The layout-stringification was necessary to understand what was going wrong, and the tests that use it help ensure future refactorings don't get it wrong.

I don't remember the bugs, but two examples of subtleties:

• On an exact match you don't want to "sink" the existing entry down a level to a new sub-trie (you need to detect "exact match" before sinking). Getting this wrong will affect performance but not otherwise be user-visible.
• The deepest sub-trie might be a different/smaller size than the others because there are only a few bits left-over, and the handling needs to be right. It's simpler to check for correct layout directly than to guess about what user-visible effects there might be for errors.

I'd be a bit uneasy with the layout tests being dropped altogether.

Maybe an alternative to testing the layout directly would be to add a verification member function that iterated through the data structure and ensured everything was self-consistent (else crash? else return false?). Then the tests could call the member function after a series of insertions that might trigger a "bad" layout.

[dblaikie]

In D133715#3993521, @dexonsmith wrote:

In D133715#3993489, @dblaikie wrote:

• a test support friend class that can inspect/test the trie layout without relying on stringification;

This bit I'm not so sure about - we don't test the bucketing behavior of DenseHashMap so far as I know (or other similar implementation details of the various other hashing data structures - (since they're the ones with fairly complicated implementation details, they seem the best comparison)), for instance, we only test its interface - why would we do differently for this data structure?

IMO the layout is more complex than a flat array with quadratic probing. The logic for equal and/or nearly-equal hashes is a bit subtle, and there were hard-to-reason about bugs originally. The layout-stringification was necessary to understand what was going wrong, and the tests that use it help ensure future refactorings don't get it wrong.

I don't remember the bugs, but two examples of subtleties:

• On an exact match you don't want to "sink" the existing entry down a level to a new sub-trie (you need to detect "exact match" before sinking). Getting this wrong will affect performance but not otherwise be user-visible.
• The deepest sub-trie might be a different/smaller size than the others because there are only a few bits left-over, and the handling needs to be right. It's simpler to check for correct layout directly than to guess about what user-visible effects there might be for errors.

I'd be a bit uneasy with the layout tests being dropped altogether.

Maybe an alternative to testing the layout directly would be to add a verification member function that iterated through the data structure and ensured everything was self-consistent (else crash? else return false?). Then the tests could call the member function after a series of insertions that might trigger a "bad" layout.

Fair enough - if it's sufficient to have a verify operation (maybe "assertValid" - so, yeah, crash when not valid) I'd go with that, but given the argument you've made, if you think verifying the specific structure is significantly more valuable than that, I'd be OK with some private/test-friended introspection API.

[dexonsmith]

In D133715#3995750, @dblaikie wrote:

In D133715#3993521, @dexonsmith wrote:

In D133715#3993489, @dblaikie wrote:

• a test support friend class that can inspect/test the trie layout without relying on stringification;

This bit I'm not so sure about - we don't test the bucketing behavior of DenseHashMap so far as I know (or other similar implementation details of the various other hashing data structures - (since they're the ones with fairly complicated implementation details, they seem the best comparison)), for instance, we only test its interface - why would we do differently for this data structure?

IMO the layout is more complex than a flat array with quadratic probing. The logic for equal and/or nearly-equal hashes is a bit subtle, and there were hard-to-reason about bugs originally. The layout-stringification was necessary to understand what was going wrong, and the tests that use it help ensure future refactorings don't get it wrong.

I don't remember the bugs, but two examples of subtleties:

• On an exact match you don't want to "sink" the existing entry down a level to a new sub-trie (you need to detect "exact match" before sinking). Getting this wrong will affect performance but not otherwise be user-visible.
• The deepest sub-trie might be a different/smaller size than the others because there are only a few bits left-over, and the handling needs to be right. It's simpler to check for correct layout directly than to guess about what user-visible effects there might be for errors.

I'd be a bit uneasy with the layout tests being dropped altogether.

Maybe an alternative to testing the layout directly would be to add a verification member function that iterated through the data structure and ensured everything was self-consistent (else crash? else return false?). Then the tests could call the member function after a series of insertions that might trigger a "bad" layout.

Fair enough - if it's sufficient to have a verify operation (maybe "assertValid" - so, yeah, crash when not valid) I'd go with that, but given the argument you've made, if you think verifying the specific structure is significantly more valuable than that, I'd be OK with some private/test-friended introspection API.

IMO it's worth it; @steven_wu, if you disagree, I could live with assertValid(). (BTW, I remembered another justification. The test case inputs/setups are a bit subtle; checking the layout ensures you've covered the corner case you think you've covered.)

[steven_wu]

In D133715#3995988, @dexonsmith wrote:

In D133715#3995750, @dblaikie wrote:

In D133715#3993521, @dexonsmith wrote:

In D133715#3993489, @dblaikie wrote:

• a test support friend class that can inspect/test the trie layout without relying on stringification;

This bit I'm not so sure about - we don't test the bucketing behavior of DenseHashMap so far as I know (or other similar implementation details of the various other hashing data structures - (since they're the ones with fairly complicated implementation details, they seem the best comparison)), for instance, we only test its interface - why would we do differently for this data structure?

IMO the layout is more complex than a flat array with quadratic probing. The logic for equal and/or nearly-equal hashes is a bit subtle, and there were hard-to-reason about bugs originally. The layout-stringification was necessary to understand what was going wrong, and the tests that use it help ensure future refactorings don't get it wrong.

I don't remember the bugs, but two examples of subtleties:

• On an exact match you don't want to "sink" the existing entry down a level to a new sub-trie (you need to detect "exact match" before sinking). Getting this wrong will affect performance but not otherwise be user-visible.
• The deepest sub-trie might be a different/smaller size than the others because there are only a few bits left-over, and the handling needs to be right. It's simpler to check for correct layout directly than to guess about what user-visible effects there might be for errors.

I'd be a bit uneasy with the layout tests being dropped altogether.

Maybe an alternative to testing the layout directly would be to add a verification member function that iterated through the data structure and ensured everything was self-consistent (else crash? else return false?). Then the tests could call the member function after a series of insertions that might trigger a "bad" layout.

Fair enough - if it's sufficient to have a verify operation (maybe "assertValid" - so, yeah, crash when not valid) I'd go with that, but given the argument you've made, if you think verifying the specific structure is significantly more valuable than that, I'd be OK with some private/test-friended introspection API.

IMO it's worth it; @steven_wu, if you disagree, I could live with assertValid(). (BTW, I remembered another justification. The test case inputs/setups are a bit subtle; checking the layout ensures you've covered the corner case you think you've covered.)

I prefer to keep those tests as it still provides value and also insights into underlying implementation. If someone got around to do a new and better implementation, we can drop them by then.

[dblaikie]

(avodiing quoting a lot)

I think the stringification's especially/sort of an unfortunate way to test this - that stringified version probably isn't how a user would want to dump the data structure (they'd want to see a user-centric view of the data structure, not the implementation details). Is it practical to at least move to friending the test from the data structure and have the test poke around in the internals to inspect the structure & assert/expect/check various things about it?

[dblaikie]

eh, maybe string's easier to read in expect diagnostics anyway... just seems a bit awkward/circuitous/unfortunate :/ (I guess the stringification could move into the test code, implemented via such a friend relationship)

[dexonsmith]

In D133715#3996103, @dblaikie wrote:

eh, maybe string's easier to read in expect diagnostics anyway... just seems a bit awkward/circuitous/unfortunate :/ (I guess the stringification could move into the test code, implemented via such a friend relationship)

I do remember the string being easy to read in expect diagnostics, FWIW.

What about renaming the methods to printLayout() and dumpLayout()? Then print() and dump() would at least still be available for something user-centric.

[dblaikie]

In D133715#3996194, @dexonsmith wrote:

In D133715#3996103, @dblaikie wrote:

eh, maybe string's easier to read in expect diagnostics anyway... just seems a bit awkward/circuitous/unfortunate :/ (I guess the stringification could move into the test code, implemented via such a friend relationship)

I do remember the string being easy to read in expect diagnostics, FWIW.

What about renaming the methods to printLayout() and dumpLayout()? Then print() and dump() would at least still be available for something user-centric.

Workable, though I'd still rather it be moved to the test file if it's not too inconvenient (with some friendship, probably). Avoid muddying the implementation with test-only features.

[tschuett]

llvm/lib/Support/HashMappedTrieIndexGenerator.h

14

Please use std::optional.

[steven_wu]

In D133715#3996263, @dblaikie wrote:

In D133715#3996194, @dexonsmith wrote:

In D133715#3996103, @dblaikie wrote:

eh, maybe string's easier to read in expect diagnostics anyway... just seems a bit awkward/circuitous/unfortunate :/ (I guess the stringification could move into the test code, implemented via such a friend relationship)

I do remember the string being easy to read in expect diagnostics, FWIW.

What about renaming the methods to printLayout() and dumpLayout()? Then print() and dump() would at least still be available for something user-centric.

Workable, though I'd still rather it be moved to the test file if it's not too inconvenient (with some friendship, probably). Avoid muddying the implementation with test-only features.

I find stringfication quite useful for debugging or inspecting the state of the CAS. Our branch (to be upstream later) has the OnDiskCAS, and we have a tool that can dump the CAS state (mostly the Trie information) in string format when pointed to the on disk CAS. My point is that even it is a testing/debugging tool, it is not limited to unit test only. I am ok with either names.

But I think we can expose some private methods for debugging to avoid string comparison in unit test and hopefully that is more readable.

llvm/unittests/ADT/HashMappedTrieTest.cpp

242–246

Agree. I don't think the actual data structure is useful outside the context of this unit test. I will simply it.

[steven_wu]

Address review feedback and rebase the patch using std::optional

Still thinking how to unittest without string compare. The only way I can think is to implement iteration on HashMappedTrie so we can have API to check the state of SubTrie. That will expose more types to user, which will make API more complicated.

Also for discussion of names, do we have other candidates to replace "HashMappedTrie" that is better and clearer?

[steven_wu]

llvm/unittests/ADT/HashMappedTrieTest.cpp

200

The test is for making sure no recursion happening when destroying a large Trie with objects inside (with or without destructor). The order doesn't matter. I added comment to clarify.

[steven_wu]

Add some documentation about HashMappedTrie

[steven_wu]

Update tests to avoid string comparsion.

It is not easy to add an iterator that can triversal Trie in a certain order but most test cases, we only care about the root node and the last sub-trie allocated. Those can be cheaply located just from the allocation chain, even it is not currently possible to construct the hash prefix if just walking the allocation chain.

[steven_wu]

Fix typo in the comments

[steven_wu]

Allow checking prefix of the sub-trie

[steven_wu]

Ping. All feedbacks are addressed.

Additional notes: I dig a bit deeper into the benchmark from https://reviews.llvm.org/D132548 as it shows bad scaling during parallel insertion tests (stop scaling to 8 threads). That is actually caused by our ThreadSafeBumpPtrAllocator that currently takes a lock. We can improve it in future since our use case doesn't expect heavy parallel insertions. However, it is quite obvious we should tune to RootBits and SubTrieBits. Increasing RootBits can significantly decrease the contention. A better strategy might be something like starting with something like 10 bits, then 4 bits, 2 bits and 1 bit. Shrinking number of bits can lead to better memory usage since the slots usage in the deep nodes are very low.

[dblaikie]

In D133715#4023734, @steven_wu wrote:

In D133715#3996263, @dblaikie wrote:

In D133715#3996194, @dexonsmith wrote:

In D133715#3996103, @dblaikie wrote:

eh, maybe string's easier to read in expect diagnostics anyway... just seems a bit awkward/circuitous/unfortunate :/ (I guess the stringification could move into the test code, implemented via such a friend relationship)

I do remember the string being easy to read in expect diagnostics, FWIW.

What about renaming the methods to printLayout() and dumpLayout()? Then print() and dump() would at least still be available for something user-centric.

Workable, though I'd still rather it be moved to the test file if it's not too inconvenient (with some friendship, probably). Avoid muddying the implementation with test-only features.

I find stringfication quite useful for debugging or inspecting the state of the CAS. Our branch (to be upstream later) has the OnDiskCAS, and we have a tool that can dump the CAS state (mostly the Trie information) in string format when pointed to the on disk CAS. My point is that even it is a testing/debugging tool, it is not limited to unit test only. I am ok with either names.

The ability to dump the data structure I'm all for - like DenseMap, etc, but I think that dumping should be the user-visible state (it's a map, the trie part is an implementation detail that ideally shouldn't be exposed in the dump developers use regularly - presumably it's not necessary except when debugging the data structure itself, which should be rare (we don't usually need to look at DenseMap's internal bucketing, for instance)).

But I think we can expose some private methods for debugging to avoid string comparison in unit test and hopefully that is more readable.

In D133715#4023992, @steven_wu wrote:

Address review feedback and rebase the patch using std::optional

Still thinking how to unittest without string compare. The only way I can think is to implement iteration on HashMappedTrie so we can have API to check the state of SubTrie. That will expose more types to user, which will make API more complicated.

Can the unit test be a friend to the data structure and use the data structure's internal APIs?

Also for discussion of names, do we have other candidates to replace "HashMappedTrie" that is better and clearer?

I'd really like to avoid "trie" in the name, though I guess it's as much an implementation detail as "Dense" is in DenseMap, so might be deserving to be in the name.

I think this is a map, so the name should probably end in 'map' not in 'trie'. I'd guess TrieHashMap - it's a type of hash map that uses a trie? Maybe make a shortlist of names to consider, etc?

[dexonsmith]

In D133715#4029442, @steven_wu wrote:

Ping. All feedbacks are addressed.

Additional notes: I dig a bit deeper into the benchmark from https://reviews.llvm.org/D132548 as it shows bad scaling during parallel insertion tests (stop scaling to 8 threads). That is actually caused by our ThreadSafeBumpPtrAllocator that currently takes a lock. We can improve it in future since our use case doesn't expect heavy parallel insertions. However, it is quite obvious we should tune to RootBits and SubTrieBits. Increasing RootBits can significantly decrease the contention. A better strategy might be something like starting with something like 10 bits, then 4 bits, 2 bits and 1 bit. Shrinking number of bits can lead to better memory usage since the slots usage in the deep nodes are very low.

Could ThreadSafeBumpPtrAllocator could be made lock-free? I think at least it would be possible to implement one that only locked when a new allocation is needed, instead of every time the ptr is bumped as now. (I’ll think about it a bit.)

Note that in the CAS use case it’s ideally true that most insertions are duplicates and don’t need to call the allocator at all. This is why we’ve been able to get away with a lock on each allocation.

[steven_wu]

The ability to dump the data structure I'm all for - like DenseMap, etc, but I think that dumping should be the user-visible state (it's a map, the trie part is an implementation detail that ideally shouldn't be exposed in the dump developers use regularly - presumably it's not necessary except when debugging the data structure itself, which should be rare (we don't usually need to look at DenseMap's internal bucketing, for instance)).

Correct. The current dump method is not designed to dump user-visible state. The goal is to dump how hash/key is stored in trie, and it doesn't even dump any user stored value. To dump user visible state from DenseMap, it needs to support iteration first but HashMappedTrie currently doesn't support iteration (and the CAS/ObjectStore it implements cannot have iteration for security reason). The only useful dump method can be implemented without iteration is what it has now. I am ok to remove dump method from this patch since I already rewrite the tests without using dump. The string dump for the trie structure can be useful to debug full CAS in the future. Since CAS cannot have iteration, a separate tool that can dump the entire trie structure can be helpful to look inside CAS. In that case, dump is a public API that needs to be used by this CAS inspection tool, not a private method that expose to test only.

Can the unit test be a friend to the data structure and use the data structure's internal APIs?

It is already the case now. I find a way to write unit-test with no string comparison and extract data from the trie without supporting real iteration. Supporting full iteration is not trivial since it will either involve a very complicated iterator or adding back edge in the trie or both. Currently, it has a very non-trivial way to iterate the subtrie in an order that is not really interesting to users, and the way it finds the hash prefix is quite expensive too. Thus, this is only useful for unit-tests and they are using private APIs that are friends to test only. A real iteration needs to do a tree walk from the root and store information it acquires along the way (like dump method).

I'd really like to avoid "trie" in the name, though I guess it's as much an implementation detail as "Dense" is in DenseMap, so might be deserving to be in the name.

I think this is a map, so the name should probably end in 'map' not in 'trie'. I'd guess TrieHashMap - it's a type of hash map that uses a trie? Maybe make a shortlist of names to consider, etc?

I don't have candidates. TrieHashMap sounds good to me.

[steven_wu]

In D133715#4029841, @dexonsmith wrote:

In D133715#4029442, @steven_wu wrote:

Ping. All feedbacks are addressed.

Additional notes: I dig a bit deeper into the benchmark from https://reviews.llvm.org/D132548 as it shows bad scaling during parallel insertion tests (stop scaling to 8 threads). That is actually caused by our ThreadSafeBumpPtrAllocator that currently takes a lock. We can improve it in future since our use case doesn't expect heavy parallel insertions. However, it is quite obvious we should tune to RootBits and SubTrieBits. Increasing RootBits can significantly decrease the contention. A better strategy might be something like starting with something like 10 bits, then 4 bits, 2 bits and 1 bit. Shrinking number of bits can lead to better memory usage since the slots usage in the deep nodes are very low.

Could ThreadSafeBumpPtrAllocator could be made lock-free? I think at least it would be possible to implement one that only locked when a new allocation is needed, instead of every time the ptr is bumped as now. (I’ll think about it a bit.)

Note that in the CAS use case it’s ideally true that most insertions are duplicates and don’t need to call the allocator at all. This is why we’ve been able to get away with a lock on each allocation.

Yes, the FIXME for a ThreadSafeBumpPtrAllocator is still there. Currently, I don't think it is urgent to fix. It is not expected to have someone to use Trie as a high performance thread safe set/map.

[dexonsmith]

In D133715#4029879, @steven_wu wrote:

In D133715#4029841, @dexonsmith wrote:

In D133715#4029442, @steven_wu wrote:

Ping. All feedbacks are addressed.

Additional notes: I dig a bit deeper into the benchmark from https://reviews.llvm.org/D132548 as it shows bad scaling during parallel insertion tests (stop scaling to 8 threads). That is actually caused by our ThreadSafeBumpPtrAllocator that currently takes a lock. We can improve it in future since our use case doesn't expect heavy parallel insertions. However, it is quite obvious we should tune to RootBits and SubTrieBits. Increasing RootBits can significantly decrease the contention. A better strategy might be something like starting with something like 10 bits, then 4 bits, 2 bits and 1 bit. Shrinking number of bits can lead to better memory usage since the slots usage in the deep nodes are very low.

Could ThreadSafeBumpPtrAllocator could be made lock-free? I think at least it would be possible to implement one that only locked when a new allocation is needed, instead of every time the ptr is bumped as now. (I’ll think about it a bit.)

Note that in the CAS use case it’s ideally true that most insertions are duplicates and don’t need to call the allocator at all. This is why we’ve been able to get away with a lock on each allocation.

Here's a sketch that I think mostly works?

// Block for bump allocations.
struct BumpBlock {
  std::atomic<char *> Ptr;
  std::atomic<BumpBlock *> Next;
  char Bytes[4084];
  BumpBlock() : Ptr{Bytes}, Next{nullptr} {}

  // Compute new "Next", try to bump if there's space, else return nullptr.
  void *tryAllocate(size_t N, size_t Align = 1);
};

// Tail-allocated data for "big" allocations.
struct BumpSeparate {
  std::atomic<BumpSeparate *> Next;
  // tail-allocated data of appropriate and alignment, using malloc....
};

// Allocator.
struct BumpAllocator {
  std::atomic<BumpBlock *> CurrentBlock;
  std::atomic<BumpSeparate *> LastAllocSeparately;

  // Delete everything since there's no ownership here...
  ~BumpAllocator();

  void *allocate(size_t N, size_t Align = 1) {
    if (N > 2048)
      return allocateSeparately(N, Align);

    BumpBlock *B = CurrentBlock;
    std::unique_ptr<BumpBlock> New;
    void *NewAlloc = nullptr;
    while (true) {
      if (LLVM_LIKELY(B))
        if (void *Alloc = B->tryAllocate(N, Align))
          return Alloc;

      if (!New) {
        New = new BumpBlock;
        NewAlloc = New->tryAllocate(N, Align);
        assert(NewAlloc && "Empty block doesn't have space!");
      }
      if (!CurrentBlock.compare_exchange_weak(B, New.get()))
        continue;

      // New was saved in CurrentBlock. Fix its "Next" pointer and release it
      // so it's not deallocated.
      New->Next = B;
      New.release();
      return NewAlloc;
    }
  }

private:
  // Maintain a list of "big" allocations, similar to above.
  void *allocateSeparately(size_t N, size_t Align);
};

Not saying it needs to block this review...

But having a fast concurrent BumpPtrAllocator would be independently useful, and I'd suggest optimizing the allocator before bloating the default trie size.

Yes, the FIXME for a ThreadSafeBumpPtrAllocator is still there. Currently, I don't think it is urgent to fix. It is not expected to have someone to use Trie as a high performance thread safe set/map.

The immediate use case is as a high performance thread-safe data store. In the CAS use case we're expecting a lot of duplicate insertions which don't happen to hit the allocator, but I'm not sure that's really been checked/measured.

[dblaikie]

In D133715#4029870, @steven_wu wrote:

The ability to dump the data structure I'm all for - like DenseMap, etc, but I think that dumping should be the user-visible state (it's a map, the trie part is an implementation detail that ideally shouldn't be exposed in the dump developers use regularly - presumably it's not necessary except when debugging the data structure itself, which should be rare (we don't usually need to look at DenseMap's internal bucketing, for instance)).

Correct. The current dump method is not designed to dump user-visible state. The goal is to dump how hash/key is stored in trie, and it doesn't even dump any user stored value. To dump user visible state from DenseMap, it needs to support iteration first but HashMappedTrie currently doesn't support iteration (and the CAS/ObjectStore it implements cannot have iteration for security reason).

Not sure I follow why it'd need to support iteration to support dumping of user-centric state. Supporting iteration (using an iterator abstraction) is a fair bit more complicated than walking the data structure directly to dump out its contents, I'd think.

The only useful dump method can be implemented without iteration is what it has now. I am ok to remove dump method from this patch since I already rewrite the tests without using dump. The string dump for the trie structure can be useful to debug full CAS in the future. Since CAS cannot have iteration, a separate tool that can dump the entire trie structure can be helpful to look inside CAS. In that case, dump is a public API that needs to be used by this CAS inspection tool, not a private method that expose to test only.

Yeah, I'm generally OK with a public dump method that gives a user-centric result, like DenseMap's dump... oh, my mistake, DenseMap doesn't have a dump method. I guess we rely on debugger pretty printers for that (& as the person who wrote the gdb one at least, it's not great - because it's hard to walk the user-visible state correctly/skipping internal implementation details - so it does end up printing the buckets, etc).

But, sure, doesn't need to be in this patch - I guess if we don't have it for other data structures, seems fair/reasonable/OK that we don't have it for this one.

Can the unit test be a friend to the data structure and use the data structure's internal APIs?

It is already the case now. I find a way to write unit-test with no string comparison and extract data from the trie without supporting real iteration. Supporting full iteration is not trivial since it will either involve a very complicated iterator or adding back edge in the trie or both. Currently, it has a very non-trivial way to iterate the subtrie in an order that is not really interesting to users, and the way it finds the hash prefix is quite expensive too. Thus, this is only useful for unit-tests and they are using private APIs that are friends to test only. A real iteration needs to do a tree walk from the root and store information it acquires along the way (like dump method).

Ah, OK, great.

I'd really like to avoid "trie" in the name, though I guess it's as much an implementation detail as "Dense" is in DenseMap, so might be deserving to be in the name.

I think this is a map, so the name should probably end in 'map' not in 'trie'. I'd guess TrieHashMap - it's a type of hash map that uses a trie? Maybe make a shortlist of names to consider, etc?

I don't have candidates. TrieHashMap sounds good to me.

Sounds good to me, then.

llvm/unittests/ADT/HashMappedTrieTest.cpp

19

Rather than having to indirect everything through this class helper - I think it's possible to name the class of the test fixture itself, and then you could friend that, so the test fixture would have direct access? Might be simpler that way.

[avl]

But having a fast concurrent BumpPtrAllocator would be independently useful, and I'd suggest optimizing the allocator before bloating the default trie size.

+1 for fast concurrent ThreadSafeBumpPtrAllocator.

What do you think about following alternative implementation?

class ThreadSafeBumpPtrAllocator {
  ThreadSafeBumpPtrAllocator() {
    size_t ThreadsNum = ThreadPoolStrategy.compute_thread_count();
    allocators.resize(ThreadsNum);
  }
  
  void* Allocate (size_t Num) {
      size_t AllocatorIdx = getThreadIdx();
      
      return allocators[AllocatorIdx].Allocate(Num);
  }

  std::vector<BumpPtrAllocator> allocators;
};

static thread_local ThreadIdx;

size_t getThreadIdx() {
  return ThreadIdx;
}

This implementation uses the fact that ThreadPoolExecutor creates a fixed number
of threads(ThreadPoolStrategy.compute_thread_count()) and keeps them until destructed
. ThreadPoolExecutor can initialise thread local field ThreadIdx to the proper thread index.
The getThreadIdx() could return index of thread inside ThreadPoolExecutor.Threads.
ThreadSafeBumpPtrAllocator keeps separate allocator for each thread. In this case each thread would
always use separate allocator. No neccessary to have locks, cas operations, no races...

[avl]

@steven_wu To have some interface compatibility and to make it possible to use HashMappedTrie for use case from D96035 probably,
Could it be possible to add boolean value to the result indicating whether data has just inserted?

std::pair<pointer, bool> insert(const_pointer Hint, value_type &&HashedData)

The use case for this:

std::pair<pointer, bool> Result = HashMappedTrie.insert(Data);
if (Result.second) {
  // initialize Result.first data
  Result.first->field = data;
}

[steven_wu]

In D133715#4031396, @avl wrote:

But having a fast concurrent BumpPtrAllocator would be independently useful, and I'd suggest optimizing the allocator before bloating the default trie size.

+1 for fast concurrent ThreadSafeBumpPtrAllocator.

What do you think about following alternative implementation?

class ThreadSafeBumpPtrAllocator {
  ThreadSafeBumpPtrAllocator() {
    size_t ThreadsNum = ThreadPoolStrategy.compute_thread_count();
    allocators.resize(ThreadsNum);
  }
  
  void* Allocate (size_t Num) {
      size_t AllocatorIdx = getThreadIdx();
      
      return allocators[AllocatorIdx].Allocate(Num);
  }

  std::vector<BumpPtrAllocator> allocators;
};

static thread_local ThreadIdx;

size_t getThreadIdx() {
  return ThreadIdx;
}

This implementation uses the fact that ThreadPoolExecutor creates a fixed number
of threads(ThreadPoolStrategy.compute_thread_count()) and keeps them until destructed
. ThreadPoolExecutor can initialise thread local field ThreadIdx to the proper thread index.
The getThreadIdx() could return index of thread inside ThreadPoolExecutor.Threads.
ThreadSafeBumpPtrAllocator keeps separate allocator for each thread. In this case each thread would
always use separate allocator. No neccessary to have locks, cas operations, no races...

Let's move the discussion of ThreadSafeAllocator to https://reviews.llvm.org/D133713 since this patch just uses it and the implementation is over there.

The background of this data structure is to use by a CAS, so it is ideal that the CAS doesn't need to lock to the amount of threads that is going to be spawned or rely on the thread id.
You can have a thread local allocator that allocates the value to be stored, you just need to do the allocation in insertLazy with your own allocator and manage its life time.

[dexonsmith]

In D133715#4031396, @avl wrote:

But having a fast concurrent BumpPtrAllocator would be independently useful, and I'd suggest optimizing the allocator before bloating the default trie size.

+1 for fast concurrent ThreadSafeBumpPtrAllocator.

What do you think about following alternative implementation?

class ThreadSafeBumpPtrAllocator {
  ThreadSafeBumpPtrAllocator() {
    size_t ThreadsNum = ThreadPoolStrategy.compute_thread_count();
    allocators.resize(ThreadsNum);
  }
  
  void* Allocate (size_t Num) {
      size_t AllocatorIdx = getThreadIdx();
      
      return allocators[AllocatorIdx].Allocate(Num);
  }

  std::vector<BumpPtrAllocator> allocators;
};

static thread_local ThreadIdx;

size_t getThreadIdx() {
  return ThreadIdx;
}

This implementation uses the fact that ThreadPoolExecutor creates a fixed number
of threads(ThreadPoolStrategy.compute_thread_count()) and keeps them until destructed
. ThreadPoolExecutor can initialise thread local field ThreadIdx to the proper thread index.
The getThreadIdx() could return index of thread inside ThreadPoolExecutor.Threads.
ThreadSafeBumpPtrAllocator keeps separate allocator for each thread. In this case each thread would
always use separate allocator. No neccessary to have locks, cas operations, no races...

+1; seems worth experimenting with (downside is you have at least as many allocations as active threads, but maybe that’s fine); IIRC C++11 thread-local initialization is slow on Darwin so we might want __thread here, or maybe the static makes it fast; +1 to Steven’s comment this should move to the other review (also IMO this could be an incremental improvement that lands later).

[steven_wu]

@dexonsmith @benlangmuir @akyrtzi
Does TrieHashMap sound good to you?

Locally, I updated to use std::pair as return value to make it more map like, and remove the dump method. I will update the patch once we have the name we agreed on.

[dblaikie]

I guess one concern with TrieHashMap is that if this is the lower level implementation, and someone might implement a more map-like API on top of this, we might not want to take the "better" name for the data structure that'll be less directly used?

Could prefix with "Raw" or maybe TrieRawHashMap? (since it's the hashing part that's particularly "raw" - relying on the hash being unique, etc)

[dexonsmith]

In D133715#4032581, @dblaikie wrote:

I guess one concern with TrieHashMap is that if this is the lower level implementation, and someone might implement a more map-like API on top of this, we might not want to take the "better" name for the data structure that'll be less directly used?

Could prefix with "Raw" or maybe TrieRawHashMap? (since it's the hashing part that's particularly "raw" - relying on the hash being unique, etc)

Either of those “raw” names SGTM.

[steven_wu]

Maybe RawHashTrieMap? It reads better when Raw is in the front, and it contains hash-trie and trie-map, which are both terms describing data structures similar to this but this is much simpler, thus raw.

llvm/unittests/ADT/HashMappedTrieTest.cpp

19

I didn't see this comment.

Can you elaborate more how this work? Since friend doesn't inherit and TEST_F are subclasses of the test fixture, the best I can think is to create forwarding in the test fixture, then it is not that much different from what it is now.

[dexonsmith]

In D133715#4032713, @steven_wu wrote:

Maybe RawHashTrieMap? It reads better when Raw is in the front, and it contains hash-trie and trie-map, which are both terms describing data structures similar to this but this is much simpler, thus raw.

I think from a client perspective, this is some sort of variant of a HashMap, so ending with that makes sense to me. It’s an implementation detail that it’s a trie so that seems better in the prefix.

[dexonsmith]

llvm/unittests/ADT/HashMappedTrieTest.cpp

19

I think:

namespace llvm::testing {
class HashMappedTrieTest;
}

namespace llvm {
class HashMappedTrie {
  friend class HashMappedTrieTest;
}
}

And then use the llvm::testing namespace to implement the test.

[steven_wu]

Rename to TrieRawHashMap.

Update tests to use test fixture.

[dblaikie]

llvm/unittests/ADT/HashMappedTrieTest.cpp

19

https://stackoverflow.com/questions/2396370/how-to-make-google-test-classes-friends-with-my-classes seems to discuss how to friend a fixture directly, though may require gtest support/inclusion in the header.

llvm/unittests/ADT/TrieRawHashMapTest.cpp

293 ↗

(On Diff #487489)

This seems like a fair bit of text to wrap the trie - what's the value/extra test coverage this is providingg? (sorry I'm not following too clearly) I'd have hoped/expected this API could be tested more directly, without needing this wrapper and/or without needing to involve something as non-trivial as std::string (instead using simple user defined types in the test)?

[steven_wu]

llvm/unittests/ADT/HashMappedTrieTest.cpp

19

I am not sure about adding friend class in library header that references tests (and for each tests added).

What do you think about the current implementation? There is an extra forwarding in the test helper but not too bad.

llvm/unittests/ADT/TrieRawHashMapTest.cpp

293 ↗

(On Diff #487489)

This a simplified version of the original test from the original patch. The original patch implements a generic set data structure in this test file and tests how it trie can be used like a set. Now it is simplified to be a stringset with a fake hash algorithm because there is no current value to put TrieSet in ADT.

[dblaikie]

llvm/unittests/ADT/HashMappedTrieTest.cpp

19

It'd only be for the one test fixture here (HashMappedTrieTest), I think. Feels like it'd be nice to avoid the indirection through the HashMappedTrieTestHelper.

llvm/unittests/ADT/TrieRawHashMapTest.cpp

293 ↗

(On Diff #487489)

What extra test coverage does it provide? How bad/what would be the tradeoff of testing that functionality more directly without the mock?

[steven_wu]

llvm/unittests/ADT/HashMappedTrieTest.cpp

19

Sorry I still don't quite get it. Current TrieRawHashMapTestHelper is the only test fixture, but I have to put the indirection in there unless I want to friend every single tests (currently 3) in llvm/ADT/TrieRawHashMap.h using FRIEND_TEST. Am I missing something?

llvm/unittests/ADT/TrieRawHashMapTest.cpp

293 ↗

(On Diff #487489)

The extra test coverage it provides is the ability to store a non-POD type data into the Trie. where insertLazy is tested for lazy construction. I guess we can also tested it with the naive uint64_t.

The alternative is might be just put ThreadSafeHashMappedTrieSet from the original patch into a header in ADT but there isn't a use case for that yet. So maybe testing insertLazy with uint64_t will make this cleaner.

[steven_wu]

Update unittest:

• Simplify the test of StringSet by explicitly calling insertLazy on TrieHashMap.
• Unify all the tests under the same template test fixture. Since we create this indirection, might as well use it to the full potential.

[steven_wu]

Update after makeArrayRef deprecation

llvm/include/llvm/ADT/HashMappedTrie.h

+//===- HashMappedTrie.h -----------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_HASHMAPPEDTRIE_H
+#define LLVM_ADT_HASHMAPPEDTRIE_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Casting.h"
+#include <atomic>
+#include <optional>
+
+namespace llvm {
+
+class raw_ostream;
+
+/// Base class for a lock-free thread-safe hash-mapped trie.
+class ThreadSafeHashMappedTrieBase {
+public:
+  static constexpr size_t TrieContentBaseSize = 4;
+  static constexpr size_t DefaultNumRootBits = 6;
+  static constexpr size_t DefaultNumSubtrieBits = 4;
+
+private:
+  template <class T> struct AllocValueType {
+    char Base[TrieContentBaseSize];
+    std::aligned_union_t<sizeof(T), T> Content;
+  };
+
+protected:
+  template <class T>
+  static constexpr size_t DefaultContentAllocSize = sizeof(AllocValueType<T>);
+
+  template <class T>
+  static constexpr size_t DefaultContentAllocAlign = alignof(AllocValueType<T>);
+
+  template <class T>
+  static constexpr size_t DefaultContentOffset =
+      offsetof(AllocValueType<T>, Content);
+
+public:
+  void operator delete(void *Ptr) { ::free(Ptr); }
+
+  LLVM_DUMP_METHOD void dump() const;
+  void print(raw_ostream &OS) const;
+
+protected:
+  /// Result of a lookup. Suitable for an insertion hint. Maybe could be
+  /// expanded into an iterator of sorts, but likely not useful (visiting
+  /// everything in the trie should probably be done some way other than
+  /// through an iterator pattern).
+  class PointerBase {
+  protected:
+    void *get() const { return I == -2u ? P : nullptr; }
+
+  public:
+    PointerBase() noexcept = default;
+    PointerBase(PointerBase &&) = default;
+    PointerBase(const PointerBase &) = default;
+    PointerBase &operator=(PointerBase &&) = default;
+    PointerBase &operator=(const PointerBase &) = default;
+
+  private:
+    friend class ThreadSafeHashMappedTrieBase;
+    explicit PointerBase(void *Content) : P(Content), I(-2u) {}
+    PointerBase(void *P, unsigned I, unsigned B) : P(P), I(I), B(B) {}
+
+    bool isHint() const { return I != -1u && I != -2u; }
+
+    void *P = nullptr;
+    unsigned I = -1u;
+    unsigned B = 0;
+  };
+
+  PointerBase find(ArrayRef<uint8_t> Hash) const;
+
+  /// Insert and return the stored content.
+  PointerBase
+  insert(PointerBase Hint, ArrayRef<uint8_t> Hash,
+         function_ref<const uint8_t *(void *Mem, ArrayRef<uint8_t> Hash)>
+             Constructor);
+
+  ThreadSafeHashMappedTrieBase() = delete;
+
+  ThreadSafeHashMappedTrieBase(
+      size_t ContentAllocSize, size_t ContentAllocAlign, size_t ContentOffset,
+      std::optional<size_t> NumRootBits = std::nullopt,
+      std::optional<size_t> NumSubtrieBits = std::nullopt);
+
+  /// Destructor, which asserts if there's anything to do. Subclasses should
+  /// call \a destroyImpl().
+  ///
+  /// \pre \a destroyImpl() was already called.
+  ~ThreadSafeHashMappedTrieBase();
+  void destroyImpl(function_ref<void(void *ValueMem)> Destructor);
+
+  ThreadSafeHashMappedTrieBase(ThreadSafeHashMappedTrieBase &&RHS);
+
+  // Move assignment can be implemented in a thread-safe way if NumRootBits and
+  // NumSubtrieBits are stored inside the Root.
+  ThreadSafeHashMappedTrieBase &
+  operator=(ThreadSafeHashMappedTrieBase &&RHS) = delete;
+
+  // No copy.
+  ThreadSafeHashMappedTrieBase(const ThreadSafeHashMappedTrieBase &) = delete;
+  ThreadSafeHashMappedTrieBase &
+  operator=(const ThreadSafeHashMappedTrieBase &) = delete;
+
+private:
+  const unsigned short ContentAllocSize;
+  const unsigned short ContentAllocAlign;
+  const unsigned short ContentOffset;
+  unsigned short NumRootBits;
+  unsigned short NumSubtrieBits;
+  struct ImplType;
+  // ImplPtr is owned by ThreadSafeHashMappedTrieBase and needs to be freed in
+  // destoryImpl.
+  std::atomic<ImplType *> ImplPtr;
+  ImplType &getOrCreateImpl();
+  ImplType *getImpl() const;
+};
+
+/// Lock-free thread-safe hash-mapped trie.
+template <class T, size_t NumHashBytes>
+class ThreadSafeHashMappedTrie : ThreadSafeHashMappedTrieBase {
+public:
+  using HashT = std::array<uint8_t, NumHashBytes>;
+
+  class LazyValueConstructor;
+  struct value_type {
+    const HashT Hash;
+    T Data;
+
+    value_type(value_type &&) = default;
+    value_type(const value_type &) = default;
+
+    value_type(ArrayRef<uint8_t> Hash, const T &Data)
+        : Hash(copyHash(Hash)), Data(Data) {}
+    value_type(ArrayRef<uint8_t> Hash, T &&Data)
+        : Hash(copyHash(Hash)), Data(std::move(Data)) {}
+
+  private:
+    friend class LazyValueConstructor;
+
+    struct EmplaceTag {};
+    template <class... ArgsT>
+    value_type(ArrayRef<uint8_t> Hash, EmplaceTag, ArgsT &&...Args)
+        : Hash(copyHash(Hash)), Data(std::forward<ArgsT>(Args)...) {}
+
+    static HashT copyHash(ArrayRef<uint8_t> HashRef) {
+      HashT Hash;
+      std::copy(HashRef.begin(), HashRef.end(), Hash.data());
+      return Hash;
+    }
+  };
+
+  using ThreadSafeHashMappedTrieBase::operator delete;
+  using HashType = HashT;
+
+  using ThreadSafeHashMappedTrieBase::dump;
+  using ThreadSafeHashMappedTrieBase::print;
+
+private:
+  template <class ValueT> class PointerImpl : PointerBase {
+    friend class ThreadSafeHashMappedTrie;
+
+    ValueT *get() const {
+      if (void *B = PointerBase::get())
+        return reinterpret_cast<ValueT *>(B);
+      return nullptr;
+    }
+
+  public:
+    ValueT &operator*() const {
+      assert(get());
+      return *get();
+    }
+    ValueT *operator->() const {
+      assert(get());
+      return get();
+    }
+    explicit operator bool() const { return get(); }
+
+    PointerImpl() = default;
+    PointerImpl(PointerImpl &&) = default;
+    PointerImpl(const PointerImpl &) = default;
+    PointerImpl &operator=(PointerImpl &&) = default;
+    PointerImpl &operator=(const PointerImpl &) = default;
+
+  protected:
+    PointerImpl(PointerBase Result) : PointerBase(Result) {}
+  };
+
+public:
+  class pointer;
+  class const_pointer;
+  class pointer : public PointerImpl<value_type> {
+    friend class ThreadSafeHashMappedTrie;
+    friend class const_pointer;
+
+  public:
+    pointer() = default;
+    pointer(pointer &&) = default;
+    pointer(const pointer &) = default;
+    pointer &operator=(pointer &&) = default;
+    pointer &operator=(const pointer &) = default;
+
+  private:
+    pointer(PointerBase Result) : pointer::PointerImpl(Result) {}
+  };
+
+  class const_pointer : public PointerImpl<const value_type> {
+    friend class ThreadSafeHashMappedTrie;
+
+  public:
+    const_pointer() = default;
+    const_pointer(const_pointer &&) = default;
+    const_pointer(const const_pointer &) = default;
+    const_pointer &operator=(const_pointer &&) = default;
+    const_pointer &operator=(const const_pointer &) = default;
+
+    const_pointer(const pointer &P) : const_pointer::PointerImpl(P) {}
+
+  private:
+    const_pointer(PointerBase Result) : const_pointer::PointerImpl(Result) {}
+  };
+
+  class LazyValueConstructor {
+  public:
+    value_type &operator()(T &&RHS) {
+      assert(Mem && "Constructor already called, or moved away");
+      return assign(::new (Mem) value_type(Hash, std::move(RHS)));
+    }
+    value_type &operator()(const T &RHS) {
+      assert(Mem && "Constructor already called, or moved away");
+      return assign(::new (Mem) value_type(Hash, RHS));
+    }
+    template <class... ArgsT> value_type &emplace(ArgsT &&...Args) {
+      assert(Mem && "Constructor already called, or moved away");
+      return assign(::new (Mem)
+                        value_type(Hash, typename value_type::EmplaceTag{},
+                                   std::forward<ArgsT>(Args)...));
+    }
+
+    LazyValueConstructor(LazyValueConstructor &&RHS)
+        : Mem(RHS.Mem), Result(RHS.Result), Hash(RHS.Hash) {
+      RHS.Mem = nullptr; // Moved away, cannot call.
+    }
+    ~LazyValueConstructor() { assert(!Mem && "Constructor never called!"); }
+
+  private:
+    value_type &assign(value_type *V) {
+      Mem = nullptr;
+      Result = V;
+      return *V;
+    }
+    friend class ThreadSafeHashMappedTrie;
+    LazyValueConstructor() = delete;
+    LazyValueConstructor(void *Mem, value_type *&Result, ArrayRef<uint8_t> Hash)
+        : Mem(Mem), Result(Result), Hash(Hash) {
+      assert(Hash.size() == sizeof(HashT) && "Invalid hash");
+      assert(Mem && "Invalid memory for construction");
+    }
+    void *Mem;
+    value_type *&Result;
+    ArrayRef<uint8_t> Hash;
+  };
+
+  /// Insert with a hint. Default-constructed hint will work, but it's
+  /// recommended to start with a lookup to avoid overhead in object creation
+  /// if it already exists.
+  pointer insertLazy(const_pointer Hint, ArrayRef<uint8_t> Hash,
+                     function_ref<void(LazyValueConstructor)> OnConstruct) {
+    return pointer(ThreadSafeHashMappedTrieBase::insert(
+        Hint, Hash, [&](void *Mem, ArrayRef<uint8_t> Hash) {
+          value_type *Result = nullptr;
+          OnConstruct(LazyValueConstructor(Mem, Result, Hash));
+          return Result->Hash.data();
+        }));
+  }
+
+  pointer insertLazy(ArrayRef<uint8_t> Hash,
+                     function_ref<void(LazyValueConstructor)> OnConstruct) {
+    return insertLazy(const_pointer(), Hash, OnConstruct);
+  }
+
+  pointer insert(const_pointer Hint, value_type &&HashedData) {
+    return insertLazy(Hint, HashedData.Hash, [&](LazyValueConstructor C) {
+      C(std::move(HashedData.Data));
+    });
+  }
+
+  pointer insert(const_pointer Hint, const value_type &HashedData) {
+    return insertLazy(Hint, HashedData.Hash,
+                      [&](LazyValueConstructor C) { C(HashedData.Data); });
+  }
+
+  pointer find(ArrayRef<uint8_t> Hash) {
+    assert(Hash.size() == std::tuple_size<HashT>::value);
+    return ThreadSafeHashMappedTrieBase::find(Hash);
+  }
+
+  const_pointer find(ArrayRef<uint8_t> Hash) const {
+    assert(Hash.size() == std::tuple_size<HashT>::value);
+    return ThreadSafeHashMappedTrieBase::find(Hash);
+  }
+
+  ThreadSafeHashMappedTrie(std::optional<size_t> NumRootBits = std::nullopt,
+                           std::optional<size_t> NumSubtrieBits = std::nullopt)
+      : ThreadSafeHashMappedTrieBase(DefaultContentAllocSize<value_type>,
+                                     DefaultContentAllocAlign<value_type>,
+                                     DefaultContentOffset<value_type>,
+                                     NumRootBits, NumSubtrieBits) {}
+
+  ~ThreadSafeHashMappedTrie() {
+    if constexpr (std::is_trivially_destructible<value_type>::value)
+      this->destroyImpl(nullptr);
+    else
+      this->destroyImpl(
+          [](void *P) { static_cast<value_type *>(P)->~value_type(); });
+  }
+
+  // Move constructor okay.
+  ThreadSafeHashMappedTrie(ThreadSafeHashMappedTrie &&) = default;
+
+  // No move assignment or any copy.
+  ThreadSafeHashMappedTrie &operator=(ThreadSafeHashMappedTrie &&) = delete;
+  ThreadSafeHashMappedTrie(const ThreadSafeHashMappedTrie &) = delete;
+  ThreadSafeHashMappedTrie &
+  operator=(const ThreadSafeHashMappedTrie &) = delete;
+};
+
+} // namespace llvm
+
+#endif // LLVM_ADT_HASHMAPPEDTRIE_H

llvm/lib/Support/CMakeLists.txt

add_llvm_component_library(LLVMSupport
   FileCollector.cpp
   FileUtilities.cpp
   FileOutputBuffer.cpp
   FoldingSet.cpp
   FormattedStream.cpp
   FormatVariadic.cpp
   GlobPattern.cpp
   GraphWriter.cpp
+  HashMappedTrie.cpp
   Hashing.cpp
   InitLLVM.cpp
   InstructionCost.cpp
   IntEqClasses.cpp
   IntervalMap.cpp
   ItaniumManglingCanonicalizer.cpp
   JSON.cpp
   KnownBits.cpp

llvm/lib/Support/HashMappedTrie.cpp

+//===- HashMappedTrie.cpp -------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/HashMappedTrie.h"
+#include "HashMappedTrieIndexGenerator.h"
+#include "llvm/ADT/LazyAtomicPointer.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/ThreadSafeAllocator.h"
+#include "llvm/Support/raw_ostream.h"
+#include <memory>
+
+using namespace llvm;
+
+namespace {
+struct TrieNode {
+  const bool IsSubtrie = false;
+
+  TrieNode(bool IsSubtrie) : IsSubtrie(IsSubtrie) {}
+
+  static void *operator new(size_t Size) { return ::malloc(Size); }
+  void operator delete(void *Ptr) { ::free(Ptr); }
+};
+
+struct TrieContent final : public TrieNode {
+  const uint8_t ContentOffset;
+  const uint8_t HashSize;
+  const uint8_t HashOffset;
+
+  void *getValuePointer() const {
+    auto Content = reinterpret_cast<const uint8_t *>(this) + ContentOffset;
+    return const_cast<uint8_t *>(Content);
+  }
+
+  ArrayRef<uint8_t> getHash() const {
+    auto *Begin = reinterpret_cast<const uint8_t *>(this) + HashOffset;
+    return makeArrayRef(Begin, Begin + HashSize);
+  }
+
+  TrieContent(size_t ContentOffset, size_t HashSize, size_t HashOffset)
+      : TrieNode(/*IsSubtrie=*/false), ContentOffset(ContentOffset),
+        HashSize(HashSize), HashOffset(HashOffset) {}
+};
+static_assert(sizeof(TrieContent) ==
+                  ThreadSafeHashMappedTrieBase::TrieContentBaseSize,
+              "Check header assumption!");
+
+class TrieSubtrie final : public TrieNode {
+public:
+  TrieNode *get(size_t I) const { return Slots[I].load(); }
+
+  TrieSubtrie *
+  sink(size_t I, TrieContent &Content, size_t NumSubtrieBits, size_t NewI,
+       function_ref<TrieSubtrie *(std::unique_ptr<TrieSubtrie>)> Saver);
+
+  void printHash(raw_ostream &OS, ArrayRef<uint8_t> Bytes) const;
+  void print(raw_ostream &OS) const { print(OS, std::nullopt); }
+  void print(raw_ostream &OS, std::optional<std::string> Prefix) const;
+  void dump() const { print(dbgs()); }
+
+  static std::unique_ptr<TrieSubtrie> create(size_t StartBit, size_t NumBits);
+
+  explicit TrieSubtrie(size_t StartBit, size_t NumBits);
+
+private:
+  // FIXME: Use a bitset to speed up access:
+  //
+  //     std::array<std::atomic<uint64_t>, NumSlots/64> IsSet;
+  //
+  // This will avoid needing to visit sparsely filled slots in
+  // \a ThreadSafeHashMappedTrieBase::destroyImpl() when there's a non-trivial
+  // destructor.
+  //
+  // It would also greatly speed up iteration, if we add that some day, and
+  // allow get() to return one level sooner.
+  //
+  // This would be the algorithm for updating IsSet (after updating Slots):
+  //
+  //     std::atomic<uint64_t> &Bits = IsSet[I.High];
+  //     const uint64_t NewBit = 1ULL << I.Low;
+  //     uint64_t Old = 0;
+  //     while (!Bits.compare_exchange_weak(Old, Old | NewBit))
+  //       ;
+
+  // For debugging.
+  unsigned StartBit = 0;
+  unsigned NumBits = 0;
+
+public:
+  /// Linked list for ownership of tries. The pointer is owned by TrieSubtrie.
+  std::atomic<TrieSubtrie *> Next;
+
+  /// The (co-allocated) slots of the subtrie.
+  MutableArrayRef<LazyAtomicPointer<TrieNode>> Slots;
+};
+} // end namespace
+
+namespace llvm {
+template <> struct isa_impl<TrieContent, TrieNode> {
+  static inline bool doit(const TrieNode &TN) { return !TN.IsSubtrie; }
+};
+template <> struct isa_impl<TrieSubtrie, TrieNode> {
+  static inline bool doit(const TrieNode &TN) { return TN.IsSubtrie; }
+};
+} // end namespace llvm
+
+static size_t getTrieTailSize(size_t StartBit, size_t NumBits) {
+  assert(NumBits < 20 && "Tries should have fewer than ~1M slots");
+  return sizeof(TrieNode *) * (1u << NumBits);
+}
+
+std::unique_ptr<TrieSubtrie> TrieSubtrie::create(size_t StartBit,
+                                                 size_t NumBits) {
+  size_t Size = sizeof(TrieSubtrie) + getTrieTailSize(StartBit, NumBits);
+  void *Memory = ::malloc(Size);
+  TrieSubtrie *S = ::new (Memory) TrieSubtrie(StartBit, NumBits);
+  return std::unique_ptr<TrieSubtrie>(S);
+}
+
+TrieSubtrie::TrieSubtrie(size_t StartBit, size_t NumBits)
+    : TrieNode(true), StartBit(StartBit), NumBits(NumBits), Next(nullptr),
+      Slots(reinterpret_cast<LazyAtomicPointer<TrieNode> *>(
+                reinterpret_cast<char *>(this) + sizeof(TrieSubtrie)),
+            (1u << NumBits)) {
+  for (auto *I = Slots.begin(), *E = Slots.end(); I != E; ++I)
+    new (I) LazyAtomicPointer<TrieNode>(nullptr);
+
+  static_assert(
+      std::is_trivially_destructible<LazyAtomicPointer<TrieNode>>::value,
+      "Expected no work in destructor for TrieNode");
+}
+
+TrieSubtrie *TrieSubtrie::sink(
+    size_t I, TrieContent &Content, size_t NumSubtrieBits, size_t NewI,
+    function_ref<TrieSubtrie *(std::unique_ptr<TrieSubtrie>)> Saver) {
+  assert(NumSubtrieBits > 0);
+  std::unique_ptr<TrieSubtrie> S = create(StartBit + NumBits, NumSubtrieBits);
+
+  assert(NewI < S->Slots.size());
+  S->Slots[NewI].store(&Content);
+
+  TrieNode *ExistingNode = &Content;
+  assert(I < Slots.size());
+  if (Slots[I].compare_exchange_strong(ExistingNode, S.get()))
+    return Saver(std::move(S));
+
+  // Another thread created a subtrie already. Return it and let "S" be
+  // destructed.
+  return cast<TrieSubtrie>(ExistingNode);
+}
+
+struct ThreadSafeHashMappedTrieBase::ImplType {
+  static ImplType *create(size_t StartBit, size_t NumBits) {
+    size_t Size = sizeof(ImplType) + getTrieTailSize(StartBit, NumBits);
+    void *Memory = ::malloc(Size);
+    return ::new (Memory) ImplType(StartBit, NumBits);
+  }
+
+  TrieSubtrie *save(std::unique_ptr<TrieSubtrie> S) {
+    assert(!S->Next && "Expected S to a freshly-constructed leaf");
+
+    TrieSubtrie *CurrentHead = nullptr;
+    // Add ownership of "S" to front of the list, so that Root -> S ->
+    // Root.Next. This works by repeatedly setting S->Next to a candidate value
+    // of Root.Next (initially nullptr), then setting Root.Next to S once the
+    // candidate matches reality.
+    while (!Root.Next.compare_exchange_weak(CurrentHead, S.get()))
+      S->Next.exchange(CurrentHead);
+
+    // Ownership transferred to subtrie.
+    return S.release();
+  }
+
+  static void *operator new(size_t Size) { return ::malloc(Size); }
+  void operator delete(void *Ptr) { ::free(Ptr); }
+
+  /// FIXME: This should take a function that allocates and constructs the
+  /// content lazily (taking the hash as a separate parameter), in case of
+  /// collision.
+  ThreadSafeAllocator<BumpPtrAllocator> ContentAlloc;
+  TrieSubtrie Root; // Must be last! Tail-allocated.
+
+private:
+  ImplType(size_t StartBit, size_t NumBits) : Root(StartBit, NumBits) {}
+};
+
+ThreadSafeHashMappedTrieBase::ImplType &
+ThreadSafeHashMappedTrieBase::getOrCreateImpl() {
+  if (ImplType *Impl = ImplPtr.load())
+    return *Impl;
+
+  // Create a new ImplType and store it if another thread doesn't do so first.
+  // If another thread wins this one is destroyed locally.
+  std::unique_ptr<ImplType> Impl(ImplType::create(0, NumRootBits));
+  ImplType *ExistingImpl = nullptr;
+  if (ImplPtr.compare_exchange_strong(ExistingImpl, Impl.get()))
+    return *Impl.release();
+
+  return *ExistingImpl;
+}
+
+ThreadSafeHashMappedTrieBase::PointerBase
+ThreadSafeHashMappedTrieBase::find(ArrayRef<uint8_t> Hash) const {
+  assert(!Hash.empty() && "Uninitialized hash");
+
+  ImplType *Impl = ImplPtr.load();
+  if (!Impl)
+    return PointerBase();
+
+  TrieSubtrie *S = &Impl->Root;
+  IndexGenerator IndexGen{NumRootBits, NumSubtrieBits, Hash};
+  size_t Index = IndexGen.next();
+  for (;;) {
+    // Try to set the content.
+    TrieNode *Existing = S->get(Index);
+    if (!Existing)
+      return PointerBase(S, Index, *IndexGen.StartBit);
+
+    // Check for an exact match.
+    if (auto *ExistingContent = dyn_cast<TrieContent>(Existing))
+      return ExistingContent->getHash() == Hash
+                 ? PointerBase(ExistingContent->getValuePointer())
+                 : PointerBase(S, Index, *IndexGen.StartBit);
+
+    Index = IndexGen.next();
+    S = cast<TrieSubtrie>(Existing);
+  }
+}
+
+ThreadSafeHashMappedTrieBase::PointerBase ThreadSafeHashMappedTrieBase::insert(
+    PointerBase Hint, ArrayRef<uint8_t> Hash,
+    function_ref<const uint8_t *(void *Mem, ArrayRef<uint8_t> Hash)>
+        Constructor) {
+  assert(!Hash.empty() && "Uninitialized hash");
+
+  ImplType &Impl = getOrCreateImpl();
+  TrieSubtrie *S = &Impl.Root;
+  IndexGenerator IndexGen{NumRootBits, NumSubtrieBits, Hash};
+  size_t Index;
+  if (Hint.isHint()) {
+    S = static_cast<TrieSubtrie *>(Hint.P);
+    Index = IndexGen.hint(Hint.I, Hint.B);
+  } else {
+    Index = IndexGen.next();
+  }
+
+  for (;;) {
+    // Load the node from the slot, allocating and calling the constructor if
+    // the slot is empty.
+    bool Generated = false;
+    TrieNode &Existing = S->Slots[Index].loadOrGenerate([&]() {
+      Generated = true;
+
+      // Construct the value itself at the tail.
+      uint8_t *Memory = reinterpret_cast<uint8_t *>(
+          Impl.ContentAlloc.Allocate(ContentAllocSize, ContentAllocAlign));
+      const uint8_t *HashStorage = Constructor(Memory + ContentOffset, Hash);
+
+      // Construct the TrieContent header, passing in the offset to the hash.
+      TrieContent *Content = ::new (Memory)
+          TrieContent(ContentOffset, Hash.size(), HashStorage - Memory);
+      assert(Hash == Content->getHash() && "Hash not properly initialized");
+      return Content;
+    });
+    // If we just generated it, return it!
+    if (Generated)
+      return PointerBase(cast<TrieContent>(Existing).getValuePointer());
+
+    if (isa<TrieSubtrie>(Existing)) {
+      S = &cast<TrieSubtrie>(Existing);
+      Index = IndexGen.next();
+      continue;
+    }
+
+    // Return the existing content if it's an exact match!
+    auto &ExistingContent = cast<TrieContent>(Existing);
+    if (ExistingContent.getHash() == Hash)
+      return PointerBase(ExistingContent.getValuePointer());
+
+    // Sink the existing content as long as the indexes match.
+    for (;;) {
+      size_t NextIndex = IndexGen.next();
+      size_t NewIndexForExistingContent =
+          IndexGen.getCollidingBits(ExistingContent.getHash());
+      S = S->sink(Index, ExistingContent, IndexGen.getNumBits(),
+                  NewIndexForExistingContent,
+                  [&Impl](std::unique_ptr<TrieSubtrie> S) {
+                    return Impl.save(std::move(S));
+                  });
+      Index = NextIndex;
+
+      // Found the difference.
+      if (NextIndex != NewIndexForExistingContent)
+        break;
+    }
+  }
+}
+
+static void printHexDigit(raw_ostream &OS, uint8_t Digit) {
+  if (Digit < 10)
+    OS << char(Digit + '0');
+  else
+    OS << char(Digit - 10 + 'a');
+}
+
+static void printHexDigits(raw_ostream &OS, ArrayRef<uint8_t> Bytes,
+                           size_t StartBit, size_t NumBits) {
+  assert(StartBit % 4 == 0);
+  assert(NumBits % 4 == 0);
+  for (size_t I = StartBit, E = StartBit + NumBits; I != E; I += 4) {
+    uint8_t HexPair = Bytes[I / 8];
+    uint8_t HexDigit = I % 8 == 0 ? HexPair >> 4 : HexPair & 0xf;
+    printHexDigit(OS, HexDigit);
+  }
+}
+
+static void printBits(raw_ostream &OS, ArrayRef<uint8_t> Bytes, size_t StartBit,
+                      size_t NumBits) {
+  assert(StartBit + NumBits <= Bytes.size() * 8u);
+  for (size_t I = StartBit, E = StartBit + NumBits; I != E; ++I) {
+    uint8_t Byte = Bytes[I / 8];
+    size_t ByteOffset = I % 8;
+    if (size_t ByteShift = 8 - ByteOffset - 1)
+      Byte >>= ByteShift;
+    OS << (Byte & 0x1 ? '1' : '0');
+  }
+}
+
+void TrieSubtrie::printHash(raw_ostream &OS, ArrayRef<uint8_t> Bytes) const {
+  // afb[1c:00*01110*0]def
+  size_t EndBit = StartBit + NumBits;
+  size_t HashEndBit = Bytes.size() * 8u;
+
+  size_t FirstBinaryBit = StartBit & ~0x3u;
+  printHexDigits(OS, Bytes, 0, FirstBinaryBit);
+
+  size_t LastBinaryBit = (EndBit + 3u) & ~0x3u;
+  OS << "[";
+  printBits(OS, Bytes, FirstBinaryBit, LastBinaryBit - FirstBinaryBit);
+  OS << "]";
+
+  printHexDigits(OS, Bytes, LastBinaryBit, HashEndBit - LastBinaryBit);
+}
+
+static void appendIndexBits(std::string &Prefix, size_t Index,
+                            size_t NumSlots) {
+  std::string Bits;
+  for (size_t NumBits = 1u; NumBits < NumSlots; NumBits <<= 1) {
+    Bits.push_back('0' + (Index & 0x1));
+    Index >>= 1;
+  }
+  for (char Ch : llvm::reverse(Bits))
+    Prefix += Ch;
+}
+
+static void printPrefix(raw_ostream &OS, StringRef Prefix) {
+  while (Prefix.size() >= 4) {
+    uint8_t Digit;
+    bool ErrorParsingBinary = Prefix.take_front(4).getAsInteger(2, Digit);
+    assert(!ErrorParsingBinary);
+    (void)ErrorParsingBinary;
+    printHexDigit(OS, Digit);
+    Prefix = Prefix.drop_front(4);
+  }
+  if (!Prefix.empty())
+    OS << "[" << Prefix << "]";
+}
+
+void TrieSubtrie::print(raw_ostream &OS,
+                        std::optional<std::string> Prefix) const {
+  if (!Prefix) {
+    OS << "root";
+    Prefix.emplace();
+  } else {
+    OS << "subtrie=";
+    printPrefix(OS, *Prefix);
+  }
+
+  OS << " num-slots=" << Slots.size() << "\n";
+  SmallVector<TrieSubtrie *> Subs;
+  SmallVector<std::string> Prefixes;
+  for (size_t I = 0, E = Slots.size(); I != E; ++I) {
+    TrieNode *N = get(I);
+    if (!N)
+      continue;
+    OS << "- index=" << I << " ";
+    if (auto *S = dyn_cast<TrieSubtrie>(N)) {
+      std::string SubtriePrefix = *Prefix;
+      appendIndexBits(SubtriePrefix, I, Slots.size());
+      OS << "subtrie=";
+      printPrefix(OS, SubtriePrefix);
+      OS << "\n";
+      Subs.push_back(S);
+      Prefixes.push_back(SubtriePrefix);
+      continue;
+    }
+    auto *Content = cast<TrieContent>(N);
+    OS << "content=";
+    printHash(OS, Content->getHash());
+    OS << "\n";
+  }
+  for (size_t I = 0, E = Subs.size(); I != E; ++I)
+    Subs[I]->print(OS, Prefixes[I]);
+}
+
+void ThreadSafeHashMappedTrieBase::print(raw_ostream &OS) const {
+  OS << "root-bits=" << NumRootBits << " subtrie-bits=" << NumSubtrieBits
+     << "\n";
+  if (ImplType *Impl = ImplPtr.load())
+    Impl->Root.print(OS);
+  else
+    OS << "[no-root]\n";
+}
+
+LLVM_DUMP_METHOD void ThreadSafeHashMappedTrieBase::dump() const {
+  print(dbgs());
+}
+
+ThreadSafeHashMappedTrieBase::ThreadSafeHashMappedTrieBase(
+    size_t ContentAllocSize, size_t ContentAllocAlign, size_t ContentOffset,
+    std::optional<size_t> NumRootBits, std::optional<size_t> NumSubtrieBits)
+    : ContentAllocSize(ContentAllocSize), ContentAllocAlign(ContentAllocAlign),
+      ContentOffset(ContentOffset),
+      NumRootBits(NumRootBits ? *NumRootBits : DefaultNumRootBits),
+      NumSubtrieBits(NumSubtrieBits ? *NumSubtrieBits : DefaultNumSubtrieBits),
+      ImplPtr(nullptr) {
+  assert((!NumRootBits || *NumRootBits < 20) &&
+         "Root should have fewer than ~1M slots");
+  assert((!NumSubtrieBits || *NumSubtrieBits < 10) &&
+         "Subtries should have fewer than ~1K slots");
+}
+
+ThreadSafeHashMappedTrieBase::ThreadSafeHashMappedTrieBase(
+    ThreadSafeHashMappedTrieBase &&RHS)
+    : ContentAllocSize(RHS.ContentAllocSize),
+      ContentAllocAlign(RHS.ContentAllocAlign),
+      ContentOffset(RHS.ContentOffset), NumRootBits(RHS.NumRootBits),
+      NumSubtrieBits(RHS.NumSubtrieBits) {
+  // Steal the root from RHS.
+  ImplPtr = RHS.ImplPtr.exchange(nullptr);
+}
+
+ThreadSafeHashMappedTrieBase::~ThreadSafeHashMappedTrieBase() {
+  assert(!ImplPtr.load() && "Expected subclass to call destroyImpl()");
+}
+
+void ThreadSafeHashMappedTrieBase::destroyImpl(
+    function_ref<void(void *)> Destructor) {
+  std::unique_ptr<ImplType> Impl(ImplPtr.exchange(nullptr));
+  if (!Impl)
+    return;
+
+  // Destroy content nodes throughout trie. Avoid destroying any subtries since
+  // we need TrieNode::classof() to find the content nodes.
+  //
+  // FIXME: Once we have bitsets (see FIXME in TrieSubtrie class), use them
+  // facilitate sparse iteration here.
+  if (Destructor)
+    for (TrieSubtrie *Trie = &Impl->Root; Trie; Trie = Trie->Next.load())
+      for (auto &Slot : Trie->Slots)
+        if (auto *Content = dyn_cast_or_null<TrieContent>(Slot.load()))
+          Destructor(Content->getValuePointer());
+
+  // Destroy the subtries. Incidentally, this destroys them in the reverse order
+  // of saving.
+  TrieSubtrie *Trie = Impl->Root.Next;
+  while (Trie) {
+    TrieSubtrie *Next = Trie->Next.exchange(nullptr);
+    delete Trie;
+    Trie = Next;
+  }
+}

llvm/lib/Support/HashMappedTrieIndexGenerator.h

+//===- HashMappedTrieIndexGenerator.h ---------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_SUPPORT_HASHMAPPEDTRIEINDEXGENERATOR_H
+#define LLVM_LIB_SUPPORT_HASHMAPPEDTRIEINDEXGENERATOR_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include <optional>
+
+namespace llvm {
+
+struct IndexGenerator {
+  size_t NumRootBits;
+  size_t NumSubtrieBits;
+  ArrayRef<uint8_t> Bytes;
+  std::optional<size_t> StartBit = std::nullopt;
+
+  size_t getNumBits() const {
+    assert(StartBit);
+    size_t TotalNumBits = Bytes.size() * 8;
+    assert(*StartBit <= TotalNumBits);
+    return std::min(*StartBit ? NumSubtrieBits : NumRootBits,
+                    TotalNumBits - *StartBit);
+  }
+  size_t next() {
+    size_t Index;
+    if (!StartBit) {
+      StartBit = 0;
+      Index = getIndex(Bytes, *StartBit, NumRootBits);
+    } else {
+      *StartBit += *StartBit ? NumSubtrieBits : NumRootBits;
+      assert((*StartBit - NumRootBits) % NumSubtrieBits == 0);
+      Index = getIndex(Bytes, *StartBit, NumSubtrieBits);
+    }
+    return Index;
+  }
+
+  size_t hint(unsigned Index, unsigned Bit) {
+    assert(Index >= 0);
+    assert(Bit < Bytes.size() * 8);
+    assert(Bit == 0 || (Bit - NumRootBits) % NumSubtrieBits == 0);
+    StartBit = Bit;
+    return Index;
+  }
+
+  size_t getCollidingBits(ArrayRef<uint8_t> CollidingBits) const {
+    assert(StartBit);
+    return getIndex(CollidingBits, *StartBit, NumSubtrieBits);
+  }
+
+  static size_t getIndex(ArrayRef<uint8_t> Bytes, size_t StartBit,
+                         size_t NumBits) {
+    assert(StartBit < Bytes.size() * 8);
+
+    Bytes = Bytes.drop_front(StartBit / 8u);
+    StartBit %= 8u;
+    size_t Index = 0;
+    for (uint8_t Byte : Bytes) {
+      size_t ByteStart = 0, ByteEnd = 8;
+      if (StartBit) {
+        ByteStart = StartBit;
+        Byte &= (1u << (8 - StartBit)) - 1u;
+        StartBit = 0;
+      }
+      size_t CurrentNumBits = ByteEnd - ByteStart;
+      if (CurrentNumBits > NumBits) {
+        Byte >>= CurrentNumBits - NumBits;
+        CurrentNumBits = NumBits;
+      }
+      Index <<= CurrentNumBits;
+      Index |= Byte & ((1u << CurrentNumBits) - 1u);
+
+      assert(NumBits >= CurrentNumBits);
+      NumBits -= CurrentNumBits;
+      if (!NumBits)
+        break;
+    }
+    return Index;
+  }
+};
+
+} // namespace llvm
+
+#endif // LLVM_LIB_SUPPORT_HASHMAPPEDTRIEINDEXGENERATOR_H

llvm/unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   EditDistanceTest.cpp
   EnumeratedArrayTest.cpp
   EquivalenceClassesTest.cpp
   FallibleIteratorTest.cpp
   FloatingPointMode.cpp
   FoldingSet.cpp
   FunctionExtrasTest.cpp
   FunctionRefTest.cpp
+  HashMappedTrieTest.cpp
   HashingTest.cpp
   IListBaseTest.cpp
   IListIteratorTest.cpp
   IListNodeBaseTest.cpp
   IListNodeTest.cpp
   IListSentinelTest.cpp
   IListTest.cpp
   ImmutableListTest.cpp

llvm/unittests/ADT/HashMappedTrieTest.cpp

+//===- HashMappedTrieTest.cpp ---------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/HashMappedTrie.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/Support/Endian.h"
+#include "llvm/Support/SHA1.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+static StringRef takeNextLine(StringRef &Lines) {
+  size_t Newline = Lines.find('\n');
+  StringRef Line = Lines.take_front(Newline);
+  Lines = Lines.drop_front(Newline + 1);
+  return Line;
+}
+
+namespace {
+
+TEST(HashMappedTrieTest, TrieStructure) {
+  using NumType = uint64_t;
+  using HashType = std::array<uint8_t, sizeof(NumType)>;
+  using TrieType = ThreadSafeHashMappedTrie<NumType, sizeof(HashType)>;
+  NumType Numbers[] = {
+      // Three numbers that will nest deeply to test (1) sinking subtries and
+      // (2) deep, non-trivial hints.
+      std::numeric_limits<NumType>::max(),
+      std::numeric_limits<NumType>::max() - 2u,
+      std::numeric_limits<NumType>::max() - 3u,
+      // One number to stay at the top-level.
+      0x37,
+  };
+
+  // Use the number itself as hash to test the pathological case.
+  auto hash = [](NumType Num) {
+    NumType HashN = llvm::support::endian::byte_swap(Num, llvm::support::big);
+    HashType Hash;
+    memcpy(&Hash[0], &HashN, sizeof(HashType));
+    return Hash;
+  };
+
+  // Use root and subtrie sizes of 1 so this gets sunk quite deep.
+  TrieType Trie(1, 1);
+  for (NumType N : Numbers) {
+    // Lookup first to exercise hint code for deep tries.
+    TrieType::pointer Lookup = Trie.find(hash(N));
+    EXPECT_FALSE(Lookup);
+
+    Trie.insert(Lookup, TrieType::value_type(hash(N), N));
+  }
+  for (NumType N : Numbers) {
+    TrieType::pointer Lookup = Trie.find(hash(N));
+    EXPECT_TRUE(Lookup);
+    if (!Lookup)
+      continue;
+    EXPECT_EQ(hash(N), Lookup->Hash);
+    EXPECT_EQ(N, Lookup->Data);
+
+    // Confirm a subsequent insertion fails to overwrite by trying to insert a
+    // bad value.
+    EXPECT_EQ(N,
+              Trie.insert(Lookup, TrieType::value_type(hash(N), N - 1))->Data);
+  }
+
+  // Dump out the trie so we can confirm the structure is correct. Each subtrie
+  // should have 2 slots. The root's index=0 should have the content for
+  // 0x37 directly, and index=1 should be a linked-list of subtries, finally
+  // ending with content for (max-2) and (max-3).
+  //
+  // Note: This structure is not exhaustive (too expensive to update tests),
+  // but it does test that the dump format is somewhat readable and that the
+  // basic structure is correct.
+  //
+  // Note: This test requires that the trie reads bytes starting from index 0
+  // of the array of uint8_t, and then reads each byte's bits from high to low.
+  SmallString<128> Dump;
+  {
+    raw_svector_ostream OS(Dump);
+    Trie.print(OS);
+  }
+
+  // Check the header.
+  StringRef DumpRef = Dump;
+  ASSERT_EQ("root-bits=1 subtrie-bits=1", takeNextLine(DumpRef));
+
+  // Check the root trie.
+  ASSERT_EQ("root num-slots=2", takeNextLine(DumpRef));
+  ASSERT_EQ("- index=0 content=[0000]000000000000037", takeNextLine(DumpRef));
+  ASSERT_EQ("- index=1 subtrie=[1]", takeNextLine(DumpRef));
+  ASSERT_EQ("subtrie=[1] num-slots=2", takeNextLine(DumpRef));
+
+  // Check the last subtrie.
+  size_t LastSubtrie = DumpRef.rfind("\nsubtrie=");
+  ASSERT_NE(StringRef::npos, LastSubtrie);
+  DumpRef = DumpRef.substr(LastSubtrie + 1);
+  ASSERT_EQ("subtrie=fffffffffffffff[110] num-slots=2", takeNextLine(DumpRef));
+  ASSERT_EQ("- index=0 content=fffffffffffffff[1100]", takeNextLine(DumpRef));
+  ASSERT_EQ("- index=1 content=fffffffffffffff[1101]", takeNextLine(DumpRef));
+  ASSERT_TRUE(DumpRef.empty());
+}
+
+TEST(HashMappedTrieTest, TrieStructureSmallFinalSubtrie) {
+  using NumType = uint64_t;
+  using HashType = std::array<uint8_t, sizeof(NumType)>;
+  using TrieType = ThreadSafeHashMappedTrie<NumType, sizeof(HashType)>;
+  NumType Numbers[] = {
+      // Three numbers that will nest deeply to test (1) sinking subtries and
+      // (2) deep, non-trivial hints.
+      std::numeric_limits<NumType>::max(),
+      std::numeric_limits<NumType>::max() - 2u,
+      std::numeric_limits<NumType>::max() - 3u,
+      // One number to stay at the top-level.
+      0x37,
+  };
+
+  // Use the number itself as hash to test the pathological case.
+  auto hash = [](NumType Num) {
+    NumType HashN = llvm::support::endian::byte_swap(Num, llvm::support::big);
+    HashType Hash;
+    memcpy(&Hash[0], &HashN, sizeof(HashType));
+    return Hash;
+  };
+
+  // Use subtrie size of 7 to avoid hitting 64 evenly, making the final subtrie
+  // small.
+  TrieType Trie(8, 5);
+  for (NumType N : Numbers) {
+    // Lookup first to exercise hint code for deep tries.
+    TrieType::pointer Lookup = Trie.find(hash(N));
+    EXPECT_FALSE(Lookup);
+
+    Trie.insert(Lookup, TrieType::value_type(hash(N), N));
+  }
+  for (NumType N : Numbers) {
+    TrieType::pointer Lookup = Trie.find(hash(N));
+    EXPECT_TRUE(Lookup);
+    if (!Lookup)
+      continue;
+    EXPECT_EQ(hash(N), Lookup->Hash);
+    EXPECT_EQ(N, Lookup->Data);
+
+    // Confirm a subsequent insertion fails to overwrite by trying to insert a
+    // bad value.
+    EXPECT_EQ(N,
+              Trie.insert(Lookup, TrieType::value_type(hash(N), N - 1))->Data);
+  }
+
+  // Dump out the trie so we can confirm the structure is correct. The root
+  // should have 2^8=256 slots, most subtries should have 2^5=32 slots, and the
+  // deepest subtrie should have 2^1=2 slots (since (64-8)mod(5)=1).
+  // should have 2 slots. The root's index=0 should have the content for
+  // 0x37 directly, and index=1 should be a linked-list of subtries, finally
+  // ending with content for (max-2) and (max-3).
+  //
+  // Note: This structure is not exhaustive (too expensive to update tests),
+  // but it does test that the dump format is somewhat readable and that the
+  // basic structure is correct.
+  //
+  // Note: This test requires that the trie reads bytes starting from index 0
+  // of the array of uint8_t, and then reads each byte's bits from high to low.
+  SmallString<128> Dump;
+  {
+    raw_svector_ostream OS(Dump);
+    Trie.print(OS);
+  }
+
+  // Check the header.
+  StringRef DumpRef = Dump;
+  ASSERT_EQ("root-bits=8 subtrie-bits=5", takeNextLine(DumpRef));
+
+  // Check the root trie.
+  ASSERT_EQ("root num-slots=256", takeNextLine(DumpRef));
+  ASSERT_EQ("- index=0 content=[00000000]00000000000037",
+            takeNextLine(DumpRef));
+  ASSERT_EQ("- index=255 subtrie=ff", takeNextLine(DumpRef));
+  ASSERT_EQ("subtrie=ff num-slots=32", takeNextLine(DumpRef));
+
+  // Check the last subtrie.
+  size_t LastSubtrie = DumpRef.rfind("\nsubtrie=");
+  ASSERT_NE(StringRef::npos, LastSubtrie);
+  DumpRef = DumpRef.substr(LastSubtrie + 1);
+  ASSERT_EQ("subtrie=fffffffffffffff[110] num-slots=2", takeNextLine(DumpRef));
+  ASSERT_EQ("- index=0 content=fffffffffffffff[1100]", takeNextLine(DumpRef));
+  ASSERT_EQ("- index=1 content=fffffffffffffff[1101]", takeNextLine(DumpRef));
+  ASSERT_TRUE(DumpRef.empty());
+}
+
+TEST(HashMappedTrieTest, TrieDestructionLoop) {
+  // Test destroying large Trie. Make sure there is no recursion that can
+  // overflow the stack.
+  using NumT = uint64_t;
+  struct NumWithDestructorT {
+    NumT Num;
+    operator NumT() const { return Num; }
+    ~NumWithDestructorT() {}
+  };
+
+  using HashT = std::array<uint8_t, sizeof(NumT)>;
+  using TrieT = ThreadSafeHashMappedTrie<NumT, sizeof(HashT)>;
+  using TrieWithDestructorT =
+      ThreadSafeHashMappedTrie<NumWithDestructorT, sizeof(HashT)>;
+
+  // Use the number itself in big-endian order as the hash.
+  auto hash = [](NumT Num) {
+    NumT HashN = llvm::support::endian::byte_swap(Num, llvm::support::big);
+    HashT Hash;
+    memcpy(&Hash[0], &HashN, sizeof(HashT));
+    return Hash;
+  };
+
+  // Use optionals to control when destructors are called.
+  std::optional<TrieT> Trie;
+  std::optional<TrieWithDestructorT> TrieWithDestructor;
+
+  // Limit the tries to 2 slots (1 bit) to generate subtries at a higher rate.
+  Trie.emplace(/*NumRootBits=*/1, /*NumSubtrieBits=*/1);
+  TrieWithDestructor.emplace(/*NumRootBits=*/1, /*NumSubtrieBits=*/1);
+
+  // Fill them up. Pick a MaxN high enough to cause a stack overflow in debug
+  // builds.
+  static constexpr uint64_t MaxN = 100000;
+  for (uint64_t N = 0; N != MaxN; ++N) {
+    HashT Hash = hash(N);
+    Trie->insert(TrieT::pointer(), TrieT::value_type(Hash, N));
+    TrieWithDestructor->insert(
+        TrieWithDestructorT::pointer(),
+        TrieWithDestructorT::value_type(Hash, NumWithDestructorT{N}));
+  }
+
+  // Destroy tries. If destruction is recursive and MaxN is high enough, these
+  // will both fail.
+  Trie.reset();
+  TrieWithDestructor.reset();
+}
+
+namespace {
+static constexpr unsigned HashSize = 20;
+using HashType = std::array<uint8_t, HashSize>;
+
+class MockTrieStringSet
+    : ThreadSafeHashMappedTrie<std::string, sizeof(HashType)> {
+public:
+  using TrieType =
+      typename MockTrieStringSet::ThreadSafeHashMappedTrie;
+  using LazyValueConstructor = typename MockTrieStringSet::
+      ThreadSafeHashMappedTrie::LazyValueConstructor;
+
+  class pointer : public TrieType::const_pointer {
+    using BaseType = typename TrieType::const_pointer;
+
+  public:
+    const std::string &operator*() const {
+      return TrieType::const_pointer::operator*().Data;
+    }
+    const std::string *operator->() const { return &operator*(); }
+
+    pointer() = default;
+    pointer(pointer &&) = default;
+    pointer(const pointer &) = default;
+    pointer &operator=(pointer &&) = default;
+    pointer &operator=(const pointer &) = default;
+
+  private:
+    pointer(BaseType Result) : BaseType(Result) {}
+    friend class MockTrieStringSet;
+  };
+
+  MockTrieStringSet(
+      std::optional<size_t> NumRootBits = std::nullopt,
+      std::optional<size_t> NumSubtrieBits = std::nullopt)
+      : TrieType(NumRootBits, NumSubtrieBits) {}
+
+  static HashType hash(const std::string &V) {
+    // Mock hash function. Create unique hash for the test case inputs below.
+    const unsigned MaxSize = 4;
+    assert(V.size() <= MaxSize && "Invalid Input");
+    std::string Input = V;
+    Input.resize(MaxSize);
+    HashType Hash;
+    // Repeat the padded string to hash length so SubTries will be created with
+    // different test configuration.
+    for (unsigned I = 0; I < HashSize; I += MaxSize)
+      llvm::copy(Input, Hash.begin() + I);
+    return Hash;
+  }
+
+  pointer find(const std::string &Value) const {
+    return pointer(TrieType::find(hash(Value)));
+  }
+  pointer insert(pointer Hint, std::string &&Value) {
+    return pointer(TrieType::insertLazy(
+        typename pointer::BaseType(Hint), hash(Value),
+        [&](LazyValueConstructor C) { C(std::move(Value)); }));
+  }
+  pointer insert(pointer Hint, const std::string &Value) {
+    return pointer(
+        TrieType::insertLazy(typename pointer::BaseType(Hint), hash(Value),
+                             [&](LazyValueConstructor C) { C(Value); }));
+  }
+  pointer insert(std::string &&Value) { return insert(pointer(), Value); }
+  pointer insert(const std::string &Value) { return insert(pointer(), Value); }
+};
+} // end anonymous namespace
+
+TEST(HashMappedTrieTest, Strings) {
+  for (unsigned RootBits : {2, 3, 6, 10}) {
+    for (unsigned SubtrieBits : {2, 3, 4}) {
+      MockTrieStringSet Strings(RootBits, SubtrieBits);
+      const std::string &A1 = *Strings.insert("A");
+      EXPECT_EQ(&A1, &*Strings.insert("A"));
+      std::string A2 = A1;
+      EXPECT_EQ(&A1, &*Strings.insert(A2));
+
+      const std::string &B1 = *Strings.insert("B");
+      EXPECT_EQ(&B1, &*Strings.insert(B1));
+      std::string B2 = B1;
+      EXPECT_EQ(&B1, &*Strings.insert(B2));
+
+      for (int I = 0, E = 1000; I != E; ++I) {
+        MockTrieStringSet::pointer Lookup;
+        std::string S = Twine(I).str();
+        if (I & 1)
+          Lookup = Strings.find(S);
+        const std::string &S1 = *Strings.insert(Lookup, S);
+        EXPECT_EQ(&S1, &*Strings.insert(S1));
+        std::string S2 = S1;
+        EXPECT_EQ(&S1, &*Strings.insert(S2));
+      }
+      for (int I = 0, E = 1000; I != E; ++I) {
+        std::string S = Twine(I).str();
+        MockTrieStringSet::pointer Lookup =
+            Strings.find(S);
+        EXPECT_TRUE(Lookup);
+        if (!Lookup)
+          continue;
+        EXPECT_EQ(S, *Lookup);
+      }
+    }
+  }
+}
+
+} // namespace