Задачка о длине числа

Вариант для Intel (Core 2, Nehalem):

Код (Text):

1.     ; Clock 0
2.     xor ebx, ebx
3.     xor ecx, ecx
4.     xor edx, edx
5.  
6.     ; Clocks 1-2
7.     cmp eax, 10
8.     setae bl
9.     cmp eax, 100
10.     setae cl
11.     cmp eax, 1000
12.     setae dl
13.  
14.     ; Clocks 3-4
15.     cmp eax, 10000
16.     setae bh
17.     cmp eax, 100000
18.     setae ch
19.     cmp eax, 1000000
20.     setae dh
21.  
22.     ; Clock 4
23.     add bl, bh
24.     add cl, ch
25.     add dl, dh
26.  
27.     ; Clocks 5-6
28.     cmp eax, 10000000
29.     setae bh
30.     cmp eax, 100000000
31.     setae ch
32.     cmp eax, 1000000000
33.     setae dh
34.  
35.     ; Clock 7
36.     add bl, bh
37.     add cl, ch
38.     add dl, dh
39.  
40.     ; Clock 8
41.     movzx ebx, bl
42.     movzx ecx, cl
43.     movzx edx, dl
44.  
45.     ; Clock 9
46.     add ebx, ecx
47.     add edx, 1
48.  
49.     ; Clock 10
50.     lea eax, [ebx + edx * 1]

IACA показывает throughput 11 (как и ожидалось) и latency 12 (ибо Front-End не успевает). Реального железа опять же у меня нет.

 

Black_mirror
Опять проблема. PCMPGTx сравнивают числа со знаком. Совсем упустил из виду.

 

murder
все числа в таблице xor 8000h, и обе половины eax тоже

 

murder
забыл поди как мы с тобой на SSE2 вычисляли mod FFF00001?
Там тоже нужно было знаковый бит перед сравнением инвертировать...

Кста, а вариант с ЯВУ типа length(inttostr(x)) чем плох?

 

это скорее не вариант яву, а вариант для тех кто совсем не экономит, но если это не надо, то почему бы и нет )

 

ну еще "словом" eax

 

Maratyszcza
Всё это только замедляет работу. Сейчас заново потестил код из поста #25 - теперь он медленнее. Быстрее всего работает #13.

Может быть я где-то в коде ошибся

 

murder
До и после выполнения rdtsc нужно сериализовать конвеер, т.е. сказать процессору, чтобы он дождался, пока все команды, которые уже загружены в конвеер, выполнятся до конца. Единственная команда, которая сериализует конвеер, и которую можно вызвать из user-mode, это cpuid. К сожалению, это команда выполняется долго (сотни тактов), поэтому нужно предпринять некоторые дополнительные усилия, чтобы учесть этот оверхед. Как это сделать можно посмотреть в примере на сайте Агнера Фога. Твой код вы нынешнем виде измеряет лишь производительность Front-End'а процессора.

 

murder
Хотя нет, учитывая, что этот кусочек выполняется миллиард раз, на конвеер можно забить. А вот саму функцию numlen стоит заинлайнить: на таких маленьких участках кода вызов функции - это значительный (и непостоянный) оверхед. И хорошо бы ещё начало цикла выровнять (не знаю, делает ли это Delphi) на 32 байта.

 

Black_mirror
Фуф. совсем запутался.

Код (Text):

1.   table: array[0..7] of word=(9 xor $8000,trunc(0.9*65536) xor $8000,99 xor $8000,trunc(0.99*65536) xor $8000,999 xor $8000,trunc(0.999*65536) xor $800,9999 xor $8000,trunc(0.9999*65536) xor $8000);

Правильно?

p.s.
Продолжу завтра утром

 

Вариант для Pentium-M

Код (Text):

1.     ; Clocks 0-1
2.     cmp eax, 10
3.     setae bl
4.     cmp eax, 100
5.     setae cl
6.  
7.     ; Clocks 2-3
8.     cmp eax, 1000
9.     setae bh
10.     cmp eax, 10000
11.     setae ch
12.  
13.     ; Clock 4
14.     add bl, bh
15.     add cl, ch
16.  
17.     ; Clocks 5-6
18.     cmp eax, 100000
19.     setae bh
20.     cmp eax, 1000000
21.     setae ch
22.  
23.     ; Clock 7
24.     add bl, bh
25.     add cl, ch
26.  
27.     ; Clocks 8-9
28.     cmp eax, 10000000
29.     setae bh
30.     cmp eax, 100000000
31.     setae ch
32.    
33.     ; Clock 10
34.     add bl, bh
35.     add cl, ch
36.    
37.     ; Clock 11
38.     add bl, cl
39.     cmp eax, 1000000000
40.    
41.     ; Clock 12
42.     setae cl
43.     movzx eax, bl
44.    
45.     ; Clock 13
46.     inc eax
47.     movzx ecx, cl
48.    
49.     ; Clock 14
50.     add eax, ecx

