[gambit-list] Nearly 20% performance improvement with -fstrict-aliasing

Bradley Lucier lucier at math.purdue.edu
Thu Oct 25 16:19:39 EDT 2012


The C memory aliasing model allows certain kinds of optimizations.  

For example, consider the following code that's generated at the end the
main loop of the FFT in _num.scm (after pulling it out of ##bignum.*):

   ___F64VECTORSET(___STK(-5),___R3,___F64V53)
   ___F64VECTORSET(___STK(-5),___R4,___F64V52)
   ___F64VECTORSET(___STK(-5),___STK(1),___F64V51)
   ___F64VECTORSET(___STK(-5),___STK(2),___F64V50)
   ___F64VECTORSET(___STK(-5),___STK(3),___F64V49)
   ___F64VECTORSET(___STK(-5),___STK(4),___F64V48)
   ___F64VECTORSET(___STK(-5),___STK(5),___F64V47)
   ___F64VECTORSET(___STK(-5),___STK(6),___F64V46)
   ___SET_R3(___FIXADD(___R3,___FIX(2L)))
   ___POLL(9)
___DEF_SLBL(9,___L9_direct_2d_fft_2d_recursive_2d_4)
   ___GOTO(___L22_direct_2d_fft_2d_recursive_2d_4)

Here we're alternating loading elements off the stack and storing
floating-point values in a vector.

Under C's memory aliasing model (i.e., with -fstrict-aliasing, the gcc
default), STK(-5) can be loaded into a register and reused after each
floating-point store, because gcc can assume that the floating-point
store does not change the value of STK(-5), since WORDs and doubles are
different types.

When we call gcc with -fno-strict-aliasing, then the compiler has to
assume that the floating-point store may affect the value of STK(-5), so
it has to reload STK(-5) before each floating-point store.

This has the following effect on the time to compute 10,000 forward and
10,000 backward complex FFTs of 1,024 elements.

With -fno-strict-aliasing (used now by Gambit for reasons I'll explain
below):

(time (do ((i 0 (fx+ i 1))) ((fx= i 10000)) (direct-fft-recursive-4 a
table) (inverse-fft-recursive-4 a table) (do ((i 0 (fx+ i 1))) ((fx= i
(fx* two^n 2))) (f64vector-set! a i (fl/ (f64vector-ref a i)
inexact-two^n)))))
    705 ms real time
    704 ms cpu time (704 user, 0 system)
    6 collections accounting for 2 ms real time (0 user, 0 system)
    1600000 bytes allocated
    22 minor faults
    no major faults

With -fstrict-aliasing:

(time (do ((i 0 (fx+ i 1))) ((fx= i 10000)) (direct-fft-recursive-4 a
table) (inverse-fft-recursive-4 a table) (do ((i 0 (fx+ i 1))) ((fx= i
(fx* two^n 2))) (f64vector-set! a i (fl/ (f64vector-ref a i)
inexact-two^n)))))
    590 ms real time
    592 ms cpu time (588 user, 4 system)
    6 collections accounting for 2 ms real time (4 user, 0 system)
    1600000 bytes allocated
    22 minor faults
    no major faults

That's a 19% performance improvement.  (And the performance isn't bad,
1.74 GFLOPS on my 2.33GHz Core 2 quad 6600.  Later I'll try to get gcc
to vectorize the main loop.)

As I understand it, the C memory aliasing model is that once you store
something of a certain type into a memory location, then you agree that
everything you read from that memory location and everything else you
write to that memory location will be of the same type.

So why do we need -fno-strict-aliasing?  I know of two reasons: (1) in
gambit.h we read and write bignums as adigits, mdigits, or fdigits, and
these are chunks of the bignums of different sizes (generally 64/32/8
bits on 64-bit machines, and 64/16/8 bits on 32-bit machines) and (2) I
believe we sometimes access double-precision floating-point numbers as
integers. Marc, maybe you know of other instances in the code.

Both of these things can be fixed by accessing the internals of a bignum
through a pointer type to a union of vectors of integers of the
appropriate bit sizes, and doing the same for double-precision floats.
(I had a much more difficult plan in mind before, of coming up with a
union type of all possible Scheme objects, but that isn't necessary, I
see now.)

I've been trying to figure out how to make the changes to gambit.h to do
this in a clean way but without luck.  Marc, you're the über programmer,
do you have time to look at this?

Brad
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20121025/58da2f61/attachment.htm>


More information about the Gambit-list mailing list