Очень быстрая сортировка массивов фиксированной длины с использованием компараторных сетей

Другие ответы интересны и довольно хороши, но я считаю, что могу предоставить некоторые дополнительные элементы ответа, пункт за пункт:

• Стоит ли усилий? Что ж, если вам нужно отсортировать небольшие коллекции целых чисел, а сети сортировки настроены так, чтобы максимально использовать некоторые инструкции, это может стоить усилий. На следующем графике представлены результаты сортировки миллиона массивов int размером 0-14 с различными алгоритмами сортировки. Как вы можете видеть, сети сортировки могут обеспечить значительное ускорение, если вам это действительно нужно.

• Нет стандартной реализации std::sort Я знаю об использовании сортировочных сетей; когда они не настроены точно, они могут быть медленнее, чем прямой тип вставки. Libc ++ s std::sort имеет специальные алгоритмы для сортировки от 0 до 5 значений одновременно, но они также не используют сети сортировки. Единственный известный мне алгоритм сортировки, который использует сортировочные сети для сортировки нескольких значений: Wikisort. Тем не менее, исследовательская работа Применение сетей сортировки для синтеза оптимизированных библиотек сортировки предполагает, что сети сортировки могут использоваться для сортировки небольших массивов или для улучшения алгоритмов рекурсивной сортировки, таких как быстрая сортировка, но только в том случае, если они настроены так, чтобы использовать преимущества конкретных аппаратных инструкций.

  доступ выравнивается сортировка Алгоритм — это своего рода восходящая сортировка, которая, по-видимому, использует сети с битовой сортировкой, реализованные с инструкциями SIMD для первого прохода. По-видимому, алгоритм может быть быстрее стандартной библиотеки для некоторых скалярных типов.

• Я действительно могу предоставить такую ​​информацию по той простой причине, что я разработал библиотека сортировки C ++ 14 это обеспечивает эффективные сети сортировки размером от 0 до 32, которые реализуют оптимизации, описанные в предыдущем разделе. Я использовал его для генерации графика в первом разделе. Я все еще работаю над частью библиотеки для сортировочных сетей, чтобы обеспечить оптимальные по размеру, оптимальным по глубине и оптимальным по размерам сети. Небольшие оптимальные сети сортировки обнаруживаются с помощью грубой силы, в то время как большие сети сортировки используют результаты литературы.

  Обратите внимание, что ни один из алгоритмов сортировки в библиотеке не использует сети сортировки напрямую, но вы можете адаптировать их так, чтобы сеть сортировки выбиралась всякий раз, когда алгоритму сортировки дается небольшой std::array или небольшой массив C фиксированного размера:

  using namespace cppsort;
  
  // Sorters are function objects that can be
  // adapted with sorter adapters from the
  // library
  using sorter = small_array_adapter<
  std_sorter,
  sorting_network_sorter
  >;
  
  // Now you can use it as a function
  sorter sort;
  
  // Instead of a size-agnostic sorting algorithm,
  // sort will use an optimal sorting network for
  // 5 inputs since the bound of the array can be
  // deduced at compile time
  int arr[] = { 2, 4, 7, 9, 3 };
  sort(arr);
  

  Как упоминалось выше, библиотека предоставляет эффективные сети сортировки для встроенных целых чисел, но вам, вероятно, не повезет, если вам нужно отсортировать небольшие массивы чего-то еще (например мои последние тесты показывают, что они не лучше, чем прямая вставка сортировки даже для long long int).

• Возможно, вы могли бы использовать шаблонное метапрограммирование для генерации сетей сортировки любого размера, но ни один из известных алгоритмов не может создать лучшие сети сортировки, поэтому вы могли бы также написать лучшие вручную. Я не думаю, что те, которые генерируются простыми алгоритмами, могут в любом случае обеспечить полезные и эффективные сети (единственно используемые сети с нечетно-четной сортировкой и попарной сортировкой Бэтчера могут быть) [Другой ответ, кажется, показывает, что сгенерированные сети действительно могут работать].

Известны оптимальные или, по крайней мере, лучшие сети компараторов длины для N<16, так что, по крайней мере, есть неплохая отправная точка. Справедливо, поскольку оптимальные сети не обязательно рассчитаны на максимальный уровень параллелизм достижимо, например, с помощью SSE или другая векторная арифметика.

Другое дело, что уже некоторые оптимальные сети для некоторого N являются вырожденными версиями для немного большей оптимальной сети для N + 1.

От википедия:

Оптимальные глубины до 10 входов известны, и они
соответственно 0, 1, 3, 3, 5, 5, 6, 6, 7, 7.

Тем не менее, я буду стремиться к реализации сетей для N = {4, 6, 8 и 10}, так как ограничение глубины не может быть смоделировано дополнительным параллелизмом (я думаю). Я также думаю, что способность работать в регистрах SSE (также с использованием некоторых инструкций min / max) или даже относительно большого набора регистров в архитектуре RISC обеспечит заметное преимущество в производительности по сравнению с «хорошо известными» методами сортировки, такими как быстрая сортировка, из-за отсутствие арифметики указателя и других накладных расходов.

Кроме того, я стремлюсь реализовать параллельную сеть, используя трюк с печально известной петлей Устройство Даффа.

РЕДАКТИРОВАТЬ
Когда известно, что входные значения являются положительными значениями IEEE-754 с плавающей точкой или двойными числами, также стоит упомянуть, что сравнение также может быть выполнено как целые числа. (float и int должны иметь одинаковые порядковые номера)

Позвольте мне поделиться некоторыми мыслями.

Есть ли у кого-нибудь мнение о том, стоит ли это
усилия?

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

Кто-нибудь знает, существует ли эта оптимизация в каком-либо стандарте?
реализации, например, std :: sort?

Например, реализация Visual C ++ std::sort использует сортировку вставки для маленьких векторов. Я не знаю о реализации, которая использует оптимальные сети сортировки.

Возможно, можно было бы создать такую ​​сортировочную сеть, как эта
статически используя шаблон магии

Существуют алгоритмы генерации сортировочных сетей, такие как алгоритмы Бозе-Нельсона, Хиббарда и Бэтчера. Поскольку шаблоны C ++ полны по Тьюрингу, вы можете реализовать их с помощью TMP. Однако эти алгоритмы не гарантируют теоретически минимальное количество компараторов, поэтому вы можете захотеть жестко закодировать оптимальную сеть.