Databases
StackOverflow2013
Postsdbo
POIntel x86 assembly optimization techniques in a sample problem
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POIntel x86 assembly optimization techniques in a sample problem
    primarykey
    data
    text
    <p>I am learning assembler quite a while and I am trying to rewrite some simple procedures \ functions to it to see performance benefits (if any). My main development tool is Delphi 2007 and first examples will be in that language but they can be easily translated to other languages as well.</p> <p>The problem states as:</p> <p>We have given an unsigned byte value in which each of the eight bits represents a pixel in one row of a screen. Each single pixel can be solid (1) or transparent (0). So in other words, we have 8 pixels packed in one byte value. I want to unpack those pixels into an eight byte array in the way that youngest pixel(bit) will land under the lowest index of the array and so on. Here is an example:</p> <pre><code>One byte value -----------&gt; eight byte array 10011011 -----------------&gt; [1][1][0][1][1][0][0][1] Array index number -------&gt; 0 1 2 3 4 5 6 7 </code></pre> <p>Below I present five methods which are solving the problem. Next I will show their time comparison and how I did measure those times.</p> <p>My questions consist of two parts:</p> <h2>1.</h2> <p>I am asking you for <strong>detailed</strong> answer concerning methods <code>DecodePixels4a</code> and <code>DecodePixels4b</code>. Why method <code>4b</code> is somewhat slower than the <code>4a</code>?</p> <p>If for example it is slower because my code is not aligned correctly then show me which instructions in a given method could be better aligned and how to do this to not break the method.</p> <p>I would like to see real examples behind the theory. Please bear in mind that I am learning assembly and I want to gain knowledge from your answers which allows me in the future to writing better optimized code.</p> <h2>2.</h2> <p>Can you write faster routine than <code>DecodePixels4a</code>? If so, please present it and describe optimization steps that you have taken. By <em>faster routine</em> I mean routine that runs in the shortest period of time in your test environment among all the routines presented here.</p> <p>All Intel family processors are allowed and those which are compatible with them.</p> <p>Below you will find routines written by me:</p> <pre><code>procedure DecodePixels1(EncPixels: Byte; var DecPixels: TDecodedPixels); var i3: Integer; begin DecPixels[0] := EncPixels and $01; for i3 := 1 to 7 do begin EncPixels := EncPixels shr 1; DecPixels[i3] := EncPixels and $01; //DecPixels[i3] := (EncPixels shr i3) and $01; //this is even slower if you replace above 2 lines with it end; end; //Lets unroll the loop and see if it will be faster. procedure DecodePixels2(EncPixels: Byte; var DecPixels: TDecodedPixels); begin DecPixels[0] := EncPixels and $01; EncPixels := EncPixels shr 1; DecPixels[1] := EncPixels and $01; EncPixels := EncPixels shr 1; DecPixels[2] := EncPixels and $01; EncPixels := EncPixels shr 1; DecPixels[3] := EncPixels and $01; EncPixels := EncPixels shr 1; DecPixels[4] := EncPixels and $01; EncPixels := EncPixels shr 1; DecPixels[5] := EncPixels and $01; EncPixels := EncPixels shr 1; DecPixels[6] := EncPixels and $01; EncPixels := EncPixels shr 1; DecPixels[7] := EncPixels and $01; end; procedure DecodePixels3(EncPixels: Byte; var DecPixels: TDecodedPixels); begin asm push eax; push ebx; push ecx; mov bl, al; and bl, $01; mov [edx], bl; mov ecx, $00; @@Decode: inc ecx; shr al, $01; mov bl, al; and bl, $01; mov [edx + ecx], bl; cmp ecx, $07; jnz @@Decode; pop ecx; pop ebx; pop eax; end; end; //Unrolled assembly loop procedure DecodePixels4a(EncPixels: Byte; var DecPixels: TDecodedPixels); begin asm push eax; push ebx; mov bl, al; and bl, $01; mov [edx], bl; shr al, $01; mov bl, al; and bl, $01; mov [edx + $01], bl; shr al, $01; mov bl, al; and bl, $01; mov [edx + $02], bl; shr al, $01; mov bl, al; and bl, $01; mov [edx + $03], bl; shr al, $01; mov bl, al; and bl, $01; mov [edx + $04], bl; shr al, $01; mov bl, al; and bl, $01; mov [edx + $05], bl; shr al, $01; mov bl, al; and bl, $01; mov [edx + $06], bl; shr al, $01; mov bl, al; and bl, $01; mov [edx + $07], bl; pop ebx; pop eax; end; end; // it differs compared to 4a only in switching two instructions (but seven times) procedure DecodePixels4b(EncPixels: Byte; var DecPixels: TDecodedPixels); begin asm push eax; push ebx; mov bl, al; and bl, $01; shr al, $01; // mov [edx], bl; // mov bl, al; and bl, $01; shr al, $01; // mov [edx + $01], bl; // mov bl, al; and bl, $01; shr al, $01; // mov [edx + $02], bl; // mov bl, al; and bl, $01; shr al, $01; // mov [edx + $03], bl; // mov bl, al; and bl, $01; shr al, $01; // mov [edx + $04], bl; // mov bl, al; and bl, $01; shr al, $01; // mov [edx + $05], bl; // mov bl, al; and bl, $01; shr al, $01; // mov [edx + $06], bl; // mov bl, al; and bl, $01; mov [edx + $07], bl; pop ebx; pop eax; end; end; </code></pre> <p>And here is how do I test them:</p> <pre><code>program Test; {$APPTYPE CONSOLE} uses SysUtils, Windows; type TDecodedPixels = array[0..7] of Byte; var Pixels: TDecodedPixels; Freq, TimeStart, TimeEnd :Int64; Time1, Time2, Time3, Time4a, Time4b: Extended; i, i2: Integer; begin if QueryPerformanceFrequency(Freq) then begin for i2 := 1 to 100 do begin QueryPerformanceCounter(TimeStart); for i := 1 to 100000 do DecodePixels1(155, Pixels); QueryPerformanceCounter(TimeEnd); Time1 := Time1 + ((TimeEnd - TimeStart) / Freq * 1000); QueryPerformanceCounter(TimeStart); for i := 1 to 100000 do DecodePixels2(155, Pixels); QueryPerformanceCounter(TimeEnd); Time2 := Time2 + ((TimeEnd - TimeStart) / Freq * 1000); QueryPerformanceCounter(TimeStart); for i := 1 to 100000 do DecodePixels3(155, Pixels); QueryPerformanceCounter(TimeEnd); Time3 := Time3 + ((TimeEnd - TimeStart) / Freq * 1000); QueryPerformanceCounter(TimeStart); for i := 1 to 100000 do DecodePixels4a(155, Pixels); QueryPerformanceCounter(TimeEnd); Time4a := Time4a + ((TimeEnd - TimeStart) / Freq * 1000); QueryPerformanceCounter(TimeStart); for i := 1 to 100000 do DecodePixels4b(155, Pixels); QueryPerformanceCounter(TimeEnd); Time4b := Time4b + ((TimeEnd - TimeStart) / Freq * 1000); end; Writeln('Time1 : ' + FloatToStr(Time1 / 100) + ' ms. &lt;- Delphi loop.'); Writeln('Time2 : ' + FloatToStr(Time2 / 100) + ' ms. &lt;- Delphi unrolled loop.'); Writeln('Time3 : ' + FloatToStr(Time3/ 100) + ' ms. &lt;- BASM loop.'); Writeln('Time4a : ' + FloatToStr(Time4a / 100) + ' ms. &lt;- BASM unrolled loop.'); Writeln('Time4b : ' + FloatToStr(Time4b / 100) + ' ms. &lt;- BASM unrolled loop instruction switch.'); end; Readln; end. </code></pre> <p>Here are the results from my machine ( Intel® Pentium® E2180 on Win32 XP) :</p> <pre><code>Time1 : 1,68443549919493 ms. &lt;- Delphi loop. Time2 : 1,33773024572211 ms. &lt;- Delphi unrolled loop. Time3 : 1,37015271374424 ms. &lt;- BASM loop. Time4a : 0,822916962526627 ms. &lt;- BASM unrolled loop. Time4b : 0,862914462301607 ms. &lt;- BASM unrolled loop instruction switch. </code></pre> <p>The results are pretty stable - times vary only by few percent between each test I've made. And that was always true: <code>Time1 &gt; Time3 &gt; Time 2 &gt; Time4b &gt; Time4a</code> </p> <p>So I think that de difference between Time4a and Time4b depends of that instructions switch in the method <code>DecodePixels4b</code>. Sometimes it is 4% sometimes it is up to 10% but <code>4b</code> is always slower than <code>4a</code>.</p> <p>I was thinking about another method with usage of MMX instructions to write into memory eight bytes at one time, but I can't figure out fast way to unpack byte into the 64 bit register.</p> <p>Thank you for your time.</p> <hr> <p>Thank you guys for your valuable input. Whish I could answer all of you at the same time, unfortunately compared to the modern CPU's I have only one "pipe" and can execute only one instruction "reply" at the time ;-) So, I will try sum up some things over here and write additional comments under your answers.</p> <p>First of all, I wanted to say that before posting my question I came up with the solution presented by Wouter van Nifterick and it was actually <strong>way slower</strong> then my assembly code. So I've decided not to post that routine here, but you may see that I took the same approach also in my loop Delphi version of the routine. It is commented there because it was giving me worser results. </p> <p>This is a mystery for me. I've run my code once again with Wouter's and PhilS's routines and here are the results:</p> <pre><code>Time1 : 1,66535493194387 ms. &lt;- Delphi loop. Time2 : 1,29115785420688 ms. &lt;- Delphi unrolled loop. Time3 : 1,33716934524107 ms. &lt;- BASM loop. Time4a : 0,795041753757838 ms. &lt;- BASM unrolled loop. Time4b : 0,843520166815013 ms. &lt;- BASM unrolled loop instruction switch. Time5 : 1,49457681191307 ms. &lt;- Wouter van Nifterick, Delphi unrolled Time6 : 0,400587402866258 ms. &lt;- PhiS, table lookup Delphi Time7 : 0,325472442519827 ms. &lt;- PhiS, table lookup Delphi inline Time8 : 0,37350491544239 ms. &lt;- PhiS, table lookup BASM </code></pre> <p>Look at the Time5 result, quite strange isn't it? I guess I have different Delphi version, since my generated assembly code differs from that provided by Wouter.</p> <p><strong>Second major edit:</strong></p> <hr> <p>I know why routine <code>5</code> was slower on my machnie. I had checked "Range checking" and "Overflow checking" in my compiler options. I've added <code>assembler</code> directive to routine <code>9</code> to see if it helps. It seems that with this directive assembly procedure is as good as Delphi inline variant or even slightly better. </p> <p>Here are the final results:</p> <pre><code>Time1 : 1,22508325749317 ms. &lt;- Delphi loop. Time2 : 1,33004145373084 ms. &lt;- Delphi unrolled loop. Time3 : 1,1473583622526 ms. &lt;- BASM loop. Time4a : 0,77322594033463 ms. &lt;- BASM unrolled loop. Time4b : 0,846033593023372 ms. &lt;- BASM unrolled loop instruction switch. Time5 : 0,688689382044384 ms. &lt;- Wouter van Nifterick, Delphi unrolled Time6 : 0,503233741036693 ms. &lt;- PhiS, table lookup Delphi Time7 : 0,385254722925063 ms. &lt;- PhiS, table lookup Delphi inline Time8 : 0,432993919452751 ms. &lt;- PhiS, table lookup BASM Time9 : 0,362680491244212 ms. &lt;- PhiS, table lookup BASM with assembler directive </code></pre> <p><strong>Third major edit:</strong></p> <hr> <p>In opinion @Pascal Cuoq and @j_random_hacker the difference in execution times between routines <code>4a</code>, <code>4b</code> and <code>5</code> is caused by the data dependency. However I have to disagree with that opinion basing on the further tests that I've made.</p> <p>I've also invented new routine <code>4c</code> based on <code>4a</code>. Here it is:</p> <pre><code>procedure DecodePixels4c(EncPixels: Byte; var DecPixels: TDecodedPixels); begin asm push ebx; mov bl, al; and bl, 1; mov [edx], bl; mov bl, al; shr bl, 1; and bl, 1; mov [edx + $01], bl; mov bl, al; shr bl, 2; and bl, 1; mov [edx + $02], bl; mov bl, al; shr bl, 3; and bl, 1; mov [edx + $03], bl; mov bl, al; shr bl, 4; and bl, 1; mov [edx + $04], bl; mov bl, al; shr bl, 5; and bl, 1; mov [edx + $05], bl; mov bl, al; shr bl, 6; and bl, 1; mov [edx + $06], bl; shr al, 7; and al, 1; mov [edx + $07], al; pop ebx; end; end; </code></pre> <p>I would say it is pretty data dependent.</p> <p>And here are the tests and results. I've made four tests to make sure there is no accident. I've also added new times for the routines proposed by GJ (Time10a, Time10b).</p> <pre><code> Test1 Test2 Test3 Test4 Time1 : 1,211 1,210 1,220 1,213 Time2 : 1,280 1,258 1,253 1,332 Time3 : 1,129 1,138 1,130 1,160 Time4a : 0,690 0,682 0,617 0,635 Time4b : 0,707 0,698 0,706 0,659 Time4c : 0,679 0,685 0,626 0,625 Time5 : 0,715 0,682 0,686 0,679 Time6 : 0,490 0,485 0,522 0,514 Time7 : 0,323 0,333 0,336 0,318 Time8 : 0,407 0,403 0,373 0,354 Time9 : 0,352 0,378 0,355 0,355 Time10a : 1,823 1,812 1,807 1,813 Time10b : 1,113 1,120 1,115 1,118 Time10c : 0,652 0,630 0,653 0,633 Time10d : 0,156 0,155 0,172 0,160 &lt;-- current winner! </code></pre> <p>As you may see the results of <code>4a</code>, <code>4b</code>, <code>4c</code> and <code>5</code> are very close to each other. Why is that? Because I've <strong>removed</strong> from 4a, 4b (4c already doesn't have it) two instructions: <code>push eax</code> and <code>pop eax</code>. Since I know I wont use anywhere else in my code the value under eax I do not have to prereserve it. Now my code has only one pair of push/pop so as the routine 5. Routine 5 prereserves value of eax beacause it firstly make copy of it under ecx but it deson't prereserve ecx.</p> <p>So my conclusion is that: the difference in time execution of 5 and 4a and 4b (before the third edit) <strong>didn't concern data dependecny but was caused by additional pair of push / pop instructions</strong>.</p> <p>I am very interested in your comments.</p> <p>After a few days GJ invented even faster routine (Time 10d) than PhiS's. Nice work GJ!</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USPhiS
    1. USWodzu
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POIntel x86 assembly optimization techniques in a sample problem
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POIntel x86 assembly optimization techniques in a sample problem
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POIntel x86 assembly optimization techniques in a sample problem
      1. USPhiS
      1. VTFavorite
    1. CONitpick: I think you mean "solid or *transparent*". "Opaque" means "can't be seen through".
      singulars
      1. POIntel x86 assembly optimization techniques in a sample problem
      1. USj_random_hacker
    2. CO@j_random_hacker: thank you, will correct that.
      singulars
      1. POIntel x86 assembly optimization techniques in a sample problem
      1. USWodzu
    3. CONormally, the Delphi "assembler" directive doesn't do anything (just for backwards compatibility with Turbo Pascal), so I am a bit surprised. Which Delphi version are you using? Do you have any compiler options turned on to always generate stack frames or something similar?
      singulars
      1. POIntel x86 assembly optimization techniques in a sample problem
      1. USPhiS
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload