Как можно улучшить эти функции преобразования регистра?

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

a_z('a' + 1);

Вызов не даст правильных результатов из-за приоритета оператора. Это легко исправить с помощью скобок:

#define a_z(c) ((c) >= 'a' && (c) <= 'z')

Но их также можно назвать так:

a_z(i++);

Этот вызов увеличит i вдвое! И это нелегко исправить (если вообще) в макросе. Вместо этого я бы рекомендовал использовать встроенные функции (при необходимости - см. Ниже).

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

Вам нужно два массива, по одному для каждого направления. Инициализируйте их как

char toUpper[128]; // we care only about standard ASCII
for (int i = 0; i < 128; i++)
  toUpper[i] = i;
toUpper['a'] = 'A';
...
toUpper['z'] = 'Z';

И преобразование тривиально:

char toUpperCase(char c)
{
  return toUpper[c];
}

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

Мои любимые:

*c += (*c-'A'<26U)<<5; /* lowercase */
*c -= (*c-'a'<26U)<<5; /* uppercase */
*c ^= ((*c|32U)-'a'<26)<<5; /* toggle case */

Поскольку вашей целью будут встроенные системы, вы должны научиться устранять ненужное раздувание кода, ветвления и т. Д. Условием для определения того, является ли символ ascii алфавитным, являются 4 операции сравнения / ветвления; у меня 1. Я бы порекомендовал поискать хорошие ресурсы по трюкам с арифметикой и битовыми манипуляциями.

Примечание. Я изменил *32 операции на <<5 после публикации своего ответа, потому что ряд компиляторов встроенных систем слишком плох, чтобы сделать это за вас. При написании кода для хорошего компилятора *32, вероятно, лучше проиллюстрирует ваши намерения.

Изменить. Что касается обвинения в том, что в моем коде слишком много неявных операций, генерируемых компилятором, я считаю, что это полностью неверно. Вот псевдо-асм, который любой полуприличный компилятор должен сгенерировать для первой строки:

1. Загрузить *c и расширить его нулем или знаком, чтобы заполнить слово размером int (в зависимости от того, является ли простой char знаковым или беззнаковым).
2. Вычтите константу 26 с помощью беззнаковой (без перегрузки) инструкции sub.
3. Условный переход за остальную часть кода, если флаг переноса не установлен.
4. В противном случае добавьте 32 к значению *c.

Шаги 2 и 3 могут быть объединены в архитектурах, которые используют операцию сравнения-перехода вместо флагов. Единственный способ увидеть, как возникают какие-либо значительные скрытые затраты, - это если машина не может напрямую адресовать символы или если она использует неприятное (знак / величина или дополнение) представление значения со знаком, и в этом случае преобразование в беззнаковое было бы нетривиально. Насколько мне известно, ни одна современная встраиваемая архитектура не имеет этих проблем; они в основном изолированы от устаревших мэйнфреймов (и, в меньшей степени, от DSP).

Если кого-то беспокоят плохие компиляторы, фактически выполняющие арифметические операции для <<5, вы можете попробовать:

if (*c-'A'<26U) *c+=32;

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

Редактировать 2: По запросу, версия первой строки без ответвлений:

*c += (64U-*c & *c-91U)>>(CHAR_BIT*sizeof(unsigned)-5);

*c += (64U-*c & *c-91U) >> CHAR_BIT*sizeof(unsigned)-1 << 5;

Чтобы это работало надежно, c должен иметь тип unsigned char *, а unsigned int должен быть строго шире, чем unsigned char.

ПРИМЕЧАНИЕ. Заголовок вопроса был отредактирован - исходный заголовок был посвящен оптимизации «Пожалуйста, критикуйте - оптимальная функция для преобразования строковых регистров в 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); 
}

Моя функция расширена для ясности и использует не жестко заданные константы. Вы можете сделать то же самое в одной строке с жестко запрограммированными значениями, но мне нравится читаемый код; однако вот «сжатая» версия моего алгоритма. Это не намного быстрее, так как оно ТОЧНО то же самое "сжимает" до одной строки.

c+=(((96-(int)c)&((int)c-123))>>9)&(-32);

Здесь вы можете сделать ряд оптимизаций, чтобы сделать его еще быстрее. Вы можете жестко закодировать более оптимальные числа для ASCII, потому что в примере не предполагается, что какое-либо отображение кодировки, кроме a-z, и A-Z являются смежными диапазонами. Например, с ASCII, если у вас нет переключателя, вы можете фактически изменить AsrBits на 4 (9-5), поскольку ConvertVal будет +/- 32 в зависимости от операции toupper или tolower.

