What's new in purely functional data structures since Okasaki? (2010) | Hacker News Reader

What's new in purely functional data structures since Okasaki? (2010)

cstheory.stackexchange.com

154 pointsr4um42 comments

Perhaps the most interesting "discovery" for me in this area is that these types of data structures are not possible in C++ as they are in other languages, due to lack of GC or tail recursion[0], either of which could make them a reality.

The other discovery is that some languages, like Swift, are introducing lots of surface-level functional idioms that resemble their counterparts in truly functional languages, but without the persistent structures. Since Swift is implemented in C++, no doubt that's why it's not a reality in that new language either.

If someone could cleverly invent an implementation of Okasaki that worked in a language like C++ (and some smart people have really tried), I think it would be a major game changer to the language's possibilities. This handicap is a rare example of something that is simply not so possible in C++.

[0] https://github.com/BartoszMilewski/Okasaki/issues/1

> "If someone could cleverly invent an implementation of Okasaki"

This is new to me, but based on the HN link, isn't Okasaki a reference to a book with multiple different algorithms? What are the names of the Okasaki algorithms that are hard to implement in C++?

Please see the GH link I posted, and consider replying directly to the author, who is a well-known C++ guy.

> due to lack of GC or tail recursion

(1) I'm pretty sure that everything that can be done by a GC can be done by `shared_ptr` and `weak_ptr`. If not, then you can use Boehm GC if you don't do anything weird with pointers.

(2) If you mean "tail recursion optimization", it's a compiler thing, not a language thing in this case, and GCC and MSVC in fact support it, and I'm sure Clang does too. So since "either one" is sufficient, as you say, it looks like you can go implement Okasaki's stuff in C++ now!

>If you mean "tail recursion optimization", it's a compiler thing, not a language thing in this case

That doesn't help so much. If it is not a standard language feature as per the C++ spec, then it's not as useful as you'd think.

Tail calls are not simply an optimization, they are semantic.

edit: Not understanding the downvotes here. In Scheme, for example, tail calls are part of the semantics of the language. We know that when we place a recursive call in tail position that we're really describing a linear process. If such a thing is just an optional optimization, programmers can't rely on it in the same way.

Luckily, you can do the rewrite manually. I recently implemented an array mapped trie that shared structure when copied. `find`, `erase`, and `at` were all rewritten to use loops after first implementing them recursively (and profiling indicated it to be a problem).

If you follow the link, the issue isn't iteration, iteration is easy. The issue is the recursive destruction of the tree when the root is destroyed and no subtree is shared.

> The list implementation is simple/nice but it imposes a limit on number of stored elements because of "additional effect" of recursive destruction.

How would you perform destruction of a tree with more than one child tail recursively? I mean this as an honest question - my current implementation of array_mapped_trie performs this operation via non-tail recursive calls.

EDIT: I also don't see how destruction of a list is any harder than iteration of a list, as far as writing it tail recursively. You would need to make sure your node destructors are trivial, but you probably need to do this anyway if you intend to support using a custom Allocator (would instead have template <typename Allocator> destroy(node*, Allocator&); that calls Allocator::destroy on the contained value and Allocator::deallocate on the node). The implementation would then look something along the lines of:

decltype(head) next; for (auto ptr = head; ptr; ptr = next) { next = ptr->next; if (ptr->unique()) { destroy(ptr, allocator); } }

(unique() is a method on node - intrusive ref count.)

> I'm pretty sure that everything that can be done by a GC can be done by `shared_ptr` and `weak_ptr`. If not, then you can use Boehm GC if you don't do anything weird with pointers.

Except only slower and subject to thread races.

Can those pointer types break cycles?

No, unless you make use of weak_ptr.

The problem with RC based solutions is that to beat the top of top GC implementations, they need compiler support and so many tricks that in the end one gets RC + mini-GC anyway.

For example, Cedar at Xerox PARC used RC with local GC for cycle collection, instead of trying to use lots of tricks for RC performance fine tuning.

That's an interesting point. One of the nice things about immutable structures is that old things can never point at new things. (Some might exploit laziness to allow some sort of loop but I'd count that thunk as a mutable structure, even if it's referentially transparent like in Haskell.)

