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

Question

Я помню, что с начала времен самый популярный подход к реализации std::list<>::sort() был ли классический алгоритм сортировки слиянием реализован снизу вверх (см. также Что делает реализацию сортировки gcc std::list такой быстрой?).

Я помню, как кто-то удачно относился к этой стратегии как к "цепочке луковиц".

По крайней мере, так обстоит дело с реализацией в GCC стандартной библиотеки C++ (см., Например, здесь). И так было в старом STL Dimkumware в версии стандартной библиотеки MSVC, а также во всех версиях MSVC вплоть до VS2013.

Однако стандартная библиотека, поставляемая с VS2015, неожиданно перестала следовать этой стратегии сортировки. Библиотека, поставляемая с VS2015, использует довольно простую рекурсивную реализацию сортировки слиянием сверху вниз. Это кажется мне странным, так как нисходящий подход требует доступа к средней точке списка, чтобы разделить его пополам. поскольку std::list<> не поддерживает произвольный доступ, единственный способ найти эту середину - буквально перебрать половину списка. Кроме того, в самом начале необходимо знать общее количество элементов в списке (которое не обязательно было операцией O(1) до C++11).

тем не менее, std::list<>::sort() в VS2015 делает именно это. Вот выдержка из этой реализации, которая находит среднюю точку и выполняет рекурсивные вызовы

...
iterator _Mid = _STD next(_First, _Size / 2);
_First = _Sort(_First, _Mid, _Pred, _Size / 2);
_Mid = _Sort(_Mid, _Last, _Pred, _Size - _Size / 2);
...

Как видите, они просто небрежно используют std::next пройти через первую половину списка и прийти к _Mid итератор.

Интересно, что может быть причиной этого переключения? Все, что я вижу, - это кажущаяся очевидной неэффективность повторяющихся призывов к std::next на каждом уровне рекурсии. Наивная логика говорит, что это медленнее. Если они готовы платить такую ​​цену, они, вероятно, ожидают получить что-то взамен. Что они получают тогда? Я не сразу вижу в этом алгоритме лучшее поведение кеша (по сравнению с оригинальным подходом снизу вверх). Я не сразу вижу, как он ведет себя лучше на предварительно отсортированных последовательностях.

Конечно, начиная с C++ 11 std::list<> в основном требуется для хранения количества элементов, что делает приведенное выше несколько более эффективным, так как мы всегда знаем количество элементов заранее. Но этого все еще недостаточно, чтобы оправдать последовательное сканирование на каждом уровне рекурсии.

(Правда, я не пытался сравнивать реализации друг с другом. Может быть, есть некоторые сюрпризы.)

Answer 1

обновление - VS2015 представила неконструктивные и сохраняющие состояние распределители по умолчанию, что создает проблему при использовании локальных списков, как это было с предыдущим восходящим подходом. Я смог решить эту проблему, используя указатели узлов вместо списков (см. Ниже) для подхода "снизу вверх".

В комментарии @ sbi он спросил автора нисходящего подхода Стефана Т. Лававея, почему было сделано изменение. Ответ Стефана заключался в том, чтобы "избежать выделения памяти и создания распределителей по умолчанию". Новый подход "сверху вниз" медленнее, чем старый подход "снизу вверх", но он использует только итераторы (рекурсивно хранящиеся в стеке), не использует локальные списки и избегает проблем, связанных с нестраиваемыми по умолчанию или сохраняющими состояние распределителями. Ответ @TC подробно об этом.

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

Я могу воспроизвести проблему (старая сортировка не компилируется, новая работает) на основе демонстрации от @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 года и по электронной почте PJ Plauger об этом изменении 1 августа 2016 года. Фрагмент его ответа:

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

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

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

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

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

Я не знаю, имел ли место возвращение PJ Plauger к исходному коду с новой проблемой распределителя, или как Microsoft взаимодействует с Dinkumware.

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

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;
        }

В качестве альтернативы новой VS2015 std::list::sort(), вы можете использовать эту автономную версию.

template <typename T>
void listsort(std::list <T> &dll)
{
    const size_t NUMLISTS = 32;
    std::list <T> al[NUMLISTS]; // array of lists
    std::list <T> tl;           // temp list
    while (!dll.empty()){
        // t1 = next element from dll
        tl.splice(tl.begin(), dll, dll.begin(), std::next(dll.begin()));
        // merge element into array
        size_t i;
        for (i = 0; i < NUMLISTS && !al[i].empty(); i++){
            tl.merge(al[i], std::less<T>());
        }
        if(i == NUMLISTS)       // don't go past end of array
            i -= 1;
        al[i].swap(tl);         // update array list, empty tl
    }
    // merge array back into original list
    for(size_t i = 0; i < NUMLISTS; i++)
        dll.merge(al[i], std::less<T>());
}

или используйте аналогичный алгоритм gcc.

Answer 2

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

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

К этому я добавлю "бесплатные базовые исключения безопасности".

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

• _Myt _Templist, _Binlist[_MAXBINS]; создает кучу промежуточных listс (_Myt это просто typedef для текущей реализации list; менее запутанное написание для этого, ну, list) удерживать узлы во время сортировки, но эти lists создаются по умолчанию, что приводит к множеству проблем:
  1. Если используемый распределитель не является конструируемым по умолчанию (и не требуется, чтобы распределители были конструируемым по умолчанию), он просто не будет компилироваться, потому что конструктор по умолчанию list будет пытаться построить его распределитель по умолчанию.
  2. Если используемый распределитель является состоящим, то созданный по умолчанию распределитель может не сравниваться равным this->get_allocator(), что означает, что позже spliceс и mergeЭто технически неопределенное поведение, которое может привести к поломке в отладочных сборках. ("Технически", потому что все узлы в конечном итоге объединяются, поэтому вы фактически не освобождаетесь от неправильного распределителя, если функция успешно завершается.)
  3. Dinkumware-х list использует динамически распределяемый сторожевой узел, что означает, что _MAXBINS + 1 динамические распределения. Я сомневаюсь, что многие ожидают sort потенциально бросить bad_alloc, Если распределитель имеет состояние, то эти дозорные узлы могут быть даже не выделены из правильного места (см. #2).
• Код не является безопасным для исключения. В частности, сравнение разрешено бросать, и если оно выбрасывает, пока есть элементы в промежуточном lists, эти элементы просто уничтожаются lists во время разматывания стека. Пользователи sort не ожидайте, что список будет отсортирован, если sort конечно, вызывает исключение, но они, вероятно, также не ожидают, что элементы пропадут.
  • Это очень плохо взаимодействует с # 2 выше, потому что теперь это не просто техническое неопределенное поведение: деструктор этих промежуточных lists будет освобождать и уничтожать узлы, врезанные в них с неправильным распределителем.

Исправлены ли эти дефекты? Наверное. #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 на первом месте.