Именно так. "У немца для всякого дела свой инструмент есть" :-)
Причём мы в итоге даже убрали из кода вилку по размеру, мол, меньше 10к сортируем стандартной сортировкой, а больше - своей. Ибо SoA, а не AoS, и для стандартной нужна обёртка, а абсолютная разница мизерная, на ТЕХ задачах - не стоящая усложнения кода, если правильно помню, меньше 20 микросекунд в худшем случае.
Это реально используется в HFT, но там таблицы маленькие - год-два от силы. Два года - это меньше 40 кб, живёт в L2, часто используемые поддиапазоны - в L1.
В исходниках там активно используется int128, с ним работает корректно уже лет десять как, если не больше. Правда, в исходниках есть специальные функции hi128/lo128 с очевидным функционалом. Ну и так-то понятно, что это просто высокоуровневая обёртка для старой традиции х86 использовать пару регистров для результата умножения или для делимого при делении.
Активно использовал её в реальном проде. Гонял тесты, чисто из любопытства. На имевшемся железе экспериментальная многопоточная сортировка (std::experimental::parallel_sort, кажись, Си++-14 это был или прототип) начинала отставать примерно на 10-20 тысяч ключей (точнее, пар ключ+нагрузка, там были варианты инт32/64/128/дабл ключ, нагрузка - один, два или три раза инт32), однопоточная сливалась ещё раньше. Многопоточный радикс в прод не пошёл, слишком грузит проц при незначительном выигрыше в скорости (там многопоточность высокая и несколько однопоточных радиксов отрабатывали интегрально быстрее). Учитывая, что сортировали десятками-сотнями миллионов - никакой квиксорт там и рядом не валялся. Константа большая, но зависит от реализации (надо правильно привязываться к размерам кэшей проца и префетч делать). "Тупо в лоб" - что угодно будет грустно. Так-то можно сказать, что и пузырёк - супер-пупер сортировка: три элемента быстрее не отсортируешь, а оверхед примерно нулевой! :-)
По поводу упора в процессор при параллельной сортировке - скорее всего, не совсем так.
Несколько лет назад весьма плотно занимался реализацией радиксной сортировки, в том числе параллельной, с оптимизацией под кэш процессора и всё такое. Результат - заметный рост скорости примерно до 20 потоков и потом резкий выход на плато. Небольшое исследование показало, что упор в контроллер памяти - 6 каналов по 2 регистровых модуля, итого 24 потока доступа, из которых два-три-четыре (в зависимости от фазы Луны) отъедаются операционкой и другими процессами. При этом - вполне ощутимые накладные расходы на синхронизацию. В итоге в прод ушла однопоточная версия, которая обгоняла классику начиная примерно с 10к ключей (ключи 32/64/128 бит или даблы, нагрузка - 32, 2*32 или 3*32 целые числа, SoA, порог обгона от комбинации ключа/нагрузки почти не зависел, у меня шаг размера тестовых массивов был больше).
Именно так. "У немца для всякого дела свой инструмент есть" :-)
Причём мы в итоге даже убрали из кода вилку по размеру, мол, меньше 10к сортируем стандартной сортировкой, а больше - своей. Ибо SoA, а не AoS, и для стандартной нужна обёртка, а абсолютная разница мизерная, на ТЕХ задачах - не стоящая усложнения кода, если правильно помню, меньше 20 микросекунд в худшем случае.
Это реально используется в HFT, но там таблицы маленькие - год-два от силы. Два года - это меньше 40 кб, живёт в L2, часто используемые поддиапазоны - в L1.
В исходниках там активно используется int128, с ним работает корректно уже лет десять как, если не больше. Правда, в исходниках есть специальные функции hi128/lo128 с очевидным функционалом. Ну и так-то понятно, что это просто высокоуровневая обёртка для старой традиции х86 использовать пару регистров для результата умножения или для делимого при делении.
HFT. Там, правда, на рабочие диапазоны делают таблицы, можно уложиться в 40 кб примерно и всё будет за одно обращение в L2 (а то и в L1).
У меня счас по работе разбор даты ВНЕЗАПНО стал бутылочным горлышком, но там исходно вообще Poco::DateTime было, оно удобное, но дико тормозное.
Активно использовал её в реальном проде. Гонял тесты, чисто из любопытства. На имевшемся железе экспериментальная многопоточная сортировка (std::experimental::parallel_sort, кажись, Си++-14 это был или прототип) начинала отставать примерно на 10-20 тысяч ключей (точнее, пар ключ+нагрузка, там были варианты инт32/64/128/дабл ключ, нагрузка - один, два или три раза инт32), однопоточная сливалась ещё раньше. Многопоточный радикс в прод не пошёл, слишком грузит проц при незначительном выигрыше в скорости (там многопоточность высокая и несколько однопоточных радиксов отрабатывали интегрально быстрее). Учитывая, что сортировали десятками-сотнями миллионов - никакой квиксорт там и рядом не валялся.
Константа большая, но зависит от реализации (надо правильно привязываться к размерам кэшей проца и префетч делать). "Тупо в лоб" - что угодно будет грустно.
Так-то можно сказать, что и пузырёк - супер-пупер сортировка: три элемента быстрее не отсортируешь, а оверхед примерно нулевой! :-)
Как раз для больших - очень даже практично. Радиксная сортировка.
По поводу упора в процессор при параллельной сортировке - скорее всего, не совсем так.
Несколько лет назад весьма плотно занимался реализацией радиксной сортировки, в том числе параллельной, с оптимизацией под кэш процессора и всё такое. Результат - заметный рост скорости примерно до 20 потоков и потом резкий выход на плато. Небольшое исследование показало, что упор в контроллер памяти - 6 каналов по 2 регистровых модуля, итого 24 потока доступа, из которых два-три-четыре (в зависимости от фазы Луны) отъедаются операционкой и другими процессами. При этом - вполне ощутимые накладные расходы на синхронизацию. В итоге в прод ушла однопоточная версия, которая обгоняла классику начиная примерно с 10к ключей (ключи 32/64/128 бит или даблы, нагрузка - 32, 2*32 или 3*32 целые числа, SoA, порог обгона от комбинации ключа/нагрузки почти не зависел, у меня шаг размера тестовых массивов был больше).