[ADT][SmallSet] `SmallSet` allocates in default constructor
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
The `SmallSet` implementation currently utilizes `std::set`. A key characteristic of `std::set` is that its default constructor allocates a sentinel node. Consequently, `SmallSet` also performs an allocation upon default construction, even though the underlying set is not yet and might never be used and no elements have been inserted.
I observed the unnecessary overhead during a performance profile of clang, for example in MachineCopyPropagation.cpp:`CopyTracker::invalidateRegister`:
Possible solutions:
- replace the `std::set` with a different implementation that does not allocate by default.
- migrate to `SmallDenseSet`. For this specific clang profile, switching from `SmallSet` to `SmallDenseSet` in `invalidateRegister` resulted in a performance improvement of ~6x of this function, as no allocations were performed. However, it could be that `SmallSet` scales way better for larger sizes than `SmallDenseSet`, so the optimized version might be slower for different inputs. The same would be true for all other usages of `SmallSet`
- Maybe you have an even better idea?
Contributor guide
Assessment
This issue has not been assessed yet.