Ожидается 15 тактов, реально 17.5 тактов

 

про iret не забыл?

 

Работает вроде-бы правильно, но реализация IMHO не удачная.

Код (Text):

1. const
2.   table2: array[0..7] of word=(9                    xor $8000,
3.                                trunc(0.00009*65536) xor $8000,
4.                                99                   xor $8000,
5.                                trunc(0.00099*65536) xor $8000,
6.                                999                  xor $8000,
7.                                trunc(0.00999*65536) xor $8000,
8.                                9999                 xor $8000,
9.                                trunc(0.09999*65536) xor $8000);
10.  
11. function numlen5(x: dword): dword;register;assembler;
12. asm
13.   mov      ecx,$A7C6
14.   mul      ecx
15.   sbb      ecx,ecx       ;вот здесь
16.   or       eax,ecx       ;можно
17.   mov      ax,dx         ;как-то
18.   xor      eax,$80008000 ;оптимизировать
19.   movd     xmm0,eax
20.   shufps   xmm0,xmm0,0
21.   pcmpgtw  xmm0,dqword[table2]
22.   pmovmskb eax,xmm0
23.   popcnt   eax,eax
24.   shr      eax,1        ;здесь
25.   cmp      dx,1         ;наверно
26.   sbb      ax,-2        ;тоже
27. end;

 

murder
Тут не реализация неудачная, тут сама идея была неудачной, из-за всех этих махинаций количество зависимостей почти в два раза выросло. В вашем изначальном варианте можно заменить movaps на еще один pshufd, а девятое сравнение делать параллельно с вычислениями на SSE, тогда количество зависимостей немного уменьшится. Любопытно еще потестировать вариант, когда таблица уже лежит в паре регистров.

Код (Text):

1. lea edx,[eax+80000000h]
2. cmp eax,10
3.  
4. movd xmm0,edx
5. mov eax,2
6.  
7. pshufd xmm1,xmm0,0
8. pshufd xmm0,xmm0,0
9. sbb eax,0
10.  
11. pcmpgtd xmm1,[table]
12. pcmpgtd xmm0,[table+16]
13.  
14. movmskps ecx,xmm1
15. movmskps edx,xmm0
16.  
17. popcnt ecx,ecx
18. popcnt edx,edx
19.  
20. add eax,ecx
21.  
22. add eax,edx

 

Cli не забыли выполнить перед тестом ?

 

Black_mirror
Странно. Если заинлайнить функцию есть улучшение в два такта (9 против 11). А так абсолютно одинаково (11).

 

Заинлайнил код из постов #13 и #33. Выдаёт 8 и 9 тактов соответственно.

Похоже, что проц сам умеет грамотно расставлять инструкции в процессе выполнения.

 

medstrax1
Про iret не знал, а теперь ещё и забыл=) Я не знаток системных инструкций.
murder
Смешивать целочисленные и floating-point SSE команды при работе с одними и теми же данными нехорошо. На Nehalem это вызывает дополнительную задержку в один такт. Поэтому лучше вместо shufps использовать pshufd, а вместо movaps - movdqa.

Проц умеет переупорядочивать инструкции ещё с незапамятных времён (Интелы, кроме Атома, - начиная с Pentium Pro/Pentium II, АМД - вероятно, начиная с K7)

 

murder

 

Мне понравились #2,#5,#7.
Перед вызовом освободите st6-st7.
После вызова st7.empty = abs(value), st0.valid = log(10;st7).
Конвенция: ccall(ret), stdcall(ret 8).
Для обрубки дроби: fisttp.
Пример:
;ffree st6
;ffree st7
stdcall lg64,-1,-1 shr 1 ;2^63
fisttp dword[esp]
pop reg
add esp,4
;inc reg

Код (Text):

1. proc lg64; value:qword
2.         fldlg2
3.         fild    qword[esp+4]
4.         fabs
5.         fyl2x
6.         ret
7. endp