competitive programming • high-performance functional programming
my submission for the ICFP 2020 programming contest, exploring high-performance functional programming and runtime implementation. gitlab.com/emberian/embershot. github.com/emberian/incinerator.
the approach
i took the combinator-based approach implied by the problem and implemented an STG machine inspired by GHC's compilation strategy. the idea was to generalize the combinator pattern and implement an efficient runtime for evaluating these combinators.
this included starting work on a concurrent garbage collector from a paper. the contest ended before i could do anything really impressive with it, and my interest waned, but it was complete (if buggy).
overengineering as exploration
i overengineered this while hanging out with some friends who did a simple thing and moved on. i wanted to see the best performance i could wring out of it before they finished the actual puzzle.
this is a pattern in some of my hobby projects: the "correct" move is to solve the problem simply and move on, but the interesting move is to explore the design space, push the performance boundaries, and learn deeply about the implementation details.
the meta-lesson
the contest was about solving a puzzle. i turned it into an exploration of language runtime design. this is characteristic of how i approach programming: the surface problem is often less interesting than the underlying systems and abstractions.
my friends solved the puzzle. i built infrastructure that could solve many puzzles, given enough time to debug and optimize. neither approach is "better"—they're optimizing for different things.
concurrent garbage collection
the incinerator was particularly interesting. concurrent GC is one of those problems that's:
- algorithmically fascinating (coordinating collection with mutator threads)
- practically important (minimizing pause times)
- devilishly hard to get right (race conditions everywhere)
i didn't finish it, but the exploration reminded me about:
- mark-sweep-compact strategies
- coordination between mutator and collector threads
- write barriers and read barriers
- memory ordering and synchronization
- the inherent tradeoffs in GC design (throughput vs latency vs pause times)
links
- embershot on gitlab
- ICFP contest: international conference on functional programming's annual programming competition