Some functional languages leverage this sort of restriction to their advantage. It can simplify garbage collection and serialization protocols don't need to track visited nodes for example. It's certainly nice to be able to step out of this mode from time to time and many functional languages provide controlled effects of sorts. I think an interesting area to study would be the balance between minimal effects and otherwise immutable structures. I wouldn't however, use this to sacrifice persistence, which it seems many implementations do.

malloc/new is slooooow, about an order of magnitude slower than GC for many small allocations. You can make it faster by using an allocator or doing allocation yourself, but nobody's come up with a dynamic manual allocator that beats GC, not even in research.

When you compare benchmarks in GC languages to benchmarks in non-GC languages, you're usually comparing mostly-static allocation to dynamic allocation, because non-GC languages tend to be oriented to the former. With functional data structures, however, lots of dynamic allocation is typically unavoidable.

Confused. Even GC requires something like malloc - a heap manager for allocating new storage. GC adds complex algorithms on top of that. It has to be slower than malloc.

For new objects, a lot of GC systems use a memory slab. Essentially, a buffer where you just allocate new data at the end, and then perform garbage collection once the slab is filled up. With this allocation is basically just a pointer bump. When your program requires lots of small allocations that all go out of use at around the same time, GC will significantly out-perform a naive malloc/free for every piece of data.

I am still just as skeptical as JoeAltmaier was. The fast-path for modern memory allocators are also just pointer-bumps in slabs. And if you keep mallocing and freeing something of the same size on the same thread, you are very likely to keep getting the same memory location on each allocation, which has excellent cache behavior.

For an excellent paper on state-of-the-art memory allocation techniques (which also has a good overview of prior techniques, and how their works builds on that), see "Fast, Multicore-Scalable, Low-Fragmentation Memory Allocation through Large Virtual Memory and Global Data Structures" from OOSPLA 2015: http://2015.splashcon.org/event/oopsla2015-fast-multicore-sc...

If you're aware of published works which show garbage collection consistently outperforming manual memory management for the reasons you explained, I'm very interested in reading them.

Agreed, except for the 'excellent cache behavior'. If you're getting cache hits on reallocated memory, you're looking at uninitialized data!

Stores access the cache too. When you initialize your newly malloc()'d memory, ignoring the previous data, you still benefit from having the cache block present in-cache.

To build on what you said: we're interested in the cache line, not the data in that cache line. Both reads and stores access the cache line, and both can see misses. It's not that you're seeing cached data, it's that your store instruction does not have to wait for the cache line to come into the L1.

Some of the state-of-the-art allocators close the performance gap pretty significantly, I was comparing to the classic Doug Lea style allocator. I imagine with something like your link the difference will be much less noticeable for allocation speed. However, not having an explicit free can lead to performance benefits, though it seems counter-intuitive. Imagine you are allocating a large number of small, short-lived objects. In the manual case, you have to explicitly call free() for each object as it goes out of scope. The free() call is rather fast for slab allocators, and free-ing everything runs in time O(dead_objects). A well-designed generational GC uses a copy collector for the eden generation, which essentially allocates a new slab and copies over all the live objects, and then frees the old slab. Copying objects is relatively fast for small objects, and this algorithm runs in time O(live_objects), which is much much smaller than the number of dead objects. Plus The copying step moves all the live objects together on the slab which reduces memory fragmentation.

You're discounting the cost of the GC approach necessarily having more live objects at once. That will require hitting more slow-path parts of the GC's allocation algorithms (either finding free slabs, finding freed new slabs from a global cache, or allocating new ones from the OS), and it will have poor cache behavior. The manual memory allocator will be on the fast path for malloc and free, as long the number of live objects is less than that of a slab.

There may be a crossover point where the GC algorithms are better (say, a pathological case where you keep forcing the manual memory allocator to hit its slow paths by allocating just one more than the size of a slab, freeing all of them, then repeat). But I would also not be surprised if there never is a crossover point.

> You're discounting the cost of the GC approach necessarily having more live objects at once.

No, by live objects I don't mean the objects that currently exist in the heap, I mean the objects currently reachable by the program, which is the same whether or not you are using GC. But you are right that GC will use much more heap on average than manual allocation.