Если у вас есть рабочие версии без ветвей, вы можете использовать методы SIMD или SWAR (SIMD в регистре) для преобразования 4–16 байтов за раз (или даже, возможно, больше в зависимости от того, насколько широки ваши регистры, и если вы развернете, чтобы скрыть задержку). Это будет намного быстрее, чем любой метод поиска, который в значительной степени ограничен однобайтовым преобразованием, если только у вас нет очень больших таблиц, которые растут экспоненциально на байт, обрабатываемый одновременно.

Кроме того, вы можете сгенерировать предикат без ветвей, не используя повышающее преобразование int, но тогда вам нужно будет выполнить еще пару операций (с повышающим преобразованием это всего лишь одно вычитание на диапазон). Возможно, вам потребуется выполнить расширенные операции для 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.

Итак, причины, по которым это должен быть самый быстрый способ:

1. Отсутствие штрафов за неверное предсказание ветвления
2. Возможность SIMD-алгоритма для 4-16 (и более) байтов за раз
3. Компилятор (или программист) может разворачивать и чередовать, чтобы устранить задержки и воспользоваться преимуществами суперскалярных (многозадачных) процессоров.
4. Нет задержек памяти (например, поиск по таблице)

Я не решился ответить на этот вопрос, потому что прошло более 20 лет с тех пор, как я работал с небольшими устройствами. Однако я думаю, что правила почти такие же (с одним возможным дополнением):

1. Минимизируйте доступ к памяти
2. Минимизируйте циклы ЦП
3. Минимизировать размер кода

Когда я разрабатывал низкоуровневый код, правило №1 затмило все остальные. На плате не было кэш-памяти, а память была невероятно медленной по сравнению с процессором; это причина того, что класс хранения «регистр» существует в C. Сегодня ситуация несколько изменилась, но это все еще одна из двух основных проблем. Как я прокомментировал к одному сообщению, таблица поиска - хорошая идея, но знайте, что это означает дополнительный доступ к памяти для каждого теста. Как только он попадает в кеш, это может не быть проблемой, но вы будете платить за несколько попаданий в кеш каждый раз, когда вводите функцию (если вы не вызываете ее так часто, что таблица поиска может оставаться в кеше) .

Правило номер 2 похоже на «да, конечно, вы хотите это сделать, почему это не правило №1?» но на самом деле рассуждения идут глубже. Фактически, в некотором смысле это повторение правила №1, поскольку каждая инструкция должна быть извлечена из памяти, прежде чем она может быть выполнена. Здесь есть тонкий компромисс: для процессора, работающего только с целыми числами, очевидным преимуществом является использование таблицы поиска для вычисления тригонометрических функций; на микросхеме со встроенной плавающей запятой, может, и нет.

Я не уверен, что правило № 3 все еще применяется. По моему опыту, всегда были попытки сократить код, уместить пресловутые 20 фунтов в 10-фунтовый мешок. Но похоже, что сегодня самый маленький мешок весит 50 фунтов. Однако даже с 50-фунтовым мешком (или многомегабайтным ПЗУ) для хранения вашего кода / данных вам все равно нужно вытащить его в кеш (если он у вас есть).

Новое правило №1: держите конвейер заполненным

