Я тут как раз небольшую рутину для radix sort тестировал, и понял, что размер строки кэша L1 – вот где настоящая проблема. Пробовал когда-нибудь полностью векторизованную версию, которая ещё и выравнивает корзины по кэшу?

Конечно. Чтобы получить следующее число, кратное степени двойки, для 32-битного слова, можно сделать так: вычитаешь единицу, потом выполняешь операции "или" со сдвигами — x |= x >> 1, x |= x >> 2, x |= x >> 4, x |= x >> 8, x |= x >> 16, и затем прибавляешь единицу. Это "зажимает" любое число, не являющееся степенью двойки, округляя его до следующей большей степени. Для сканирования битов используй инструкцию bsf процессора, если пишешь на ассемблере; на C можно использовать __builtin_ctz, чтобы найти индекс младшего установленного бита. Если нужен индекс старшего — используй __builtin_clz. А для обнуления младшего установленного бита делай x &= x - 1. Эти приемы позволяют тебе оставаться в области целочисленных операций, без сюрпризов с плавающей точкой, и они работают быстро на современных конвейерах.

Просто подумал: если у тебя основание системы — 256, количество корзин всегда будет степенью двойки, и тогда вместо операции взятия остатка можно использовать маску. Это сэкономит одну инструкцию деления и позволит компилятору держать индекс в регистре. И еще, если расположить корзины в массиве непрерывно и выровнять по 64 байта, избежишь разбиения строк кэша при записи. И не забудь использовать ключевое слово "restrict" для указателей на источник и назначение – компилятор без проблем вынесет цикл из вложенности, если увидит, что алиасинг невозможен.

Проверь, пожалуйста, чтобы ты случайно не обнулил защитные записи; последний контейнер немного сложнее. Удачи в поисках.