К разделу 'Компьютерная Графика' сайта AlgoList.







ОПТИМИЗАЦИЯ
6.2. Примеры внутренних циклов текстурирования

Если немного поработать профайлером, можно выяснить следующую интересную вещь: большая часть времени на отрисовку сцены тратится именно в процедуре текстурирования, а в ней, в свою очередь, большая часть времени проходит во внутреннем цикле (inner loop). Естественно, что его и надо оптимизировать в первую очередь.

Возьмем этот самый inner loop от обычного аффинного текстурирования (такой же, на самом деле, используется и в перспективно-корректном) и перепишем на ассемблере (в критических участках кода на компилятор надеяться не стоит). Будем использовать 24:8 fixedpoint для u, v, а также 8-битную текстуру шириной 256 байт.

    mov eax,u        ; 24:8 fixedpoint
    mov ebx,v        ; 24:8 fixedpoint
    mov ecx,length
    xor edx,edx
    mov esi,texture
    mov edi,outputbuffer
inner:
    mov dl,ah        ; вытащили целую часть u
    mov dh,bh        ; вытащили целую часть v
                     ; теперь edx = dx = (100h * v + u) - как раз
                     ; смещение тексела [v][u] относительно начала
                     ; текстуры
    mov dl,[esi+edx] ; dl = texture[v][u]
    mov [edi],dl     ; *outputBuffer = dl
    add eax,du       ; u += du
    add ebx,dv       ; v += dv
    inc edi          ; outputBuffer++
    loop inner
    ; ...

Красиво, аккуратно, на ассемблере. Только вот согласно правилам спаривания, половина команд в этом цикле не спарится, и цикл займет порядка 6-7 тактов. А на самом деле, чуточку переставив местами команды, можно его загнать где-то в 4.5 такта:

    ; ...
inner:
    mov dl,ah
    add eax,du
    mov dh,bh
    add ebx,dv
    mov dl,[esi+edx]
    inc edi
    dec ecx
    mov [edi-1],dl
    jnz inner
    ; ...

В таком виде любая пара команд отлично спаривается, получаем те самые 4.5 такта. Здесь, правда, есть обращения к внешним переменным du и dv, что может снизить скорость. Решение - самомодифицирующийся код:

    ; ...
    mov eax,du
    mov ebx,dv
    mov inner_du,eax
    mov inner_dv,ebx
    ; ...
inner:
    ; ...
    add eax,12345678h
    org $-4
inner_du dd ?
    add edx,12345678h
    org $-4
inner_dv dd ?
    ; ...

Однозначного ответа насчет использования самомодификации нет, а совет, что можно по этому поводу дать, стандартен - попробуйте, если будет быстрее, то используйте.

Дальше - больше. 4.5 такта на пиксел - это тоже не предел. В fatmap.txt приводится вот такой красивый inner loop на четыре такта.

    ; текстура должна быть выравнена на 64k
    ; линии рисуются справа налево
    ; верхние 16 бит ebx = сегмент текстуры
    ; bh = целая часть v
    ; dh = дробная часть v
    ; dl = дробная часть dv
    ; ah = целая часть v
    ; ecx = u
    ; ebp = du
inner:
    add ecx,ebp        ; u += du
    mov al,[ebx]       ; al = texture[v][u]
    mov bl,ch          ; bl = новая целая часть u
    add dh,dl          ; считаем новую дробную часть v
    adc bh,ah          ; считаем новую целую часть v
    mov [edi+esi],al   ; рисуем пиксел
    dec esi            ;
    jnz inner          ;

Надо, правда, отметить, что он уже требует каких-то ухищрений - а именно, выравнивания текстуры на 64k и отрисовки строк справа налево. Кроме того, требует более подробного рассмотрения фрагмент с add и adc, об этом более подробно рассказано чуть ниже.

И, наконец, цитата из fatmap2.txt - 4-тактовый inner loop, использующий 16:16 fixedpoint. Недостатки - текстура должна быть выравнена на 64k; есть две команды adc, которые могут запросто испортить спаривание.

; текстура должна быть выравнена на 64k
;
;         верхние 16 бит | ah/bh/ch/dh    | al/bl/cl/dl
;       -----------------+----------------+----------------
; eax = дробная часть u  | -              | -
; ebx = сегмент текстуры | целая часть v  | целая часть u
; edx = дробная часть v  | целая часть dv | целая часть du
; esi = дробная часть du | 0              | 0
; ebp = дробная часть dv | 0              | 0
; ecx = длина линии
; edi = буфер

    lea edi,[edi+ecx]  ; edi += ecx
    neg ecx            ; ecx = -ecx
inner:
    mov al,[ebx]       ; al = texture[v][u]
    add edx,ebp        ; обновляем дробную часть v
    adc bh,dh          ; обновляем целую часть v (учитывая
                       ; перенос от дробной)
    add eax,esi        ; обновляем дробную часть u
    adc bl,dl          ; обновляем целую часть u (учитывая
                       ; перенос от дробной)
    mov [edi+ecx],al   ; outputBuffer[ecx] = al
    inc ecx
    jnz inner

Этот цикл, с виду, ничем не лучше цикла для 24:8 fixedpoint. Но на самом деле, он может пригодиться в том случае, если циклу с 24:8 fixedpoint не хватит точности. Упомянутая нехватка точности проявляется в эффекте "пилы" внутри относительно больших треугольников, который вовсе не устраняется добавлением subpixel/subtexel accuracy.

Два последних цикла используют конструкции вида add/adc. Здесь мнения авторов этих самых циклов явно расходятся с мнениями автора pentopt.txt. Согласно последнему (и п.6.1.1., соответственно, тоже), add и adc НЕ спарятся (так как add изменяет регистр флагов, adc - читает из него). Проведенный эксперимент показал, что они действительно не спариваются, но он был поставлен на k5; так что на данный момент я достоверной информацией по этому поводу не располагаю. Впрочем, в любом случае лучше еще чуть-чуть попереставлять команды - для полной надежности. И для полной надежности, самостоятельно замеряйте скорость выполнения каждой новой версии цикла и смотрите, что получилось. Да, совет тривиальный. Но после того, как на моем k5 цикл из четырех инструкций исполнился, согласно замерам, за такт...



 в самое начало


demo.design
3D programming FAQ