`std :: list‹ ›:: sort ()` - почему внезапный переход на стратегию сверху вниз?

Обратите внимание, что этот ответ был обновлен для решения всех проблем, упомянутых в комментариях ниже и после вопроса, путем внесения того же изменения из массива списков в массив итераторов, сохраняя при этом более быстрый алгоритм сортировки слиянием снизу вверх и исключая небольшая вероятность переполнения стека из-за рекурсии с алгоритмом сортировки слиянием сверху вниз.

Причина, по которой я изначально не рассматривал итераторы, была связана с изменением VS2015 на нисходящий, что привело меня к мысли, что есть некоторая проблема с попыткой изменить существующий восходящий алгоритм для использования итераторов, требующих перехода на более медленный нисходящий алгоритм. Только когда я сам попытался проанализировать переход на итераторы, я понял, что есть решение для алгоритма снизу вверх.

В комментарии @ sbi он спросил автора подхода «сверху вниз» Стефана Т. Лававея, почему было внесено изменение. В ответ Стефан отказался от выделения памяти и построения распределителей по умолчанию. VS2015 представил не конструируемые по умолчанию и отслеживающие состояние распределители, что представляет проблему при использовании массива списков предыдущей версии, поскольку каждый экземпляр списка выделяет фиктивный узел, и потребуется изменение, чтобы не обрабатывать распределитель по умолчанию.

Решение Lavavej заключалось в том, чтобы переключиться на использование итераторов для отслеживания границ выполнения в исходном списке вместо внутреннего массива списков. Логика слияния была изменена, чтобы использовать 3 параметра итератора, 1-й параметр - итератор до начала левого прогона, 2-й параметр - итератор до конца левого прогона == итератор до начала правого прогона, 3-й параметр - итератор до конца правого прогона. Процесс слияния использует std :: list :: splice для перемещения узлов в исходном списке во время операций слияния. Это имеет дополнительное преимущество - безопасность исключений. Если функция сравнения вызывающего абонента вызывает исключение, список будет переупорядочен, но потери данных не произойдет (при условии, что сварка не может завершиться ошибкой). В предыдущей схеме некоторые (или большая часть) данных были бы во внутреннем массиве списков, если бы произошло исключение, и данные были бы потеряны из исходного списка.

Однако переключение на сортировку слиянием сверху вниз не потребовалось. Первоначально, думая, что существует какая-то неизвестная мне причина для переключения VS2015 сверху вниз, я сосредоточился на использовании внутренних интерфейсов так же, как std :: list :: splice. Позже я решил исследовать переключение снизу вверх, чтобы использовать массив итераторов. Я понял, что порядок запусков, хранящихся во внутреннем массиве, был от самого нового (array [0] = крайний правый) до самого старого (array [last] = крайний левый), и что он мог использовать ту же логику слияния на основе итератора, что и подход VS2015 сверху вниз.

Для сортировки слиянием снизу вверх array [i] является итератором для начала отсортированного подсписка с 2 узлами ^ i, или он пуст (используется std :: list :: end для обозначения пустоты). Конец каждого отсортированного подсписка будет началом отсортированного подсписка в следующей предыдущей непустой записи в массиве или, если в начале массива, в локальном итераторе (он указывает на конец самого нового запустить). Подобно подходу сверху вниз, массив итераторов используется только для отслеживания отсортированных границ выполнения в исходном связанном списке, в то время как процесс слияния использует std :: list :: splice для перемещения узлов в исходном связанном списке.

Если связанный список большой, а узлы разбросаны, будет много промахов кеша. Снизу вверх будет примерно на 30% быстрее, чем сверху вниз (эквивалентно заявлению, что сверху вниз примерно на 42% медленнее, чем снизу вверх). Опять же, если памяти достаточно, обычно быстрее переместить список в массив или вектор, отсортировать массив или вектор, а затем создать новый список из отсортированного массива или вектора.

Пример кода C ++:

#define ASZ 32

template <typename T>
void SortList(std::list<T> &ll)
{
    if (ll.size() < 2)                  // return if nothing to do
        return;
    std::list<T>::iterator ai[ASZ];     // array of iterators
    std::list<T>::iterator mi;          // middle iterator (end lft, bgn rgt)
    std::list<T>::iterator ei;          // end    iterator
    size_t i;
    for (i = 0; i < ASZ; i++)           // "clear" array
        ai[i] = ll.end();
    // merge nodes into array
    for (ei = ll.begin(); ei != ll.end();) {
        mi = ei++;
        for (i = 0; (i < ASZ) && ai[i] != ll.end(); i++) {
            mi = Merge(ll, ai[i], mi, ei);
            ai[i] = ll.end();
        }
        if(i == ASZ)
            i--;
        ai[i] = mi;
    }
    // merge array into single list
    ei = ll.end();                              
    for(i = 0; (i < ASZ) && ai[i] == ei; i++);
    mi = ai[i++];
    while(1){
        for( ; (i < ASZ) && ai[i] == ei; i++);
        if (i == ASZ)
            break;
        mi = Merge(ll, ai[i++], mi, ei);
    }
}

template <typename T>
typename std::list<T>::iterator Merge(std::list<T> &ll,
                             typename std::list<T>::iterator li,
                             typename std::list<T>::iterator mi,
                             typename std::list<T>::iterator ei)
{
    std::list<T>::iterator ni;
    (*mi < *li) ? ni = mi : ni = li;
    while(1){
        if(*mi < *li){
            ll.splice(li, ll, mi++);
            if(mi == ei)
                return ni;
        } else {
            if(++li == mi)
                return ni;
        }
    }
}

Пример кода замены для std :: list :: sort () VS2019 (логика слияния была выделена в отдельную внутреннюю функцию, поскольку теперь она используется в двух местах).

private:
    template <class _Pr2>
    iterator _Merge(_Pr2 _Pred, iterator _First, iterator _Mid, iterator _Last){
        iterator _Newfirst = _First;
        for (bool _Initial_loop = true;;
            _Initial_loop       = false) { // [_First, _Mid) and [_Mid, _Last) are sorted and non-empty
            if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First)) { // consume _Mid
                if (_Initial_loop) {
                    _Newfirst = _Mid; // update return value
                }
                splice(_First, *this, _Mid++);
                if (_Mid == _Last) {
                    return _Newfirst; // exhausted [_Mid, _Last); done
                }
            }
            else { // consume _First
                ++_First;
                if (_First == _Mid) {
                    return _Newfirst; // exhausted [_First, _Mid); done
                }
            }
        }
    }

    template <class _Pr2>
    void _Sort(iterator _First, iterator _Last, _Pr2 _Pred,
        size_type _Size) { // order [_First, _Last), using _Pred, return new first
                           // _Size must be distance from _First to _Last
        if (_Size < 2) {
            return;        // nothing to do
        }
        const size_t _ASZ = 32;         // array size
        iterator _Ai[_ASZ];             // array of   iterators to runs
        iterator _Mi;                   // middle     iterator
        iterator _Li;                   // last (end) iterator
        size_t _I;                      // index to _Ai
        for (_I = 0; _I < _ASZ; _I++)   // "empty" array
            _Ai[_I] = _Last;            //   _Ai[] == _Last => empty entry
        // merge nodes into array
        for (_Li = _First; _Li != _Last;) {
            _Mi = _Li++;
            for (_I = 0; (_I < _ASZ) && _Ai[_I] != _Last; _I++) {
                _Mi = _Merge(_Pass_fn(_Pred), _Ai[_I], _Mi, _Li);
                _Ai[_I] = _Last;
            }
            if (_I == _ASZ)
                _I--;
            _Ai[_I] = _Mi;
        }
        // merge array runs into single run
        for (_I = 0; _I < _ASZ && _Ai[_I] == _Last; _I++);
        _Mi = _Ai[_I++];
        while (1) {
            for (; _I < _ASZ && _Ai[_I] == _Last; _I++);
            if (_I == _ASZ)
                break;
            _Mi = _Merge(_Pass_fn(_Pred), _Ai[_I++], _Mi, _Last);
        }
    }