I agree that you can probably always beat GC using manual allocation if you are sufficiently smart about it. For instance, if you have some data structure you know is going to allocate a bunch of small objects, and none of the small objects can outlive the data structure, you can have that data structure create a special slab just for its objects, so when you free the data structure you just need to call one free() on the slab instead of a bunch of free() calls on every object.

I don't you need to be particular smart using manual memory allocation to beat GC. You just need to free your memory once you're done with it. Consider:

    for (size_t i = 0; i < 100000000; ++i) {
        size_t* val = malloc(sizeof(size_t));
        *val = i;
        free(val);
    }

Decent memory allocators will just keep reusing the same memory location over-and-over. All 100 million calls to malloc and free will be fast-path calls. GC-based schemes will most likely not be 100 million fast-path allocations. Yes, this is a contrived example, but freeing memory as you no longer need it is common in languages with manual memory allocation. It is also harder, more error prone, and quite often leads to nasty bugs, but it's usually faster.

I think you're reasoning about just the cost of the frees versus garbage collection cost. But by ignoring the extra memory required on the heap, you're also ignoring the extra slow-path allocations.

I believe in this example GC will actually perform better! With GC, this code will fill up the eden slab with a bunch on these integers. When there is no more space in the eden slab, the GC makes a new slab (one malloc() call), copies over any live data by checking what's accesible from the stack (there are no pointer saved on the stack except for the current val) and the old slab is freed (one free() call). So GC calls free 100M/(number of ints we can fit in the eden slab) times, as opposed to the manual case which calls free 100M times. And, just like the manual case, the GC's malloc and free will be fast-path calls (our eden slab will essentially just switch back and forth between two different memory locations). And the cost for tracing out the live variables here is essentially nothing (10-100s of nanoseconds) since nothing is referenced in local variables. The only cost you have to pay with GC in this situation is increased heap usage and, consequently, a larger cache footprint.

I would be shocked if the GC performed better. I think you are severely over-estimating how expensive the fast-path for memory allocations are. For this example, decent memory allocators will execute on the order of a dozen instructions for each malloc and free call - no need to allocate new slabs in the allocator, no need to free old ones, no interactions with the operating system or even the internal slab allocator.

Calling free is not what is expensive. It's what we do when we call free. GC has to do more work because it has to figure things out. Manual memory allocation does not need to spend any instructions figuring anything out because the programmer has already done that. As I have said before, decent memory allocators will keep returning the exact same address for each malloc call in this situation. That is the ideal situation for this case.

Also keep in mind that larger heap sizes don't come for free - that means more page faults, which will slow you down.

If the language semantics allow for a top of the tops GC implementation,it means a generational collecting GC.

Allocation is a mere pointer bump.

> Since Swift is implemented in C++, no doubt that's why it's not a reality in that new language either.

The language the compiler is implemented in doesn't matter, so I guess you mean that it's not possible because Swift is too heavily influenced by C++? I don't think that this is really the case, it's more influenced by Objective-C

Have you looked at trampolines/continuation passing?

> these types of data structures are not possible in C++ as they are in other languages, due to lack of GC or tail recursion[0]

The link doesn't really explain why though. I mean, I'm willing to believe this is true until proven otherwise - it's safe to assume Milewski knows what he's talking about - but I'd love to see a proper explanation.

It is in fact incorrect. The incorrect assumption is nested structure implies nested destructor calls. This can be avoided by ensuring each node in the structure does not destroy the next node_ptr (explicitly or more likely implicitly). Instead, the destruction has to happen more manually (internally to the overall data structure - not by the user). If the structure only recurses on one child, it can be performed as a loop.

I implemented Okasaki's persistent queue in Scheme recently using SRFI-41 streams and it was a lot of fun. Now, I need to grok things like finger trees so I can understand persistent vectors and hash tables.

Look at hash array mapped tries, which is what most functional languages use to implement hashmaps.

Whats new since "What's new in purely functional data structures since Okasaki?"? Its been 5+ years now...

I learned functional programming from Ralf Hinze, great to see his contributions, even if he did teach me to say 'mooo-nad'.

Reply on news.ycombinator.com