[llvm-dev] Default set type

Russell Wallace via llvm-dev llvm-dev at lists.llvm.org
Sat Dec 19 01:14:17 PST 2015

In the typical case where you want a set of pointers,

If the number of elements is expected to be usually small, SmallPtrSet is
recommended; this seems clear enough.

However, if the number of elements is not particularly likely to be small,

"DenseSet is a simple quadratically probed hash table. It excels at
supporting small values: it uses a single allocation to hold all of the
pairs that are currently inserted in the set. DenseSet is a great way to
unique small values that are not simple pointers (use *SmallPtrSet*
<http://llvm.org/docs/ProgrammersManual.html#dss-smallptrset> for

The name plus the above paragraph from the documentation suggest DenseSet
should be used for small integers that have a limited range of values, and
SparseSet should be used for pointers (whose values are sparse within the
space of all possible values).

However, looking at examples of usage, it seems to be the other way round;
'dense' vs 'sparse' refer not to the space of values but to the data
structures used internally in the implementation, and actually SparseSet is
intended for small integers with a limited range of values...

And the answer to the original question is that DenseSet should be used as
the normal/default set type (for pointers, where there is no particular
expectation about the number of elements and no other special requirements).

Is the above correct, or am I missing anything?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20151219/da2a6360/attachment-0001.html>

More information about the llvm-dev mailing list