небольшая разгадка для программистов

[avva]

Итак, подробное обсуждение вчерашней загадки: что именно делает функция

unsigned char func(unsigned char c) {
  return c - 128 + (c >> 5&3)["(PI)"];
}

и как она это делает?


Правильный ответ: эта функция переводит шестнадцатиричную цифру в ее значение, причем как большие буквы, так и маленькие. Иными словами, эта функция переводит '0'...'9' в 0..9, 'A'...'F' в 10...15, и 'a'...'f' в 10...15. Подходящее название для этой функции - hex2int (или hex_to_int, или HexToInt, как пожелаете).

Первым правильный ответ дал renatm, второй - ashalynd. Потом еще многие дали правильный ответ. Некоторые комментаторы справедливо заметили, что функция работает не только для 16-ричных цифр, но и для других оснований, до конца алфавита. Это верно, но скорее побочный эффект, а не задумано так: в оригинале функция назывались HexToInt.

Немного о том, как это происходит. Запись "c >> 5&3" специально обманчива, потому что очередность операторов такова, что на самом деле это (c >> 5) & 3. Т.е. вынимаем из c шестой и седьмой биты. Далее, странное применение оператора [] - это старый трюк, который иногда используется для специального усложнения исходников, и больше ни на что особенно не годен. Дело в том, что в стандартах C и C++ значение оператора [] определяется так: a[b] это ровно то же самое, что *(a+b). Это формальное выражение известного принципа о том, что работа с массивами в C сводится (по большей части) к арифметике с указателями. А это значит, что, например, a[1] и 1[a] - совершенно одно и то же, хотя второй вариант выглядит странно и в нормальных программах никто так никогда не пишет.

