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

Тема в разделе "WASM.A&O", создана пользователем murder, 27 мар 2010.

  1. Maratyszcza

    Maratyszcza New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2006
    Сообщения:
    32
    Я когда-то оптимизировал такую вещь. На AMD быстрее всего вариант Black_Mirror (только лучше использовать несколько регистров в качестве счётчиков, чтобы уменьшить число зависимостей), на Intel - аналогичный код, но с использованием setnc
     
  2. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Сейчас ещё раз посмотрел на вариант с cmp/sbb и кажется он быстрее табличного. Буду сравнивать.
     
  3. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Замерил так
    Код (Text):
    1. @1:call numlen
    2. loop @1
    Мой табличный вариант из поста #6 - 15 тактов
    Вариант Black_Mirror из поста #13 - 12 тактов

    P.S.
    Проц - Athlon II
     
  4. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Добавил в цикл перед call mov eax,ecx стало выдавать одинаковое время.
     
  5. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    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
     
  6. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Выиграл один такт и потерял регистры.
     
  7. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Вот ещё вариант. Можно как-нибудь оптимизировать?
    Код (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;
     
  8. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    table: array[0..7] of dword=(999999999,99999999,9999999,999999,99999,9999,999,99);
     
  9. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Забавно, самый примитивный вариант оказался почти самым быстрым. А вот для 64битного кода остаётся только табличный и вариант c cmov. Но здесь наверно победит табличный.
     
  10. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Почему почти?
     
  11. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    murder
    Ну на P4 табличный вариант быстрее в 2 раза, чем сравнение со всеми степенями и суммирование.
     
  12. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Да слышал там adc не очень...
     
  13. Maratyszcza

    Maratyszcza New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2006
    Сообщения:
    32
    Вот код для 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
    Фенома у меня нет, так что реально измерить время не могу.
     
  14. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Медленнее стало. А как ты по тактам расписываешь?

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

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    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 должно в два раза уменьшиться
     
  16. Maratyszcza

    Maratyszcza New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2006
    Сообщения:
    32
    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
     
  17. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Black_mirror
    Я тебя понял. Но не уверен с этими округлениями. Как ты можешь быть уверен, что округлять надо всегда вниз (или вверх)?
     
  18. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Black_mirror
    Не получится:dntknw: Взял число 4500000 и получил нулевую дробную часть.
     
  19. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    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, и по нему можно не только младшую часть единицами заполнить, но и скорректировать количество цифр.
     
  20. Black_mirror

    Black_mirror Active Member

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