Современные процессоры имеют глубокие конвейеры команд (если вы не знакомы с этим термином, см. Эту статью: http://arstechnica.com/old/content/2004/09/pipelining-1.ars/1). Общее практическое правило с глубокими конвейерами состоит в том, что ветвление - тест «если» - дорого обходится, потому что это означает, что конвейер, возможно, придется очистить для загрузки в новый код. Таким образом, вы пишете свой код для ветвления в маловероятном случае (см. Сообщение Adisak для возможно оправданной реализации без ветвления; +1, если можно).

Кто-то с более свежим опытом, чем я, вероятно, прокомментирует и скажет, что «современные процессоры загружают конвейер с обеими ветвями, поэтому нет штрафных затрат». Это все хорошо, но это приводит к общему правилу:

Правило 0: оптимизация зависит от вашей архитектуры и рабочей нагрузки

Микропроцессор в моей посудомоечной машине, вероятно, не имеет конвейера и, возможно, не имеет кеша. Конечно, он, вероятно, также не будет много обрабатывать текст. Или, может быть, есть и то, и другое; кажется, что на рынке всего несколько основных встраиваемых процессоров, так что, возможно, на этой плате стоит Pentium, а не производная от 8051. Даже в этом случае существует широкий спектр встроенных процессоров на базе Pentium (http://en.wikipedia.org/wiki/List_of_Intel_Pentium_microprocessors#Embedded_processors). То, что лучше для одного, может оказаться не лучшим для другого.

Затем возникает вопрос, какие данные вы обрабатываете. Если вы обрабатываете текст, то вероятно (но не гарантируется), что большая часть ваших данных будет состоять из букв, а не цифр или знаков препинания; так что вы можете оптимизировать для этого.

Однако есть еще кое-что: я прокомментировал «Только ASCII, а?» на ОП; другой комментатор был более явным: если вы обрабатываете текст в 2010 году, вы, вероятно, не обрабатываете ASCII. По крайней мере, вы будете иметь дело с ISO-8859-1 или аналогичным 8-битным набором символов. И в этом случае, возможно, решение no-branch или smart-branch (обращая внимание на конвейер) все равно будет быстрее, чем таблица поиска (да, это мое предположение). Но если вы имеете дело с Unicode BMP (16 бит), вам в значительной степени придется использовать эту таблицу, независимо от ее стоимости с точки зрения памяти, потому что нет простых правил, чтобы определить, что нижний, а какой верхний регистр. И если вы имеете дело с высшими уровнями Unicode ... ну, может быть, использование заглавных букв в "старом курсиве" не так важно (особенно потому, что в нем нет верхнего и нижнего регистра).

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

И наконец: очистить код FTW

Этот пост начался, когда я написал комментарий к OP о том, что его / ее использование макросов было плохой идеей (и не смог ввести его, потому что SO перешел в режим обслуживания). Питер Торок (извините, я не поддерживаю Unicode или даже ISO-8859-1) назвал одну причину, но есть и другую: это черные ящики.

OP выглядит красиво и чисто: короткий код, интенсивное использование побитовых и тернарных операторов, его легко понять, если вы понимаете язык. Но было бы намного легче понять реальную работу, если бы вы увидели A_Z в развернутом виде. Это могло заставить вас задуматься о том, сколько ветвлений вы выполняли, особенно в методе ToggleCase. А затем вы, возможно, подумали о том, как можно переупорядочить эти ветки, чтобы минимизировать количество реальных тестов, которые вы выполняете. И, возможно, подумал о поддержании трубопровода.

Хорошо, поехали. Запись на этой вкладке ... прокрутка кода на другой вкладке :-)

заголовок

1. #define a_z(c) (c >= 'a' && c <= 'z')

   • the name of the function like macro should be in ALL CAPS (maybe IS_LOWERCASE) to alert users it's a macro
   • c в расширении должен быть внутри скобок, чтобы предотвратить странные побочные эффекты
   • личный выбор: мне нравится переупорядочивать условия, чтобы они больше походили на английское 'a' ‹= c‹ = 'z' как (('a' <= (c)) && ((c) <= 'z'))

2. Я бы сделал так, чтобы функции void ToggleCase(char* c) возвращали char* (то же, что было отправлено), чтобы можно было использовать их последовательно: printf("%s\n", UpperCase(LowerCase("FooBar")));

исходный код

1. Тернарный оператор не делает ваш код более быстрым или легким для чтения. Я бы написал простой if

Вот и все.

Ой! Еще одна вещь: ваш код предполагает ASCII (вы сами так сказали), но не документирует это. Я бы добавил об этом примечание в заголовочный файл.

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

ANSI C включает необходимые функции в стандартную библиотеку, и, по-видимому, они были сильно оптимизированы для вашей архитектуры поставщиком компилятора.

Стандартный заголовок ctype.h включает функции tolower () и toupper ().

Первым делом я бы сказал переименовать a_z и A_Z во что-то вроде is_ASCII_Lowercase и is_ASCII_Uppercase. Это не так C-ish, но это легче понять.

Кроме того, использование ^= и ?: работает, но, опять же, я считаю его менее читаемым, чем простой if-оператор.

Возможно, я провел слишком много времени с C ++ и недостаточно с C, но я не большой поклонник макросов, у которых есть параметры ... как отмечает Питер Торок, они могут привести к некоторым проблемам. Ваше определение CASE_FLAG в порядке (оно не принимает никаких параметров), но вместо этого я бы заменил макросы a_z и A_Z функциями.

как насчет (почти работает):

char slot[] = { 0, 31, 63, 63 };
*c = slot[*c/32] + *c%32;

Пара вещей, которые можно изменить:

*c += a_z(*c)*CASE_FLAG; // adds either zero or three two
// you could also replace multiplication with the shift (1<<5) trick

строки на самом деле массивы:

char upper[] = "ABC..ABC..."; // 
...
*c = upper[*c+offset];

or

char upper[] = "ABC.."; // 
...
*c = upper[*c%32];

or

*c = 'A' + *c%32;

или как там ...

Мой подход - «обрезать только при необходимости».

В зависимости от вашей системы и архитектуры вашего процессора, многое можно сделать по-разному.

У меня есть несколько моментов в дизайне вашего кода. Во-первых, макросы. Макросы имеют несколько серьезных недостатков, и их следует использовать с осторожностью. Во-вторых, использование глобального переключателя регистра. Я бы переписал примерно так -

 enum CASE {UPPER, LOWER};

void ToggleCase(char* c, CASE newcase)
{
    if(newcase == UPPER)
       UpperCase(c);
    else if(newcase == LOWER)
       LowerCase(c);
    else 
       { ; } //null
}

С точки зрения микроэффективности это добавляет примерно 1 дополнительную инструкцию на вызов. Также может произойти некоторое ветвление, которое потенциально может вызвать промах в кеше.

void LowerCase(char* c)
{
  while (*c++)  //standard idiom for moving through a string.
  {
    *c = *c < 'Z' ? *c + 32 : *c;
  }
}


void UpperCase(char* c)
{
  while (*c++)
  {
    *c = *c > 'a' ? *c - 32 : *c;
  }
}

Теперь есть некоторые критические замечания в мой код.

Во-первых, ветвистый. Во-вторых, предполагается, что ввод [a-zA-Z] +. В-третьих, это только ASCII (как насчет EBDIC?). В-четвертых, предполагается нулевое завершение (некоторые строки имеют некоторые символы в начале строки - я думаю, Паскаль). В-пятых, не на 100% наивно очевидно, что код в верхнем / нижнем регистрах. Также обратите внимание, что ENUM - это плохо завуалированное целое число. Вы можете передать ToggleCase("some string", 1024), и он будет компилироваться.

Это не значит, что мой код очень плохой. Он служит и будет служить - только при определенных условиях.

Я использовал макросы, потому что, как мне кажется, они улучшают внешний вид кода и более эффективны, чем вызовы функций.

Это более эффективно? Каковы ваши требования к размеру кода? (Для сгенерированного исполняемого кода, а не для исходного кода C.) В современных настольных системах это редко является проблемой, и скорость имеет гораздо большее значение; но вы не предоставили нам никаких дополнительных сведений, помимо «приложений для встроенных систем», поэтому мы не сможем ответить на этот вопрос за вас. Однако здесь это не проблема, потому что код внутри макросов действительно такой маленький, но вы не можете предположить, что избегание вызовов функций всегда более эффективно!

Вы можете использовать встроенные функции, если вам разрешено. Они официально являются частью C с 1999 года, но гораздо дольше поддерживаются в нескольких компиляторах. Встроенные функции намного чище, чем макросы, но, опять же, в зависимости от ваших точных целевых требований, может быть трудно предсказать сгенерированный код из источника. Однако чаще люди застревают на устаревших (уже более десяти лет!) Компиляторах C, которые их не поддерживают.

Короче говоря, вы всегда должны знать свои точные требования, чтобы определить, что является оптимальным. Затем вам необходимо выполнить тест, чтобы проверить свои прогнозы производительности.

Если кто-то пытается обработать несколько байтов одновременно, я думаю, что лучшим подходом было бы заставить все значения быть 0..127, добавить 5 или 37 (что сделало бы 'z' к 'Z' равным 127), обратите внимание, что значение, а затем добавьте 26, обратите внимание на это значение, а затем немного измените. Что-то вроде:

unsigned long long orig,t1,t2,result;

t1 = (orig & 0x7F7F7F7F7F7F7F7F) + 0x0505050505050505;
t2 = t1 + 0x1A1A1A1A1A1A1A1A;
result = orig ^ ((~(orig | t1) & t2 & 0x8080808080808080) >> 2);

Хм ... Думаю, это неплохо работает, даже если адаптировано для 32-битной машины. Если в четыре регистра предварительно загружены правильные константы, ARM с оптимальным кодом, вероятно, сможет выполнять операции с семью инструкциями, занимая семь циклов; Я сомневаюсь, что компилятор найдет оптимизацию (или выяснит, что сохранение констант в регистрах было бы полезно - если константы не хранятся в регистрах, обработка байтов по отдельности будет быстрее).