?

Log in

забавный код на C - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

забавный код на C [сент. 7, 2001|07:26 pm]
Anatoly Vorobey
Эту запись имеет смысл читать только тем, кто знает язык программирования C.

Мне его выдал форчун, уже не в первый раз, и я решил на этот раз записать. Если вам
нечего делать, разгадывайте, что делает этот код с 32-битным числом n:

n = ((n >> 1) & 0x55555555) | ((n << 1) & 0xaaaaaaaa);
n = ((n >> 2) & 0x33333333) | ((n << 2) & 0xcccccccc);
n = ((n >> 4) & 0x0f0f0f0f) | ((n << 4) & 0xf0f0f0f0);
n = ((n >> 8) & 0x00ff00ff) | ((n << 8) & 0xff00ff00);
n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000);


Update: 37 нашёл отличную ссылку по теме.
СсылкаОтветить

Comments:
[User Picture]From: 37
2001-09-07 10:14 am
Биты переворачивает. Свинство какое-то...
(Ответить) (Thread)
[User Picture]From: oxfv
2001-09-07 10:32 am
Отчего же свинство, довольно эффективный способ. Прямо скажем, самый эффективный из мне известных.
(Ответить) (Parent) (Thread)
[User Picture]From: 37
2001-09-07 11:02 am
Может и эффективный, но очень невнятный. С ходу написал что-то более понятное (на мой взгляд):
.....
maskl = 0x80000000, maskr = 0x00000001;
for(i = 0; i < 16; ++i)
{
if(n & maskl)
n1 |= maskr;
if(n & maskr)
n1 |= maskl;
maskl = maskl >> 1;
maskr = maskr << 1;
}
......
Сравнил эффективность по времени: разница примерно 10%. А ведь можно еще и подумать:-)))
(Ответить) (Parent) (Thread)
[User Picture]From: oxfv
2001-09-07 11:11 am
Ну уж 10%. Kуда как больше. 16 шагов вместо 5.

У нас в программе используется массив из 16 нибблов, содержащий перевернутые нибблы. Дальше понятно. По эффективности это похуже, чем в варианте Анатолия, но понятнее и дает гибкость в отношении переворачивания нецелых байтов.
(Ответить) (Parent) (Thread)
[User Picture]From: 37
2001-09-07 11:21 am

Re:

Что забавно, после оптимизации обоих кодов:
(на 10000000 повторов)

-rw-rw-r-- 1 4216 07 10:58 Sep 07 11:13 ntest2
-rw-rw-r-- 1 4152 07 10:56 Sep 07 11:14 ntest3

$ ./ntest2 12345
Before 0x003039 ; After 0x9c0c0000, Time 0x7fc2c638

$ ./ntest3 12345
Before 0x003039 ; After 0x9c0c0000, Time 0x5f380a32

ntest2 - старый, ntest2 - новый.
(Ответить) (Parent) (Thread)
[User Picture]From: oxfv
2001-09-07 11:39 am
Это в смысле - ваш вариант быстрее аввиного? Или ваш оптимизированный быстрее вашего неоптимизированного? Возможно, если в аввином варианте ввести доп. переменные, оно станет быстрее из-за конвейерных штучек...

Kстати, если уж пошла такая пьянка, то вот так можно:

n1 |= n & 1;

for ( int i = 1; i < 32; i ++ )
{
    n1 <<= 1;
    n  >>= 1;

    n1 |= n & 1;
}

(Ответить) (Parent) (Thread)
[User Picture]From: 37
2001-09-07 12:01 pm

Re:

Нет, мой оптимизированный лучше аввиного оптимизированного. А ведь мой еще с ходу можно чуть-чуть улучщить:

