Subject: categories: Re: Update on FISh and shape

From: "Ralph Loader" <[email-masked]>
Date: Thu, 29 Oct 1998 13:46:02 +0000

> 
> 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