enikesha
/
old


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252
							<!--
	demo.design 3D programming FAQ

	Idea, texts, screenshots:
		Andrew A. Aksyonoff,
		shodan@chat.ru

	Web-design, illustrations:
		Andrey Samoilov,
		asy@sense.simbirsk.su
-->

<html>
<head>
<title>demo.design 3D programming FAQ. Оптимизация. Примеры внутренних циклов текстурирования.</title>
<link rel=stylesheet href="../style.css" type="text/css">
</head>

<script language="javascript">
<!--//
browser = navigator.appName;
version = parseFloat(navigator.appVersion);
if (browser == "Netscape" && version >= 3.0) { jsenabled = 1; } else
if (browser == "Microsoft Internet Explorer" && version >= 3.0) { jsenabled = 1; } else { jsenabled = 0; }

function swap(img,ref) { if (jsenabled) {document.images[img].src = ref;} }
function loadtocache(img,ref) { cache[img] = new Image(); cache[img].src = ref; }

if (jsenabled) {
cache = new Array();
loadtocache(0,"../img/xdl.gif");
loadtocache(1,"../img/xfaq.gif");
loadtocache(2,"../img/xlinks.gif");
loadtocache(3,"../img/xauthor.gif");
loadtocache(4,"../img/xe.gif");
loadtocache(5,"../img/xprev.gif");
loadtocache(6,"../img/xnext.gif");}
//-->
</script>

<body bgcolor=white><center>

<!-- Title -->

<img src="../img/b.gif" width=500 height=1 alt=""><br>
<img src="../img/t.gif" width=500 height=1 alt=""><br>
<img src="../img/b.gif" width=500 height=1 alt=""><br>
<img src="../img/t.gif" width=500 height=2 alt=""><br>
<table width=500 cellpadding=0 cellspacing=0 border=0>
<td><img src="../img/t.gif" width=5 height=1 alt=""><a href="../main.htm" onmouseover="swap('logo','../img/xe.gif');" onmouseout="swap('logo','../img/e.gif');"><img src="../img/e.gif" name=logo width=60 height=50 hspace=10 border=0 alt=" в самое начало "></a></td>
<td><p class=pagetitle><img src="../img/t.gif" width=265 height=1 alt=""><br>demo.design<br>3D programming FAQ</td>
<td align=center><p class=navy><a href="../download.htm" onmouseover="swap('dl','../img/xdl.gif');" onmouseout="swap('dl','../img/dl.gif');"><img src="../img/dl.gif" name=dl width=40 height=40 border=0 hspace=5 alt=" download "></a><br>download</td>
<td align=center><p class=navy><a href="../links.htm" onmouseover="swap('links','../img/xlinks.gif');" onmouseout="swap('links','../img/links.gif');"><img src="../img/links.gif" name=links width=40 height=40 border=0 hspace=5 alt=" коллекция линков "></a><br>links</td>
<td align=center><p class=navy><a href="../author.htm"  onmouseover="swap('author','../img/xauthor.gif');" onmouseout="swap('author','../img/author.gif');"><img src="../img/author.gif" name=author width=40 height=40 border=0 hspace=5 alt=" автора! "></a><br>author</td>
</table>
<img src="../img/t.gif" width=500 height=4 alt=""><br><img src="../img/b.gif" width=500 height=1 alt=""><br>

<!-- Head -->

<table width=500 cellpadding=0 cellspacing=10 border=0><td><div align=justify>

<p class=title>
<img src="../img/b6.gif" width=70 height=70 align=left hspace=0 alt="">
<img src="../img/t.gif" width=5 height=70 align=left hspace=0 alt="">
ОПТИМИЗАЦИЯ<br>6.2. Примеры внутренних циклов текстурирования

<!-- Article -->

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

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

<pre class=source>
    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
    ; ...
</pre>

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

<pre class=source>
    ; ...
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
    ; ...
</pre>

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

<pre class=source>
    ; ...
    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 ?
    ; ...
</pre>

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

<p>Дальше - больше. 4.5 такта на пиксел - это тоже не предел. В fatmap.txt
(<a href="ftp://ftp.hornet.org/pub/demos/code/3d/trifill/texmap/fatmap.txt">ftp://ftp.hornet.org/pub/demos/code/3d/trifill/texmap/fatmap.txt</a>)
приводится вот такой красивый inner loop на четыре такта.

<pre class=source>
    ; текстура должна быть выравнена на 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          ;
</pre>

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

<p>И, наконец, цитата из fatmap2.txt - 4-тактовый inner loop, использующий
16:16 fixedpoint. Недостатки - текстура должна быть выравнена на 64k;
есть две команды adc, которые могут запросто испортить спаривание. Кстати,
рекомендую скачать этот самый fatmap2.txt; например, по этому адресу:
<a href="ftp://ftp.hornet.org/pub/demos/code/3d/trifill/texmap/fatmap2.zip">ftp://ftp.hornet.org/pub/demos/code/3d/trifill/texmap/fatmap2.zip</a>.


<pre class=source>
; текстура должна быть выравнена на 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
</pre>

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

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

</div>
</td></table>

<!-- Bottom Navigation -->

<img src="../img/b.gif" width=500 height=1 alt=""><br><img src="../img/t.gif" width=500 height=2 alt=""><br>
<table width=500 cellpadding=0 cellspacing=0 border=0>
<td><img src="../img/t.gif" width=5 height=1 alt=""><a href="../main.htm" onmouseover="swap('logo2','../img/xe.gif');" onmouseout="swap('logo2','../img/e.gif');"><img src="../img/e.gif" name=logo2 width=60 height=50 hspace=10 border=0 alt=" в самое начало "></a></td>
<td><p class=pagetitle><img src="../img/t.gif" width=265 height=1 alt=""><br>demo.design<br>3D programming FAQ</td>
<td align=center><p class=navy><a href="61.htm" onmouseover="swap('prev','../img/xprev.gif');" onmouseout="swap('prev','../img/prev.gif');"><img src="../img/prev.gif" name=prev width=40 height=40 border=0 hspace=5 alt=" предыдущая статья "></a><br>previous</td>
<td align=center><p class=navy><a href="../content.htm" onmouseover="swap('faq','../img/xfaq.gif');" onmouseout="swap('faq','../img/faq.gif');"><img src="../img/faq.gif" name=faq width=40 height=40 border=0 hspace=5 alt=" содержание "></a><br>content</td>
<td align=center><p class=navy><a href="63.htm" onmouseover="swap('next','../img/xnext.gif');" onmouseout="swap('next','../img/next.gif');"><img src="../img/next.gif" name=next width=40 height=40 border=0 hspace=5 alt=" следующая статья "></a><br>next</td>
</table>
<img src="../img/t.gif" width=500 height=4 alt=""><br>
<img src="../img/b.gif" width=500 height=1 alt=""><br>
<img src="../img/t.gif" width=500 height=1 alt=""><br>
<img src="../img/b.gif" width=500 height=1 alt=""><br>


</center></body>
</html>