Koka: A Functional Language with Effects

Koka uses an allocator design inspired by mimalloc, which, instead of excessively optimizing for low fragmentation such as dlmalloc does, instead optimizes for data locality (e.g. objects allocated nearby "in time" also are put near each other "in space" on the same pages, whereas other allocators might put two successive allocations very far apart.) Doing this improves cache usage — because objects that are allocated together are often accessed together, which is a dominating performance consideration. In general there are a number of other tricks it shares with some allocators to help reduce internal and external fragmentation on top of this, but the point here is that it is an explicit design choice to optimize for locality and treat it as a dominating concern, as opposed to the classical approach of fighting fragmentation at any cost (internal fragmentation is basically unavoidable, but offset because, again, allocations are temporally correlated; if you allocate N objects rapidly, they're often of the same size class, in fact the exact same type, and fill in holes quickly before needing to slap down more pages. External fragmentation can be handled by using a low number of size classes so you don't have to waste so much slop aligning them. Pages have their corresponding metadata "up front" a la BIBOP. Et cetera, et cetera.) In practice, mimalloc has very good performance for a number of workloads.

The mimalloc paper has more information on this, and a lot of other interesting design choices. For instance, it uses no bump pointer, despite the fact functional languages are absolutely allocation hungry — a bump pointer was something I considered near unavoidable, speaking as someone who previously worked on Glasgow Haskell internals. Lean v4 is another functional language that uses this same allocation strategy, and it has excellent performance in practice despite all this, especially when combined with "in place" updates so that memory locations get reused in the first place.

The actual bigger "problem" with it all is that the lack of any garbage collector at all means that things like cycles cannot be handled implicitly by the underlying allocator ala Python, and this impacts the programming model. Neither Lean nor Koka, to my knowledge, contain any built in mechanism to e.g. create and write to global references (Haskell's IORef), and so cannot be used to create cycles; but at the same time, it means you can avoid the need for weak pointers at the user level, and that deallocation/allocation doesn't have such costly hidden tail latencies (see the mimalloc paper about temporal cadence on this note). Lean and Koka also both offer strong FFI support, so in some sense you can "just" (big quotes) punt this over that barrier and do dirty work manually at a big cost, if you absolutely must. In practice I suspect this will be fine for many things; as a Haskell programmer writing code I often get away without newIORef, quite easily in fact, because most of the time you actually don't peek behind the curtain to see who the Wizard of Oz really is.

The paper is here: "Mimalloc: Free List Sharding in Action" by Leijen, et al. https://www.microsoft.com/en-us/research/uploads/prod/2019/0...

You can deal with this by restarting the whole process occasionally. Usually this is fine.

(Alternatively, you could use reference counting almost all the time but rarely run a GC to do compaction. This means still being able to identify all pointers in memory, so I'm not sure anyone does it.)

Memory fragmentation isn't a big problem these days. The worst case scenario is 50% waste, that's the overhead that a copying garbage collector will incur all the time.

And strictly speaking, this will do as well or badly on fragmentation as the underlying malloc implementation does as the memory allocation itself is deferred to it.

Others off the top of my head in no particular order (all effectively research languages): Multicore Ocaml, Eff, Frank, Effekt, Helium, Links. Also Fused Effects in Haskell and an experimental library for it in Idris. I guess the Common Lisp condition system could be used for general effect handling too, albeit without type-level guarantees.