Why is std::list<>::sort so slow ??? A (much!) faster way to sort lists.

[tikabass]

The other day on stackoverflow, I helped a student with his implementation of bubblesort for a list. In doing so, I created a small project on godbolt with 3 different algorithms for sorting lists. I did some naive comparisons of performance and compared to their performance to std::list::sort(). The STL is slow. for smalll arrays, it is even slower than the simple algorithm I've been using ;fr ages, which is very simple and easy.

Anyway, while comparing these algotithms, I implemented a naive partition based algorithm for sorting lists, bvery similar to qsort, and was surprised by the results. Around 90% improvement over std::list::sort for short lists, whiich was not surprising, but the improvements were consistent over a wide range, it's still stands at over 50% for a 10000 elements list.

I know I'm not doing anything wrong... And I don't think I invented anything new. Is thre a specific reason why std::sort is so slow,
even when compiling with -O3 ? I wouldn't dare make puI-down request before this is reviewed and tested, and timed by someone else as well. Is there any chance to see improvements to the STL ? A faster sort would sure make list more useful..

You'll find my sandbox on godbolt here: https://godbolt.org/z/Y8eE1f

Here is the sorting function:,

[edit] I've added pivot selection for corner cases. Still up to 75% improvement (in corner case), even with 1,000,000 elements
I'm still testing.

void qsort(Node*& head) {
  struct local {
    static size_t get_distance(Node* begin, Node* end = nullptr) {
      size_t result = 0;
      for (; begin != end; begin = begin->next, ++result)
        ;
      return result;
    }

    static void prepare_for_qsort(Node*& begin, Node* end) {
    size_t len = get_distance(begin, end);
    size_t i = 0;
    size_t j = 0;
    size_t next_idx = 0;

    if (len < 10) return;

    struct candidate_t {
        Node* prev;
        Node* node;
    };

    candidate_t candidates[5] = {};

    // select and move best candiate for partition to top of list.
    for (Node* prev = begin; prev != end && prev->next != end;
        prev = prev->next, ++i) {
        Node* p = prev->next;
        if (i == next_idx) {
        candidates[j++] = candidate_t{prev, p};
        next_idx += (len - 1) / 5;
        }
    }

    // pick median of candidates
    std::sort(std::begin(candidates), std::end(candidates),
                [](const candidate_t& a, const candidate_t& b) {
                return a.node->data < b.node->data;
                });

    auto& best = candidates[2];

    best.prev->next = best.node->next;
    best.node->next = begin;
    begin = best.node;
    }

    static void sort(Node*& begin, Node* end) {
    auto partition = [](Node*& begin, Node* end) {
        if (begin == end || begin->next == end) return;

        Node* pivot = begin;
        for (Node* prev = begin; prev != end && prev->next != end;
            prev = prev->next) {
        Node* p = prev->next;
        while (p != end && p->data < pivot->data) {
            prev->next = p->next;
            p->next = begin;
            begin = p;
            p = prev->next;
        }
        }
    };

    if (begin == end || begin->next == end) return;

    prepare_for_qsort(begin, end);
    Node* pivot = begin;
    partition(begin, end);
    sort(begin, pivot);
    sort(pivot->next, end);
    }
};

if (!head || !head->next) return;

local::sort(head, nullptr);
}

m:o)

[lone-wolf-akela]

As far as I can tell, your Node is an intrusive singly-linked list, while std::list is non-intrusive doubly-linked list. These are very different data structures and performance differences are expected.

[wew036]

std::list::sort is stable. Is your version a stable sort?

[frederick-vs-ja]

I think implementations of std::(forward_)list::<>::sort generally use merge sort. And merge sort is expected because the standard requires that these sort's are stable.

If the requirement of stability were removed, we would be able to use the combination of quick sort and merge sort.