3 ms·

"Practically O(1)" is meaningless. If it's not actually constant time, then how does it grow?

• Tuna-Fish 10y ago
  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.
  • Syzygies 10y ago
    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.
    • izym 10y ago
      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.
      • izym 10y ago
        It seems I was a bit too fast. I meant to write C++ and not C.
  • Kutta 10y ago
    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.
• saasinator 10y ago
  "Practically O(1)" == amortized constant time?