llvm / llvm/llvm-project

[libc++] flat_set uses 2x as many comparisons as it should

Open
#175,086 5 comments 0 reactions 0 assignees View on GitHub
libc++ performance
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

```c++
#include
#include

int Count = 0;
struct Comp { bool operator()(int x, int y) const { ++Count; return x < y; } };

int main() {
std::flat_set x = {0,0,0,0,0,0,0,0,0,0};
std::cout << Count;
}
```

This program uses 27 comparisons. It can be done in 18. The problem is that `flat_set::__key_equiv` always calls the comparator twice instead of once. I will post a patch for this.

Contributor guide

Open the contributing guide

Research direction

Start by locating libc++'s flat_set implementation and the flat_set::__key_equiv helper named in the issue. Run the supplied reproducer to confirm the 27 comparisons, then verify that the completed change reduces this case to 18 without changing flat_set behavior. The issue does not name a source file or test.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
devtools
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.