Остальная часть этого ответа историческая.

Мне удалось воспроизвести проблему (старая сортировка не компилируется, новая работает) на основе демонстрации от @IgorTandetnik:

#include <iostream>
#include <list>
#include <memory>

template <typename T>
class MyAlloc : public std::allocator<T> {
public:
    MyAlloc(T) {}  // suppress default constructor
    
    template <typename U>
    MyAlloc(const MyAlloc<U>& other) : std::allocator<T>(other) {}
    
    template< class U > struct rebind { typedef MyAlloc<U> other; };
};

int main()
{
    std::list<int, MyAlloc<int>> l(MyAlloc<int>(0));
    l.push_back(3);
    l.push_back(0);
    l.push_back(2);
    l.push_back(1);
    l.sort();
    return 0;
}

Я заметил это изменение еще в июле 2016 года и 1 августа 2016 года написал П.Дж. Плаугеру об этом изменении. Фрагмент его ответа:

Что интересно, в нашем журнале изменений это изменение не отражено. Это, вероятно, означает, что это было предложено одним из наших крупных клиентов и получено мной при проверке кода. Все, что я знаю сейчас, это то, что изменение произошло примерно осенью 2015 года. Когда я просматривал код, первое, что меня поразило, - это строка:

    iterator _Mid = _STD next(_First, _Size / 2);

что, конечно, может занять очень время для большого списка.

Код выглядит немного элегантнее, чем то, что я написал в начале 1995 года (!), Но определенно имеет худшую временную сложность. Эта версия была смоделирована после подхода Степанова, Ли и Массера в исходной STL. Они редко ошибаются в выборе алгоритмов.

Сейчас я возвращаюсь к нашей последней заведомо исправной версии исходного кода.

Я не знаю, решило ли возвращение П.Дж.Плагера к исходному коду проблему с новым распределителем, или как Microsoft взаимодействует с Dinkumware.

Для сравнения методов сверху вниз и снизу вверх я создал связанный список из 4 миллионов элементов, каждый из которых состоит из одного 64-битного целого числа без знака, предполагая, что в итоге я получу двусвязный список почти последовательно упорядоченных узлов (даже если они будут размещаться динамически), заполнили их случайными числами, а затем отсортировали. Узлы не перемещаются, изменяется только связь, но теперь при обходе списка узлы получают доступ в случайном порядке. Затем я заполнил эти случайно упорядоченные узлы другим набором случайных чисел и снова отсортировал их. Я сравнил подход 2015 года сверху вниз с предыдущим подходом снизу вверх, модифицированным для соответствия другим изменениям, внесенным в 2015 году (sort () теперь вызывает sort () с функцией сравнения предикатов, а не с двумя отдельными функциями). Вот результаты. update - я добавил версию на основе указателя узла, а также отметил время для простого создания вектора из списка, сортировки вектора, копирования обратно.

sequential nodes: 2015 version 1.6 seconds, prior version 1.5  seconds
random nodes:     2015 version 4.0 seconds, prior version 2.8  seconds
random nodes:                  node pointer based version 2.6  seconds
random nodes:    create vector from list, sort, copy back 1.25 seconds

Для последовательных узлов предыдущая версия только немного быстрее, но для случайных узлов предыдущая версия на 30% быстрее, а версия указателя узла на 35% быстрее, и создание вектора из списка, сортировка вектора, затем копирование обратно на 69% быстрее.

