🚀 go-pugleaf

We have some code that I have been trying to optimize using the sun's 
OS 4.1.1 native sparc compiler.  Tonight I tried gcc 2.2.2 and was
very pleased to find the critical code segment about 30% smaller with
better register lifetimes resulting in no local loop variables being
stored on the stack.

Big surprise!  The smaller gcc code ran 20% slower!  My guess is that
the sun compiler is coalescing adjacent memory accesses so they can be
accessed faster.  I say this for two reasons:
  - no matter how I organize the code, the sun compiler always makes sure
    that the (known adjacent) memory accesses always end up together.
  - it runs faster than your smaller, better code

Before I provide the detail, what I want to ask is two things
  - among the options is there one that forces accesses to
    adjacent memory slots to happen together?  I have looked.
  - is there something else that would cause this (unexpected)
    performance difference?

Below I have included the assembly language for a test version of
the code being optimized.  What it does is fairly complex and would
take hours to explain, but below is a very accurate abstraction of what should
be helpful to you in understanding what the coding is doing.  Essentially
this test routine is a triple loop that does a lookup into a table
that has three shorts, then uses those three shorts to lookup three
bytes elsewhere.  The shorts are always adjacent in memory.  The
bytes are almost never adjacent.  Conceptually,

    struct Lookup1 {
	short index1;
	short index2;
	short index3;
    };

    struct Lookup1 *plookup1;
    unsigned char *plookup2;

    for (i = 256; i < 256<<8; i += 256) {
	for (j = 0; j < 256; j++) {
	    for (k = 0; k < 256; k++) {
		plookup1 = pFirstTable[ i | j ];

		index = k munged a bit;

		plookup2 = pSecondTable + plookup->index1;
		foo |= plookup2[ index ] munged a bit;

		plookup2 = pSecondTable + plookup->index2;
		foo |= plookup2[ index ] munged a bit;

		plookup2 = pSecondTable + plookup->index3;
		foo |= plookup2[ index ] munged a bit;

		*pMemory++ = foo;
	    }
	}
    }

The code produced by your compiler keeps the accesses to the
three elements pointed to by plookup-> separate... presumably to
be able to reuse registers.  The sun compiler forces them
together.

The inner loop of both is marked with * in the left column.  I have
also marked the index1, 2 and 3 accesses with comments.

    gnu compiler                        sun compiler
------------------------------      -----------------------------------
_TimeLookupData:		    _TimeLookupData:
	!#PROLOGUE# 0		    !#PROLOGUE# 0
	save %sp,-136,%sp	    !#PROLOGUE# 1
	!#PROLOGUE# 1			    save    %sp,-104,%sp
	sll %i2,8,%i2			    sll	    %i2,8,%i2
	sll %i3,8,%i3			    sll	    %i3,8,%i3
	sethi %hi(_FirstTable),%o0	    sethi   %hi(_FirstTable),%o2
	or %o0,%lo(_FirstTable),%l1	    or	    %o2,%lo(_FirstTable),%o2
	sethi %hi(_SecondTable),%o	    cmp	    %i2,%i3
	or %o0,%lo(_SecondTable),%	    sethi   %hi(_SecondTable),%o3
	cmp %i2,%i3			    mov	    %i1,%l3
	bg L62				    mov	    %i0,%l1
	mov %i2,%g4			    st	    %i5,[%fp+88]
	sethi %hi(_Memory),%l2		    st	    %i4,[%fp+84]
	or %l2,%lo(_Memory),%g1		    st	    %i1,[%fp+72]
L80:					    st	    %i0,[%fp+68]
	cmp %i4,%i5			    st	    %i2,[%fp-8]
	bg L63				    st	    %i2,[%fp+76]
	mov %i4,%o7			    st	    %i3,[%fp+80]
	cmp %i0,%i1			    st	    %o2,[%fp-4]
L79:					    bg	    L77101
	bg L66				    add	    %o3,%lo(_SecondTable),%l0
	mov %i0,%o5		    L77085:
	or %g4,%o7,%o0			    ld	    [%fp+84],%l2
	sll %o0,3,%o0			    ld	    [%fp+88],%o2
	add %l1,%o0,%g3			    mov	    %l2,%o1
