This repository is an embryonic collection of ray tracers written with parallel functional programming techniques. The intent is to investigate, on a rather small and simple problem, to which degree functional programming lives up to the frequent promise of easy parallelism, and whether the resulting code is actually fast in an objective sense. The benchmarking technique is mostly crude, so assume only large relative differences are meaningful. I welcome contributions, as I have little confidence that any of my code is optimal. I am an expert in at most one of the languages on exhibition here. I also welcome new implementations in other languages!
Note also that this is not a good ray tracer. It does not generate particularly pretty images. It's chosen simply because it expresses two interesting kinds of parallelism (see below), and because even an ugly image is more interesting than just a number. Two scenes are used. The first is rgbbox:
The second is irreg:
This second scene is interesting because the load is unbalanced: all objects are in the lower half of the pixels.
For each scene, two things are benchmarked:
-
Constructing a BVH of the scene. This is interesting because it is a divide-and-conquer task parallel problem.
-
Actually rendering the scene, accelerated by the BVH. This is mostly straightforward data parallelism, but with a potentially beefy amount of work for each pixel.
The following measurements are for 1000x1000 renderings. I used a Ryzen 1700X (8 cores, 16 threads) CPU and a Vega 64 GPU. Compare numbers within the same column.
| Language | rgbbox (BVH) | rgbbox (render) | irreg (BVH) | irreg (render) |
|---|---|---|---|---|
| F# | 10ms | 957ms | 16ms | 484ms |
| Futhark (GPU) | 5.5ms | 32ms | 5.8ms | 16ms |
| Futhark (CPU) | 9ms | 477ms | 15.7ms | 226ms |
| Haskell | 0.3ms | 1842ms | 10.6ms | 2062ms |
| MPL | 0.4ms | 341ms | 9.4ms | 112ms |
| OCaml | 1.3ms | 723ms | 15ms | 240ms |
| Rust | 0.5ms | 248ms | 0.7ms | 99ms |
The Haskell implementation uses the Strict language pragma to
disable laziness in the core modules. This has about 1.5-2x impact on
the run-time.
After a few false starts, F# runs quite fast when using .NET Core 2.1. The main tricks appear to be using inline functions and explicit value types.
MPL (which is a parallelism-oriented fork of MLton for Standard ML) is definitely the star here. The code is readable, written in a completely natural style, and performance is excellent.
Multicore OCaml is also quite fast, and the code is likewise very clean.
While Futhark is fast, the code is significantly longer and more complex. This is particularly because of the BVH construction. In all other implementations, the BVH is expressed as a straightforward recursive divide-and-conquer function, which is also easy to parallelise with fork-join techniques. Since Futhark does not support recursion, it instead uses a bottom-up technique presented by Tero Karras in the paper Maximizing Parallelism in the Construction of BVHs, Octrees, and k-d Trees. This is actually a pretty fast technique (although not for the small scenes used here), but it is about two hundred lines longer than the recursive formulation. The CPU timings use an early experimental multicore backend.
It is interesting that the fastest implementations are all from exotic or experimental language implementations. Considering how long both functional and parallel programming has existed, it's surprising that the relatively mainstream languages don't do better.
Jon Harrop's Ray tracer language comparison is an inspiration for this page. The main difference is that I focus on parallelism. The ray tracer here also requires the construction of an explicit BVH from scene data, while Jon Harrop's ray tracer used a functional formulation to describe the recursive structure of his scene.