Это спецификация процессора c, относящаяся к внутреннему кешу и способу его реализации. В случае процессоров X86 может быть 3 или 4 уровня кеша, и обычно они связаны с 8 путями.
Некоторые процессоры также чувствительны к расположению кода в тесных циклах. В моей системе я видел до 40% разницы во времени выполнения для идентичного кода, где единственная разница - это nops между функциями, которые я использовал для выравнивания их по четным или нечетным 16-байтовым границам.
Для использования radix сортировка по 32- или 64-битным целым числам без знака, база 256 кажется наилучшей. Я выполнил тест для сортировки 36 миллионов псевдослучайных 64-разрядных целых чисел без знака, используя размеры полей битов {8,8,8,8,8,8,8,8} (основа 256), принимая 8 проходов. Я попытался использовать {11,11,11,11,10,10} (база 2048 или 1024), взяв 6 проходов, и это заняло вдвое больше времени (~ 2 секунды против ~ 1 секунды), проблема, связанная с реализацией кэша на моем процессоре. Я также попробовал {16,16,16,16} (основа 65536), 4 прохода, и это заняло почти 2,5 секунды.
Можно рассмотреть относительно небольшие значения m . Если m равно <= 65536, то основа сортировки по основанию 256 (2 ^ 8) может быть выполнена за 2 прохода. Если сортировка целых чисел и <em>m достаточно мала, то сортировка с однократным проходом, которая генерирует отсортированный вывод на основе подсчета, а не на самом деле, сортирует данные быстрее.