Polymorphic quicksort in FISh is faster than in C for quicksort (see below).
Some comments. You're simply not comparing like-with-like. The differences in performance that you're seeing have nothing to do with the boxing/ unboxing issues that you claim are involved. (1) Your C code compares using two floating point operations (subtraction, compare), while the fish program uses just one (no subtraction). (2) The output of the fish-to-C translation uses statically allocated memory, and won't multi-thread correctly. Sun Solaris does support multi-threading, so while your compiler uses statically allocated memory here, the Solaris C library can't. [As a matter of interest, what happens if you call your fish quicksort with a comparison function that itself calls quicksort?]. (3) The C library qsort takes a three-valued comparison function, while your fish code uses a two-valued comparison.
Shape analysis in FISh allows polymorphic functions to be specialised to the exact shape of their arguments, so that it is never necessary to box data structures. This can have a significant impact when the cost of pointer-chasing is high compared to the operation being performed.
["never"? Show me an unboxed cyclic data structure.] (4) As you note, your fish code gets optimised by specialising to the datatype and comparison function used. This is the main performance issue, and has nothing to do with boxing/unboxing issues. Note that the C library qsort is a polymorphic function, is not specialised to particular arguments, and still takes an array of unboxed elements. Specialising functions to their arguments is nothing new to FISh - some (but not all) C compilers, for instance, on inlining a function will also specialise it. The reason why the qsort function is not specialised to its arguments is because it's a precompiled library function, not because it's written in C.
The reason is that the C program achieves polymorphism by requiring the comparison function to act on pointers, rather than values. The actual comparison function for floats is
The reality is that the machine code generated by your fish program ends up dealing with pointers also: on a typical RISC processor, to compare two doubles held in memory, you need to compute the addresses of the doubles, load them into registers and do the comparison. Passing pointers to the comparison function just means that the values are loaded into registers in the function, rather than before the function call. Whether its faster to load the values into registers before the function call or in the function will depend on things like instruction scheduling in the compiler & CPU, & register allocation in the caller & in any case the difference will be tiny.
As well as slowing down the program, these pointers are a source of
It's not very often that you want to sort an array of numbers. If you want to sort some records that contain both a sort-key and some extra data, then using pointers is faster.
program clutter, potential errors, and type violations.
Ralph. (not speaking on behalf of Paradigm) Ralph Loader Paradigm Technology, Level 13, Paxus House, 79 Boulcott Steet, Wellington, New Zealand Phone: +64 4 495 1004 Fax: +64 4 499 7762