home *** CD-ROM | disk | FTP | other *** search
/ Collection of Hack-Phreak Scene Programs / cleanhpvac.zip / cleanhpvac / FAQSYS18.ZIP / FAQS.DAT / OPTIMIZE.TXT < prev    next >
Text File  |  1996-01-04  |  46KB  |  1,101 lines

  1. ---------------------------------
  2.  
  3. OPTIMIZE.TXT
  4.  
  5. ---------------------------------
  6.  
  7. Some useful informations about how to optimize code on a 386/486/Pentium
  8.  
  9. This initially was a posting on the Internet made by
  10.  
  11.         Michael Kunstelj.
  12.         Contact at :  virteam@smoke.canberra.edu.au
  13.                         or
  14.                       mick@cairo.anu.edu.au
  15.  
  16. Initially it included 486 and Pentium optimizations with some "holes"
  17. (like the profiling instructions), i filled the Pentium "holes"
  18. then refined some exaplanations (uh! maybe i made 'em worse! :} ).
  19. Then added some not-so-obviuos cache optimization techniques
  20. and other infos about specific optimizations you can make on 386.
  21.  
  22.         Lorenzo Micheletto
  23. N.B.
  24.         I added some generic examples about how a cpu works
  25.         BUT they are just examples, intel cpus work in slightly different ways.
  26.  
  27. N.B./2
  28.         Always check in the books for things you are not sure
  29.         there may be typos here.
  30.  
  31. ----------------------------------
  32. Brief intro about how a CPU works
  33. ----------------------------------
  34.  
  35. Now a brief intro on the innards Intel CPUs.
  36.  
  37. Most processors these days have within in them a system termed a "pipeline".
  38. The 486 / 586 are certainly within this category.  However, most people 
  39. aren't quite sure what exactly a pipeline is, here follows a complete
  40. explanation:
  41.  
  42. The execution of a machine code instruction can be roughtly split
  43. in five stages:   [n.b. this is a generic pipeline]
  44.         1) FETCH instruction opcode and immediate data
  45.         2) DECODE opcode and align immediata data into temporary registers
  46.         3) CALCULATE ADDRESS OF OPERANDS and load 'em into memory.
  47.            (calculate the address of memory locations to access
  48.             and select the register operands to use)
  49.            (sometimes called DECODE 2)
  50.         4) EXECUTE instruction (loading memory operands if needed)
  51.            & write results to INTERNAL registers
  52.         5) WRITEBACK memory-operand results to memory
  53.  
  54. Every stage takes ONE OR MORE cpu cycles to be completed, but usually
  55. a modern cpu needs just one cpu cycle for every execution stage
  56. (excluding stages 1 and 5 that have to deal with memory/cache access
  57.  and stage 4 when "complex" microcoded instructions are executed).
  58.  
  59. A cpu-core ( the "real" cpu, not cache support nor the other things
  60. that are usually integrated into a modern cpu) has five "specialized"
  61. units, one for every stage of instruction execution, plus a "register file"
  62. (and ultra-fast on-chip memory where internal register values
  63.  are stored) and a CONTROL UNIT.
  64.  
  65. The control unit "coordinates" the action of all the other units
  66. so they can work together.
  67.  
  68. Here follows an extended ascii drawing
  69. of ONE on the many ways these units can be connected
  70. (use a ms-dos text editor to see this, or convert it to the
  71.  Windows line-drawing character set if you are using a Windows editor):
  72.  
  73.               MEMORY INPUT ("memory load" unit)
  74.                         │                                ┌────────────┐
  75.                         └─────┬─>┌────────────┐<────────>│            │
  76.                              ┌┼┐ │ FETCH      │          │            │
  77.        ┌─────────────────────┘│└>└────────────┴──┐       │            │
  78.        │ (instruction pointer)│                  │       │            │
  79.        │                      │  ┌────────────┐<─┘       │            │
  80.        │                      │  │ DECODE     │<────────>│            │
  81.        │                      │  └────────────┴──┐       │            │
  82.        │                      │                  │       │            │
  83.        │                      │  ┌────────────┐<─┘       │ CONTROL    │
  84.        │                     ┌┘  │ ADDRESS C. │<────────>│            │
  85.        │                ┌────┼──>└────────────┴──┐       │ UNIT       │
  86.        │                │    └┐                  │       │            │
  87.  ┌─────┴────────────────┴─┐   └─>┌────────────┐<─┘       │            │
  88.  │ REGISTER FILE          ├─────>│ EXECUTE    │<────────>│            │
  89.  └────────────────────────┘<─────┴────────────┴──┐       │            │
  90.                                                  │       │            │
  91.                                  ┌────────────┐<─┘       │            │
  92.                                  │ WRITEBACK  │<────────>│            │
  93.                                  └────────────┴──┐       │            │
  94.                                                  │       └────────────┘
  95.                                MEMORY OUTPUT <───┘
  96.                               ("memory store" unit)
  97.  
  98. If you look the drawing, the control unit needs to communicate
  99. with all the other units to make 'em work together.
  100. Usually the "control unit" is scattered in little units that coordinates
  101. intruction and data flow between adiacent units, but you can think
  102. at it as a single indipendent unit.
  103.  
  104. The five execution units are what gives the "raw" cpu power
  105. but the control unit is what lets you fully utilize 'em.
  106.  
  107. Let's suppose every unit performs one operation in one step.
  108.  
  109. With a "cheap" control unit, to execute a complete machine language
  110. instruction you first enable  FETCH, then you enable DECODE
  111. and so on until WRITEBACK is completed and the control unit
  112. enables FETCH again to execute the next instruction.
  113.  
  114. This is what happens into an "absolutely not pipelined" cpu
  115. with "one cycle" stages, the fastest instructions takes 5 cycles
  116. but the control unit is very simple
  117. (just a circular shift register that enables one unit at a time).
  118.  
  119. Of course this is the worst case, nobody is so jerk to build
  120. a cpu like that.
  121.  
  122. Every cpu stage-execution unit is a stand alone thing, it has its hardware
  123. and its "temporary registers" so it is capable to operate "alone".
  124.  
  125. So, IF THE CONTROL UNIT can SINCHRONIZE the operations
  126. of all the stage-execution units, it can make 'em WORK IN PIPELINE
  127. (like in a factory, where every worker/robot in a production line
  128.  a) receives a partially refined product from the previous worker in line
  129.  b) performs some simple operations to refine the product a little more
  130.  c) pass the result to the next worker in line
  131. ).
  132. A cpu with such a control unit is called a pipelined CPU.
  133.  
  134. If you have to execute in sequence instructions A,B,C,D,E
  135. on a pipelined processor ....
  136.  
  137. While the WRITEBACK unit is performing stage 5 of A
  138. the EXECUTION         unit can perform stage 4 of B
  139. the ADDRESS CALCULATE unit can perform stage 3 of C
  140. the DECODE            unit can perform stage 2 of D
  141. and the FETCH         unit can perform stage 1 of E
  142.  
  143. So if you start the cpu at instruction A
  144. it looks like that instruction A takes 5 cycles
  145. while instructions B,C,D,E (immediately one stage behind) looks like they take
  146. JUST ONE CYCLE!!!
  147.  
  148. So if you execute a SEQUENCE of 8 instructions
  149. on a "not pipelined" processor with a five stage "pipe"
  150. it takes 40 steps to execute the sequence
  151. while on a pipelined processor this takes 5+7=12  steps!!!
  152. ( 5 steps for the first instruction to get thru the pipeline
  153.  then 7 steps for the other instructions immediately "one step" behind)
  154. And the more instructions are executed in sequence, the more it looks like
  155. every instruction takes "just" one cycle to execute.
  156.  
  157.  
  158. This is of course the optimal situation, when the processor pipeline
  159. is filled and WHEN EVERY INSTRUCTION DOES NOT USE MEMORY/REGISTER OPERANDS
  160. "still under processing" IN SUCCESSIVE EXECUTION-STAGES!!!!!!
  161.  
  162. -------------------------------------------------------------------------------
  163. THINGS A CPU MUST CHECK TO MAKE A PIPELINE WORK CORRECTLY
  164.  
  165. A pipelined processor control-unit must "check" :
  166.  A) at stage 1 (FETCH)
  167.     IF in stage 2..4 there are JUMP instructions
  168.              [ they change the program counter
  169.                (the same register used by the fetch unit)
  170.              ]
  171.     THEN stage 1 must "wait" until the jump is completed
  172.          and then "restarts", loading  the memory location pointed by the
  173.          new program counter value.
  174.  
  175.     Because the jump opcode must pass thru the decode stage ...
  176.     ... if the DECODE unit "detects" a jump opcode, it makes the FETCH unit
  177.     "stops" AT LEAST for two cycles until the jump is performed.
  178.     This of course means the processor pipeline "wastes" some cpu cycles.
  179.  
  180.     A 486 handles jumps in a smarter way, when the FETCH unit loads
  181.     a jump instruction, it goes on assuming the jump WON'T BE TAKEN
  182.     (it read the instructions following the jump).
  183.     If the jump is taken, the values in the DECODE 1 and DECODE 2 units
  184.     are "discarded" and the FETCH unit starts loading from the new
  185.     program counter value.
  186.     This explains why on 486 relative jumps (the fastest jumps) takes
  187.     3 cycles if taken    (two cycles "lost")
  188.     1 cycle if not taken (no cycles lost)
  189.  
  190.     A "smarter" control unit can recognize in advance unconditional jumps
  191.     and start immediately loading opcodes from the new program counter
  192.     location
  193.     AND/OR try to "predict" the jump destination of conditional jumps
  194.     (like the Pentium does).
  195.  
  196.  
  197.  B) at step 3  (ADDRESS CALCULATION)
  198.     IF in stage 3 a register needed for address calculation is under processing
  199.        in stage 4 (EXECUTE)
  200.     THEN the stage 3 unit generates a "do nothing" control sequence
  201.          for one cpu cycle.
  202.  
  203.  C) memory access conflicts
  204.     These can be caused by lots of different things, they are usually
  205.     resolved by the memory load/store units.
  206.  
  207. Told in a short way, in a fully pipelined processor
  208. when the pipeline is "working on a sequence"
  209. the first instruction in the sequence takes the full execution time
  210. while the other instructions takes a shorter time (usually one cycle)
  211. because they are immediately behind, this means they "look faster"
  212. (and in fact they are, because the pipeline fully utilizes all the functional
  213. units it has).
  214.  
  215. If some instructions "modify" values needed in the previous cpu stages
  216. the control unit stops the unit needing those values (and the others behind it)
  217. and inserts "do nothing" codes into the successive units in the processor pipe
  218. to make things work as expected (this is called a PIPELINE STALL
  219. or a PIPELINE FLUSH)
  220.  
  221. This explains why usually a taken jump takes more time than one that's not taken
  222. (when a jump is performed you must flush the pipeline).
  223.  
  224. The newer processors includes JUMP PREDICTION UNITS that handles
  225. jump faster, but the less you jump, the better.
  226.  
  227. ------------------------------------------------------------------------------
  228. PIPELINING IN INTEL PROCESSORS:
  229.  
  230. The 386 is a "partially pipelined" processor with some optimizations.
  231. It checks for jumps ( A check) in a quite slow way
  232. and most of times can execute every stage in one cycle.
  233. It cannot perform the address generation check (B check)
  234. so it must execute stage 3 and 4 in "not pipelined mode".
  235. This explains why THE FASTEST 386 INSTRUCTIONS TAKE TWO CYCLES
  236. ( stage 3 unit must wait stage 4 to complete before managing
  237.   the next instructions).
  238.  
  239. The 486 has an improved EXECUTION unit (stage 4), improved memory access
  240. AND its control unit can perform the address generation check
  241. so that it can pipe stage 3 and 4 if there are no
  242. register/memory conflicts with two successive instructions.
  243. This explains why lots of 486 instructions take just one cycle
  244. (if the pipeline is filled and no pipeline stalls are produced).
  245. What's more, pipeline reloading is improved, so even jumps have less
  246. impact on execution time.
  247. It also has a 4Kbyte internal cache that boosts memory access
  248. and allows big gains from strip-mining optimizations.
  249. Another nice thing is the BURST READ access that accelerates memory reads
  250. when it needs to update its internal cache.
  251.  
  252. PIPELINED,SUPERSCALAR & BRANCH PREDITING CPU: THE PENTIUM
  253.  
  254. Well, what's beyound a fully pipelined processor like the 486 ?
  255. There is a 586/Pentium processor, that's SUPER SCALAR (more than one pipeline)
  256. and BRANCH PREDICTING (it has a specialized unit that annotates the
  257. position and the result of some og the most recent  jumps, and so
  258. it can try to "guess" from where the next instruction after the jump execution
  259. will be loaded, if it guess correcly a pipeline stall is avoided, else
  260. it stalls)(this helps speeding up the execution of nested loops).
  261.  
  262. The 586 can execute UP TO TWO integer operations in a single step
  263. (because it has TWO pipelines, but with some limitations)
  264. it can BURST READ/WRITE and has TWO indipendent 8k caches
  265. (Harvard style CPU to cache architecture) this means you can
  266. strip-mine to the max. if strips fit into the 8Kbyte data cache.
  267.  
  268. Well, now you know how they work, let's see how to make 'em work to the max.
  269.  
  270. ------------------------------------------------------------------------------
  271. SPEEDING UP 486/586 CODE.
  272. ------------------------------------------------------------------------------
  273.  
  274. -------------------------------
  275. ADDRESS GENERATION STALLS (AGI)
  276. -------------------------------
  277. An Address Generation Interlock occurs when a register which is
  278. currently being used as the base or an index was the destination component 
  279. of a previous instruction (the stage 3 to 4 pipeline stall i described above)
  280.  
  281. For example,:
  282.  
  283.         add edx, 4
  284.         // AGI, ONE CLOCK STALL
  285.         mov esi, [edx]
  286.  
  287. For the 486, AGI's can only occur on adjacent instructions.
  288.  
  289. On the 586 or Pentium instructions up to 3 locations away can cause an AGI.
  290. ( i.e. an instruction waiting to execute step 4 on pipeline 1
  291.        may need to wait the result produced by an instruction
  292.        still executing on pipeline 2)
  293.  
  294.                 pipeline step              pipe1  pipe2
  295.         addres_calculate/fetch_operand       C      D    |
  296.         execute                              B      A    |
  297.                                                          V
  298.  
  299.       If C needs the results of A, it must stall pipeline 1 for one cycle
  300.       to wait for A to "exit from" pipeline 2.
  301.       If C needs the results of D, it must stall pipeline 1 for two cycles
  302.       to wait for D to "exit from" pipeline 2.
  303.  
  304. An example of 3 instruction away AGI:
  305.  
  306.         add esi, 4
  307.         pop ebx
  308.         dec ebx
  309.         mov edx, [esi]
  310.  
  311. Takes 4 clocks on a 486.  On a 586, the move command must wait for the 
  312. add command, thus AGI stalling for one clock.  The code above then 
  313. would run in three clock cycles on a 586.
  314.  
  315. Remember that even instructions that read or write implicitly to registers
  316. cause AGI stalls:
  317.  
  318.     mov esp,ebp
  319.     pop ebp.
  320.  
  321.     is executed as...
  322.  
  323.     mov esp,ebp
  324.     [agi]          ; pop uses the esp as a pointer
  325.     pop ebp
  326.  
  327. ----------------------------
  328. INSTRUCTION DECODING STALLS:
  329. ----------------------------
  330.  
  331. When decoding an instruction with an IMMEDIATE VALUE
  332. AND
  333. either an  INDEX OFFSET or an IMMEDIATE DISPLACEMENT
  334. 486's have a one clock penalty. (586's do not)
  335.  
  336.         Example:
  337.  
  338.                 mov  spam, 248
  339.                 mov dword ptr [esp+4], 1
  340.  
  341. This happens because the decode stage of the pipeline can read and decode
  342. ONE "immediate" value at a time
  343. while an immediate value and an immediate offset are TWO immediate values.
  344. The 586 instead has not such problems (when decoding) (execution is different)
  345.  
  346. ---------------------------------
  347. REGISTER ACCESS CPU STALLS:
  348. ---------------------------------
  349.  
  350. 486's have a 1 clock penalty when modifying the lower word of a DWORD register
  351. that's used immediately after it, 586's do not.
  352.         Example:
  353.                 mov al,0
  354.                 mov [ebp], eax
  355.                 (a one clock penalty on 486, no penalty on a 586)
  356.  
  357.  
  358. -------------------------------
  359. CODE ALIGNMENT
  360. -------------------------------
  361.  
  362. To speed up the instructions, alignment of code should be on the
  363. beginning of cache boundaries.
  364. (32 bytes on 586, 16 bytes on 486)
  365.  
  366. Thus, start your routine on the start of the cache page.
  367. This way, when someone calls the routine, the processor
  368. will just have to load a cache line to get the first sequence to feed
  369. into the pipeline, and while they are executing it will have
  370. enough time to load the other cache lines needed.
  371.  
  372. This will speed up the processing  of all the instructions within that page.
  373. The effect of this speed up on the 586 is not a dramatic as is it is on the 486
  374. because the 586 has bigger caches and faster access to memory
  375. so a cache line load/store has less impact on cpu.
  376.  
  377. ------------------------------
  378. DATA ALIGNMENT
  379. ------------------------------
  380.  
  381. Misaligned access in the data cache causes an extra 3 cycles on both the 
  382. 486 and 586.
  383.  
  384. Ways to speed up data:
  385. For DWORD data, alignment should be on a 4-byte boundary.
  386. For WORD data, alignment should be on a 2 byte boundary for the 486, 
  387. and simply within the 4-byte page for the 586.
  388. For 8 byte data (64 bits), data should be aligned on a 8-byte boundary
  389. so it is possible to use BURST READS (and burst writes too, on a Pentium).
  390.  
  391. And yes, on many applications with tight inner loops, these things do 
  392. accumulate to make a noticeable speed-up.
  393.  
  394. -------------------------------------------------------------------------------
  395. SPEEDING UP REGISTER AND OPERAND USAGE
  396. -------------------------------------------------------------------------------
  397.  
  398. Use the EAX as much as possible.
  399. Many instructions are 1 byte shorter when using EAX.
  400. That's less code you have to move around and slightly less internal processing.
  401. Use the DS register as much as possible for roughly the same reason,
  402. In the case of several references being made to a variable addressed with a 
  403. displacement, load the displacement into a register.
  404.  
  405. Try to use the ESP register to reference the stack in lower levels of your 
  406. subroutines (faster than push/pop things and leaves EBP free for other
  407. uses)
  408.  
  409.  
  410. -------------------------------------------------------------------------------
  411. HANDY INFO ON SPEEDING UP INTEGER INSTRUCTIONS
  412. -------------------------------------------------------------------------------
  413.  
  414. 1. Avoid using complex instructions like LEAVE, ENTER, LOOP, string 
  415.    instructions etc  Simpler instructions will get the job done faster.
  416.    Simpler instructions have been getting faster with every new processor
  417.    that has come along.
  418.  
  419. 2. With 8-bit operands, do your best to use the byte opcodes, rather than 
  420.    using the 32 bit instructions  with sign and zero extended modes.
  421.    Internal sign extension is expensive, and speed increases can be found by
  422.    simplifying the process as much as possible.
  423.  
  424. 3.  LEA's generally increase the chance of AGI's.  However, LEA's can be
  425.     advantageous because:
  426.     *  In many cases an LEA instruction may be used to replace constant
  427.        multiply instructions. (a sequence of LEA, add and shift for example)
  428.     *  LEA may be used as a three/four operand addition instruction.
  429.        LEA ECX, [EAX+EBX*4+ARRAY_NAME]
  430.     *  Can be advantageous to avoid copying a register when both operands to
  431.        an ADD are being used after the ADD as LEA need not overwrite its
  432.        operands.
  433.  
  434.     The general rule is that the "generic"
  435.  
  436.     LEA A,[B+C*INDEX+DISPLACEMENT]
  437.  
  438.         where A can be a register or a memory location and B,C are registers
  439.         and INDEX=1,2,4,8
  440.         and DISPLACEMENT = 0 ... 4*1024*1024*1024
  441.                            or (if performing signed int operations)
  442.                            -2*1024*1024*1024 ... + (2*1024*1024*1024 -1 )
  443.  
  444.     replaces the "generic" worst-case sequence
  445.  
  446.     MOV X,C    ; X is a "dummy" register
  447.     MOV A,B
  448.     MUL X,INDEX    ;actually  SHL X, (log2(INDEX))
  449.     ADD A,DISPLACEMENT
  450.     ADD A,X
  451.  
  452.     So using LEA you can actually "pack"  up to FIVE instructions into one
  453.     Even counting a "worst case" of TWO OR THREE AGIs caused by the LEA
  454.     this is very fast compared to "normal" code.
  455.     What's more, cpu registers are precious, and using LEA
  456.     you don't need a dummy "X" register to preserve the value of B and C.
  457.  
  458. 4. Zero-Extension with short ints terror tales
  459.  
  460.   The MOVZX  takes four cycles to execute due to due zero-extension
  461.   wobblies. A better way to load a byte into a register is by:
  462.      xor eax,eax
  463.      mov al,memory
  464.  
  465.   As the xor just clears the top parts of EAX, the xor may be placed on the
  466.   OUTSIDE of a loop that uses just byte values.
  467.   The 586 shows greater response to such actions.
  468.  
  469.   It is recommended that 16 bit data be accessed with the MOVSX and
  470.   MOVZX if you cannot place the XOR on the outside of the loop.
  471.  
  472.   N.B. Do the "replacement" only for movsx/zx inside loops.
  473.  
  474. 5. When comparing a value in a register with 0, use the TEST command.
  475.   
  476.   TEST operands by ANDing the operands together without spending any
  477.   internal time worrying about a destination register.
  478.   Use test when comparing the result of a boolean AND command with an
  479.   immediate constant for equality or inequality if the register is EAX.
  480.   You can also use it for zero testing.
  481.   (i.e. test ebx,ebx  sets the zero flag if ebx is zero)
  482.  
  483. 6. Address Calculations
  484.  
  485.   Pull address calculations into load and store instructions.  Memory
  486.   reference instructions have 4 operands: a relocatable time segment base, a
  487.   base register, a scaled index register and a displacement.  Often several
  488.   integer instructions can be eliminated by fully using the operands of
  489.   memory addresses.  (more on this later)
  490.  
  491. 7.  INTEGER DIVIDE
  492.   In most cases, an Integer Divide is preceded by a CDQ instruction.
  493.   This is as  divide instructions use EDX:EAX as  the dividend and CDQ sets
  494.   up EDX.
  495.   It is better to copy EAX into EDX, then arithmetic-right-shift EDX 31 places
  496.   to sign extend.
  497.   The copy/shift instructions take the same number of clocks as CDQ,
  498.   however, on 586's allows two other instructions to execute at the same
  499.   time.  If you know the value is a positive, use XOR EDX,EDX.
  500.  
  501. 8. INTEGER MULTIPLY
  502.   The integer multiply by an immediate can usually be replaced with a faster
  503.   and simpler series of shifts, subs, adds and lea's.
  504.   As a rule of thumb when 6 or fewer bits are set in the binary representation
  505.   of the constant, it is better to look at other ways of multiplying and not use
  506.   INTEGER MULTIPLY. (the thumb value is 8 on a 586)
  507.   A simple way to do it is to shift and add for each bit set, or use LEA.
  508.  
  509.   Here the LEA instruction comes in as major cpu booster, for example:
  510.       LEA ECX,[EDX*2]       ; multiply EDX by 2 and store result into ECX
  511.       LEA ECX,[EDX+EDX*2]   ; multiply EDX by 3 and store result into ECX
  512.       LEA ECX,[EDX*4]       ; multiply EDX by 4 and store result into ECX
  513.       LEA ECX,[EDX+EDX*4]   ; multiply EDX by 5 and store result into ECX
  514.       LEA ECX,[EDX*8]       ; multiply EDX by 8 and store result into ECX
  515.       LEA ECX,[EDX+EDX*9]   ; multiply EDX by 9 and store result into ECX
  516.  
  517.   And you can combine leas too!!!!
  518.       lea ecx,[edx+edx*2]   ;
  519.       lea ecx,[ecx+ecx*8]   ;  ecx <--  edx*27
  520.   (of course, if you can, put three instructions between the two LEA
  521.    so even on Pentiums, no AGIs will be produced).
  522.  
  523. 9. Clearing Registers
  524.   Using   XOR reg,reg is fast but sets up conditions codes.
  525.   A slightly slower way to do it of course is to mov reg,0
  526.   which preserves condition codes.
  527.  
  528. 10. Avoid ENTER, instead, try something like:
  529.   PUSH EBP
  530.   mov ebp, esp
  531.   sub esp, BYTE_COUNT
  532.  
  533. 11. JUMP INSTRUCTIONS
  534.   Jump instruction come in two forms, one real near that jumps between -127
  535.   and 128 of the current location, and a 32 bit version that does a full jump.
  536.   The short form is quite a bit faster, however unfortunately many compilers
  537.   put long jumps where short jumps would suffice.
  538.   To ensure that short jumps can be used (when you know it is possible),
  539.   explicitly specify the destination as being byte length
  540.   (i.e use jmp short instead of plain jmp, if you can)
  541.  
  542. 12. Task Switching
  543.   Task Switching is evil.  It is slow,  real slow.  Avoid task switching too
  544.   often, as more and more of your time will be spent in processing the task
  545.   switch.
  546.   For faster task switching, perform you task switching in software.  This
  547.   allows a smaller processor state to be saved and restored.  Anything that
  548.   shaves time off  75+ clock cycles isn't all that bad in my book.
  549.  
  550. 13.  Minimize segment register loads and the use of far pointers as dearly
  551.   much as you can.  If you are doing a lot of processing on a small piece of
  552.   data far away, it might be faster just to copy the data to nearby and work
  553.   on it there (by the way, this is a good reason to use flat protected mode).
  554.  
  555. ...and....
  556.  
  557. 14. THINK ABOUT WHAT YOU WANT TO DO
  558.   All the other optimisations of Unrolling Loops, moving the invariant data
  559.   etc still apply.  That, however, is more an algorithmic problem for you, but
  560.   still keep it firmly in mind.
  561.  
  562. _______________________________________________________________________________
  563. 586 Specific Optimizations
  564. -------------------------------------------------------------------------------
  565.  
  566. The 586Pent has a five stage pipeline structure.
  567. However, the pipeline is split into two different pipelines, known 
  568. as Pipeline U and Pipeline V.   This allows two instructions to be
  569. executed in parallel and thus presents the opportunity of 
  570. executing two/instuctions per clock.
  571. The U pipeline is very much like the 486 pipeline, in that it can handle
  572. the entire set of instructions.  Pipeline V on the other hand can
  573. handle only "simple" instructions.
  574. The fast parts of the U and V pipelines are possible as much of the 
  575. functions are hardwired not microcoded.
  576.  
  577. Anyway, I've blurted on about that for a bit, but what you want to know
  578. is "How to I get two instructions running in one clock/cycle?"
  579.  
  580. Lament no further, here are the criteria:
  581.  
  582.   1. Both instructions must be simple (see below)
  583.   2. There must not be a read-after-write or write-after-read
  584.       register/flag dependencies between them.
  585.   3. Neither can have a displacement and an immediate
  586.   4. Instructions with prefixes can only occurr in the U-pipe
  587.      (except for branches on condition jz,jc, etc.etc.)
  588.  
  589. The following are considered "simple" instructions,
  590. the ALU means any ALU command (ADD etc):
  591.  
  592.  1. Mov reg, reg/mem/immed
  593.  2. mov mem, reg/imm
  594.  3. ALU reg, reg/mem/immed
  595.  4. ALU mem, reg/immed
  596.  5. inc reg/mem
  597.  6. dec reg/mem
  598.  7. push reg/mem
  599.  8. pop reg
  600.  9. nop
  601.  10. lea reg/mem
  602.  11. Jmp/ Call / Jcc near
  603.  
  604. N.B Remember only the U pipe can perform SHIFTS/ROTATIONS
  605.     so "couple" every shift/rol with a simple instruction
  606.     before and after to be sure every pipeline is filled.
  607.  
  608. Note, however, than while both pipelines can perform ALU
  609. instructions concurrently, this is not the case when
  610. one ALU instruction requires the output of the
  611. other pipeline ALU instruction.
  612. Example:  ALU instruction in pipe U and
  613.           performing ADC in pipe V.
  614.  
  615. There are two exceptions to this rule:
  616. 1) In the case of a compare/branch combination.
  617. 2) With push/pop combinations (because of optimized stack access)
  618.  
  619. --------------------------
  620. Branch Prediction
  621. -------------------------
  622.  
  623. Another nice optimisation with the 586 hardware is that whenever there is 
  624. a possibility of a jump, for example, Jg, the 586 can automatically
  625. start "reading ahead" code from the jump location just in case the the
  626. Jump is accepted.  Remember the CODE alignment thing above?  Well,
  627. it couldn't hurt your grandmother to align the labels on the code pages.
  628.  
  629. ------------------------------------------
  630. Amazing new 586 Optimizations and speedups
  631. ------------------------------------------
  632.  
  633. The 586 has a lot of really nice optimizations and kick-ass
  634. features in addition to what I've mentioned above, unfortunately,
  635. this information is proprietary and will only be given
  636. to people who sign non-disclosure agreements and shell out a
  637.  $$ or two...  Bummer...
  638. (Meethinks, 586 clone-makers won't be too happy about that... :-) )
  639. Compiler/OS makers will probably be the purchasers.
  640. Quite a few of these optimisations won't work on anything less than
  641. a 586, so don't sweat too much about it.  Hey, just write
  642. for 386/486/586 and you'll be ok.
  643.  
  644. Hovewer, i found a nice article on July 1994 Byte about some
  645. "secret weapons of Pentium coders"....
  646.  
  647. ============================================================================
  648. PENTIUM'S PROFILING REGISTERS:
  649.  
  650. Pentiums have a set of 64bit "machine specific registers" (MSR)
  651. that are accessed by way of the RDMSR (read MSR) and WRMSR (write MSR)
  652. instructions.
  653.  
  654. THESE ARE PROTECTED MODE, RING 0 INSTRUCTIONS (CPU LEVEL 0)
  655. ( can work in a 386Powered programs only if executing under VCPI
  656.   XMS or "no V86 manager"
  657.   or if you find a way to "toggle" DPMI from ring 3 to ring 0)
  658. (I think they can work even if you boot ms-dos in real mode
  659.  and use the proper instruction prefixes needed to execute
  660.  32bit instructions in real mode).
  661.  
  662. -----------------------------------------------------------
  663. RDMSR   Read MSR
  664.         Copies the MSR register indexed by ECX
  665.         into the 64bit pair  EDX:EAX
  666.  
  667.         RDMSR macro
  668.                 db 0Fh,032h
  669.         endm
  670. -----------------------------------------------------------
  671. WRMSR   Write MSR
  672.         Copies into the MSR register indexed by ECX
  673.         the value contained into the 64bit pair  EDX:EAX
  674.  
  675.         Macro to insert it into code if your assembler
  676.         does not support Pentiums:
  677.  
  678.         WRMSR macro
  679.                 db 0Fh,030h
  680.         endm
  681. -----------------------------------------------------------
  682.  
  683.  
  684. Intel Pentium user manuals, documents only MSR 0, 1 and 0Eh
  685. and states that MSR 3, 0Fh and above 13h are reserved and illegal.
  686.  
  687. So, what's left? And what's useful to you ?
  688.  
  689. MSR 10h is the counter of CPU CYCLES since last power-up.
  690. That value can also be read with the RDTSC (Read time stamp counter)
  691. instruction)
  692. RDTSC is 0Fh,031h in bytes and must be executed while in ring 0 too.
  693.  
  694. MSR 10h is the most precise timer available on the Pentium
  695. because it "ticks" at the CPU frequency.
  696.  
  697. Then comes MSR 11h,12h and 13h there you will find the hot stuff
  698.  
  699. The lower 32bits of MSR 11h are actually two INDEXES
  700. INTO THE CPU PROFILING REGISTERS!!!!
  701.  
  702. The profiling registers are CPU EVENT TIMERS AND COUNTERS
  703. they can keep track of what's going on inside and outside
  704. your super-duper processor, they can detect nearly everything the CPU does.
  705.  
  706. The first 16bits of MSR11h selects
  707. the profiling register accessible thru MSR 12h.
  708. The second 16bits of MSR11h selects
  709. the profiling register accessible thru MSR 13h.
  710.  
  711. Here comes the format of the "profiling register indexes":
  712. bit 0..5 : type of the profiling register to access
  713. bit    6 : Set if you want to monitor the events in cpu ring 0,1,2 (system)
  714. bit    7 : Set if you want to monitor the events in cpu ring 3 (user level)
  715. bit    8 : 0 = access count-of-hardware-events
  716.            1 = access count-of-total-cpu-cycles used to process the cumulated
  717.                events.
  718.            (i'm not sure of this, maybe 0 means count time and 1 count events)
  719. bit 9..15: UNKNOWN, DO NOT MODIFY
  720.  
  721.  
  722.  
  723. Profiling registers types:
  724. INDEX  NAME
  725. 0       data write
  726. 1       data read
  727. 2       data TLB miss (translation look-aside buffer)
  728. 3       data read miss
  729. 4       data write miss
  730. 5       write (hit) to M or E state lines
  731. 6       data cache lines written back
  732. 7       data cache snoops
  733. 8       data cache snoop hits
  734. 9       memory accesses in both pipes
  735. 0Ah     bank conflict
  736. 0Bh     misaligned data memory reference
  737. 0Ch     code read
  738. 0Dh     code TLB miss
  739. 0Eh     code cache miss
  740. 0Fh     segment load
  741. 10h     ????
  742. 11h     ????
  743. 12h     branches
  744. 13h     BTB hits  (Branch Target Buffer)
  745. 14h     taken branch OR BTB hit
  746. 15h     pipeline flushes
  747. 16h     instructions executed
  748. 17h     instructions executed in V-pipe
  749. 18h     bus utilization (clocks)
  750. 19h     pipeline stalled by write backup
  751. 1Ah     pipeline stalled by data memory write
  752. 1Bh     pipeline stalled by write to E or M line
  753. 1Ch     locked bus cycles
  754. 1Dh     i/o read or write cycles
  755. 1Eh     non cacheable memory references
  756. 1Fh     AGI (Address Generation Interlock)
  757. 20h     ????
  758. 21h     ????
  759. 22h     FPU operations
  760. 23h     breakpoint 0 match
  761. 24h     breakpoint 1 match
  762. 25h     breakpoint 2 match
  763. 26h     breakpoint 3 match
  764. 27h     hardware interrupts
  765. 28h     data read or data write
  766. 29h     data read miss or data write miss
  767.  
  768. So if you want to profile things:
  769. 0) Set properly the environment of the test
  770.    (cache empty, cache filled with all the routine code, etc. etc.)
  771. 1) Set MSR 11h to the two counters you want to read
  772. 2) Read MSR 12h,13h to get the initial values,
  773. 3) Execute the code you want to profile
  774. 4) Read the final values of MSR 12h,13h
  775.    (without setting MSR 11h again this time).
  776. 5) Calculate the difference between the initial and final values.
  777.  
  778. This way if you are not sure how to optimize things
  779. you can actually test how they work and what's going on.
  780.  
  781. USING THE PROFILING REGISTER YOU CAN "TEST ON THE ROAD"
  782. YOUR CODE DOWN TO THE LAST CPU CYCLE!!!!!
  783.  
  784. -------------------------------------------------------------------------------
  785. 386 Optimization
  786. -------------------------------------------------------------------------------
  787.  
  788. Well, nobody buys a 386 now, right?
  789. But still lots of people has one....
  790. So if you wanna be 386 friendly remember .....
  791.  
  792.  
  793. --------------------------
  794. DECODE-AFTER-JUMP OVERHEAD
  795. --------------------------
  796.  
  797. When a jump is performed, a 386 spends some extra time decoding
  798. the next instruction to execute and flushing the pipeline.
  799.  
  800. THE FIRST INSTRUCTION requires exactly ONE EXTRA CPU CYCLE
  801. for every COMPONENT ( prefixes, opcode, mod/rm , sib ,offset, immediate value )
  802. of the instruction.  Notice i said COMPONENT!!!
  803. An 8bit displacement or a 32bit one, count always as an 1 extra cycle.
  804.  
  805. So, in 32bit mode (where no prefixes are needed for 32bit instructions):
  806.  
  807.         loopme: inc esi              ; opcode
  808.                 mov [edi+1234h],eax  ; opcode, mod/rm , immediate offset
  809.                 dec ecx              ; opcode
  810.                 jne short loopme     ; opcode short_displacement
  811.  
  812. IS FASTER THAN:
  813.  
  814.         loopme: mov [edi+1234h],eax
  815.                 inc esi
  816.                 dec ecx
  817.                 jne short loopme
  818.  
  819. Because placing first the three component mov instruction
  820. adds 2 cycles to the instruction execution time, weird, uh?
  821. But if you remember this thing, you can boost 386 code a lot.
  822.  
  823. By the way, remember that "pipeline overhead" is not so obvious to calculate.
  824.         Look at this:
  825.         add eax,ebx   ; opcode, mod/rm
  826.         add eax,1234h ; opcode, immediate_value
  827.         stosd         ; opcode    <--- these "slow" instruction pipes-in faster
  828.         pop eax       ; opcode    <--- so if you can, put 'em first
  829.  
  830. ------------------
  831. SHORT INSTRUCTIONS
  832. ------------------
  833.  
  834. Short instructions are loaded and decoded faster than longer ones
  835. and since 386 has no internal cache and less memory access bandwidth
  836. than a plain 486, this helps a lot.
  837.  
  838. Well that's all for a 386.
  839.  
  840. -------------------------------------------------------------------------------
  841. CACHE OPTIMIZATION TECHNIQUES  (THEY CAN WORK ON ANY CPU!!!!!!!!!!!!)
  842. -------------------------------------------------------------------------------
  843.  
  844. Usually "code optimization" is cpu-based, but there more things
  845. up in the sky and down on earth than just a cpu... the cache for example!
  846.  
  847. Well, the difference between a cache hit and a cache miss
  848. means lots of cpu cycles lost, so better hit the cached locations to the max.
  849.  
  850. 386 usually have and external 64k ... 128k cache (mine has none, sigh! :( )
  851. 486 have a 4k internal cache and a 64k...512k (usually 256k) second level cache
  852. Pentiums have an Harvard 8k code + 8k data cache
  853. plus a 256k..1Mbyte second level cache.
  854.  
  855. Use "short" loops so there is more probability that the code to execute
  856. will reside fully into the cache.
  857.  
  858. Then remember you can count on an external cache of at least 64k
  859. (usually 128k..256k for a 486).
  860.  
  861. So, if you have to process big arrays or big bitmaps with multiple passages
  862. do not "scan" all the array for every pass, use a "strip by strip"
  863. strategy instead so every "strip" fully fits into the cache
  864. and is ready for the second and third pass without cache misses.
  865.  
  866. This technique is called STRIP-MINING, you can include into your program
  867. a routine that checks the optimal "strip size" trying a multi-pass test
  868. on 64k,128k,256k,512k strips and "complete array"
  869. and then sets the optimal "strip size" to use
  870. when perfoming "strip-mining" routines.
  871.  
  872. On a Pentium you can use 8k "strips" so your "strip mined" routines
  873. will work with the full speed of the internal data cache
  874. (remember the internal cache works at full cpu speed while
  875.  the secondary cache may be runnin at half that).
  876.  
  877. The advantage of strip mining is caused by the fact that
  878. the additional jumping/looping needed to process arrays in "strips"
  879. of adiacent memory locations that can fit together into the cache
  880. is A LOT LESS than the time caused by a single cache miss.
  881.  
  882. -------------------------------------------------------------------------------
  883. NOT SO OBVIOUS OPTIMIZATIONS
  884. -------------------------------------------------------------------------------
  885.  
  886. ----------------------
  887. COMPLEX INSTRUCTIONS
  888. ----------------------
  889. Intel says complex instruction are evil on 486 and up, but there are
  890. exceptions... expecially if want to make things run smooth on 386 too.
  891.  
  892. STRING instructions are FASTER on 386, expecially if they are the first
  893. in a loop.
  894.  
  895. If you have to move data in 32bit chunks you'd better use REP MOVSD if you can
  896. because it alone replaces this "simple instructions only"
  897. super-optimized sequence:
  898.  
  899.         rep_loop:
  900.                 mov eax,[esi]
  901.                 add esi,4      ; or -4
  902.                 mov [edi],eax
  903.                 add edi,4      ; or -4
  904.                 dec ecx
  905.                 jne rep_loop
  906.  
  907. REP MOVSD takes  2+7*n cycles on a 386 or 486
  908.  
  909. While the "optimized" sequence uses EAX
  910. and takes [(2+4+2+2+2+2+7)*n - 4 ] = [21*n - 4] cycles on a 386
  911.       and [  (1+1+1+1+1+3)*n - 2 ] = [ 8*n - 2] cycles on a 486
  912.  
  913. Cache-line aligning the "optimized" code on a Pentium
  914. i think it takes  [ 3*n ]  cycles.
  915. So if 486s are your base system don't throw away REP MOVSD
  916.  
  917. Also remember that REP MOVSD take 2 bytes instead of 13 bytes
  918. does not need to use EAX (one more register free for other things)
  919. and it does not use the Pentium's BTB (Branch Target Buffer)
  920. so you can be sure it does not miss and the outer loops
  921. with entries in the BTB can be one level deeper.
  922.  
  923. What's more, the AMD K5 automatically splits a complex instruction
  924. into an optimized sequence of simple instructions
  925. and issues them to fully utilize the four execution units it has.
  926. Guess what it means for poor old movsd :)
  927.  
  928. <Intel bashing ON>
  929. Heck! I think those Intel engineers lost a big thing when they
  930. decided to not improve MOVS/LODS/STOS. A "blitter" unit directly
  931. controlled by string instructions (with "fetch ahead","bufferize"
  932. and "auto align" capabilities) could be a great thing for us.
  933.  
  934. Think about this: a REP MOVSB/W/D "translated" to
  935. a "head" byte move (to align things)
  936. a "central" qword move (burst read/burst writes)
  937. and a "tail" byte move (to align things).
  938. And all this without trashing the processor data cache!!!!
  939. Can you immagine the boost your code may get?
  940. Heck! Sun engineers ADDED "blitter" support in their new 64bit sparc cpus
  941. because they seen their software moving data a lot, why Intel ones did not?
  942.  
  943. On a Pentium you can get the optimal 2-cycle memory to memory MOV
  944. by way of pipelining, but this cannot take advantage of the fact
  945. that when performing REP MOVS the processor KNOWS AHEAD how many locations
  946. will be moved (read: on a "smarter" cpu this can help optimize to the
  947. max the processor-to-memory bandwidth and avoid caching overhead)
  948. nor it can take advantage of the full power of burst read/writes
  949. neither it can take advantage of the fact that WHILE THE STRING MOVE
  950. IS GOING ON, the processor pipelines can execute OTHER instructions after
  951. the MOVS and "not dealing" with the memory range "under transfert"
  952. or with ECX,ESI,EDI and Direction Flag.
  953. I hope they will take note of this for P7.
  954.  
  955. <Intel bashing OFF>
  956.  
  957. -------------------------------------------------------------
  958. THE ADDRESSING MODE ADVANTAGE
  959. -------------------------------------------------------------
  960. Don't be fooled by the current Riscy trend, be cooler than the rest.
  961. Some Intel "complex addressing" modes are really powerful
  962. if you just have enough creativity.
  963. Lets suppose you need to add together data from "four"
  964. streams of data....
  965.  
  966. A riscy (risc-like) way to do this could be...
  967.                               ; 486 timings when looping
  968.       riscy_way:
  969.                mov eax,[esi]  ; 1
  970.                add esi,4      ; 1
  971.                add eax,[edx]  ; 2
  972.                add edx,4      ; 1
  973.                add eax,[ebx]  ; 2
  974.                add ebx,4      ; 1
  975.                add eax,[ecx]  ; 2
  976.                add ecx,4      ; 1
  977.                mov [edi],eax  ; 1
  978.                add edi,4      ; 1
  979.                dec ebp        ; 1
  980.                jne riscy_way  ; 3
  981.                               ; loop cycles = 17
  982.  
  983. Now lets see the "intelly" way! :)
  984. Let's suppose the "counter" EBP won't exceed 2^31 -1
  985. we can do the following ...
  986.  
  987.                ; move pointers ahead ...
  988.                lea esi,[esi+ebp*4]
  989.                lea edx,[edx+ebp*4]
  990.                lea ebx,[ebx+ebp*4]
  991.                lea ecx,[ecx+ebp*4]
  992.                lea edi,[edi+ebp*4]
  993.                neg ebp ; negate increment
  994.                ; then you can fully use the address unit ALU
  995.  
  996.                                     ; 486 timing when looping
  997.     intelly_way:
  998.                mov eax,[esi+ebp*4]  ; 1
  999.                add eax,[edx+ebp*4]  ; 2
  1000.                add eax,[ebx+ebp*4]  ; 2
  1001.                add eax,[ecx+ebp*4]  ; 2
  1002.                mov [edi+ebp*4],eax  ; 1
  1003.                inc ebp              ; 1
  1004.                jnz intelly_way      ; 3
  1005.                                     ; loop cycles = 12
  1006.                
  1007.  
  1008. On a Pentium, "riscy" and "intelly" runs at nearly the same speed
  1009. BUT ON A 486, the "riscy" way runs 30% slower than "intelly" !!!!
  1010.  
  1011. This means that using the "riscy" code
  1012. your 486 will look like a slow cow compared to a Pentium
  1013. while using the "intelly" code your 486 will look good enough
  1014. ( not to mention this helps to make the difference between
  1015.   "needs a Pentium" and "this flies on 486 too!!").
  1016.  
  1017. -------------------------------------------------------------
  1018. 32bit ACCESS SPEAKS FOR ITSELF, just remember to fully use it
  1019. -------------------------------------------------------------
  1020.  
  1021. Everywhere you can, use 32bit instructions
  1022. and if you can, align data on 32bit.
  1023.  
  1024. For example, let's say you have to manipulate lots of strings,
  1025. if you align them on dword boundaries (including string lenght)
  1026. with null byte paddings, you can boost processing time MORE THAN 8 TIMES!!!!
  1027.  
  1028. The same thing applies to manipulating 8bit bitmaps and "software" sound mixing.
  1029.  
  1030. Into 386mixer coded a routine that mixed simultaneously 4 sound channels
  1031. running only on internal register and mixing up to 4 samples at a time
  1032. from the 4 channels (look at the "intelly" example above).
  1033.  
  1034. If you need speed, you can even tollerate small calculation errors
  1035. or reduced precision
  1036. and manipulate successive 8,16bit values in a single 32bit instruction.
  1037.  
  1038. Let's say you have and array of unsigned words and you need to multiply them
  1039. for a constant, say 45, how can you do that ?
  1040. If you know the values won't overflow the 16 bit they use
  1041. (if they overflow you will have to choose another method), you can do the
  1042. following:
  1043.            mov ecx,count
  1044.            mov esi,start_address
  1045.      handle_two_words:
  1046.            mov eax,[esi] ; load two words at a time
  1047.            ; an AGI happens, but i can't eliminate it
  1048.            lea eax,[eax+eax*4]  ; multiply by 5
  1049.            add esi,4  ; increment pointer, avoid 486 AGI
  1050.                       ; reduce by 1 the Pentium AGIs
  1051.            lea eax,[eax+eax*8]  ; then multiply by 9
  1052.            dec ecx  ; decrement counter & keep Pentium at full power
  1053.            mov [esi],eax   ;
  1054.            jne handle_two_words
  1055.  
  1056. And if you have very big arrays, you can even unroll two or three times
  1057. the loop to further speed up this code.
  1058.  
  1059. ------------------
  1060. SELF COMPILED CODE
  1061. ------------------
  1062.  
  1063. Sometimes you need to execute lots of times the same "jump filled"
  1064. instruction sequence, and you know ahead what jumps will be taken
  1065. and what won't.
  1066. What's worse if there are lots of conditional jumps (Jcc) "in sequence"
  1067. they may be enough to overflow the capability of branch-prediction units!!!
  1068.  
  1069. So, what can you do?
  1070. My answer to this is a SELF-COMPILER!!!
  1071. A small finite state machine that instead of crunching data directly
  1072. IT GENERATES SUPER-SPECIALIZED ROUTINES that will crunch the data in the
  1073. fastest way the code generator knows.
  1074.  
  1075. I've done a thing like that for the _PageFLip1 routine in 386video.asm.
  1076. At mode initialization a code generator generates
  1077. all the 256 blit-skip sequences the _PageFLip1 routines may need
  1078. when copying "modified" pixels on screen.
  1079.  
  1080. This way a call is performed only after 32 blitted pixels, instead of jumping
  1081. every 2..4 pixels (or every pixels in the worst case situations).
  1082.  
  1083. By the way, this is NOT self-modifying code
  1084. this is an "integrated code compiler".
  1085.  
  1086. ------------------------------------------------------------------------------
  1087. I hope this information has been helpful for you.
  1088. Now make some coffee, brush your teeth and phone up your girlfriend and 
  1089. go and see a movie.   This document will be here when you get back, and I 
  1090. imagine there is only so much of this you can take in one day.... :-)  :-)  :-)
  1091.  
  1092. Live long and code well...
  1093.  
  1094. Regards,
  1095.  
  1096.    Michael Kunstelj.
  1097.  
  1098. Regards from me too,
  1099.  
  1100.    Lorenzo Micheletto
  1101.