> So it seems like you'd expect to see almost no difference except in the most > extreme cases, and even in those cases the Nim program would likely just be > producing unnecessary garbage anyway, right?
Not entirely what I meant, though I may not have been clear. Some imperative algorithms are allocation-heavy even if you write them naturally and if they occur in a hot loop, you can have a problem. However, there are a few points to make: 1\. You can generally make them more efficient using imperative code. The standard insertion algorithm for red-black-trees requires O(1) allocation work per insertion (and also O(1) memory writes overall, but of course still O(log n) memory reads); a purely functional red-black-tree implementation requires O(log n) allocation work per insertion. 2\. You can reduce the allocation work in many cases. There are a number of common approaches: (a) Represent e.g. a tree as an array and references as integer offsets within the array. (b) If your allocator is slow, keep a size-limited free list per data structure. Say, up to 100 entries. Whenever you free a node, put it on the free list, unless it exceeds it max size, then you free it normally. To allocate a node, you go to the free list first, unless it's empty, in which case you allocate normally. This means for data structures that fluctuate in size, you save a fair amount of allocations. (c) Represent subjects as tuples that reference another data structure. For example, I had a string interning implementation I wrote once, where I didn't allocate the string that was to be interned separately (which in most cases would have been discarded right after the interning operation), but passed a (original string, start, length) triple. String interning allocated a string only if there wasn't already an interned variant. Note that on contemporary hardware with state of the art GC, there's a limit on how much you can allocate. This is difficult to reach within a single thread, but if you use multiple threads and use a purely functional style, [you can run fairly easily into it](https://gist.github.com/plokhotnyuk/42af1ebfeac791bb5b52bbaeb974acbe). Even the best GC can't fix that. The core issue that I tend to get back to is that as I wrote above, most programs that run into GC issues have a garbage problem rather than a garbage collection problem. And unlike with most purely functional languages, imperative or multi-paradigm languages can usually avoid it or work around it.