while(maskl)
{
.....

Ваш и мой в-ты по скорости не отличимы.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2001-09-07 12:06 pm

Re:

Осталось теперь только дизассемблировать оптимизированный код и понять, почему Ваш вариант быстрее моего (на первый взгляд, загадка - мой не требует прыжков)
(Ответить) (Parent) (Thread)
[User Picture]From: 37
2001-09-07 12:16 pm

Re:

Потом попробую. Думаю (опять же, с ходу), разная стоимость операций).
(Ответить) (Parent) (Thread)
[User Picture]From: 37
2001-09-07 12:38 pm

Re:

А вот и результат:

мой:
.L6:
xorl %ebx,%ebx
movl $-2147483648,%ecx
movl $1,%edx
xorl %eax,%eax
.align 4
.L10:
testl %esi,%ecx
je .L11
orl %edx,%ebx
.L11:
testl %esi,%edx
je .L12
orl %ecx,%ebx
.L12:
shrl $1,%ecx
addl %edx,%edx
incl %eax
cmpl $15,%eax
jle .L10
incl %edi
cmpl $9999999,%edi
jle .L6
==================
Ваш:
.L6:
addl $-4,%esp
pushl $10
pushl $0
pushl 4(%edi)
call strtoul
movl %eax,%ebx
movl %ebx,%edx
shrl $1,%edx
andl $1431655765,%edx
leal (%ebx,%ebx),%eax
andl $-1431655766,%eax
movl %edx,%ecx
orl %eax,%ecx
movl %ecx,%edx
shrl $2,%edx
andl $858993459,%edx
leal 0(,%ecx,4),%eax
andl $-858993460,%eax
movl %edx,%ecx
orl %eax,%ecx
movl %ecx,%edx
shrl $4,%edx
andl $252645135,%edx
movl %ecx,%eax
sall $4,%eax
andl $-252645136,%eax
movl %edx,%ecx
orl %eax,%ecx
movl %ecx,%edx
shrl $8,%edx
andl $16711935,%edx
movl %ecx,%eax
sall $8,%eax
andl $-16711936,%eax
movl %edx,%ecx
orl %eax,%ecx
roll $16,%ecx
addl $16,%esp
incl %esi
cmpl $9999999,%esi
jle .L6
===================
Прошу прощения за объем
(Ответить) (Parent) (Thread)
From: (Anonymous)
2001-09-07 07:55 pm
Not seeing assembly, did not undertand how your variant can be faster. Well, you have extra call to stroul() in loop in assembly for avva's variant.

Here are the numbers in seconds on Intel box:

avva - 0.43
37 - 10.13
oxfv - 1.23 / 0.55 with loop unroll
oxfv/byte table - 0.48 / 0.22 with loop unroll


(Ответить) (Parent) (Thread)
[User Picture]From: 37
2001-09-07 08:25 pm
strtoul - да я, как я думаю, просто не отрезал его в аввином коде. Хотя, конечно, проверю еще раз, но делал эти примеры из одного шаблона. К сожалению, код остался у меня на раьоте, заново набивать его не буду, могу послать Вам для проверки только в понедельник (на тот случай, если Вы сомневаетесь в добросовестности моих упражнений:-))). В свою очередь, можете прислать мне свои примеры для проверки, но сразу скажу, что разница более чем в 20 раз(!) и, особенно, во втором случае в 20 раз вызывает большое сомнение и подозрение в чисто методической ошибке. Не очень понятно Ваше неверие в саму возможность этого - уж не считаете ли Вы, что количество строк С-кода однозначно коррелирует с длиной его выполнения? Тогда еще раз посмотрите на ассемблерный код (о strtoul, разумеется, забудьте).
(Ответить) (Parent) (Thread)
From: (Anonymous)
2001-09-07 10:26 pm
20 times difference indeed sounds excessive. I just checked and looks like in attempt to optimize your code I slowed it down twice. From quick look at the assembly you gave, difference should be 5-10 times.

Reason is that for branches Intel (and generally all modern CPUs) takes a performance penalty due to pipeline stalls and flushes. Also in your main
loop there is 1 instruction between branches where as potentially Intel can execute several instructions simultaneosly.

