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

Ответ 1

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

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

Ответ 2

Мои избранные:

*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, вероятно, лучше иллюстрирует ваше намерение.

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

• Загрузите *c и добавьте нуль или знак - заполните его, чтобы заполнить слово int (в зависимости от того, подписана ли простая char или без знака).
• Вычитайте константу 26, используя инструкцию unsigned (non-overflow-trapping) sub.
• Условный переход через остальную часть кода, если флаг переноса не установлен.
• Осталось добавить 32 к значению в *c.

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

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

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

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

Изменить 2: По запросу версия без ветвей первой строки:

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

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

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

Ответ 3

ПРИМЕЧАНИЕ: Название вопроса было отредактировано - исходное название было посвящено оптимизации " Критику критики - оптимальная функция для преобразования строковых событий в 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 или бит-twiddling SWAR (SIMD Within A Register) для преобразования 4-16 байтов за раз ( или даже, возможно, больше зависит от того, насколько широки ваши регистры, и если вы разворачиваете, чтобы скрыть латентность). Это будет намного быстрее, чем любой метод поиска, который в значительной степени ограничен однобайтовым преобразованием, если у вас нет чрезвычайно больших таблиц, которые растут экспоненциально для каждого байта, обрабатываемого одновременно.

Кроме того, вы можете сгенерировать предикат branchfree без использования int upcasting, но тогда вам нужно сделать еще пару операций (с повышением уровня его только одного вычитания за диапазон). Возможно, вам придется выполнять расширенные операции для SWAR, но большинство реализаций SIMD имеют операцию сравнения, которая будет генерировать маску для вас бесплатно.

Операции SWAR/SIMD также могут выиграть от меньшего количества чтений/записи в память, и записи, которые могут произойти, могут быть выровнены. Это намного быстрее на процессорах, у которых есть штрафы за загрузку при загрузке (например, Cell Cell Processor). Объедините это с простой предварительной выборкой в ​​развернутой версии, и вы можете почти полностью избежать хранилищ памяти.

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

Ответ 4

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

заголовок

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

  • имя функции, такой как macro, должно быть во ВСЕХ CAPS (возможно, IS_LOWERCASE), чтобы предупредить пользователей о макросе
  • c в расширении должно быть внутри скобок, чтобы предотвратить странные побочные эффекты
  • личный выбор: мне нравится переупорядочивать условия, чтобы больше походить на английский 'a' <= c <= 'z' как (('a' <= (c)) && ((c) <= 'z'))

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

исходный код

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

Что это.

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

Ответ 5

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

• Сведение к минимуму доступа к памяти
• Свернуть циклы процессора
• Свернуть размер кода

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

Правило № 2 похоже на "duh, конечно, вы хотите это сделать, почему это не правило № 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-битным набором символов. И в этом случае, возможно, решение без ветки или смарт-ветки (обращая внимание на конвейер) будет по-прежнему быстрее, чем таблица поиска (да, это предположение с моей стороны). Но если вы имеете дело с Unicode BMP (16 бит), вам в значительной степени придется использовать таблицу, независимо от ее стоимости с точки зрения памяти, потому что нет простых правил для определения того, что ниже или в верхнем регистре. И если вы имеете дело с более высокими плоскостями Юникода... ну, возможно, капитализация "Старого курсив" не так важна (особенно потому, что она не имеет верхнего и нижнего регистров).

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

Наконец: Clear Code FTW

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

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

Ответ 6

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

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

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

Ответ 7

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

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

Ответ 8

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

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];

или

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

или

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

или что-то еще...

Ответ 9

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

Ответ 10

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

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

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

 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?). В-четвертых, он предполагает нулевое завершение (некоторые строки имеют некоторые символы в начале строки - Pascal, я думаю). В-пятых, это не на 100% наивно очевидно, что верхний/нижний регистр кода. Также обратите внимание, что ENUM является сильно завуалированным целым числом. Вы можете передать ToggleCase("some string", 1024) и скомпилировать его.

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

Ответ 11

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

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

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

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

Ответ 12

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