Ниже приведен первый код замены для std :: list :: sort (), который я использовал для сравнения предыдущего метода снизу вверх с методом малого массива (_BinList []) с подходом сверху вниз VS2015. Я хотел, чтобы сравнение было справедливым, поэтому я изменил копия ‹списка›.

    void sort()
        {   // order sequence, using operator<
        sort(less<>());
        }

    template<class _Pr2>
        void sort(_Pr2 _Pred)
        {   // order sequence, using _Pred
        if (2 > this->_Mysize())
            return;
        const size_t _MAXBINS = 25;
        _Myt _Templist, _Binlist[_MAXBINS];
        while (!empty())
            {
            // _Templist = next element
            _Templist._Splice_same(_Templist.begin(), *this, begin(),
                ++begin(), 1);
            // merge with array of ever larger bins
            size_t _Bin;
            for (_Bin = 0; _Bin < _MAXBINS && !_Binlist[_Bin].empty();
                ++_Bin)
                _Templist.merge(_Binlist[_Bin], _Pred);
            // don't go past end of array
            if (_Bin == _MAXBINS)
                _Bin--;
            // update bin with merged list, empty _Templist
            _Binlist[_Bin].swap(_Templist);
            }
            // merge bins back into caller's list
            for (size_t _Bin = 0; _Bin < _MAXBINS; _Bin++)
                if(!_Binlist[_Bin].empty())
                    this->merge(_Binlist[_Bin], _Pred);
        }

Я внес небольшие изменения. Исходный код отслеживал фактический максимальный размер корзины в переменной с именем _Maxbin, но накладные расходы при окончательном слиянии достаточно малы, поэтому я удалил код, связанный с _Maxbin. Во время построения массива внутренний цикл исходного кода слился с элементом _Binlist [], после чего последовал переход в _Templist, что казалось бессмысленным. Я изменил внутренний цикл, чтобы он просто слился с _Templist, меняя местами только после того, как будет найден пустой элемент _Binlist [].

Ниже приведена замена std :: list :: sort () на основе указателя узла, которую я использовал для еще одного сравнения. Это устраняет проблемы, связанные с распределением. Если исключение сравнения возможно и произошло, все узлы в массиве и временном списке (pNode) должны быть добавлены обратно в исходный список, или, возможно, исключение сравнения может рассматриваться как меньшее, чем сравнение.

    void sort()
        {   // order sequence, using operator<
        sort(less<>());
        }

    template<class _Pr2>
        void sort(_Pr2 _Pred)
        {   // order sequence, using _Pred
        const size_t _NUMBINS = 25;
        _Nodeptr aList[_NUMBINS];           // array of lists
        _Nodeptr pNode;
        _Nodeptr pNext;
        _Nodeptr pPrev;
        if (this->size() < 2)               // return if nothing to do
            return;
        this->_Myhead()->_Prev->_Next = 0;  // set last node ->_Next = 0
        pNode = this->_Myhead()->_Next;     // set ptr to start of list
        size_t i;
        for (i = 0; i < _NUMBINS; i++)      // zero array
            aList[i] = 0;
        while (pNode != 0)                  // merge nodes into array
            {
            pNext = pNode->_Next;
            pNode->_Next = 0;
            for (i = 0; (i < _NUMBINS) && (aList[i] != 0); i++)
                {
                pNode = _MergeN(_Pred, aList[i], pNode);
                aList[i] = 0;
                }
            if (i == _NUMBINS)
                i--;
            aList[i] = pNode;
            pNode = pNext;
            }
        pNode = 0;                          // merge array into one list
        for (i = 0; i < _NUMBINS; i++)
            pNode = _MergeN(_Pred, aList[i], pNode);
        this->_Myhead()->_Next = pNode;     // update sentinel node links
        pPrev = this->_Myhead();            //  and _Prev pointers
        while (pNode)
            {
            pNode->_Prev = pPrev;
            pPrev = pNode;
            pNode = pNode->_Next;
            }
        pPrev->_Next = this->_Myhead();
        this->_Myhead()->_Prev = pPrev;
        }

    template<class _Pr2>
        _Nodeptr _MergeN(_Pr2 &_Pred, _Nodeptr pSrc1, _Nodeptr pSrc2)
        {
        _Nodeptr pDst = 0;          // destination head ptr
        _Nodeptr *ppDst = &pDst;    // ptr to head or prev->_Next
        if (pSrc1 == 0)
            return pSrc2;
        if (pSrc2 == 0)
            return pSrc1;
        while (1)
            {
            if (_DEBUG_LT_PRED(_Pred, pSrc2->_Myval, pSrc1->_Myval))
                {
                *ppDst = pSrc2;
                pSrc2 = *(ppDst = &pSrc2->_Next);
                if (pSrc2 == 0)
                    {
                    *ppDst = pSrc1;
                    break;
                    }
                }
            else
                {
                *ppDst = pSrc1;
                pSrc1 = *(ppDst = &pSrc1->_Next);
                if (pSrc1 == 0)
                    {
                    *ppDst = pSrc2;
                    break;
                    }
                }
            }
        return pDst;
        }