As for assembly from avva's code, it's linear and the only possible problem I see with it is that on Pentium IV shifts are slower and have higher latency than ALU operations. But then, there is 7 assembly shifts in his variant and 16 in yours.

You are right in a sense that this all is mostly compiler problem. Given your code I don't see any reason why compiler shouldn't be able to generate code which executes at most 2-3 times slower than
original tricky implementation.
(Ответить) (Parent) (Thread)
[User Picture]From: 37
2001-09-08 06:24 am
Как заключение. Вы правы: основное зло - в branch. Интел выполняет это очень медленно, чего я, конечно, не учел в оценках (про себя считал, что if(...) something стоит очень грубо говоря в среднем 1.5 операции, а оказалось - в среднем больше 2-х, т.е., когда сравнение - истина, выполнение идет быстрее, чем когда пропускается следующий оператор). Как парадокс, я для примера построил вообще чисто линейный длинющий код по типу:
n1 |= (n & 0x800000000) >> 31;
.....
И этот огромный (и в ассеблере as well) код выполнялся всего в 2.5 раза медленнее, чем код аввы, и намного быстрее чем если использовать команды типа
if(n & 0x800000000) n1 |= 0x00000001;
В понедельник попробую ради интереса на нескольких других типах процессоров.
За сим прощаюсь, ибо и так наплодил уже неимоверное количество текста в чужом журнале.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2001-09-07 10:22 am

А кто–то

чего–то обещал...
(Ответить) (Thread)
[User Picture]From: avva
2001-09-07 10:25 am

Re: А кто–то

Всё будет, чесслово, в течение дня-двух. Простите мне задержки. Всё-таки иногда внешняя ЖЖжизнь вмешивается и вносит свои поправки.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2001-09-07 10:43 am

Конечно, конечно.

Как говаривает мой папа, понимаем, все понимаем. Надеюсь, поправки приятного свойства.))
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2001-09-09 04:08 am

Re: Конечно, конечно.

Кроме всего прочего (жизненного), я ещё осознал, что то, что я помню из своей позиции по поводу компьютеров и доказательств, сильно устарело в моей же картине мира, т.е. я не позаботился о совмещении его с тем, что для меня прояснилось в последнее время. Пришлось посидеть и подумать немножко, но, кажется, теперь я могу представить какую-никакую когерентную позицию, что сегодня и сделаю.
(Ответить) (Parent) (Thread)
[User Picture]From: 37
2001-09-07 09:46 pm
Каюсь и посыпаю голову пеплом. Код остался на работе, но решил проверить и без спешки аккуратно набрал еще раз. Получилось, что, наверное, действительно, забыл закомментарить strtoul в цикле, что дало жуткое искажение почти на порядок. Код Аввы получился в 8 раз быстрее.
(Ответить) (Thread)
[User Picture]From: silpol
2001-09-10 11:58 am

просто интересно...

на каком железе опробовано?
(Ответить) (Parent) (Thread)
[User Picture]From: 37
2001-09-10 12:12 pm

Re: просто интересно...

Пока только на Intel (разница в 8 раз), на MIPS (разница только в 2 раза), вечером попробую на HITACHI(sh), завтра, м.б., -на PPC, ARM, м.б. SPARC.
(Ответить) (Parent) (Thread)
[User Picture]From: silpol
2001-09-10 01:06 pm

гхм...

а на АМД Атлон???
(Ответить) (Parent) (Thread)
[User Picture]From: 37
2001-09-10 01:31 pm

Re: гхм...

No
(Ответить) (Parent) (Thread)
[User Picture]From: silpol
2001-09-10 01:39 pm

жаль...

прийдется самому рисовать... о! не! коллегу подобью ;) он точно купиться гонять на разном... у нас похожее - packets assembling/disassembling ;)
(Ответить) (Parent) (Thread)