забавный код на C

[avva]

Эту запись имеет смысл читать только тем, кто знает язык программирования 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

Re:

[37.livejournal.com]

×òî çàáàâíî, ïîñëå îïòèìèçàöèè îáîèõ êîäîâ:
(íà 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 - íîâûé.

[oxfv.livejournal.com]

Ýòî â ñìûñëå - âàø âàðèàíò áûñòðåå àââèíîãî? Èëè âàø îïòèìèçèðîâàííûé áûñòðåå âàøåãî íåîïòèìèçèðîâàííîãî? Âîçìîæíî, åñëè â àââèíîì âàðèàíòå ââåñòè äîï. ïåðåìåííûå, îíî ñòàíåò áûñòðåå èç-çà êîíâåéåðíûõ øòó÷åê...

Kñòàòè, åñëè óæ ïîøëà òàêàÿ ïüÿíêà, òî âîò òàê ìîæíî:

n1 |= n & 1;

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

    n1 |= n & 1;
}

Re:

[37.livejournal.com]

Íåò, ìîé îïòèìèçèðîâàííûé ëó÷øå àââèíîãî îïòèìèçèðîâàííîãî. À âåäü ìîé åùå ñ õîäó ìîæíî ÷óòü-÷óòü óëó÷ùèòü:

while(maskl)
{
.....

Âàø è ìîé â-òû ïî ñêîðîñòè íå îòëè÷èìû.

Re:

[avva.livejournal.com]

Îñòàëîñü òåïåðü òîëüêî äèçàññåìáëèðîâàòü îïòèìèçèðîâàííûé êîä è ïîíÿòü, ïî÷åìó Âàø âàðèàíò áûñòðåå ìîåãî (íà ïåðâûé âçãëÿä, çàãàäêà - ìîé íå òðåáóåò ïðûæêîâ)

Re:

[37.livejournal.com]

Ïîòîì ïîïðîáóþ. Äóìàþ (îïÿòü æå, ñ õîäó), ðàçíàÿ ñòîèìîñòü îïåðàöèé).

Re:

[37.livejournal.com]

À âîò è ðåçóëüòàò:

ìîé:
.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
===================
Ïðîøó ïðîùåíèÿ çà îáúåì

[(Anonymous)]

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

[37.livejournal.com]

strtoul - äà ÿ, êàê ÿ äóìàþ, ïðîñòî íå îòðåçàë åãî â àââèíîì êîäå. Õîòÿ, êîíå÷íî, ïðîâåðþ åùå ðàç, íî äåëàë ýòè ïðèìåðû èç îäíîãî øàáëîíà. Ê ñîæàëåíèþ, êîä îñòàëñÿ ó ìåíÿ íà ðàüîòå, çàíîâî íàáèâàòü åãî íå áóäó, ìîãó ïîñëàòü Âàì äëÿ ïðîâåðêè òîëüêî â ïîíåäåëüíèê (íà òîò ñëó÷àé, åñëè Âû ñîìíåâàåòåñü â äîáðîñîâåñòíîñòè ìîèõ óïðàæíåíèé:-))).  ñâîþ î÷åðåäü, ìîæåòå ïðèñëàòü ìíå ñâîè ïðèìåðû äëÿ ïðîâåðêè, íî ñðàçó ñêàæó, ÷òî ðàçíèöà áîëåå ÷åì â 20 ðàç(!) è, îñîáåííî, âî âòîðîì ñëó÷àå â 20 ðàç âûçûâàåò áîëüøîå ñîìíåíèå è ïîäîçðåíèå â ÷èñòî ìåòîäè÷åñêîé îøèáêå. Íå î÷åíü ïîíÿòíî Âàøå íåâåðèå â ñàìó âîçìîæíîñòü ýòîãî - óæ íå ñ÷èòàåòå ëè Âû, ÷òî êîëè÷åñòâî ñòðîê Ñ-êîäà îäíîçíà÷íî êîððåëèðóåò ñ äëèíîé åãî âûïîëíåíèÿ? Òîãäà åùå ðàç ïîñìîòðèòå íà àññåìáëåðíûé êîä (î strtoul, ðàçóìååòñÿ, çàáóäüòå).

[(Anonymous)]

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.

[37.livejournal.com]

Êàê çàêëþ÷åíèå. Âû ïðàâû: îñíîâíîå çëî - â branch. Èíòåë âûïîëíÿåò ýòî î÷åíü ìåäëåííî, ÷åãî ÿ, êîíå÷íî, íå ó÷åë â îöåíêàõ (ïðî ñåáÿ ñ÷èòàë, ÷òî if(...) something ñòîèò î÷åíü ãðóáî ãîâîðÿ â ñðåäíåì 1.5 îïåðàöèè, à îêàçàëîñü - â ñðåäíåì áîëüøå 2-õ, ò.å., êîãäà ñðàâíåíèå - èñòèíà, âûïîëíåíèå èäåò áûñòðåå, ÷åì êîãäà ïðîïóñêàåòñÿ ñëåäóþùèé îïåðàòîð). Êàê ïàðàäîêñ, ÿ äëÿ ïðèìåðà ïîñòðîèë âîîáùå ÷èñòî ëèíåéíûé äëèíþùèé êîä ïî òèïó:
n1 |= (n & 0x800000000) >> 31;
.....
È ýòîò îãðîìíûé (è â àññåáëåðå as well) êîä âûïîëíÿëñÿ âñåãî â 2.5 ðàçà ìåäëåííåå, ÷åì êîä àââû, è íàìíîãî áûñòðåå ÷åì åñëè èñïîëüçîâàòü êîìàíäû òèïà
if(n & 0x800000000) n1 |= 0x00000001;
 ïîíåäåëüíèê ïîïðîáóþ ðàäè èíòåðåñà íà íåñêîëüêèõ äðóãèõ òèïàõ ïðîöåññîðîâ.
Çà ñèì ïðîùàþñü, èáî è òàê íàïëîäèë óæå íåèìîâåðíîå êîëè÷åñòâî òåêñòà â ÷óæîì æóðíàëå.