L76:					    cmp	    %o1,%o2
 *	add %o5,4,%o0			    sethi   %hi(_Memory),%o0
 *	sll %o0,3,%o4			    bg	    L77099
 *	ldsh [%g3],%o0 ! index 1	    add	    %o0,%lo(_Memory),%i0
 *	add %o5,2,%o1			    cmp	    %l1,%l3
 *	add %o5,1,%o5		    LY25:		    ! [internal]
 *	add %l0,%o0,%o2		     *	    bg	    L77097
 *	ldub [%o2+%o4],%o3	     *	    mov	    %l1,%i2
 *	ldsh [%g3+4],%o0 ! index 2   *	    ld	    [%fp-8],%o3
 *	cmp %o5,%i1		     *	    ld	    [%fp-4],%l4
 *	add %l0,%o0,%o2		     *	    or	    %o3,%l2,%o3
 *	and %o3,192,%o0		     *	    sll	    %o3,3,%o3
 *	sll %o0,23,%o0		     *	    add	    %l4,%o3,%l4
 *	or %g2,%o0,%g2		     *	    ldsh    [%l4+2],%l6 ! index 1
 *	ldub [%o2+%o4],%o3	     *	    ldsh    [%l4+4],%l5 ! index 2
 *	ldsh [%g3+2],%o0 ! index 3   *	    ldsh    [%l4],%l4   ! index 3
 *	sll %o1,3,%o4		     *	    sll	    %l1,3,%i1
 *	add %l0,%o0,%o2		     *	    add	    %i1,16,%i3
 *	and %o3,192,%o0		     *	    inc	    32,%i1
 *	ldub [%o2+%o4],%o3	     *	    add	    %l0,%l4,%l4
 *	sll %o0,18,%o0		     *	    add	    %l0,%l5,%l5
 *	or %g2,%o0,%g2		     *	    add	    %l0,%l6,%l6
 *	and %o3,224,%o0		    L77089:
 *	sll %o0,21,%o0		     *	    mov	    %i1,%i5
 *	or %g2,%o0,%g2		     *	    ldub    [%l4+%i5],%l7
 *	st %g2,[%g1]		     *	    ldub    [%l5+%i5],%i5
 *	ble L76			     *	    and	    %l7,192,%l7
 *	add %g1,4,%g1		     *	    sll	    %l7,23,%l7
L66:				     *	    and	    %i5,192,%i5
	add %o7,1,%o7		     *	    sll	    %i5,18,%i5
	cmp %o7,%i5		     *	    or	    %i4,%l7,%i4
	ble L79			     *	    or	    %i4,%i5,%i4
	cmp %i0,%i1		     *	    ldub    [%l6+%i3],%i5
L63:				     *	    inc	    %i2
	add %g4,256,%g4		     *	    and	    %i5,224,%i5
	cmp %g4,%i3		     *	    sll	    %i5,21,%i5
	ble L80			     *	    or	    %i4,%i5,%i4
	or %l2,%lo(_Memory),%g1	     *	    st	    %i4,[%i0]
L62:				     *	    cmp	    %i2,%l3
	sra %i2,8,%i2		     *	    inc	    8,%i1
	sra %i3,8,%i3		     *	    inc	    8,%i3
	sub %i3,%i2,%o0		     *	    ble	    L77089
	add %o0,1,%o0		     *	    inc	    4,%i0
	sub %i5,%i4,%o1		    L77097:
	call .umul,0			    ld	    [%fp+88],%o0
	add %o1,1,%o1			    inc	    %l2
	sub %i1,%i0,%o1			    cmp	    %l2,%o0
	call .umul,0			    ble,a   LY25
	add %o1,1,%o1			    cmp	    %l1,%l3
	mov %o0,%o1		    L77099:
	sethi %hi(LC22),%o0		    ld	    [%fp-8],%o1
	call _printf,0			    ld	    [%fp+80],%o3
	or %o0,%lo(LC22),%o0		    inc	    256,%o1
	ret				    cmp	    %o1,%o3
	restore				    ble	    L77085
					    st	    %o1,[%fp-8]
				    L77101:
					    ld	    [%fp+80],%i3
					    ld	    [%fp+76],%o4
					    ld	    [%fp+84],%o2
					    ld	    [%fp+88],%o1
					    sra	    %o4,8,%o4
					    sra	    %i3,8,%i3
					    sub	    %i3,%o4,%i3
					    sub	    %o1,%o2,%o1
					    inc	    %o1
					    call    .mul,2
					    add	    %i3,1,%o0
					    sub	    %l3,%l1,%l3
					    call    .mul,2
					    add	    %l3,1,%o1
					    mov	    %o0,%o1
					    sethi   %hi(L180),%o0
					    call    _printf,2
					    or	    %o0,%lo(L180),%o0
					    ret
					    restore

Thanks !
---------------
internet: toddb@nvr.com                                             c--Q Q
US:       Todd Brunhoff; North Valley Research;                         `
          15262 NW Greenbriar Pkwy; Beaverton, OR  97006                -
Phone:    (503) 531-5707
Fax:      (503) 690-2320