Берем простой, хотя и нетривиальный си-шный код, и сравниваем количество получившихся машинных команд. Компилятор GCC 4.1.2, оптимизация -O1. Исходный код такой:
unsigned long rot13_hash (unsigned char *str, unsigned int len)
{
unsigned long hash = 0;
while (len-- > 0) {
hash += *str++;
hash -= (hash << 13) | (hash >> 19);
}
return hash;
}
Результаты:
| Архитектура | Команд в цикле | Всего команд |
|---|
| ARM | 6 | 13 |
| Thumb | 8 | 17 |
| MIPS32 | 9 | 17 |
| Intel 386 | 9 | 25 |
| MIPS16 | 10 | 17 |
| Blackfin | 11 | 22 |
Для MIPS и Blackfin компилятор не догадался заменить два арифметических сдвига на один циклический. Предположим, мы исправили компилятор. Тогда получится так:
| Архитектура | Команд в цикле | Всего команд |
|---|
| ARM | 6 | 13 |
| MIPS32 | 7 | 15 |
| MIPS16 | 8 | 15 |
| Thumb | 8 | 17 |
| Blackfin | 8 | 19 |
| Intel 386 | 9 | 25 |
Хорошо видно, насколько архитектура Intel 386, она же Pentium, проигрывает RISC-процессорам.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
vak
no subject
Date: 2007-05-24 21:42 (UTC)no subject
Date: 2007-05-24 21:52 (UTC)no subject
Date: 2007-05-24 22:02 (UTC)rot13_hash: movl $0, %edx decl %esi cmpl $-1, %esi je .L6 .L4: movzbl (%rdi), %eax addl %eax, %edx incq %rdi movl %edx, %eax roll $13, %eax subl %eax, %edx decl %esi cmpl $-1, %esi jne .L4 .L6: movl %edx, %eax retNow what?
no subject
Date: 2007-05-24 22:03 (UTC)no subject
Date: 2007-05-24 22:08 (UTC)rot13_hash: mov ip, r0 cmp r1, #0 moveq r0, r1 bxeq lr mov r0, #0 mov r2, r0 .L5: ldrb r3, [r2, ip] add r3, r3, r0 sub r0, r3, r3, ror #19 add r2, r2, #1 cmp r2, r1 bne .L5 bx lrno subject
Date: 2007-05-24 22:11 (UTC)Не верю. Насколько я понимаю, предсказанный переход на адрес, который уже во внутреннем представлении - бесплатный, да и суперскалярность никто не отменял. Ну и -Os тоже никто не отменял:
rot13_hash: xorl %edx, %edx .L7: decl %esi cmpl $-1, %esi je .L6 movzbl (%rdi), %eax incq %rdi addl %eax, %edx movl %edx, %eax roll $13, %eax subl %eax, %edx jmp .L7 .L6: movl %edx, %eax retno subject
Date: 2007-05-24 22:14 (UTC)Интел
Date: 2007-05-25 07:32 (UTC)БОРЦЫ ПРОТИВ АРХИТЕКТУРНЫХ ИЗЛИШЕСТВ!
no subject
Date: 2007-05-25 07:34 (UTC)/* Яндекс на запрос "decl" выдает:
"Translit? Возможно, имелось в виду: «децл» " */
Разные MIPS
Date: 2007-05-25 08:18 (UTC)Он есть только в SmartMIPS Crypto и MIPS32 Release 2.
Поэтому, нужен был -march...
И в старых встроенных ядрах, его, по-моему, нет.
Есть ли он в Lexra, это для меня вопрос...
no subject
Date: 2007-05-25 08:33 (UTC)Кстати, i386 ты тоже поставил циклический сдвиг, или нет?
Теперь - про размер команд. CISC почти в два раза компактней, чем RISC. VLIW, соответственно, в два раза хуже RISC, а TTA - вдвое хуже VLIW. ;)
Правда, не на этом, твоем специально подобранном коде. ;)
no subject
Date: 2007-05-25 09:54 (UTC)Понаклепали процессоров, мама не горюй.
no subject
Date: 2007-05-25 10:17 (UTC)Легенда про четыре команды на такт возникла из того, что в Pentium 4 АЛУ работает по обоим фронтам синхросигнала. И таких АЛУ аж два. Реально померять что-то не представляется возможным, слишком всё замешано в кучу с трансляцией, VLIW, кэшами и т.п. Можно рассуждать только статистически. Из каких-то бенчмарков я слышал цифру про ~1 такт на команду, но отстаивать не берусь.
no subject
Date: 2007-05-25 10:31 (UTC)На i386 компилятор сам, я не вмешивался. :)
Компактность кода это отдельный вопрос. Вот, к примеру, размер кода embedded-реализации TCP/IP для трех архитектур. Компилятор GCC 4.1.2, оптимизация "-Os". В байтах:
- Thumb - 14377
- i386 - 20862
- ARM - 21017
Нечетные значения - по причине размещения текстовых строк в том же сегменте, кто и код. Интел не сильно лучше чем ARM, а 16-битный Thumb заметно компактнее.Re: Разные MIPS
Date: 2007-05-25 10:50 (UTC)Но суть не в циклическом сдвиге, а в общей эффективности. Очевидно, что тут MIPS вполне на уровне.
Интересно, что Blackfin оказался вполне неплох по сравнению с другими 16-битными форматами, Thumb и MIPS16.
За красоту
Date: 2007-05-25 10:53 (UTC)no subject
Date: 2007-05-25 11:21 (UTC)Кстати, Ваш хэш в идеале должен бы питаться не байтами, а словами...
Для Вашего теста padding некритичен, можно 0-ями.
no subject
Date: 2007-05-25 17:13 (UTC)Re За красоту
Date: 2007-05-25 17:42 (UTC)За рынок!
no subject
Date: 2007-05-25 20:05 (UTC)Гипотеза по поводу слов тоже нуждается в подтверждении. Между словами и байтами есть существенная (математическая) разница. Интуиция подсказывает, что характеристики такого хэша могут оказаться совсем не интересными.
no subject
Date: 2007-05-27 19:33 (UTC)Сеть Фейстеля построена, как положено, на чистом XOR.
Суммирование было перед S-boxes, а сдвиг после, но и его лучше к бинарному оператору сети не относить, поскольку он портит ассоциативность.
no subject
Date: 2007-05-28 12:40 (UTC)А рынок, по Анахарсису Скифскому, "это место, нарочно назначенное, чтобы обманывать и обкрадывать друг друга."
no subject
Date: 2007-06-12 13:41 (UTC)no subject
Date: 2008-02-12 08:22 (UTC)0014<0000d0> HS a0800412 M_d0: ALS3 e405c005 ldgdb,3,sm [ %b[5] + 0 ], %b[5] ALS5 90060706 adds,5,sm %b[6], %b[7], %b[6] ALES 01c00000 0015<0000e0> HS 80000401 : ALS5 9406cd08 scls,5,sm %b[6], 13, %b[8] 0016<0000e8> HS e0001424 : SS 806f04a0 ct %ctpr1 ? #NOT_LOOP_END abn abnf=1, abnt=1 abp abpf=1, abpt=1 alc alcf=1, alct=1 ALS3 9003c101 adds,3,sm %b[3], 1, %b[1] ALS4 90c00303 adds,4,sm 0, %b[3], %b[3] ALS5 92060804 subs,5,sm %b[6], %b[8], %b[4] ---- 00000000Если компилировать с профилированием или указать перед циклом "#pragma loop count(1000)", то начинает применяться APB (array prefetch buffer):0014<000218> HS 80000401 M_218: ALS5 90060505 adds,5,sm %b[6], %b[5], %b[5] 0015<000220> HS 80001412 : SS 80002000 ALS5 9405cd07 scls,5,sm %b[5], 13, %b[7] AAS 00011001 movab,1 area = 0, ind = 0, am = 1, be = 0, %db[1] 0016<000230> HS 80011412 : SS 806f04a0 ct %ctpr1 ? #NOT_LOOP_END abn abnf=1, abnt=1 abp abpf=1, abpt=1 alc alcf=1, alct=1 ALS5 92050704 subs,5,sm %b[5], %b[7], %b[4] ? %pcnt0 CDS0 50400000 rlp,cd00 %pcnt0, >alc5Т.е. в обоих случаях получам 3-х тактный цикл...no subject
Date: 2008-02-12 09:22 (UTC)no subject
Date: 2008-02-12 12:40 (UTC)Документация есть, но она всё ещё не публичная,
хотя вроде были планы это изменить.
no subject
Date: 2008-02-12 12:46 (UTC)http://smallcode.weblogs.us/2008/01/22/hash-functions-an-empirical-comparison/
http://smallcode.weblogs.us/2008/02/04/hash-functions-additional-tests/
http://smallcode.weblogs.us/2008/02/12/hash-functions-part-3/
no subject
Date: 2008-02-12 13:00 (UTC)А это действительно работает? У Бабаяна слова всегда настолько расходились с делом, что пока сам не увижу, не поверю. :)
no subject
Date: 2008-02-12 13:13 (UTC)no subject
Date: 2008-02-12 13:31 (UTC)Оно работает. Даже прошли гос. испытания (http://www.mcst.ru/news.shtml#071029).
С Бабаяном лично знаком не был, так что позволю себе не комментировать последнее высказывание...
no subject
Date: 2008-02-12 14:00 (UTC)По тексту: "Комиссия... в составе 43 человек... заключила, что микропроцессор «Эльбрус» и ВК «Эльбрус-3М1»... являются оригинальной отечественной разработкой". Похоже на полный провал. Сорок три человека собрались в кучу только для того, чтобы объявить Эльбрус оригинальной разработкой? Приняла ли комиссия изделие? Рекомендовала ли к применению? Непонятно.
Может быть и не на asm, но почему бы не выпустить микропроцессор в народ? Наверняка на коммерческом рынке он нашёл бы свою нишу.
no subject
Date: 2008-02-12 14:40 (UTC)Понятно что сейчас мало кому нужно голое процессорное ядро, а E3M требует чипсета (северного моста), которого нет в кремнии, только в дорогом FPGA. Это основная проблема у E3M для вывода его на рынок. В этом году должны сделать E3S (кеш L2 не 256K, а уже 2М, два встроенных контроллера памяти и 3 межпроцессорных линка), - у него на много больше шансов быть реально востребованным.
no subject
Date: 2008-02-18 10:32 (UTC)