The project currently uses std::set in various places to store unique elements. However, std::set is typically implemented as a balanced tree, which can be inefficient, especially for small sets of pointers.
LLVM 17 provides llvm::SmallPtrSet, which is optimized for such cases, offering better cache locality and performance. This refactoring aims to replace instances of std::set<T*> with llvm::SmallPtrSet<T*, N>, where N is chosen based on expected usage patterns.
While we recommend using SmallPtrSet, you are free to select a different LLVM data structure if it better suits a specific use case.
Tasks
- Identify all occurrences of
std::set<T*> and evaluate whether they can be replaced with llvm::SmallPtrSet<T*, N>.
- Replace applicable instances, selecting an appropriate inline size (
N) to optimize performance.
- Ensure all affected code compiles and passes existing tests.
References
The project currently uses
std::setin various places to store unique elements. However,std::setis typically implemented as a balanced tree, which can be inefficient, especially for small sets of pointers.LLVM 17 provides
llvm::SmallPtrSet, which is optimized for such cases, offering better cache locality and performance. This refactoring aims to replace instances ofstd::set<T*>withllvm::SmallPtrSet<T*, N>, whereNis chosen based on expected usage patterns.While we recommend using
SmallPtrSet, you are free to select a different LLVM data structure if it better suits a specific use case.Tasks
std::set<T*>and evaluate whether they can be replaced withllvm::SmallPtrSet<T*, N>.N) to optimize performance.References