<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 TRANSITIONAL//EN">
<HTML>
<HEAD>
  <META HTTP-EQUIV="Content-Type" CONTENT="text/html; CHARSET=UTF-8">
  <META NAME="GENERATOR" CONTENT="GtkHTML/4.6.0">
</HEAD>
<BODY>
The C memory aliasing model allows certain kinds of optimizations.  <BR>
<BR>
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.*):<BR>
<BR>
   ___F64VECTORSET(___STK(-5),___R3,___F64V53)<BR>
   ___F64VECTORSET(___STK(-5),___R4,___F64V52)<BR>
   ___F64VECTORSET(___STK(-5),___STK(1),___F64V51)<BR>
   ___F64VECTORSET(___STK(-5),___STK(2),___F64V50)<BR>
   ___F64VECTORSET(___STK(-5),___STK(3),___F64V49)<BR>
   ___F64VECTORSET(___STK(-5),___STK(4),___F64V48)<BR>
   ___F64VECTORSET(___STK(-5),___STK(5),___F64V47)<BR>
   ___F64VECTORSET(___STK(-5),___STK(6),___F64V46)<BR>
   ___SET_R3(___FIXADD(___R3,___FIX(2L)))<BR>
   ___POLL(9)<BR>
___DEF_SLBL(9,___L9_direct_2d_fft_2d_recursive_2d_4)<BR>
   ___GOTO(___L22_direct_2d_fft_2d_recursive_2d_4)<BR>
<BR>
Here we're alternating loading elements off the stack and storing floating-point values in a vector.<BR>
<BR>
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.<BR>
<BR>
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.<BR>
<BR>
This has the following effect on the time to compute 10,000 forward and 10,000 backward complex FFTs of 1,024 elements.<BR>
<BR>
With -fno-strict-aliasing (used now by Gambit for reasons I'll explain below):<BR>
<BR>
(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)))))<BR>
    705 ms real time<BR>
    704 ms cpu time (704 user, 0 system)<BR>
    6 collections accounting for 2 ms real time (0 user, 0 system)<BR>
    1600000 bytes allocated<BR>
    22 minor faults<BR>
    no major faults<BR>
<BR>
With -fstrict-aliasing:<BR>
<BR>
(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)))))<BR>
    590 ms real time<BR>
    592 ms cpu time (588 user, 4 system)<BR>
    6 collections accounting for 2 ms real time (4 user, 0 system)<BR>
    1600000 bytes allocated<BR>
    22 minor faults<BR>
    no major faults<BR>
<BR>
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.)<BR>
<BR>
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.<BR>
<BR>
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.<BR>
<BR>
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.)<BR>
<BR>
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?<BR>
<BR>
Brad
</BODY>
</HTML>