небольшая разгадка для программистов
Mar. 4th, 2011 03:24 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaИтак, подробное обсуждение вчерашней загадки: что именно делает функция
и как она это делает?
Правильный ответ: эта функция переводит шестнадцатиричную цифру в ее значение, причем как большие буквы, так и маленькие. Иными словами, эта функция переводит '0'...'9' в 0..9, 'A'...'F' в 10...15, и 'a'...'f' в 10...15. Подходящее название для этой функции - hex2int (или hex_to_int, или HexToInt, как пожелаете).
Первым правильный ответ дал![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
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).
До того, как над ней поработали усложнители (до меня - еще несколько коллег на внутренней рассылке), исходная функция выглядела так:
Она была в одном из исходных файлов браузера Chrome, но полгода назад ее убрали, когда кто-то справедливо решил методически убить расплодившиеся функции перевода шестнадцатеричных цифр. Вот чекин, в котором ее убивают.
Наверное, кому-то может быть интересно знать, зачем вообще писать эту функцию таким странным и непонятным способом, а не очевидный код, который проверяет, находится ли символ между '0' и '9', и тогда вычитает '0', потом между 'A' и 'F', и так далее. Все это можно написать одним выражением, используя оператор ?:, конечно. Этот вопрос затрагивает интересные и весьма нетривиальные соображения насчет оптимизации кода для современных CPU. С одной стороны, чем меньше код обращается к памяти, тем лучше, потому что обращение к памяти, особенно не попадающее в кэш процессора, занимает в наше время астрономическое время по сравнению с операциями в регистрах - в десятки или сотни раз дольше. Да и даже если обращение попадает в кэш, это может означать, что что-нибудь другое полезное туда не попадет, он ведь не резиновый. Поэтому, казалось бы, эта версия с массивом должна быть медленней, чем "очевидный" код, который я описал выше. Но с другой стороны, в "очевидной" версии есть условные переходы (после сравнения мы выбираем, что дальше делать), а они на современных архитектурах тоже весьма дороги, потому что если процессору не удастся верно угадать, какой из двух выборов ему предстоит совершить, то ему придется обнулить конвейер (flush the pipeline) уже прочитанных и приготовленных инструкций.
Поэтому я не знаю точно, какая из двух версий функции HexToInt - "очевидная", сравнивающая символы, или "странная", приведенная выше, быстрее на практике. Подозреваю, что зависит от того, как часто она вызывается: если миллионы раз подряд, то наверняка быстрее "странная", потому что вспомогательный массив будет плотно сидеть в кэше все время; если редко, то "очевидная" может оказаться быстрее. В любом случае, если нет необходимости оптимизировать именно эту функцию - а такую функцию почти никогда нет нужды оптимизировать - я лично написал бы "очевидную" версию, конечно - именно потому, что ее легче прочесть и сразу понять.
В качестве подарка тем, кто дочитал до конца - еще две версии функции HexToInt; подозреваю, что они обе быстрее тех двух, что я рассматривал выше. Несомненно, вы сами теперь сможете разобраться, как они работают.
Первая версия взята из исходников SQLite:
Вторую версию написал на рабочей рассылке коллега по имени Дэвид Тернер:
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);
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2011-03-04 01:33 pm (UTC)Я пока так и не знаю, как это делается.
no subject
Date: 2011-03-04 01:41 pm (UTC)no subject
Date: 2011-03-04 01:44 pm (UTC)no subject
Date: 2011-03-04 01:46 pm (UTC)no subject
Date: 2011-03-04 01:50 pm (UTC)return c - (0x57373000 >> ((c >> 5) << 3));
должно бы быть ещё быстрее.
no subject
Date: 2011-03-04 01:53 pm (UTC)Вообще интересно было бы сравнить ассемблер, а не реализацию на C.
no subject
Date: 2011-03-04 01:57 pm (UTC)no subject
Date: 2011-03-04 02:02 pm (UTC)Моё образование можно считать "неправильным": я пришёл из ассемблера, поэтому отношусь к всем компиляторам с известным недоверием. Понятно, что это контрпродуктивно, но я и не занимаюсь программированием профессионально.
no subject
Date: 2011-03-04 02:09 pm (UTC)no subject
Date: 2011-03-04 02:10 pm (UTC)no subject
Date: 2011-03-04 02:10 pm (UTC)no subject
Date: 2011-03-04 02:12 pm (UTC)Собственно, вот:
00000000004004e0 <func>:
4004e0: 8d 47 80 lea -0x80(%rdi),%eax
4004e3: 40 c0 ef 05 shr $0x5,%dil
4004e7: 83 e7 03 and $0x3,%edi
4004ea: 02 87 4c 06 40 00 add 0x40064c(%rdi),%al
4004f0: c3 retq
4004f1: 66 66 66 66 66 66 2e nopw %cs:0x0(%rax,%rax,1)
4004f8: 0f 1f 84 00 00 00 00
4004ff: 00
0000000000400500 <HexToInt>:
400500: 89 fa mov %edi,%edx
400502: 89 f8 mov %edi,%eax
400504: c0 ea 05 shr $0x5,%dl
400507: 83 e2 03 and $0x3,%edx
40050a: 2a 82 51 06 40 00 sub 0x400651(%rdx),%al
400510: c3 retq
400511: 66 66 66 66 66 66 2e nopw %cs:0x0(%rax,%rax,1)
400518: 0f 1f 84 00 00 00 00
40051f: 00
0000000000400520 <SQLitehtoi>:
400520: 89 fa mov %edi,%edx
400522: c0 ea 06 shr $0x6,%dl
400525: 83 e2 01 and $0x1,%edx
400528: 8d 04 d5 00 00 00 00 lea 0x0(,%rdx,8),%eax
40052f: 8d 14 10 lea (%rax,%rdx,1),%edx
400532: 8d 04 3a lea (%rdx,%rdi,1),%eax
400535: 83 e0 0f and $0xf,%eax
400538: c3 retq
400539: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
0000000000400540 <Turnerhtoi>:
400540: 89 f9 mov %edi,%ecx
400542: ba 00 30 37 57 mov $0x57373000,%edx
400547: 89 f8 mov %edi,%eax
400549: c0 e9 05 shr $0x5,%cl
40054c: 0f b6 c9 movzbl %cl,%ecx
40054f: c1 e1 03 shl $0x3,%ecx
400552: d3 fa sar %cl,%edx
400554: 28 d0 sub %dl,%al
400556: c3 retq
400557: 66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1)
40055e: 00 00
Компиляторы не всесильны, однако умножение на степень двойки уже давно освоили :)
no subject
Date: 2011-03-04 02:12 pm (UTC)movzx ecx, byte ptr [ebp+08]
sar ecx, 05
shl ecx, 03
mov edx, 57373000
sar edx, cl
sub eax, edx
Это Visual Studio 2008.
no subject
Date: 2011-03-04 02:19 pm (UTC)no subject
Date: 2011-03-04 02:20 pm (UTC)Какая там сейчас строка кеша используется...
no subject
Date: 2011-03-04 02:23 pm (UTC)Мозговой штурм предложил следующую формализацию задачи: 16-битный x86, исходно в некотором (по желанию программиста) 8-битном регистре находится нужный байт, содержимое прочих регистров неизвестно; на выходе в 16-битном регистре (тоже по выбору программиста) находятся ASCII-коды двух 16-ричных цифр, составляющих этот байт, в любом удобном регистре.
В общем, задачу мы всё равно не решили. Лучшим приближением стал найденный в какой-то книжке способ визуализации половинки байта за 5 байт.
no subject
Date: 2011-03-04 02:58 pm (UTC)В режиме отладки *8 переводится как "shl ecx, 03" (хорошо). В режиме оптимизатора он выдал три подряд "add ecx, ecx" (что лично меня вдохновляет уже меньше).
Вариант с >>3 переводится как "shl ecx, 03" (логично); оптимизатор же предпочитает
sar ecx, 02
and ecx, FFFFFFF8
т.е. return c - (0x57373000 >> ((c >> 2) & 0xF8));
что на любых платформах будет как минимум не хуже.
Мораль: если бы этот код был узким местом, данный оптимизирающий компилятор не справился бы как следует даже с умножением на 8.
no subject
Date: 2011-03-04 03:22 pm (UTC)no subject
Date: 2011-03-04 03:23 pm (UTC)no subject
Date: 2011-03-04 03:28 pm (UTC)no subject
Date: 2011-03-04 05:18 pm (UTC)no subject
Date: 2011-03-04 05:51 pm (UTC)Скажите, а вы там проверяли на практике результаты или это ради развлечения?
no subject
Date: 2011-03-04 06:01 pm (UTC)В ответ на ваш вопрос: это чисто ради развлечения. Полгода назад, когда эту функцию удалили из исходников Хрома, это было не потому, что она быстрее или медленнее, а чтобы код использовал одну стандартную фунцкию для этого дела, а не десять разных[1], которые накопились в разных местах.
Вообще не очень легко представить естественные обстоятельства, при которых оптимизация этой функции может дать нетривиальный вклад в performance. 16-ричные цифры должны придти из какого-то источника - например, файла или веб-страницы - и тогда время, затраченное в I/O на чтение этой цифры, на несколько порядков больше времени любого из вариантов HexToInt(). Если, может быть, кто-то делает очень интенсивные вычисления на 16-ричных строках, переводя их в числа и обратно миллионы раз все время - но кто ж будет так извращаться.
[1] Я не знаю точно, сколько их было, скорее всего меньше десяти.
no subject
Date: 2011-03-04 06:01 pm (UTC)no subject
Date: 2011-03-04 06:24 pm (UTC)