Conclusions

The benchmarks show that FISh is significantly faster than Ocaml in all cases. There appear to be three separate sources of speed-up:

No garbage collection
Exploitation of the C compiler
Function in-lining

Of even greater interest is the evidence that FISh can significantly outperform C on polymorphic programs, such as quicksort.

No Garbage Collection

FISh supports a strong stack discipline, so there is no need for a garbage collector. In all cases, system times for FISh are between 50-100% of those for Ocaml. The graph for mapping is typical. System times are the same for the first half of the tests, but then rise steeply for Ocaml, presumably due to garbage collection. For the remainder of this section we will focus on user times.

-------------------------------------------------------------
|               |Map   Reduce  Q'sort  FFT   MM-loops  MM-ip |
|_______________|____________________________________________|
|---------------|--------------------------------------------|
|FISh           |1.04  0.37     1.93   3.57  4.36       7.05 |
|---------------|--------------------------------------------|
|Ocaml(in-lined)|4.00  2.66     3.53                         |
|---------------|--------------------------------------------|
|Ocaml          |5.99  4.59    15.47   8.16  7.71      60.61 |
|---------------|--------------------------------------------|
|speedup        |5.8   12.4     8.0    2.3   1.8        8.6  |
--------------------------------------------------------------

Benchmark user times

Each benchmark was plotted for a series of input sizes, and produced a smooth curve in every case. The figure above shows user times for the largest example in each series of tests.

Exploitation of the C compiler

FISh produces simple C code which can be compiled using mature techology. For example, in-lined mapping, reducing or quicksort, the fast Fourier transform, or matrix multiplication all show FIsh running at at least twice the speed of Ocaml are all examples of simple imperative programs, written almost identically in both languages. Yet FISh programs run at least twice as fast as the corresponding Ocaml programs. Mapping and reducing show even greater speed-up, (four and ten times, respectively). A fraction of this may be due to Ocaml initialising arrays before use, whereas FISh only requires their shapes.

Function in-lining

FISh in-lines all function calls. This leads to even more significant speed-up, on mapping, reducing, quicksort and matrix-multilication, of eight to twenty times. Normally, in-lining is only aplied selectively, as it may eliminate some overheads, but risks code explosion, and possibly duplication of computations. Neither of these things happen in these benchmarks. In part this is because the benchmarks are all data intensive. More importantly, the shape-based approach supports construction of polymorphic, higher-order functions from simple imperative procedures, and shape functions.

Faster than C?

Page Last Updated:

Please feel free to send any comments.