ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sashka Yackubtchick                  2:5054/29.54   01 Dec 2001  16:13:25
 To : All
 Subject : Min and Max without branching
 -------------------------------------------------------------------------------- 
 

 
 Почитав в эхе на тему сабжа, решил описать некоторые методы
 больше для того чтобы было понятно какие закономерности лежат в
 их основе нежели для того чтобы придложить готовый рецепт.
 Думаю всегда существует возможность когда кому то прийдёт в голову
 новый более оптимальный вариант, но для этого нужна пища для ума,
 вот такую "пищу" довольно прожёванную я хочу попытаться пердложить.
 
 Min \ Max двух чисел без условных переходов.
 --------------------------------------------
 Данные приёмы строятся на трёх китах:
 1.Если сделать AND числа A с числом B в котором все биты установлены в 1 то
 получим тоже самое число A (01011100 and 11111111 = 01011100)
   Если сделать AND числа A с числом B где все биты установлены в 0 то получим 0
   01011100 and 00000000 = 00000000
   результатом AND будет 1 тогда и только тогда когда оба оператора = 1
 2.Если в результате вычитания из меньшего числа вычитается большее то в
 результате произойдёт заем из старшего (воображаемого) разряда и сигналом об
 этом будет установка carry flag с тем чтобы можно его было использовать в
 дальнейшем (вычитать или прибавлять его значение) Сравнение осуществляется в
 компьютере именно вычитанием при этом разница состоит с обычным вычитанием лишь 
 в том что результат не пишется в вычитаемое но флаги ( а они то и
   показывают как через вычитание видно результат сравнения) устанавливаются
 3.Минус 1 выглядит в дополнительном коде как число где все биты установлены в  1
 а 0 где все биты установлены в 0.
 
 Теперь представим что мы сравнили два числа и у нас установился в результате
 carry flag если первое число было меньше второго (произошёл заем при вычитании)
 если мы вычтем carry flag из 0 то получим -1 (11111111) если же займа небыло то 
 останется 0
 Если результат такого вычитания мы используем для AND с неким числом то получим 
 либо это число либо 0.
 Посмотрим как это можно использовать для того чтобы получить минимум двух чисел.
 if (B < A) A = B
 eax  A
 ebx  B
          SUB EBX,EAX ;получим разницу B - A исходя из того что В = А + (B - A)
          SBB ECX,ECX ;вычитает число из само из себя и вычитает carry получим 0
                      ;если B>A и -1 (число где все биты = 1) если B<A
          AND ECX,EBX ;превратим ecx в разницу EBX - EAX если эта разница была 
 ;отрицательной или в 0 если она была положительной
          ADD EAX,ECX ;если ebx был меньше прибавится отрицательная разница    
 ;(иначе говоря произойдёт вычитание) в противном случае                   
 ;прибавится 0 и результат не изменится.
 
 Данный пример взят из известного мануала Ангера Фога по оптимизации для
 процессоров семейства
 Pentium. Правда без всяких коментариев и назван трюком(слово которое я просто
 ненавижу).
 Что даёт мне основание думать что сам Фог к авторству не имеет никакого
 отношения
 хотя он не упоминает откуда взял пример.
 Как и многие другие авторы примеров оптимизации которые "густо" комментируют
 абсолютно
 очевидные вещи и оставляют без комментариев вещи неочевидные для непросвящённых.
 Тем не менее как писал Кнут "многие учёные разными путями и в разное время
 независимо друг от
 друга открыли ..." будем считать что и этот приём один из подобных открытий
 пришедший в голову
 многим независимо.
 
 Теперь к нашим баранам.
 Посмотрим можно ли использовать подобный эффект при нахождении максимума двух
 чисел.
 Обратите внимание на второй шаг кода SBB ECX,ECX
 он означает ecx - ecx - carry flag.  Естествено что A = A и A - A = 0 поэтому
 эта простейшая
 однотактовая команда делает настоящую работу:
 if cf then
  ecx = -1
 else
  ecx = 0
 Причём что важно - предидущее значение cf не важно в любом случае A - A = 0
 и 0 - 1 = -1 а 0 - 0 = 0
 Почему я так долго мурыжу очевидные вещи - в обратном действии не получится
 сделать выбор за 4 команды как примере с MIN HО! Можно это сделать за 4е такта
 также как в MIN (все команды в приведенном примере зависимые и это не позволяет
 их распаралелить по разным АЛУ)
 Итак вариант MAX пять команд но 4е такта (c)Svin.
 
 1. mov ecx,-1 ;ecx = 11111111 11111111 11111111 11111111
 2. sub ebx,eax ;B-A
 3. adc ecx,0  ;if B-A < 0 (-1+ 0 + 1) ecx = 0 else (-1 + 0 + 0) ecx = -1
 4. and ecx,ebx ;if B<A ecx = 0 else ecx = B-A
 5. add eax,ecx ;if B<A eax + 0 else eax+(B-A)
 
 1. Поместим в ecx - 1 (все биты установливаются в 1)
 2. Получим разницу B - A Шаг первый и второй независимы от друг друга и
 выполнятся в разных АЛУ за один такт
 3. Если ebx был меньше eax то установится carry flag и сложение его с -1 даст 0
 4. Результат зависит от шага 3 либо 0 либо B-A
 5. К А добавится разница B-A если B был больше в противном случае добавится 0
 Пока!
              Sashka
 
 --- GoldED/W32 3.00.Beta1+
  * Origin: Svin, Perm, Russia  (2:5054/29.54)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор