Page MenuHomePhabricator

Switch SmallSetVector to use DenseSet when it overflows its inline space.
ClosedPublic

Authored by jlebar on Oct 15 2016, 3:56 PM.

Details

Summary

SetVector already used DenseSet, but SmallSetVector used std::set. This
leads to surprising performance differences. Moreover, it means that
the set of key types accepted by SetVector and SmallSetVector are
quite different!

In order to make this change, we had to convert some callsites that used
SmallSetVector<std::string, N> to use SmallSetVector<CachedHashString, N>
instead.

Diff Detail

Repository
rL LLVM

Event Timeline

jlebar updated this revision to Diff 74781.Oct 15 2016, 3:56 PM
jlebar retitled this revision from to Switch SmallSetVector to use DenseSet when it overflows its inline space..
jlebar updated this object.
jlebar added a reviewer: timshen.
jlebar added a subscriber: llvm-commits.

Here's the whole patch queue, in a topological order.

  • D25628 [ADT] Add SmallDenseSet.
  • D25629 [ADT] Add an initializer_list constructor to {Small,}DenseSet.
  • D25643 [IR] Add DenseMapInfo<CallSite>.
  • D25644 [ADT] Move CachedHashString to a own header in ADT, and rename to CachedHashStringRef.
  • D25645 [ADT] Add CachedHashString.
  • D25646 Use CachedHashStringRef instead of CachedHash<StringRef>.
  • D25630 [ADT] Remove CachedHash, which is unused.
  • D25647 [clang-tidy] Don't use a SmallSetVector of an enum.
  • D25648 Switch SmallSetVector to use DenseSet when it overflows its inline space.

I *think* the metadata in the "stack" view is now correct. :)

timshen accepted this revision.Oct 20 2016, 4:42 PM
timshen edited edge metadata.

I'm surprised that nothing breaks. :)

This revision is now accepted and ready to land.Oct 20 2016, 4:42 PM

I'm surprised that nothing breaks. :)

Well, there *were* a lot of dependent patches. :)

This revision was automatically updated to reflect the committed changes.