llvm / llvm/llvm-project

[ADT][SmallSet] `SmallSet` allocates in default constructor

Open
#160,286 0 comments 0 reactions 0 assignees View on GitHub
llvm:adt
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`:

Image

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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.