Так что эта часть функции сводится к "(PI)"[(c>>5) &3]. Это значит, что из c мы вычитаем 128, а потом прибавляем, в зависимости от 6-7 бит c, одно из чисел 40, 80, 73, 41 (численные значения '(', 'P', 'I', ')' ).
Поскольку вся арифметика тут 8-битная беззнаковая (unsigned), то тот факт, что при вычитании 128 мы можем перепрыгнуть в верхние 128 байт, а потом при прибавлении перепрыгнуть 0 обратно, никакой роли не играет, и можно это упростить так: -128 + 40/80/73/41 все равно, что -88/-48/-55/-87, в зависимости от шестого-седьмого бита c. Ну а теперь осталось заметить, что это можно написать так: -88 / -'0' / -('A'-10) / -('a'-10), а также заметить, что для символов '0'..'9', 'A'..'F', 'a'..f' шестой и седьмой биты получаются соответственно 1, 2 и 3. Теперь, надеюсь, понятно, почему получается желаемый результат. Первое число из четырех - оно же левая скобка '(' - вообще никакой роли не играет, и я выбрал ее просто для симметрии, чтобы получилась красивая строка (PI).

До того, как над ней поработали усложнители (до меня - еще несколько коллег на внутренней рассылке), исходная функция выглядела так:

inline unsigned char HexToInt(unsigned char c) {	 
  DCHECK(IsHexDigit(c));	 
  static unsigned char kOffset[4] = {0, 0x30u, 0x37u, 0x57u};	 
  return c - kOffset[(c >> 5) & 3];	 
}	 

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

Наверное, кому-то может быть интересно знать, зачем вообще писать эту функцию таким странным и непонятным способом, а не очевидный код, который проверяет, находится ли символ между '0' и '9', и тогда вычитает '0', потом между 'A' и 'F', и так далее. Все это можно написать одним выражением, используя оператор ?:, конечно. Этот вопрос затрагивает интересные и весьма нетривиальные соображения насчет оптимизации кода для современных CPU. С одной стороны, чем меньше код обращается к памяти, тем лучше, потому что обращение к памяти, особенно не попадающее в кэш процессора, занимает в наше время астрономическое время по сравнению с операциями в регистрах - в десятки или сотни раз дольше. Да и даже если обращение попадает в кэш, это может означать, что что-нибудь другое полезное туда не попадет, он ведь не резиновый. Поэтому, казалось бы, эта версия с массивом должна быть медленней, чем "очевидный" код, который я описал выше. Но с другой стороны, в "очевидной" версии есть условные переходы (после сравнения мы выбираем, что дальше делать), а они на современных архитектурах тоже весьма дороги, потому что если процессору не удастся верно угадать, какой из двух выборов ему предстоит совершить, то ему придется обнулить конвейер (flush the pipeline) уже прочитанных и приготовленных инструкций.

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

В качестве подарка тем, кто дочитал до конца - еще две версии функции HexToInt; подозреваю, что они обе быстрее тех двух, что я рассматривал выше. Несомненно, вы сами теперь сможете разобраться, как они работают.

Первая версия взята из исходников SQLite:

return (c + 9*(1 & (c>>6))) & 15;

Вторую версию написал на рабочей рассылке коллега по имени Дэвид Тернер:

return c - (0x57373000 >> (c >> 5)*8);

Comments

[(Anonymous)]

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

Скажите, а вы там проверяли на практике результаты или это ради развлечения?

[avva.livejournal.com]

Простите, не очень понял, какой из вариантов вы называете "функцией по таблице".

В ответ на ваш вопрос: это чисто ради развлечения. Полгода назад, когда эту функцию удалили из исходников Хрома, это было не потому, что она быстрее или медленнее, а чтобы код использовал одну стандартную фунцкию для этого дела, а не десять разных[1], которые накопились в разных местах.

Вообще не очень легко представить естественные обстоятельства, при которых оптимизация этой функции может дать нетривиальный вклад в performance. 16-ричные цифры должны придти из какого-то источника - например, файла или веб-страницы - и тогда время, затраченное в I/O на чтение этой цифры, на несколько порядков больше времени любого из вариантов HexToInt(). Если, может быть, кто-то делает очень интенсивные вычисления на 16-ричных строках, переводя их в числа и обратно миллионы раз все время - но кто ж будет так извращаться.

[1] Я не знаю точно, сколько их было, скорее всего меньше десяти.

[(Anonymous)]

я думаю, коллега имеет в виду что-то такое:

unsigned char hex2int (unsigned char c)
{
  static unsigned char n[256] = { /* что-то */};
  return n[c];
}
обработка ошибок пропущена, как и в исходной функции.

[(Anonymous)]

ммм... Скажем так, создаем char[255] и заполняем, а потом c масива возвращаем значение.
А вот конкретно то что я имею ввиду

char foo[255] ;

void init()
{
char i;
// собственно, тут скорость не имеет значительного влияния, можно и через if делать
for(i=0; i!=255; i++)
foo[i] = i - 128 + (i >> 5&3)["(PI)"];
}

unsigned char func(unsigned char c)
{
return foo[c];
}

Я проверял в простом цикле на 90000000 итераций, на сервере где я это делал(Xeon X5365)
для вашей ф-ции время в районе 410-450мс, для условного перехода 440-490.

И потом решил проверить этот вариант -- 320-390 мс. Учитывая обращения к памяти результат немного странный, конечно.

[avva.livejournal.com]

А, я просто не понял - думал, что вы говорите о каком-то из решений в моей записи. Да, конечно, это отлично работает. Наверное, понятно, почему быстрее - весь массив после первых нескольких итераций плотно сидит в L1-кэше, и доступ к нему очень быстрый. Если замерить скорость одного вызова сразу после начала работы программы или после очистки кэша(например, с помощью счетчика rdtsc), то думаю, что будет намного медленнее, чем варианты без обращения к памяти.

[igogo3000.livejournal.com]

Кстати да, в этом смысле сабжевый вариант существенно хуже оригинального (из Хрома), ибо в оригинальном память под "(PI)" на стеке выделялась. А стек, как известно, закэширован.

[avva.livejournal.com]

Вы уверены в этом? Мне казалось, что на x86 обычно константные строки выделяются всегда в секции .data и компилятор просто загружает в регистр константное значение указателя.

(если я прав, то можно все равно выделить 32-битную переменную на стеке, записать в нее "(PI)", и с помощью кастов сделать все как надо. Но код будет тогда зависеть от little endian/big endian).

[igogo3000.livejournal.com]

Так и есть. Но секция .data может оказаться вне кэша, и массив придется читать из памяти.

Не надо 32-битную переменную, можно просто

unsigned char func(unsigned char c) {
  char pi[] = "(PI)";
  return c - 128 + (c >> 5&3)[pi];
}

gcc сам преобразует "(PI)" в 32-битное число (даже без оптимизации) :)

[avva.livejournal.com]

это он молодец :-)

[igogo3000.livejournal.com]

Даже если бы он не был молодцом, он, как я понимаю, должен был выделить память на стеке, ибо в

type var[] = { ... };

как и в

type var[5];

переменной type* var образовываться не должно (иначе необъяснимо было поведение sizeof(var), например).

[igogo3000.livejournal.com]

... если конечно это не

static type var[] =

, как и было в коде Хрома (что-то я упустил это). В этом случае, конечно, var указывает кудато в .data, и все плохо :)

[avva.livejournal.com]

Э, у компилятора нет проблемы с тем, чтобы выделить память для массива в .data, а не на стеке, и меж тем не считать var указателем. Собственно, и на стек указатели вполне существуют без проблем. Это если определить переменную как register, вот тогда указатель на нее не может существовать.

