Re:Bubble sort slower with -O3 than -O2 with GCC
by mgraczyk on Sunday October 17, 2021 @01:57PM
(#28898314)
To me the more interesting meta-point here is that some algorithms are less microarchitecture friendly than others.
Algorithms with larger distances between data dependencies are less likely to stall.
For example I compared an insertion sort and see the same performance between O2 and O3:
void insertionsort(int *buf)
{
for (int i = 1; i < n; ++i) {
const int x = buf[i];
int j = i - 1;
for (; j >= 0 && buf[j] > x; --j) buf[j + 1] = buf[j];
buf[j + 1] = x;
}
}
For example I compared an insertion sort and see the same performance between O2 and O3:
bubble O2: 1.208sbubble O3: 1.469s
insertion O2: 0.126s
insertion O3: 0.126s