Floating point speed of Gambit-C
Yesterday at the MSLUG meeting Houman Zolfaghari gave an interesting talk on the use of Scheme in the "real-world". In his presentation he said that in his work he uses both C++ and Scheme; the parts that do floating-point intensive computations are programmed in C++ and the scripts are written in Scheme. An audience member asked why Scheme was not being used for the numerical computations. Houman stated, as if it was common knowledge, that C++ had better performance than Scheme on numerical computations. I have heard this misconception from several people, and I am compelled to set the record straight, at least to the MSLUG members who should know better. Brad Lucier has been using Gambit-C for floating-point intensive computations for a long time. His involvement with Gambit-C has helped me improve the compiler's performance on numerical computation. For the kind of computations that he does (partial differential equations) the performance of Gambit-C is equal to that of C. The short paper he wrote on the subject, presented at the 2000 Scheme workshop, is: http://www.ccs.neu.edu/home/matthias/Scheme2000/lucier.ps Of course the performance compared to C++ might be different for different numerical computations. The important message here is that the performance of floating point code can be in the same ballpark as C ++. If some computational kernels are critical to overall performance, it might even be possible to beat C++ by doing some agressive loop unrolling and function inlining of the kernel (which Gambit-C does automatically based on programmer declarations). Marc
Thanks for pointing out that old paper, Marc. There's a short paragraph in it that talks about what could be improved:
Keeping flonums unboxed as long as possible is important for iterative algorithms. Gambit-C currently boxes flonums across all jumps; this can be a performance issue (e.g., the code for Gauss-Seidel preconditioning is not competitive with C). Gambit-C uses an on-the-fly register allocation algorithm that behaves poorly for heavily nested, lambda- lifted, iterations. While many small routines that return Points (two-vectors) are inlined by Gambit-C, a structure analysis that eliminates the allocation of temporary vectors that are not referenced outside a function would improve performance somewhat.
Plus ça change, and all that. Brad
Well, offering a numerical performance at the same level as C/C++ with Gambit-C is certainly an amazing feat, and it deserves more publicity and exposure. And maybe a more extensive paper. There is obviously this performance myth, but that was not exactly what I meant when I answered the question in the meeting. I realize that my answer might have been misleading. So maybe I should try to give a clearer answer: 1. The scheme system I'm using does not have a great numerical performance, and in this case it is common knowledge, it's admitted and documented. Instead, this implementation offers bindings to external mathematical libraries, which in my view is not necessarily a bad method. 2. We chose scheme for other reasons that where more critical for our task when we made this decision. We already had the C++ libraries for the numerical aspects. We needed other qualities that I think are specific to scheme or functional and logical languages. In the talk, I tried to define these specific qualities. Being able to compete with C++ in it's own turf would certainly be a plus. But in the context of the problem we had to solve, and with the time we had to do it, it was not a requirement. 3. I think the ability to easily incorporate C/C++ code and libraries is in itself a crucial asset, and it is worth emphasising. Many scheme systems are exceptionally good at it (and Gambit-C and chicken both are). That was one of the factor for our choice of scheme. 4. This is a matter of personal taste, but for me, as much as I hate using C or C++ for working on trees and formal structures and other complex structures, I don't dislike them for linear iterative programming. (Maybe because I did my first real programming in Fortran). In short, I don't necessarily see an all-or-thing war between C++ and scheme, quite on the opposite. All this said, I will certainly try Gambit-C for numerical calculations as soon as I can :) Cheers Houman On 6-Dec-07, at 4:29 PM, Marc Feeley wrote:
Yesterday at the MSLUG meeting Houman Zolfaghari gave an interesting talk on the use of Scheme in the "real-world". In his presentation he said that in his work he uses both C++ and Scheme; the parts that do floating-point intensive computations are programmed in C++ and the scripts are written in Scheme. An audience member asked why Scheme was not being used for the numerical computations. Houman stated, as if it was common knowledge, that C++ had better performance than Scheme on numerical computations. I have heard this misconception from several people, and I am compelled to set the record straight, at least to the MSLUG members who should know better.
Brad Lucier has been using Gambit-C for floating-point intensive computations for a long time. His involvement with Gambit-C has helped me improve the compiler's performance on numerical computation. For the kind of computations that he does (partial differential equations) the performance of Gambit-C is equal to that of C. The short paper he wrote on the subject, presented at the 2000 Scheme workshop, is:
On Sat, 8 Dec 2007, Houman Zolfaghari wrote:
2. We chose scheme for other reasons that where more critical for our task when we made this decision. We already had the C++ libraries for the numerical aspects. We needed other qualities that I think are specific to scheme or functional and logical languages.
I could've sworn that there was some decision like this behind. I'd suspect that a damn lot of scheme projects are multilanguage and involve libraries that are written in C++, that one has to reason to translate to scheme, that would take a long while to translate, or often even that has to remain written in C++ for some reason (such as existing applications using a library...). Often the use of Scheme or other language starts when a project expands to the point that working exclusively in C++ begins to suck. Quite a few languages are full of wrappers for C/C++ libraries and often it's because the normal interpreter/compiler has speed problems, but most often not, it's just because it's easier to wrap than to rewrite, especially considering the aspect of applying/translating diffs across two branches of essentially the same software in different languages, over several years. Thus for many cases, it doesn't matter how fast Scheme is, though it's can be a nice bonus.
In short, I don't necessarily see an all-or-thing war between C++ and scheme, quite on the opposite.
All-or-nothing wars are waged by people who have something else than the interest of the project in mind. It can be caused by fear, but it also can be a conflict of interest (language fandom or other). That said, every cross-language interface introduces a cost, which is at least that to understand the whole system you need to understand two languages and you need to understand that interface. _ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801, Montréal QC Canada
Perhaps I should say what my design goals were when designing the numerical PDE library. This is not really an argument against using a mixed-language programming model, but I will say that I like to use Scheme as a single language for the entire system for the following reason. In the scripting language/low-level language model that is popular these days in scientific computing, the "interface" between these languages is fairly fixed, as it is often difficult to achieve high performance in the scripting language or high flexibility in the low-level language. In Scheme, I can move that boundary just by choosing different implementation strategies for parts of the code. For my numerical PDE class I wanted something that allowed graduate students to be able to program new (for them) parts of algorithms that were fairly sophisticated (e.g., multigrid) and be able to do it in the context of a one-semester project. So nearly all the value in the system is in the high-level parts, being able to take an algorithm from a textbook or paper and translate it into code nearly verbatim (after you struggle to really understand the half-page algorithm ;-). The reason that the system is (nearly) as fast as one programmed in C or C++ is that almost all the floating-point operations in a multigrid method for solving a finite-element method for elliptic or parabolic PDEs, say, are in sparse-matrix--vector multiplication, and that operation is limited by memory bandwidth in either language. So the fact that the final assembly code for floating-point vector accesses in Gambit-C--generated code is about 1/2 the speed of that in C doesn't matter, we're always waiting for memory in either case. I'll teach the course again next semester, and I plan to have a preliminary project where students write a complete code for a two- point boundary-value problem; this will involve rational arithmetic, symbolic manipulation of polynomials, etc., but also finding the roots of those polynomials in order to calculate Gaussian quadrature rules dynamically. The best way to do this is by finding the eigenvalues of specially-constructed matrices, and a very good way of doing that is to use the LAPACK code, and, no, I don't want to rewrite the LAPACK code for that, so I'm going to provide some sort of FFI interface to that code for the students. I'm not into the business of rewriting code. I didn't mind rewriting the level-1 BLAS code in Scheme, however, as it didn't seem worth the trouble to get a small speedup in the entire system just to use a dot-product or saxpy written in C and called from an FFI. I have enough difficulty in getting students to admit to themselves that, yes, this system is fast (just about as fast as any expert could have written it, and probably much faster than your average graduate student could have written it) and it's flexible (it's only at the end of the course that some students reluctantly admit that they could not have finished their semester project in their favorite language, whether C or C++), and that the speed doesn't arise from level-1 BLAS written in C (because they're written in Scheme). One point that most students seem to take away from the class is that multigrid is one hell of a lot faster than conjugate gradient, and many of them have been using conjugate gradient in their own projects simply because it's too hard to program multigrid in C or C++ (at least the first time you try it). So one gets a lot of speedup simply by being able to program more sophisticated algorithms. Another example might be codes for large integer arithmetic. There is a very simple radix-4 recursive floating-point FFT in the Gambit runtime; it's half as fast as the same code in FFTW (which won SIAM's award for a numerical package), and a lot faster than many, many other FFT codes written in Fortran or C. It's also ~200 lines of fairly straightforward code translated from a textbook. Using Scheme in this one-person project allowed me to try a new algorithm for FFT- based integer multiplication that gets up to about 1/2 the speed of the FFT multiplication in gmp. I tried to get the gmp folks interested, but they already knew about the principles the algorithm is based on (I didn't invent the algorithm) and they aren't interested; perhaps written in C it would beat their current code, and these guys are *all* about speed. The next GCD code in gmp *will* be a variant of what is now in Gambit's runtime library, put into an already-existing half-gcd framework by Niels Möller of Sweden after some correspondence between him and myself; I used this algorithm by Schönhage after some correspondence with him because it was especially well-suited to Scheme's computational model, but now it seems that it is faster than any other generally-known GCD algorithm. (Schönhage might know a faster one, but he doesn't talk too much about his current work.) Anyway, I'm going on too long. I use Scheme for numerical stuff because it allows me to try new algorithms, or more sophisticated algorithms, that would just be too difficult to play with in other languages. And I get good enough speed (and the new or more sophisticated algorithms often more than make up for the constant factor I might gain by using C instead of Scheme). Brad
On Sat, 8 Dec 2007, Bradley Lucier wrote:
In the scripting language/low-level language model that is popular these days in scientific computing, the "interface" between these languages is fairly fixed, as it is often difficult to achieve high performance in the scripting language or high flexibility in the low-level language. In Scheme, I can move that boundary just by choosing different implementation strategies for parts of the code.
Yes, that is right. It might even be an oft-neglected argument, but also, I suspect that many people are just not asking themselves any questions, and just assume that the project is gonna use multiple languages with C++ at the centre.
So nearly all the value in the system is in the high-level parts, being able to take an algorithm from a textbook or paper and translate it into code nearly verbatim (after you struggle to really understand the half-page algorithm ;-).
I'd say that a lot of languages aren't bad at direct translations from textbook algorithms. I'd even say that the prefix list notation of LISP is at a disadvantage because of how many books use the usual Pascal/Ada/C/Python mishmash kind of pseudo-code. For everything else, LISP is pretty much better, especially with a good macro system. C++ is often not that far behind, even though its macro system sucks.
The reason that the system is (nearly) as fast as one programmed in C or C++ is that almost all the floating-point operations in a multigrid method for solving a finite-element method for elliptic or parabolic PDEs, say, are in sparse-matrix--vector multiplication, and that operation is limited by memory bandwidth in either language. So the fact that the final assembly code for floating-point vector accesses in Gambit-C--generated code is about 1/2 the speed of that in C doesn't matter, we're always waiting for memory in either case.
If you want to beat C++ on this, you could look at how to stream the data from one component to the other so that they share the bandwidth: instead of doing several passes one after the other, start them in near-parallel. It might be easier to do this with some kind of coroutines (can't do this in C++), or not. What I said may make more sense for sparse matrices than non-sparse, because non-sparse is usually divided in rows or columns rather than squares. In any case, you have to worry about the order in which the data is sent so that you don't have to buffer much so that you don't have to use too much RAM at a time. But be warned, that still nowadays, cache RAM can be quite slower than just registers. I have made a system which streams at the level of cache RAM instead of registers, and it can't get any close in speed to a hand-written loop of a whole chain of operations compiled together. I'd need a runtime-compiler, but for C++, I have to forget it. I haven't considered Scheme seriously so far because I assume that I will have trouble with garbage collectors. I already have garbage collector slowdowns in my current version, but I'd like to get rid of them, and I wouldn't switch to Scheme if I don't know how much I can configure or get rid of the GC, or otherwise make it run much more smoothly. I do realtime programming. _ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801, Montréal QC Canada
participants (4)
-
Bradley Lucier -
Houman Zolfaghari -
Marc Feeley -
Mathieu Bouchard