News for hackers. Stuff that matters.
Re:Immutable-cpp: persistent immutable data structures for C++ by TillE on Saturday July 23, 2016 @08:16AM (#12149254)
"Practically O(1)" is meaningless. If it's not actually constant time, then how does it grow?
Re:Immutable-cpp: persistent immutable data structures for C++ by Tuna-Fish on Saturday July 23, 2016 @08:29AM (#12149289)
Every operation that is not actually constant time grows by log32. Or in other words, by no more than the constant factor 5.

In practice, these data structures live and die by your memory allocator. They do so many allocations that unless you are using a world-class GC, the memory allocation costs completely overshadow any other time costs. Using the typical platform malloc, or even jemalloc or it's ilk, this will be very slow indeed.

Re:Immutable-cpp: persistent immutable data structures for C++ by Kutta on Saturday July 23, 2016 @10:45AM (#12149597)
Yes. Copying GC with bump pointer allocation is critical for pretty much any persistent data structure. In C++ and Rust one should use memory pools/arenas for them instead.
Re:Immutable-cpp: persistent immutable data structures for C++ by Syzygies on Saturday July 23, 2016 @10:06AM (#12149484)
Yes. This begs for a port to Rust, to see if the fine-grained memory support there pays off. While Rust can do anything, it wants to be bare-metal Haskell.
Re:Immutable-cpp: persistent immutable data structures for C++ by izym on Saturday July 23, 2016 @06:07PM (#12151186)
C has just as much fine-grained memory support as Rust. Rust does however have better memory safety with its borrow checker, but I'm not sure if you could implement something like this without unsafe.
Re:Immutable-cpp: persistent immutable data structures for C++ by izym on Sunday July 24, 2016 @02:44AM (#12152503)
It seems I was a bit too fast. I meant to write C++ and not C.
Re:Immutable-cpp: persistent immutable data structures for C++ by saasinator on Saturday July 23, 2016 @04:01PM (#12150795)
"Practically O(1)" == amortized constant time?