На уровне ассемблера любой C-массив - указатель. На уровне самого языка имя массива не является указателем (именно для того, чтобы работал sizeof(), в частности), но попытка доступа к нему, т.е. использование имени массива в арифметическом контексте, низвергает его до статуса указателя.

[igogo3000.livejournal.com]

>>> Э, у компилятора нет проблемы с тем, чтобы выделить память для массива в .data, а не на стеке, и меж тем не считать var указателем

Да, так он и детает, если написано static type var[]. А если без static, то, может быть, не делает их соображений типа того, что память под локальные переменные должна быть освобождена по выходу из блока...

>>> Это если определить переменную как register, вот тогда указатель на нее не может существовать

Не спорю :). Но компилятор не создаст автоматически указатель на область памяти, выделенную как например "char s[5];", ибо "char s[5];" означает всего навсего создание объекта размера 5 так же как "int i;" означает создание объекта размера 4.

>>> На уровне ассемблера любой C-массив - указатель

Нет, часто на уровне ассемблера массива вообще не существует. Например, код

void f()
{
  int vars[2];
  vars[0] = 1;
  vars[1] = 2;
  ...
}

после компиляции неотличим от

void f()
{
  int var1;
  int var2;
  var1 = 1;
  var2 = 2;
  ...
}

хотя в первом варианте массив есть, а во втором - нету.

[avva.livejournal.com]

Но компилятор не создаст автоматически указатель на область памяти, выделенную как например "char s[5];", ибо "char s[5];" означает всего навсего создание объекта размера 5 так же как "int i;" означает создание объекта размера 4.

Но если где-то будет выражение s[some_index], то ему придется-таки создавать указатель, не так ли? Независимо от того, на стеке этот массив, или не на стеке. Это, собственно, то, что я хотел сказать: что принципиальной разницы между стеком и секцией данных с точки зрения использования указателей для компилятора не должно быть. Может быть так, что в случае массива, к-й он хочет выделить на стеке, компилятор рассматривает возможность относиться к нему, как к списку переменных, и анализирует для этого код (и скажем, если в коде есть обращения по неизвестным во время компиляции индексам, отказывается от этой оптимизации), а в случае глобального массива он даже не рассматривает такую возможность. Но это уж решение компилятора, модель памяти x86 ему не мешает.

[igogo3000.livejournal.com]

>>> Но если где-то будет выражение s[some_index], то ему придется-таки создавать указатель, не так ли?

Если он и создаст указатель, то это будет не указатель "s", а "s + some_index", но может и не создать никакого. На моем amd64, gcc (без оптимизации) операцию "положить в eax значение s[some_index]" выполняет одной инструкцией, которая является лишь усложненным вариантом инструкции "положить в eax значение локальной переменной x" - т.е. без промежуточных шагов построения указателя (и хранения его в памяти или в регистре).

>>> принципиальной разницы между стеком и секцией данных с точки зрения использования указателей для компилятора не должно быть

Я хотел бы согласиться, но не понял, что Вы в данном контесте называете указателями :). Началось все с того, что главное отличие: стек закеширован, а .data - черте где.

Собственно, что я отстаиваю (не зная, соглашаетесь Вы с этим, или нет): в примере

void f(int i)
{
  const char s2[] = "abc";
  static const char s3[] = "abc"; 
  const char *s4  = "abc";

  char c1 = "abc"[i];
  char c2 = s2[i];
  char c3 = s3[i];
  char c4 = s4[i];
}

Значение c1 будет получено через сдвиг зашитой в бинарник прямо в месте использования константы - адреса глобальной "abc";

c2 - через сдвиг регистра ebp с прибавлением зашитой в бинарник в месте использования константой - расположением s1 в стековом фрейме;

c3 - так же, как c1;

c4 - через сдвиг адреса, прочитанного из стека по адресу расположения s4, равному (чудом) тому, что был зашит в месте получения c1. Вот это и есть настоящий массив и настоящий указатель, а остальное - игрушки. С массивами в куче работают только так.

>>> Может быть так, что в случае массива, к-й он хочет выделить на стеке, компилятор рассматривает возможность относиться к нему, как к списку переменных, и анализирует для этого код

Подозреваю, что это не прихоть компилятора, а требование языка - выделять локальные массивы на стеке. И никакой "оптимизации", от которой компилятор мог бы "отказаться" тут нет - доступ к элементам массива осуществляется через сдвиги на фиксированное или не фиксированное число регистра ebp и взятие значения по полученному адресу (все одной инструкцией).

Хотя все может быть.

[igogo3000.livejournal.com]

опечатка: "расположением s1 в стековом фрейме;" -> "расположением s2 в стековом фрейме;" :)

[igogo3000.livejournal.com]

Что странного в этом результате? При первом же обращении результат попадает в кэш, и все работает как нельзя быстрее.

А массив можно статически инициализировать. Даже пожалуй нужно.

[(Anonymous)]

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