swap() on x86 platforms.

[Iain McClatchie]

Pal-Kristian> Testing on a Pentium revealed that using xchgl for
Pal-Kristian> swapping numbers is not the best way!
Pal-Kristian> Results: (Don't count on them!)

Pal-Kristian> Normal   = ~5.5 secs (+/- 0.1)
Pal-Kristian> XOR      = ~8.5 secs (+/- 0.1)

Here I've included some timings on a 150MHz PPro, egcs-2.91.02 971216
vs gcc-2.7.2.  I translated the code into C for comparison as well.

gcc-2.7.2:
in C++
	-O	-O2	-O3	-O6
swap1:  4.22	4.93	4.93	4.92
swap2:	8.67	7.11	7.10	7.11
swap3:	5.39	5.36	5.38	5.40
swap4:	7.06	7.07	7.04	7.06

in C
swap1:	4.93	4.22	4.22	4.24
swap2:	9.63	7.76	7.74	7.77

egcs-2.91.02 971216:
in C++:
swap1:	4.95	4.23	4.24	4.23
swap2:	9.73	7.76	7.74	7.79
swap3:	5.53	4.97	4.99	4.93
swap4:	7.10	7.03	7.06	7.05

in C
swap1:	3.59	4.23	4.23	4.23
swap2:	9.87	6.40	6.34	6.34

Obviously, swap1 is the way to go, which is good; it's also the way
everybody does it right now in existing code.  -O3 and -O6 don't do
anything to this kernel.

C is faster than C++.  It's a little interesting to note the
performance loss in C going from -O to -O2.  In an effort to discover
the problem, I extracted the inner loops from the C and C++ versions
of swap1 at -O and -O2:

C++:
	-O: 7 cycles/loop			-O2: 6 cycles/loop
.L60:					.L60:
        cmpl $10238,%esi		        cmpl $10238,%esi
        jg .L58				        jg .L58
        leal -40960(%ebp,%esi,4),%eax	        leal
-40956(%ebp,%esi,4),%eax
        leal -40956(%ebp,%esi,4),%ecx	        movl (%ebx),%ecx
        movl (%eax),%ebx		        movl (%eax),%edx
        movl (%ecx),%edx		        movl %edx,(%ebx)
        movl %edx,(%eax)		        movl %ecx,(%eax)
        movl %ebx,(%ecx)		        addl $4,%ebx
        incl %esi			        incl %esi
        jmp .L60			        jmp .L60

C:
	-O: 5 cycles/loop			-O2: 6 cycles/loop
.L39:					.L39:
        leal -40960(%ebp,%esi,4),%eax	        movl (%ecx),%edx
        leal -40956(%ebp,%esi,4),%edx	        movl (%ebx),%eax
        movl (%eax),%ebx		        movl %eax,(%ecx)
        movl (%edx),%ecx		        movl %edx,(%ebx)
        movl %ecx,(%eax)		        addl $4,%ebx
        movl %ebx,(%edx)		        addl $4,%ecx
        incl %esi			        incl %esi
        cmpl $10238,%esi		        cmpl $10238,%esi
        jle .L39			        jle .L39

You can see that C++ fails to combine the loop exit branch with the
loop closure branch, although since both branches are almost perfectly
predicted, and we have spare operational units, there is no loss.

I suspect that without higher level optimization, 5 cycles/loop is
optimal on the PPro.  Unrolling the loop does not help.  The machine
can do one memory operation per cycle, and is probably spending a
cycle bypassing the result of one store to a successive load.  You can
imagine a compiler that notices that one iteration's stored ebx will
be the next iteration's loaded ebx, and thereby eliminates a load and
potentially even a store.  On some numeric code this might be an
interesting optimization, but on this example it is somewhat
contrived.

Eliminating that load is worth one cycle per iteration, and since the
machine is no longer bypassing stores to loads, we can unroll the loop
to amortize what appears to be a one cycle per taken branch cost over
several iterations.  Eliminating that store is worth another cycle per
iteration.  The resulting loop averages 2.34 cycles per iteration of
the source (Why not 2.5 cycles?  I don't know).  I've included the
loop setup and exit code.

        leal -40960(%ebp),%ecx
        leal -8(%ebp),%esi
        movl (%ecx),%edx
        .align 16
.L39:
        movl 4(%ecx),%eax
        movl %eax,(%ecx)
        movl 8(%ecx),%eax
        movl %eax,4(%ecx)
        addl $8,%ecx
        cmpl %esi,%ecx
        jle .L39
        movl %edx,(%ecx)


I cannot imagine why the "C -O2" loop runs a cycle slower than the "C
-O" loop.

Here's GCC-2.7.2.  (I formatted the table differently.)  You can see
that the older GCC could actually do induction variable elimination in
C at -O2.  The newer egcs-121697 cannot do it -- perhaps someone will
dig around to find out why.

at -O, inner loop:
	C++:6 cycles/loop			C:7 cycles/loop
.L60:					.L44:
        cmpl $10238,%esi			
        jg .L58				        leal 0(,%esi,4),%eax
        leal 0(,%esi,4),%eax		        leal -40960(%ebp,%eax),%ebx
        leal -40960(%ebp,%eax),%ebx	        leal -40956(%ebp,%eax),%ecx
        leal -40956(%eax,%ebp),%ecx	        movl (%ebx),%edx
        movl (%ebx),%edx			movl (%ecx),%eax
        movl (%ecx),%eax		        movl %eax,(%ebx)
        movl %eax,(%ebx)		        movl %edx,(%ecx)
        movl %edx,(%ecx)		        incl %esi
        incl %esi			        cmpl $10238,%esi
        jmp .L60			        jle .L44

at -O2, inner loop:
	C++:7 cycles/loop			C:6 cycles/loop
.L60:					.L44:
        cmpl $10238,%edi		        leal -40960(%ebp,%esi),%ebx
        jg .L58				        leal -40956(%ebp,%esi),%ecx
        leal -40960(%ebp,%esi),%ebx	        movl (%ebx),%edx
        leal -40956(%esi,%ebp),%ecx	        movl (%ecx),%eax
        movl (%ebx),%edx		        movl %eax,(%ebx)
        movl (%ecx),%eax		        movl %edx,(%ecx)
        movl %eax,(%ebx)		        addl $4,%esi
        movl %edx,(%ecx)		        cmpl $40952,%esi
        addl $4,%esi			        jle .L44
        incl %edi
        jmp .L60

-Iain