ПРИМЕЧАНИЕ: заголовок вопроса был отредактирован - исходное название было об оптимизации " Пожалуйста, критикуйте - оптимальная функция для преобразования строковых падежей в C", которая объясняет, почему мой ответ имеет дело скорее только с оптимизацией чем в целом "улучшение" функций.
Если вы действительно ищете самый быстрый способ сделать это, версия без ответвлений будет подходить в долгосрочной перспективе, потому что она может использовать SIMD. Кроме того, он позволяет избежать таблиц (которые могут быть слишком большими во встроенной системе, если память действительно ограничена).
Вот простой пример без ветвления без SIMD, и ToLower - тривиальное изменение по сравнению с этим.
char BranchFree_AsciiToUpper(char inchar)
{
// Branch-Free / No-Lookup
// toupper() for ASCII-only
const int ConvertVal = 'A' - 'a';
// Bits to Shift Arithmetic to Right : 9 == (char-bits + 1)
const int AsrBits = 9;
int c=(int)inchar;
//if( (('a'-1)<c) && (c<('z'+1)) ) { c += 'A'-'a'; }
int LowerBound = ('a'-1) - c;
int UpperBound = c - ('z' + 1);
int BranchFreeMask = (LowerBound & UpperBound)>>AsrBits;
c = c + (BranchFreeMask & ConvertVal);
return((char)c);
}
Моя функция расширена для ясности и использует не жестко закодированные константы. Вы можете сделать то же самое в одной строке с жестко закодированными значениями, но мне нравится читаемый код; тем не менее, вот «сжатая» версия моего алгоритма. Это не быстрее, поскольку EXACT то же самое "сжалось" в одну строку .
c+=(((96-(int)c)&((int)c-123))>>9)&(-32);
Вы можете сделать ряд оптимизаций, чтобы сделать его еще быстрее. Вы можете жестко закодировать более оптимальные числа для ASCII, потому что в примере не предполагается, что какое-либо отображение кодирования, кроме a-z и A-Z, является смежными диапазонами. Например, в ASCII, если у вас нет переключателя ствола, вы можете изменить AsrBits на 4 (9-5), поскольку ConvertVal будет +/- 32 в зависимости от операции касания или подачи.
После того, как вы работаете с версиями без ветвления, вы можете использовать методы SIMD или SWAR (SIMD в регистре) с битовым переключением для преобразования 4-16 байт за раз (или даже возможно больше в зависимости от того, насколько широки ваши регистры и если вы развернетесь, чтобы скрыть задержку). Это будет намного быстрее, чем любой метод поиска, который в значительной степени ограничен однобайтовым преобразованием, если только у вас не очень большие таблицы, которые растут экспоненциально на байт, обрабатываемые одновременно.
Кроме того, вы можете генерировать предикат без ответвлений, не используя int upcasting, но затем вам нужно будет выполнить еще пару операций (при upcasting это всего лишь одно вычитание на диапазон). Возможно, вам придется выполнить расширенные операции для SWAR, но в большинстве реализаций SIMD есть операция сравнения, которая генерирует для вас маску бесплатно.
Операции SWAR / SIMD также могут выиграть от меньшего числа операций чтения / записи в память, а записи, которые происходят, могут быть выровнены. Это намного быстрее на процессорах, которые имеют штрафы за попадание в хранилище (например, процессор ячейки PS3). Добавьте к этому простую предварительную выборку в развернутой версии, и вы сможете почти полностью избежать сбоев памяти.
Я знаю, что в моем примере много кода, но есть ZERO ответвлений (неявных или явных) и, как следствие, ошибочных предсказаний переходов. Если вы работаете на платформе со значительными штрафами за неправильное предсказание ветвлений (что справедливо для многих конвейерных встроенных процессоров), то даже без SIMD ваша оптимизированная сборка выпуска вышеуказанного кода должна выполняться быстрее, чем то, что кажется гораздо менее сложным, но создает неявные ветви .
Даже без SIMD / SWAR умный компилятор может развернуть и перемежить вышеприведенную реализацию, чтобы скрыть задержки и получить очень быструю версию - особенно на современных суперскалярных процессорах, которые могут выдавать более одной независимой инструкции в цикл. Обычно это невозможно с любой из версий ветвления.
Если вы развернете вручную, я бы сгруппировал загрузки и собрал хранилища, чтобы компилятору было проще чередовать не ветвящиеся независимые инструкции между ними. Пример:
// Unrolled inner loop where 'char *c' is the string we're converting
char c0=c[0],c1=c[1],c2=c[2],c3=c[3]; // Grouped-Loads
c[0]=BranchFree_AsciiToUpper(c0);
c[1]=BranchFree_AsciiToUpper(c1);
c[2]=BranchFree_AsciiToUpper(c2);
c[3]=BranchFree_AsciiToUpper(c3);
c+=4;
Приличный компилятор должен иметь возможность встроить ToUpper и полностью перемежать приведенный выше код, так как между ними нет ветвей, псевдонимов и кодозависимых инструкций.Просто для удовольствия я решил скомпилировать это, и компилятор, нацеленный на PowerPC, сгенерировал идеальное чередование для суперскалярного ядра двух выпусков, которое легко превзойдет любой код с ветвями .
mr r31,r3
mr r13,r13
lbz r11,0(r31)
lbz r10,1(r31)
extsb r11,r11
lbz r9,2(r31)
extsb r10,r10
lbz r8,3(r31)
subfic r7,r11,96
addi r6,r11,-123
srawi r5,r7,9
srawi r4,r6,9
subfic r3,r10,96
addi r7,r10,-123
extsb r9,r9
srawi r6,r3,9
srawi r3,r7,9
subfic r7,r9,96
addi r30,r9,-123
extsb r8,r8
srawi r7,r7,9
srawi r30,r30,9
subfic r29,r8,96
addi r28,r8,-123
srawi r29,r29,9
srawi r28,r28,9
and r5,r5,r4
and r3,r6,r3
and r7,r7,r30
and r30,r29,r28
clrrwi r4,r5,5
clrrwi r6,r7,5
clrrwi r5,r3,5
clrrwi r7,r30,5
add r4,r4,r11
add r3,r5,r10
add r11,r6,r9
stb r4,0(r31)
add r10,r7,r8
stb r3,1(r31)
stb r11,2(r31)
stb r10,3(r31)
.доказательство в пудинге и вышеупомянутый скомпилированный код будет очень быстрым по сравнению с ветвящимися версиями даже до перехода к SWAR или SIMD.
Вкратце, причины, по которым этот метод должен быть самым быстрым:
- Нет штрафов за неверное предсказание ветвления
- Возможность использовать SIMD-ify алгоритм для 4-16 (или более) байтов за раз
- Компилятор (или программист) может развернутьи чередование для устранения задержек и использования суперскалярных (многозадачных) процессоров
- Без задержек в памяти (т. е. при просмотре таблиц)