News for hackers. Stuff that matters.
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;
      }
    }
bubble O2: 1.208s

bubble O3: 1.469s

insertion O2: 0.126s

insertion O3: 0.126s

There are no comments on this comment yet.