5 ms·

> 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

by tines 11y ago

> 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!

hellofunk 11y ago
>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.
deleted 11y ago
[deleted]
davexunit 11y ago
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.
- sonyandy 11y ago
  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).
  - masklinn 11y ago
    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.
    - sonyandy 11y ago
      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.)
pjmlp 11y ago
> 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.
- dikaiosune 11y ago
  Can those pointer types break cycles?
  - pjmlp 11y ago
    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.
  - strmpnk 11y ago
    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.
cynicalkane 11y ago
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.
- JoeAltmaier 11y ago
  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.
  - openasocket 11y ago
    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.
    - scott_s 11y ago
      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-scalable-low-fragmentation-memory-allocation-through-large-virtual-memory-and-global-data-structures 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.

by tines 11y ago

hellofunk 11y ago

>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.

deleted 11y ago

[deleted]

davexunit 11y ago

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.

sonyandy 11y ago
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).
- masklinn 11y ago
  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.
  - sonyandy 11y ago
    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.)

pjmlp 11y ago

> 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.

dikaiosune 11y ago
Can those pointer types break cycles?
- pjmlp 11y ago
  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.
- strmpnk 11y ago
  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.

cynicalkane 11y ago

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.

JoeAltmaier 11y ago
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.
- openasocket 11y ago
  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.
  - scott_s 11y ago
    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-scalable-low-fragmentation-memory-allocation-through-large-virtual-memory-and-global-data-structures 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.