Marc:
I don't know why, but I got looking at the compiled code for fib, and it seems to use much more stack space than needed, 8 words per invocation, which seems counter-intuitive to me; is there a problem with the compiler? I'm using the latest git compiler.
Brad
I started with
(declare (standard-bindings) (extended-bindings) (block) (not safe))
(define (fib n) (if (or (fx= n 0) (fx= n 1)) n (fx+ (fib (fx- n 1)) (fib (fx- n 2)))))
and got
#undef ___PH_PROC #define ___PH_PROC ___H_fib #undef ___PH_LBL0 #define ___PH_LBL0 3 #undef ___PD_ALL #define ___PD_ALL ___D_FP ___D_R0 ___D_R1 #undef ___PR_ALL #define ___PR_ALL ___R_FP ___R_R0 ___R_R1 #undef ___PW_ALL #define ___PW_ALL ___W_FP ___W_R0 ___W_R1 ___BEGIN_P_COD ___BEGIN_P_HLBL ___DEF_P_HLBL_INTRO ___DEF_P_HLBL(___L0_fib) ___DEF_P_HLBL(___L1_fib) ___DEF_P_HLBL(___L2_fib) ___DEF_P_HLBL(___L3_fib) ___DEF_P_HLBL(___L4_fib) ___END_P_HLBL ___BEGIN_P_SW ___DEF_SLBL(0,___L0_fib) ___IF_NARGS_EQ(1,___NOTHING) ___WRONG_NARGS(0,1,0,0) ___DEF_GLBL(___L_fib) ___IF(___FIXEQ(___R1,___FIX(0L))) ___GOTO(___L7_fib) ___END_IF ___GOTO(___L6_fib) ___DEF_GLBL(___L5_fib) ___SET_STK(1,___R0) ___SET_STK(2,___R1) ___SET_R1(___FIXSUB(___R1,___FIX(1L))) ___SET_R0(___LBL(2)) ___ADJFP(8) ___POLL(1) ___DEF_SLBL(1,___L1_fib) ___IF(___FIXEQ(___R1,___FIX(0L))) ___GOTO(___L7_fib) ___END_IF ___DEF_GLBL(___L6_fib) ___IF(___NOT(___FIXEQ(___R1,___FIX(1L)))) ___GOTO(___L5_fib) ___END_IF ___DEF_GLBL(___L7_fib) ___JUMPPRM(___NOTHING,___R0) ___DEF_SLBL(2,___L2_fib) ___SET_STK(-5,___R1) ___SET_R1(___FIXSUB(___STK(-6),___FIX(2L))) ___SET_R0(___LBL(3)) ___IF(___FIXEQ(___R1,___FIX(0L))) ___GOTO(___L7_fib) ___END_IF ___GOTO(___L6_fib) ___DEF_SLBL(3,___L3_fib) ___SET_R1(___FIXADD(___STK(-5),___R1)) ___POLL(4) ___DEF_SLBL(4,___L4_fib) ___ADJFP(-8) ___JUMPPRM(___NOTHING,___STK(1)) ___END_P_SW ___END_P_COD
Afficher les réponses par date
On 2011-01-20, at 9:15 PM, Bradley Lucier wrote:
Marc:
I don't know why, but I got looking at the compiled code for fib, and it seems to use much more stack space than needed, 8 words per invocation, which seems counter-intuitive to me; is there a problem with the compiler? I'm using the latest git compiler.
Brad
The frame size (8 words) can be explained by the constraints on the frame in order to implement continuations efficiently. Specifically, the frames are aligned on multiples of 4 words and the last 3 slots of the frame are reserved for linking frames explicitly (these slots are only touched when the frames are captured by a call/cc and live when the GC runs).
In the case of fib, there are 2 live slots when the frame must be constructed for the recursive call. But because 3 extra slots must be reserved, that makes 5 slots. But this has to be rounded up to a multiple of 4, so that gives 8 slots.
Marc
<Explanation by Marc about padding in call frames deleted.>
Ah, so this is the cost that all calls incur in Gambit so that one can implement call/cc?
I thought of this when perusing
http://translate.google.com/translate?js=n&prev=_t&hl=en&ie=UTF-...
(apologies to those who understand the original Italian). The guy says that he wrote the C code
include <stdio.h>
int fib (int n) { if (n == 0 || n == 1) { return n; } else { return fib(n - 1) + fib(n - 2); } }
int main() { int n; for (n = 0; n < 40; n++) { printf ("fib(%d)=%d\n", n, fib(n)); } return 0; }
and the scheme code
declare (standard-bindings) (extended-bindings) (block) (not safe))
(define (fib n) (if (or (fx= n 0) (fx= n 1)) n (fx+ (fib (fx- n 1)) (fib (fx- n 2)))))
(do ((n 0 (fx+ n 1))) ((fx= n 40)) (for-each display (list "fib(" n ")=" (fib n) #\newline)))
and on his box Chicken ran the Scheme code (at -O5 compilation level) faster than the C code with
gcc -O3 -W -Wall -o fib_c fib_c.c
On my box, I don't have chicken installed, but
heine:~> time ./fib_c 1.490u 0.000s 0:01.49 100.0% 0+0k 0+0io 0pf+0w
and after compilation
heine:~> time gsi fib_scm 4.860u 0.010s 0:04.87 100.0% 0+0k 0+0io 0pf+0w
So, it looks like Chicken really smokes Gambit on this femtobenchmark. The question is, should it?
(I suppose you'll come back with benchmarks using your native x86-32 back end at this point, but I need to run 64-bit Gambit ...)
Brad
Hallo,
On Fri, Jan 21, 2011 at 4:59 PM, Bradley Lucier lucier@math.purdue.edu wrote:
<Explanation by Marc about padding in call frames deleted.>
Ah, so this is the cost that all calls incur in Gambit so that one can implement call/cc?
I thought of this when perusing
http://translate.google.com/translate?js=n&prev=_t&hl=en&ie=UTF-...
(apologies to those who understand the original Italian). The guy says that he wrote the C code
Eh... Portuguese. Mario's Brazilian, despite his name.
Hallo,
On Fri, Jan 21, 2011 at 5:35 PM, Bradley Lucier lucier@math.purdue.edu wrote:
On Fri, 2011-01-21 at 17:06 -0200, Alex Queiroz wrote:
Eh... Portuguese. Mario's Brazilian, despite his name.
Desculpe!
Brad (who probably just made another mistake ...)
Not at all, it's the correct word. :)
On Fri, 21 Jan 2011 14:35:47 -0500 Bradley Lucier lucier@math.purdue.edu wrote:
On Fri, 2011-01-21 at 17:06 -0200, Alex Queiroz wrote:
Eh... Portuguese. Mario's Brazilian, despite his name.Desculpe!
Brad (who probably just made another mistake ...)
Sem problemas, Brad ("Desculpe" is perfectly correct, BTW). :-)
Best wishes. Mario
On 2011-01-21, at 1:59 PM, Bradley Lucier wrote:
<Explanation by Marc about padding in call frames deleted.>
Ah, so this is the cost that all calls incur in Gambit so that one can implement call/cc?
You could say that. But the "cost" is just more memory usage. And this extra memory is not touched (written/read) in the usual case (i.e. call/cc is not called). Very probably, the main run time cost is that the caches will be less efficient at accessing variables on the stack, but that is hard to measure except for specific benchmarks.
I thought of this when perusing
http://translate.google.com/translate?js=n&prev=_t&hl=en&ie=UTF-...
(apologies to those who understand the original Italian). The guy says that he wrote the C code
include <stdio.h>
int fib (int n) { if (n == 0 || n == 1) { return n; } else { return fib(n - 1) + fib(n - 2); } }
int main() { int n; for (n = 0; n < 40; n++) { printf ("fib(%d)=%d\n", n, fib(n)); } return 0; }
and the scheme code
declare (standard-bindings) (extended-bindings) (block) (not safe))
(define (fib n) (if (or (fx= n 0) (fx= n 1)) n (fx+ (fib (fx- n 1)) (fib (fx- n 2)))))
(do ((n 0 (fx+ n 1))) ((fx= n 40)) (for-each display (list "fib(" n ")=" (fib n) #\newline)))
and on his box Chicken ran the Scheme code (at -O5 compilation level) faster than the C code with
gcc -O3 -W -Wall -o fib_c fib_c.c
On my box, I don't have chicken installed, but
heine:~> time ./fib_c 1.490u 0.000s 0:01.49 100.0% 0+0k 0+0io 0pf+0w
and after compilation
heine:~> time gsi fib_scm 4.860u 0.010s 0:04.87 100.0% 0+0k 0+0io 0pf+0w
So, it looks like Chicken really smokes Gambit on this femtobenchmark. The question is, should it?
To really draw such conclusions, you should actually compile and run the program with Chicken! There are so many factors that can affect performance (actual CPU you are using, version of gcc, version of Chicken, etc).
Have you checked the assembly code that is generated by gcc -O3 for fib_c . It is quite amazing. gcc manages to rewrite the code to remove one of the two recursive calls. I have a hunch that the gcc folks put in an optimization specifically for fib-like recursions... If you compile fib_c with -O2 the program runs 3 times slower! Don't forget also that Gambit uses gcc -O1 by default to compile the generated C code because at -O2, gcc undoes some of Gambit's optimizations.
Also, it just so happens that because the base case uses the test (or (fx= n 0) (fx= n 1)) the body of fib is just slightly too big to be inlined at the recursive calls to fib. If the base case is rewritten to (fx<= n 1) then the function gets inlined and the performance improves drastically. Also, you didn't play around much with the Gambit declarations... if you add (inlining-limit 1000), you will enable more inlining. The code below runs 2.1 times faster than your original fib_scm .
(declare (standard-bindings) (extended-bindings) (block) (inlining-limit 1000) ;; ADDED (not safe) )
(define (fib n) (if (fx<= n 1) ;; CHANGED FROM: (or (fx= n 0) (fx= n 1)) n (fx+ (fib (fx- n 1)) (fib (fx- n 2)))))
(do ((n 0 (fx+ n 1))) ((fx= n 40)) (for-each display (list "fib(" n ")=" (fib n) #\newline)))
(I suppose you'll come back with benchmarks using your native x86-32 back end at this point, but I need to run 64-bit Gambit ...)
The x86 back-end runs fib_scm about 2.5 times faster than when using the C back-end. That's faster than Chicken, and also Larceny and Ikarus (which have x86 back-ends). The Gambit x86 back-end supports both x86-32 and x86-64.
Marc
Hallo,
On Fri, Jan 21, 2011 at 5:38 PM, Marc Feeley feeley@iro.umontreal.ca wrote:
(I suppose you'll come back with benchmarks using your native x86-32 back end at this point, but I need to run 64-bit Gambit ...)
The x86 back-end runs fib_scm about 2.5 times faster than when using the C back-end. That's faster than Chicken, and also Larceny and Ikarus (which have x86 back-ends). The Gambit x86 back-end supports both x86-32 and x86-64.
I never heard of this x86 backend before. Is it in another git branch?
Cheers,
On Fri, 2011-01-21 at 15:08 -0500, Marc Feeley wrote:
On 2011-01-21, at 2:44 PM, Raffael Cavallaro wrote:
Any chance of an ARM back end?
ARM would be the logical next back-end to write. But there are no plans for that yet.
Marc:
You have not suggested this, but ...
I would REALLY, REALLY, REALLY not like to see the C back end become some kind of second-class citizen because of all this work. I have not been following closely the development of other Scheme systems, but my impression is that the C back ends of some of them are something of an afterthought.
Also, I would prefer that general improvements be made to the compiler, rather than relying on the (partial) speedup (on some things) that compiling directly to assembler gives. I'm reminded here of the gmp project, which in my opinion always has nearly optimal implementations of any algorithms they might choose (because of their assembly coding of inner loops, etc.), but which has also shown that improving the algorithms they use sometimes gives orders of magnitude improvements in speeds. (It is my opinion that relying on a higher-order language than C and assembler would make it easier to explore different algorithms, but I've explored that choice in Gambit, and gmp now beats Gambit in all bignum operations, in part by implementing some algorithms implemented first in Gambit.)
Brad
On 2011-01-22, at 5:13 PM, Bradley Lucier wrote:
On Fri, 2011-01-21 at 15:08 -0500, Marc Feeley wrote:
On 2011-01-21, at 2:44 PM, Raffael Cavallaro wrote:
Any chance of an ARM back end?
ARM would be the logical next back-end to write. But there are no plans for that yet.
Marc:
You have not suggested this, but ...
I would REALLY, REALLY, REALLY not like to see the C back end become some kind of second-class citizen because of all this work. I have not been following closely the development of other Scheme systems, but my impression is that the C back ends of some of them are something of an afterthought.
There are no plans to make the C back-end a second-class citizen! The C back-end has great value for its portability. The Gambit compiler will include the C back-end and native back-ends simultaneously, so that it is easy to switch between them. The compiler will certainly be distributed as C files (produced by the C back-end) so that Gambit can be built on any platform and will behave consistently on all platforms.
Also, I would prefer that general improvements be made to the compiler, rather than relying on the (partial) speedup (on some things) that compiling directly to assembler gives.
The fact is that some important performance issues are related to the C back-end. Resolving these issues can't be done by modifying the front-end. Of course improvements to the front-end will benefit all variants of Gambit (C and native back-ends).
Marc
Does that x86 back end generate code directly into memory, augmenting the running system? Or does it generate code into a file that has to be executed from the OS?
-- hendrik
Marc
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
On 2011-01-26, at 6:38 PM, Hendrik Boom wrote:
Does that x86 back end generate code directly into memory, augmenting the running system? Or does it generate code into a file that has to be executed from the OS?
The back-end includes an assembler which can output the machine code to a byte vector or a file. In the tests I have done the code was generated into memory and executed without accessing the filesystem.
Marc
On Wed, Jan 26, 2011 at 09:42:31PM -0500, Marc Feeley wrote:
On 2011-01-26, at 6:38 PM, Hendrik Boom wrote:
Does that x86 back end generate code directly into memory, augmenting the running system? Or does it generate code into a file that has to be executed from the OS?
The back-end includes an assembler which can output the machine code to a byte vector or a file. In the tests I have done the code was generated into memory and executed without accessing the filesystem.
Great! That's what I was hoping for. I've been tinkering with some similar stuff, but without using a nice language to write the code generator in (I used C/C++) and was just realising I needed a better notation for expressing the code generation patterns -- A better notation such as that available in Scheme. I was trying to be source-language-agnostic.
Any chance I could have a look at your code, and possibly repurpose it?
-- hendrik
On 2011-01-27, at 2:42 AM, Hendrik Boom wrote:
On Wed, Jan 26, 2011 at 09:42:31PM -0500, Marc Feeley wrote:
On 2011-01-26, at 6:38 PM, Hendrik Boom wrote:
Does that x86 back end generate code directly into memory, augmenting the running system? Or does it generate code into a file that has to be executed from the OS?
The back-end includes an assembler which can output the machine code to a byte vector or a file. In the tests I have done the code was generated into memory and executed without accessing the filesystem.
Great! That's what I was hoping for. I've been tinkering with some similar stuff, but without using a nice language to write the code generator in (I used C/C++) and was just realising I needed a better notation for expressing the code generation patterns -- A better notation such as that available in Scheme. I was trying to be source-language-agnostic.
Any chance I could have a look at your code, and possibly repurpose it?
I'm currently doing a major refactoring of the code, so this is a bad moment to share the code with you. Can you wait a few weeks?
Marc
Yes, but only barely. :)
Totally stoked about running my music synth on an x86 backend that compiles to memory. Dare we dream of saveable heap images? On Jan 28, 2011 11:05 AM, "Marc Feeley" feeley@iro.umontreal.ca wrote:
On 2011-01-27, at 2:42 AM, Hendrik Boom wrote:
On Wed, Jan 26, 2011 at 09:42:31PM -0500, Marc Feeley wrote:
On 2011-01-26, at 6:38 PM, Hendrik Boom wrote:
Does that x86 back end generate code directly into memory, augmenting the running system? Or does it generate code into a file that has to be
executed from the OS?
The back-end includes an assembler which can output the machine code to
a byte vector or a file. In the tests I have done the code was generated into memory and executed without accessing the filesystem.
Great! That's what I was hoping for. I've been tinkering with some similar stuff, but without using a nice language to write the code generator in (I used C/C++) and was just realising I needed a better notation for expressing the code generation patterns -- A better notation such as that available in Scheme. I was trying to be source-language-agnostic.
Any chance I could have a look at your code, and possibly repurpose it?
I'm currently doing a major refactoring of the code, so this is a bad
moment to share the code with you. Can you wait a few weeks?
Marc
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
On Fri, Jan 28, 2011 at 11:04:55AM -0500, Marc Feeley wrote:
On 2011-01-27, at 2:42 AM, Hendrik Boom wrote:
On Wed, Jan 26, 2011 at 09:42:31PM -0500, Marc Feeley wrote:
On 2011-01-26, at 6:38 PM, Hendrik Boom wrote:
Does that x86 back end generate code directly into memory, augmenting the running system? Or does it generate code into a file that has to be executed from the OS?
The back-end includes an assembler which can output the machine code to a byte vector or a file. In the tests I have done the code was generated into memory and executed without accessing the filesystem.
Great! That's what I was hoping for. I've been tinkering with some similar stuff, but without using a nice language to write the code generator in (I used C/C++) and was just realising I needed a better notation for expressing the code generation patterns -- A better notation such as that available in Scheme. I was trying to be source-language-agnostic.
Any chance I could have a look at your code, and possibly repurpose it?
I'm currently doing a major refactoring of the code, so this is a bad moment to share the code with you. Can you wait a few weeks?
This might be the worst possible time to start using or modifying your code, but an excellent time to start reading it. Most of my effort will probably be into figuring out how Scheme has changed since I first ran into it in Guy Steele's masters thesis. That was, after all, another Scheme in Scheme (or something like it) compiler.
-- hendrik
On Fri, Jan 28, 2011 at 03:56:38PM -0500, Hendrik Boom wrote:
On Fri, Jan 28, 2011 at 11:04:55AM -0500, Marc Feeley wrote:
On 2011-01-27, at 2:42 AM, Hendrik Boom wrote:
On Wed, Jan 26, 2011 at 09:42:31PM -0500, Marc Feeley wrote:
On 2011-01-26, at 6:38 PM, Hendrik Boom wrote:
Does that x86 back end generate code directly into memory, augmenting the running system? Or does it generate code into a file that has to be executed from the OS?
The back-end includes an assembler which can output the machine code to a byte vector or a file. In the tests I have done the code was generated into memory and executed without accessing the filesystem.
Great! That's what I was hoping for. I've been tinkering with some similar stuff, but without using a nice language to write the code generator in (I used C/C++) and was just realising I needed a better notation for expressing the code generation patterns -- A better notation such as that available in Scheme. I was trying to be source-language-agnostic.
Any chance I could have a look at your code, and possibly repurpose it?
I'm currently doing a major refactoring of the code, so this is a bad moment to share the code with you. Can you wait a few weeks?
A few weeks have now passed. May I have a look at it now?
If it's still not ready, I'd rather look at what you've got than wait another few weeks.
-- hendrik
This might be the worst possible time to start using or modifying your code, but an excellent time to start reading it. Most of my effort will probably be into figuring out how Scheme has changed since I first ran into it in Guy Steele's masters thesis. That was, after all, another Scheme in Scheme (or something like it) compiler.
-- hendrik _______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
On 2011-01-21, at 2:38 PM, Marc Feeley wrote:
On 2011-01-21, at 1:59 PM, Bradley Lucier wrote:
<Explanation by Marc about padding in call frames deleted.>
Ah, so this is the cost that all calls incur in Gambit so that one can implement call/cc?
You could say that. But the "cost" is just more memory usage. And this extra memory is not touched (written/read) in the usual case (i.e. call/cc is not called). Very probably, the main run time cost is that the caches will be less efficient at accessing variables on the stack, but that is hard to measure except for specific benchmarks.
Let me add that gcc (at least on the Mac) also pads stack frames on multiples of 16 bytes. If you write assembly code that doesn't align properly and that calls a C library function, the code will crash.
Marc
On Fri, 2011-01-21 at 14:47 -0500, Marc Feeley wrote:
Let me add that gcc (at least on the Mac) also pads stack frames on multiples of 16 bytes. If you write assembly code that doesn't align properly and that calls a C library function, the code will crash.
I wasn't precise enough; I meant the extra cost is in the three words added to each stack frame that is used only by the GC for continuation frames that are captured by call/cc. Is this correct?
Brad
On Fri, 2011-01-21 at 14:38 -0500, Marc Feeley wrote:
On 2011-01-21, at 1:59 PM, Bradley Lucier wrote:
On my box, I don't have chicken installed, but
heine:~> time ./fib_c 1.490u 0.000s 0:01.49 100.0% 0+0k 0+0io 0pf+0w
and after compilation
heine:~> time gsi fib_scm 4.860u 0.010s 0:04.87 100.0% 0+0k 0+0io 0pf+0w
So, it looks like Chicken really smokes Gambit on this
femtobenchmark. The question is, should it?
To really draw such conclusions, you should actually compile and run the program with Chicken! There are so many factors that can affect performance (actual CPU you are using, version of gcc, version of Chicken, etc).
OK, so I installed chicken, for chicken used
heine:~> gcc -v Using built-in specs. Target: x86_64-linux-gnu Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.4.4-14ubuntu5' --with-bugurl=file:///usr/share/doc/gcc-4.4/README.Bugs --enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.4 --enable-shared --enable-multiarch --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.4 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-objc-gc --disable-werror --with-arch-32=i686 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu Thread model: posix gcc version 4.4.5 (Ubuntu/Linaro 4.4.4-14ubuntu5)
for Gambit used
heine:~> gsc -v v4.6.0 20110117205308 x86_64-unknown-linux-gnu "./configure CC=/usr/bin/gcc-4.5 -fschedule-insns -march=native --enable-multiple-versions --enable-single-host --enable-shared"
(so I added "-fschedule-insns -march=native") and
heine:~> gcc-4.5 -v Using built-in specs. COLLECT_GCC=gcc-4.5 COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.5.1/lto-wrapper Target: x86_64-linux-gnu Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.5.1-7ubuntu2' --with-bugurl=file:///usr/share/doc/gcc-4.5/README.Bugs --enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.5 --enable-shared --enable-multiarch --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.5 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-plugin --enable-gold --with-plugin-ld=ld.gold --enable-objc-gc --disable-werror --with-arch-32=i686 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu Thread model: posix gcc version 4.5.1 (Ubuntu/Linaro 4.5.1-7ubuntu2)
and got
heine:~> /pkgs/chicken-4.6.0/bin/csc -O5 fib_scm.scm heine:~> time ./fib_scm 1.120u 0.010s 0:01.13 100.0% 0+0k 0+0io 0pf+0w
Have you checked the assembly code that is generated by gcc -O3 for fib_c . It is quite amazing. gcc manages to rewrite the code to remove one of the two recursive calls. I have a hunch that the gcc folks put in an optimization specifically for fib-like recursions...
I think they just note that with descending recursions the left-most one can be unrolled to a loop.
If you compile fib_c with -O2 the program runs 3 times slower!
Your point is? If I use tiny-c, presumably the code would suck more, too.
Don't forget also that Gambit uses gcc -O1 by default to compile the generated C code because at -O2, gcc undoes some of Gambit's optimizations.
Also, it just so happens that because the base case uses the test (or (fx= n 0) (fx= n 1)) the body of fib is just slightly too big to be inlined at the recursive calls to fib. If the base case is rewritten to (fx<= n 1) then the function gets inlined and the performance improves drastically. Also, you didn't play around much with the Gambit declarations... if you add (inlining-limit 1000), you will enable more inlining. The code below runs 2.1 times faster than your original fib_scm .
(declare (standard-bindings) (extended-bindings) (block) (inlining-limit 1000) ;; ADDED (not safe) )
(define (fib n) (if (fx<= n 1) ;; CHANGED FROM: (or (fx= n 0) (fx= n 1)) n (fx+ (fib (fx- n 1)) (fib (fx- n 2)))))
(do ((n 0 (fx+ n 1))) ((fx= n 40)) (for-each display (list "fib(" n ")=" (fib n) #\newline)))
On my machine I get:
heine:~> gsc -exe fib2_scm.scm heine:~> time ./fib2_scm 2.150u 0.010s 0:02.16 100.0% 0+0k 0+0io 0pf+0w
and if I run it through chicken I get
heine:~> /pkgs/chicken-4.6.0/bin/csc -O5 fib2_scm.scm
Warning: illegal declaration specifier: (inlining-limit 1000) heine:~> time ./fib2_scm 0.980u 0.000s 0:00.98 100.0% 0+0k 0+0io 0pf+0w
Still smoked, only worse ...
The x86 back-end runs fib_scm about 2.5 times faster than when using the C back-end.
What kind of speedups do you see on your new version of fib with the native back end?
Brad
On 2011-01-21, at 2:59 PM, Bradley Lucier wrote:
Have you checked the assembly code that is generated by gcc -O3 for fib_c . It is quite amazing. gcc manages to rewrite the code to remove one of the two recursive calls. I have a hunch that the gcc folks put in an optimization specifically for fib-like recursions...
I think they just note that with descending recursions the left-most one can be unrolled to a loop.
If you compile fib_c with -O2 the program runs 3 times slower!
Your point is? If I use tiny-c, presumably the code would suck more, too.
I find it suspect that with such a small change (going from -O2 to -O3) there is such a large performance difference (3 *times* faster). In a way, gcc is exploiting the very specific nature of doubly-recursive fib to generate fast code. You have to wonder how often this pattern actually occurs in real programs.
Gambit could also "smoke" gcc by simply adding a "fib" detector and turning the function into an iterative algorithm for fib. It could even be generalized to other fib-like recursions. Would that make Gambit a better compiler? Not in my opinion.
The main performance issue with Gambit-C is related to the jump to fib's return point. Because of the trampolines used by Gambit-C to implement tail-calls, there is a high cost to "return" to the caller. This cost vanishes (it becomes a plain "jump" instruction) in the x86 back-end. That's why the performance improves so dramatically with the x86 back-end (2.5 times faster).
Marc
In fact, once you change the test to (fx<= n 1), the (inlining-limit 1000) doesn't change much; with it, I get
heine:~> gsc -exe fib2_scm heine:~> time ./fib2_scm 2.160u 0.000s 0:02.16 100.0% 0+0k 0+0io 0pf+0w
Without it, I get
heine:~> gsc -exe fib2_scm heine:~> time ./fib2_scm 2.280u 0.010s 0:02.29 100.0% 0+0k 0+0io 0pf+0w
If I add (inlining-limit 1000) to the original code with I get
heine:~> gsc -exe fib_scm heine:~> time ./fib_scm 2.140u 0.020s 0:02.16 100.0% 0+0k 0+0io 0pf+0w
If I declare (not interrupts-enabled) in fib (I know this is not a good idea, because stack overflows are not caught), I get with (inlining-limit 1000) and the revised code:
heine:~> gsc -exe fib2_scm heine:~> time ./fib2_scm 1.800u 0.010s 0:01.82 99.4% 0+0k 0+0io 0pf+0w
By the way, with
heine:~> /pkgs/chicken-4.6.0/bin/csc -O4 fib2_scm.scm Warning: illegal declaration specifier: (inlining-limit 1000) heine:~> time ./fib2_scm 3.080u 0.000s 0:03.08 100.0% 0+0k 0+0io 0pf+0w
while with
heine:~> /pkgs/chicken-4.6.0/bin/csc -O5 fib2_scm.scm Warning: illegal declaration specifier: (inlining-limit 1000) heine:~> time ./fib2_scm 0.970u 0.010s 0:00.98 100.0% 0+0k 0+0io 0pf+0w
I don't know what the various optimization levels of chicken mean precisely, or which options in -O5 makes the biggest difference over -O4:
-optimize-level 0 is equivalent to -no-usual-integrations -no-compiler-syntax -optimize-level 1 is equivalent to -optimize-leaf-routine -optimize-level 2 is equivalent to -optimize-leaf-routines -inline -optimize-level 3 is equivalent to -optimize-leaf-routines -local -inline -inline-global -optimize-level 4 is equivalent to -optimize-leaf-routines -local -inline -unsafe -unboxing -optimize-level 5 is equivalent to -optimize-leaf-routines -block -inline -unsafe -unboxing -lambda-lift -disable-interrupts -no-trace -no-lambda-info
Marc, you know that with me and Gambit it's like the old Velvet Underground song: "I'm sticking with you, cause I'm made out of glue ..."
Brad
On 2011-01-21, at 4:34 PM, Bradley Lucier wrote:
I don't know what the various optimization levels of chicken mean precisely, or which options in -O5 makes the biggest difference over -O4: -optimize-level 0 is equivalent to -no-usual-integrations -no-compiler-syntax -optimize-level 1 is equivalent to -optimize-leaf-routine -optimize-level 2 is equivalent to -optimize-leaf-routines -inline -optimize-level 3 is equivalent to -optimize-leaf-routines -local -inline -inline-global -optimize-level 4 is equivalent to -optimize-leaf-routines -local -inline -unsafe -unboxing -optimize-level 5 is equivalent to -optimize-leaf-routines -block -inline -unsafe -unboxing -lambda-lift -disable-interrupts -no-trace -no -lambda-info
Marc, you know that with me and Gambit it's like the old Velvet Underground song: "I'm sticking with you, cause I'm made out of glue ..."
Perhaps this will be a more rational argument for sticking with Gambit...
Upon further investigation, compiling fib_scm with Chicken with -O5 gives this C code for the fib function:
/* fib in k32 in k29 */ static C_word C_fcall f_36(C_word t1){ C_word tmp; C_word t2; C_word t3; C_word t4; C_word t5; C_word t6; C_word t7; if(C_truep(C_fixnum_less_or_equal_p(t1,C_fix(1)))){ t2=t1; return(t2);} else{ t2=C_u_fixnum_difference(t1,C_fix(1)); t3=f_36(t2); t4=C_u_fixnum_difference(t1,C_fix(2)); t5=f_36(t4); return(C_u_fixnum_plus(t3,t5));}}
This is basically the same code as fib_c once the C macros are expanded. Note that the recursive calls to fib are translated to direct C calls. Not only are interrupts no longer checked (due to the -disable-interrupts implied by -O5) but there is no stack overflow check! So the code no longer supports preemptive multithreading, and if you are close to the C stack limit the program will crash. The programmer has to be concerned with avoiding deep recursions which could crash the program. In other words, you're no longer dealing with a high-level language with graceful support for recursion.
Here's an example where that matters:
% cat deep.scm (declare (standard-bindings) (extended-bindings) (block) (not safe) )
;; Recursive algorithm for computing (even? n). The depth of ;; recursion is equal to n.
(define (even n) (if (fx= n 0) #t (not (even (fx- n 1)))))
(display (even 10000000)) % csc -O5 deep.scm % ./deep Segmentation fault
Gambit has not problem with deep recursions. It can fill the whole heap with continuation frames if needed:
% gsc -exe deep.scm % ./deep #t%
If the Gambit heap overflows, you'll get an exception that your code can catch and act upon gracefully, not a segmentation fault.
So I'm not sure comparing Gambit against Chicken with -O5 is very meaningful. Perhaps -O4 is more in line with the expectations of a Scheme programmer, but I don't know enough about the meaning of Chicken's optimization levels to really tell what is reasonable.
Marc
On 2011-01-21, at 7:40 PM, Marc Feeley wrote:
On 2011-01-21, at 4:34 PM, Bradley Lucier wrote:
I don't know what the various optimization levels of chicken mean precisely, or which options in -O5 makes the biggest difference over -O4: -optimize-level 0 is equivalent to -no-usual-integrations -no-compiler-syntax -optimize-level 1 is equivalent to -optimize-leaf-routine -optimize-level 2 is equivalent to -optimize-leaf-routines -inline -optimize-level 3 is equivalent to -optimize-leaf-routines -local -inline -inline-global -optimize-level 4 is equivalent to -optimize-leaf-routines -local -inline -unsafe -unboxing -optimize-level 5 is equivalent to -optimize-leaf-routines -block -inline -unsafe -unboxing -lambda-lift -disable-interrupts -no-trace -no -lambda-info
Marc, you know that with me and Gambit it's like the old Velvet Underground song: "I'm sticking with you, cause I'm made out of glue ..."
Perhaps this will be a more rational argument for sticking with Gambit...
Upon further investigation, compiling fib_scm with Chicken with -O5 gives this C code for the fib function:
/* fib in k32 in k29 */ static C_word C_fcall f_36(C_word t1){ C_word tmp; C_word t2; C_word t3; C_word t4; C_word t5; C_word t6; C_word t7; if(C_truep(C_fixnum_less_or_equal_p(t1,C_fix(1)))){ t2=t1; return(t2);} else{ t2=C_u_fixnum_difference(t1,C_fix(1)); t3=f_36(t2); t4=C_u_fixnum_difference(t1,C_fix(2)); t5=f_36(t4); return(C_u_fixnum_plus(t3,t5));}}
This is basically the same code as fib_c once the C macros are expanded. Note that the recursive calls to fib are translated to direct C calls. Not only are interrupts no longer checked (due to the -disable-interrupts implied by -O5) but there is no stack overflow check! So the code no longer supports preemptive multithreading, and if you are close to the C stack limit the program will crash. The programmer has to be concerned with avoiding deep recursions which could crash the program. In other words, you're no longer dealing with a high-level language with graceful support for recursion.
Here's an example where that matters:
% cat deep.scm (declare (standard-bindings) (extended-bindings) (block) (not safe) )
;; Recursive algorithm for computing (even? n). The depth of ;; recursion is equal to n.
(define (even n) (if (fx= n 0) #t (not (even (fx- n 1)))))
(display (even 10000000)) % csc -O5 deep.scm % ./deep Segmentation fault
Gambit has not problem with deep recursions. It can fill the whole heap with continuation frames if needed:
% gsc -exe deep.scm % ./deep #t%
If the Gambit heap overflows, you'll get an exception that your code can catch and act upon gracefully, not a segmentation fault.
So I'm not sure comparing Gambit against Chicken with -O5 is very meaningful. Perhaps -O4 is more in line with the expectations of a Scheme programmer, but I don't know enough about the meaning of Chicken's optimization levels to really tell what is reasonable.
Marc
I have done some more experimenting with fib_scm. I analyzed the machine code generated by gcc for the jump to fib's return address. It turns out that gcc is failing to do a simple constant folding operation (combining two offsets into one for an indirect memory access). I've now committed a patch to do the constant folding explicitly (at the C level).
The new code decreases the run time by about 10% at the default optimization level (gcc -O1). If the optimization level is increased to -O2 with
gsc -exe -cc-options "-O2" fib_scm.scm
then the run time drops by 24%.
Here are the run times in seconds on my MacBook Pro:
x86-32 (i.e. "gcc -m32") old : 1.859 new : 1.654 new -O2 : 1.437
x86-64 old : 1.914 new : 1.728 new -O2 : 1.449
With gcc -O2 fib_scm is still not as fast as fib_c compiled with gcc -O3, but the difference is smaller (fib_scm takes 50% longer to execute than fib_c, rather than 100% longer). On the other hand, with gcc -O2 fib_scm is about twice as fast as fib_c compiled with gcc -O2. Note that for all these measurements the declaration (not interrupts-enabled) was used.
Marc
On 2011-01-21, at 2:59 PM, Bradley Lucier wrote:
What kind of speedups do you see on your new version of fib with the native back end?
On x86-32 I tried fib_scm and fib_c. I removed the printf/display because the x86-32 back-end doesn't support Gambit's I/O library yet. I also played with various options and the inlining level and used (not interrupts-enabled) by default. The run time for the plain "no special tweaks" compilation of fib_scm on Gambit-C is also given. In parentheses is the time relative to the fastest time. I'm using this morning's Gambit-C patch which improves the speed of jumps to the return address.
gcc -m32 -O1 -fomit-frame-pointer 3.11s (3.3x) gcc -m32 -O2 -fomit-frame-pointer 2.72s (2.9x) gcc -m32 -O3 -fomit-frame-pointer 0.93s (1.0x) Gambit-x86-32 (inlining-limit 1000) 1.03s (1.1x) Gambit-C (inlining-limit 300) -cc-options "-O2" 1.31s (1.4x) Gambit-C (inlining-limit 300) 1.65s (1.8x) Gambit-x86-32 (not inline) 1.75s (1.9x) Gambit-x86-32 (not inline) (enable-interrupts) 2.11s (2.3x) Larceny x86 2.64s (2.8x)
So the code generated by the x86-32 back-end for fib_scm is about 10% slower than the code generated for fib_c by gcc -O3.
Marc
On 2011-01-24, at 4:00 PM, Marc Feeley wrote:
On 2011-01-21, at 2:59 PM, Bradley Lucier wrote:
What kind of speedups do you see on your new version of fib with the native back end?
On x86-32 I tried fib_scm and fib_c. I removed the printf/display because the x86-32 back-end doesn't support Gambit's I/O library yet. I also played with various options and the inlining level and used (not interrupts-enabled) by default. The run time for the plain "no special tweaks" compilation of fib_scm on Gambit-C is also given. In parentheses is the time relative to the fastest time. I'm using this morning's Gambit-C patch which improves the speed of jumps to the return address.
gcc -m32 -O1 -fomit-frame-pointer 3.11s (3.3x) gcc -m32 -O2 -fomit-frame-pointer 2.72s (2.9x) gcc -m32 -O3 -fomit-frame-pointer 0.93s (1.0x) Gambit-x86-32 (inlining-limit 1000) 1.03s (1.1x) Gambit-C (inlining-limit 300) -cc-options "-O2" 1.31s (1.4x) Gambit-C (inlining-limit 300) 1.65s (1.8x) Gambit-x86-32 (not inline) 1.75s (1.9x) Gambit-x86-32 (not inline) (enable-interrupts) 2.11s (2.3x) Larceny x86 2.64s (2.8x)
I added a simple optimization to the x86 back-end (using the "lea" instruction to compute r1=r2+n instead of a "mov" and "add"). This has improved the execution time:
gcc -m32 -O1 -fomit-frame-pointer 3.11s (3.42x) gcc -m32 -O2 -fomit-frame-pointer 2.72s (2.99x) gcc -m32 -O3 -fomit-frame-pointer 0.93s (1.02x) Gambit-x86-32 (inlining-limit 1000) 0.91s (1.00x) Gambit-x86-32 (inlining-limit 300) (enable-interrupts) 1.06s (1.16x) Gambit-x86-32 (not inline) 1.81s (1.99x) Gambit-x86-32 (not inline) (enable-interrupts) 2.12s (2.33x) Larceny x86 2.64s (2.90x)
Now Gambit with the x86-32 back-end is slightly faster than gcc -O3.
Marc
2011/1/26 Marc Feeley feeley@iro.umontreal.ca
On 2011-01-24, at 4:00 PM, Marc Feeley wrote:
On 2011-01-21, at 2:59 PM, Bradley Lucier wrote:
What kind of speedups do you see on your new version of fib with the
native back end?
On x86-32 I tried fib_scm and fib_c. I removed the printf/display
because the x86-32 back-end doesn't support Gambit's I/O library yet. I also played with various options and the inlining level and used (not interrupts-enabled) by default. The run time for the plain "no special tweaks" compilation of fib_scm on Gambit-C is also given. In parentheses is the time relative to the fastest time. I'm using this morning's Gambit-C patch which improves the speed of jumps to the return address.
gcc -m32 -O1 -fomit-frame-pointer 3.11s (3.3x) gcc -m32 -O2 -fomit-frame-pointer 2.72s (2.9x) gcc -m32 -O3 -fomit-frame-pointer 0.93s (1.0x) Gambit-x86-32 (inlining-limit 1000) 1.03s (1.1x) Gambit-C (inlining-limit 300) -cc-options "-O2" 1.31s (1.4x) Gambit-C (inlining-limit 300) 1.65s (1.8x) Gambit-x86-32 (not inline) 1.75s (1.9x) Gambit-x86-32 (not inline) (enable-interrupts) 2.11s (2.3x) Larceny x86 2.64s (2.8x)
I added a simple optimization to the x86 back-end (using the "lea" instruction to compute r1=r2+n instead of a "mov" and "add"). This has improved the execution time:
gcc -m32 -O1 -fomit-frame-pointer 3.11s (3.42x) gcc -m32 -O2 -fomit-frame-pointer 2.72s (2.99x) gcc -m32 -O3 -fomit-frame-pointer 0.93s (1.02x) Gambit-x86-32 (inlining-limit 1000) 0.91s (1.00x) Gambit-x86-32 (inlining-limit 300) (enable-interrupts) 1.06s (1.16x) Gambit-x86-32 (not inline) 1.81s (1.99x) Gambit-x86-32 (not inline) (enable-interrupts) 2.12s (2.33x) Larceny x86 2.64s (2.90x)
Now Gambit with the x86-32 back-end is slightly faster than gcc -O3.
Marc
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
Amazing. I'm so looking forward taking a look at that backend :)
Thank you for this great work!
Álvaro
-
Alex Queiroz -
Bradley Lucier -
Hendrik Boom -
Jeff Read -
Marc Feeley -
Mario Domenech Goulart -
Raffael Cavallaro -
Álvaro Castro-Castilla