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

Я когда-то оптимизировал такую вещь. На AMD быстрее всего вариант Black_Mirror (только лучше использовать несколько регистров в качестве счётчиков, чтобы уменьшить число зависимостей), на Intel - аналогичный код, но с использованием setnc

 

Сейчас ещё раз посмотрел на вариант с cmp/sbb и кажется он быстрее табличного. Буду сравнивать.

 

Замерил так

Код (Text):

1. @1:call numlen
2. loop @1

Мой табличный вариант из поста #6 - 15 тактов
Вариант Black_Mirror из поста #13 - 12 тактов

P.S.
Проц - Athlon II

 

Добавил в цикл перед call mov eax,ecx стало выдавать одинаковое время.

 

murder
а если попробовать сделать как предлагает Maratyszcza?

Код (Text):

1. mov ecx,5
2. xor ebx,ebx
3. mov edx,ecx
4.  
5. cmp eax,10^9
6. sbb ecx,ebx
7. cmp eax,10^8
8. sbb edx,ebx
9.  
10. cmp eax,10^7
11. sbb ecx,ebx
12. cmp eax,10^6
13. sbb edx,ebx
14.  
15. cmp eax,10^5
16. sbb ecx,ebx
17. cmp eax,10^4
18. sbb edx,ebx
19.  
20. cmp eax,10^3
21. sbb ecx,ebx
22. cmp eax,10^2
23. sbb edx,ebx
24.  
25. cmp eax,10^1
26. lea eax,[ecx+edx]
27. sbb eax,ebx

 

Выиграл один такт и потерял регистры.

 

Вот ещё вариант. Можно как-нибудь оптимизировать?

Код (Text):

1. function numlen4(x: dword): dword;register;assembler;
2. asm
3. movd     xmm0,eax
4. shufps   xmm0,xmm0,0
5. movaps   xmm1,xmm0
6. pcmpgtd  xmm0,dqword[table]
7. pcmpgtd  xmm1,dqword[table+16]
8. movmskps ebx,xmm0
9. movmskps edx,xmm1
10. popcnt   ebx,ebx
11. popcnt   edx,edx
12. cmp      eax,10
13. cmc
14. adc      ebx,edx
15. lea      eax,[ebx+1]
16. end;

 

table: array[0..7] of dword=(999999999,99999999,9999999,999999,99999,9999,999,99);

 

Забавно, самый примитивный вариант оказался почти самым быстрым. А вот для 64битного кода остаётся только табличный и вариант c cmov. Но здесь наверно победит табличный.

 

Почему почти?

 

murder
Ну на P4 табличный вариант быстрее в 2 раза, чем сравнение со всеми степенями и суммирование.

 

Да слышал там adc не очень...

 

Вот код для AMD (K10):

Код (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 ; Clock 1
8. sbb ebx, -1 ; Clock 2
9. cmp eax,  100 ; Clock 1
10. sbb ecx, -1 ; Clock 2
11. cmp eax, 1000 ; Clock 1
12. sbb edx, -1 ; Clock 2
13.  
14. ; Clocks 3-4
15. cmp eax, 10000 ; Clock 3
16. sbb ebx, -1 ; Clock 4
17. cmp eax, 100000 ; Clock 3
18. sbb ecx, -1 ; Clock 4
19. cmp eax, 1000000 ; Clock 3
20. sbb edx, -1 ; Clock 4
21.  
22. ; Clock 5-6
23. cmp eax, 10000000 ; Clock 5
24. sbb ebx, -1 ; Clock 6
25. cmp eax, 100000000 ; Clock 5
26. sbb ecx, -1 ; Clock 6
27. cmp eax, 1000000000 ; Clock 5
28. sbb edx, -1 ; Clock 6
29.  
30. ; Clock 7
31. lea eax, [ebx + ecx * 1 + 1]
32.  
33. ; Clock 8
34. add eax, edx

Фенома у меня нет, так что реально измерить время не могу.

 

Медленнее стало. А как ты по тактам расписываешь?

Да и ещё не понял как несколько cmp могут исполняться на 5 такте а зависимые от них sbb на 6.

 

murder
можно умножить число на 2^32/10^5(только нужно правильно эту константу округлить, вроде бы вверх)
если edx!=0, то в eax=-1
пересылаем в ax,dx
в младших 16 битах eax будет целая часть от деления на 100000, а в старших - дробная
ну а дальше как у вас пересылаем eax с размножением в xmm0, сравниваем слова(не двойные) с установкой маски
для целых частей константы будут 0,9,99,999(с константой 9999 сравниваем в обычных регистрах)
а для дробных 2^16/10^1,..,2^16/10^4(тут уже вроде вниз нужно округлять)
в общем количество команд для SSE должно в два раза уменьшиться

 

murder

Пожалуй, последние две строчки лучше переписать так:

Код (Text):

1. ; Clock 7
2. add ebx, ecx
3. mov eax, edx
4. stc
5.  
6. ; Clock 8
7. adc eax, ebx

Расписываю по таблица задержек от Агнера Фога (www.agner.org/optimize). Можно ещё заглянуть в дампы Everest'а на instlatx64.freeweb.hu

Все современные процессоры умеют переименовывать eflags, поэтому каждый sbb зависит только от своего cmp

 

Black_mirror
Я тебя понял. Но не уверен с этими округлениями. Как ты можешь быть уверен, что округлять надо всегда вниз (или вверх)?

 

Black_mirror
Не получится Взял число 4500000 и получил нулевую дробную часть.

 

murder
Первую константу нужно округлять вверх C=42950
99999*C=FFFFD7FAh
100000*C=100007FC0h
а вот остальные на самом деле должны быть 2^16/10^n-1:
9*C=5E5F6h
10*C=68DBCh
99*C=40E192h
100*C=418958h
999*C=28EB5AAh
1000*C=28F5D70h
9999*C=1998FE9Ah
10000*C=1999A660h
Кстати для целых частей лучше взять константы 9,99,999,9999, потому что у нас было сравнение старшей части с 0, и по нему можно не только младшую часть единицами заполнить, но и скорректировать количество цифр.

 

murder
Если старшая часть ненулевая, то дробную часть нужно заполнить единицами, чтобы они не портили результаты сравнений на SSE: 4500000*С=2D001674C0->2DFFFFFFFF->FFFF002D вот что должно быть.