2 ms·
To me the more interesting meta-point here is that some algorithms are less microarchitecture friendly than others. Algorithms with larger distances between dat
by mgraczyk 5y ago
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;
}
}
bubble O2: 1.208s
bubble O3: 1.469s
insertion O2: 0.126s
insertion O3: 0.126s