@sbi спросил Стефан Т. Лававедж, сопровождающий стандартной библиотеки MSVC, ответил:

Я сделал это, чтобы избежать выделения памяти и построения распределителей по умолчанию.

К этому я добавлю «бесплатную базовую безопасность исключений».

Для уточнения: реализация до VS2015 страдает несколькими дефектами:

• _Myt _Templist, _Binlist[_MAXBINS]; creates a bunch of intermediate lists (_Myt is simply a typedef for the current instantiation of list; a less confusing spelling for that is, well, list) to hold the nodes during sorting, but these lists are default constructed, which leads to a multitude of problems:
  1. If the allocator used is not default constructible (and there is no requirement that allocators be default constructible), this simply won't compile, because the default constructor of list will attempt to default construct its allocator.
  2. Если используемый распределитель отслеживает состояние, то созданный по умолчанию распределитель может не сравниваться с this->get_allocator(), что означает, что более поздние splice и merge являются технически неопределенным поведением и вполне могут сломаться в отладочных сборках. («Технически», потому что в конце все узлы объединяются, поэтому вы фактически не освобождаете память с неправильным распределителем, если функция успешно завершается.)
  3. list Dinkumware использует динамически выделяемый контрольный узел, что означает, что вышеприведенное будет выполнять _MAXBINS + 1 динамическое распределение. Я сомневаюсь, что многие люди ожидают, что sort потенциально бросит bad_alloc. Если распределитель отслеживает состояние, то эти контрольные узлы могут даже не выделяться из нужного места (см. №2).
• The code is not exception safe. In particular, the comparison is allowed to throw, and if it throws while there are elements in the intermediate lists, those elements are simply destroyed with the lists during stack unwinding. Users of sort don't expect the list to be sorted if sort throws an exception, of course, but they probably also don't expect the elements to go missing.
  • This interacts very poorly with #2 above, because now it's not just technical undefined behavior: the destructor of those intermediate lists will be deallocating and destroying the nodes spliced into them with the wrong allocator.

Можно ли исправить эти дефекты? Наверное. # 1 и # 2 можно исправить, передав get_allocator() конструктору lists:

 _Myt _Templist(get_allocator());
 _Myt _Binlist[_MAXBINS] = { _Myt(get_allocator()), _Myt(get_allocator()), 
                             _Myt(get_allocator()),  /* ... repeat _MAXBINS times */ };

Проблема безопасности исключений может быть решена путем окружения цикла try-catch, который соединяет все узлы в промежуточных list обратно в *this безотносительно порядка, если возникает исключение.

Исправить №3 сложнее, потому что это означает, что list вообще не используется в качестве держателя узлов, что, вероятно, потребует приличного рефакторинга, но это выполнимо.

Возникает вопрос: стоит ли прыгать через все эти препятствия, чтобы улучшить производительность контейнера, производительность которого снизилась по конструкции? В конце концов, тот, кто действительно заботится о производительности, вероятно, вообще не будет использовать list.