Hacker News Reader

Comment by throwaway81523 | Hacker News Reader

Single ownership (std::unique_ptr) works pretty well in C++ a lot of the time, but not always. Reference counting including unique_ptr also have to be locked for updates, slowing down multi-threaded programs, as exemplified by the notorious CPython GIL (global interpreter lock). And the idea of transferring ownership between lightweight processes leads to memory fragmentation within the processes. Erlang deep-copies message contents except for large binaries, so each lightweight process has its own semispace GC and maintains good cache locality. There are also styles of programming (such as using RB trees as persistent data structures with multiple versions sharing parts of the structure) that are not conducive to single ownership.

At the end of the day, in a general purpose language, it's great to have machinery to avoid needing GC when possible, but you really do want to have GC to fall back on.

View on HN

> Reference counting including unique_ptr also have to be locked for updates

This is not true. The counter itself can have its count updated atomically with a compare & exchange. I think this is what actually happens in most cpp std libs, but haven't checked in a while. (This doesn't mean the object they point to is thread safe though!)

But here's my question: Why do C++ programmers always refer to the overhead of "reference counting", when the overhead is not in the counting, but in the memory management: the use of doug lea's malloc or its derivatives such as ptmalloc3. This is what "new" wraps, and the STL objects all use it to resize themselves too. These routines are written by geniuses, but if you actually read up on how they work, they are doing a lot of (completely necessary) stuff, and one of the longest-running std lib calls you can make. (Way longer than an exp(), for example).

>Why do C++ programmers always refer to the overhead of "reference counting", when the overhead is not in the counting, but in the memory management

Presumably they're looking at reference counting as an alternative to unique_ptr, and in that context the memory management overhead is already being paid.

Unique_ptr is basically a pointer to a refcounted object whose refcount is always 0 or 1, and therefore doesn't have to be stored in the object itself. If the unique_ptr is a non-null address than the object is alive (refcount=1), if all the unique_ptrs are null then the object is dead (so it gets freed), and C++'s fancy scope rules and move semantics statically ensure that there is at most one non-null unique_ptr to the object at any time.

I have been under the impression that glibc implements both unique_ptr and shared_ptr (that's the one with arbitrary refcounts) using locks, but ok, if it's done with something like CMPXCHG that's still a heck of a lot slower than ordinary copying.

As for overhead, well, if an object lives for a long time and lots of references are updated or moved around, then that itself can be expensive, besides the malloc/free costs. Copying garbage collectors by comparison are simple and fast, at the expense of making your program gobble a lot more memory, limiting the language so that the gc can know where all the pointers are, and having to stop the program during gc.

I'd be very surprised if GCC actually used locks for unique_ptr. A unique_ptr owns the object it points to, so we know for a fact that it doesn't need to check anything before deleting it.

You might be right about that, i.e. I probably derped up. It's been a long while since I looked at it, and the issue might only be with shared_ptr. I'm starting to remember finding out that shared_ptr was surprisingly expensive even in single threaded programs. It looks like some finer grained versions of shared_ptr (like atomic_shared_ptr) arrived recently. I haven't checked into them yet.

Typically unique_ptr is represented as a pointer (check sizeof). For shared_ptr, there’s an atomic refcount but no locks. Operations on the shared_ptr object itself aren’t threadsafe (you can’t have the same shared_ptr assigned by two threads at the same time without locking), just like int, but the reference count is atomic, so copies of shared_ptr can safely be shared among threads. Atomic_shared_ptr adds atomicity to the pointer itself. I believe that usually uses locks.

> I have been under the impression that glibc implements both unique_ptr and shared_ptr (that's the one with arbitrary refcounts) using locks

Why would unique_ptr ever need a lock?

> As for overhead, well, if an object lives for a long time and lots of references are updated or moved around

If performance is important you only pass a shared_ptr if the callee needs to keep it around, otherwise just pass a plain (const) reference. You can also pass a (const) reference to the shared_ptr and then the callee can decide if they actually need to keep it. Moving shared_ptr is free, because the refcount stays the same.

With std::shared_ptr each copy has a pointer to the ref count & there is only one ref count, atomically updated with a cmpxchg instruction. Not sure what you mean by "references are updated or moved around"?

But I agree that GC has higher thruput than malloc/free as most gc allocations are a single op, at the cost of higher initial memory usage and worst-case latency. That's why "scripting" languages like python / perl use refcounting as they need to start quickly and might not run for very long, whereas java / c# programs tend to be longer running.

Not sure what you mean here, std::unique_ptr is for when you want to auto destruct a ptr when going out of scope (ref counting limited to one) and std::shared_ptr is normal reference counting, they aren't alternatives to each other but specific things for specific situations?

> (Way longer than an exp(), for example).

eh, not that much.

use.cpp:

    double rand_double() { return 16.; }
    int rand_int() { return 16; }
    void use(void*) { }

main.cpp:

    #include <iostream>
    #include <chrono>

    void run();
    int main()
    {
      auto t0 = std::chrono::high_resolution_clock::now();
      for(int i = 0; i < 10000000; i++) {
        run();
      }
      auto t1 = std::chrono::high_resolution_clock::now();
      std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(t1 - t0).count() << std::endl;
    }

alloc.cpp:

    #include <cstdlib>

    int rand_int();
    void use(void*);
    void run()
    {
      auto res = malloc(rand_int());
      use(res);
      free(res);
    }

exp.cpp:

    #include <cmath>

    double rand_double();
    void use(void*);
    void run()
    {
      auto res = exp(rand_double());
      use(&res);
    }

I get ~100ms for the exp, ~130ms for the malloc/free at -O3 / -Ofast with both clang and gcc (and checking with perf ensures that the time is indeed spent in these functions). So it's a bit faster, but not exactly fast (or rather, the math functions are really fucking slow)

.. are you sure it's not the rand functions that are slow?

the rand functions are

    double rand_double() { return 16.; }
    int rand_int() { return 16; }

here are profiling traces:

https://imgur.com/a/5vkblDr

You mean the ones that RET 16? My computer person instincts tell me no, it's not those.

That's definitely very interesting. I do wonder if malloc and free would take longer if there would multiple threads in the program, which is more relevant to this discussion; surely exp would not, assuming sufficient free cores. Even more interesting would be if you malloced in one thread and freed in another, given that allocators usually make use of thread-local pools.

Excuse me if I have mis-read your sample program but it looks like you are allocating 16 bytes, then immediately freeing it, again and again in a loop. Since you're not allocating anything else, the allocate and free will happen almost immediately. Malloc() has a run time that can vary a lot depending on what has already been allocated & freed in the past, so this test is not meaningful.

Not only that, but the original doug lea's malloc has a bin specifically for 16 byte allocations: http://gee.cs.oswego.edu/dl/html/malloc.html (the smallest size), so you've specifically chosen a very fast example.

In order to properly test malloc() you have to pre-generate some pseudo random numbers for your allocation sizes, and allocate and free unpredictably. But it's more complicated than that, as in the very occasional case when malloc() has to ask the OS for more heap, that system call may not "finish" until your program first writes to that region of memory... (ie malloc() returns but hasn't finished!)

I actually tried with up to 256 bytes and got the exact same timings. But sure, that's the absolute possible best case considering glibc thread pool, but it's (allocating and freeing in a loop) still a pretty common case

But when you enter the loop you have no other "objects" in your program allocated at all, so it doesn't have to do a search for a suitably sized block. Near-identical timings for changing the size to 256 is what I would expect.

The traditional alternative is what I might call "static reference counting", where the programmer knows by inspection/convention (C) or through the type system (Rust) how many references exist at any point statically, so they can skip the dynamic reference count entirely.

I agree that malloc/new is comparatively expensive, but that ends up as a cost borne by all heap-allocated variables in every language. Unless people use special techniques like pool or slab allocators.

Rust also allows for non-thread safe reference-counted objects (Rc<>) that don't have the overhead of atomic instructions for updating the reference count. And it's getting support for custom local allocators, addressing the overhead of malloc/free. Along with a bunch of further advantages compared to C++ shared_ptr (such as being able to dispense with a pointer indirection in some cases, and allowing for sub-borrows that don't even need a refcount update because they can't possibly affect the 'ownership' of the object).

There's a huge difference between C/C++'s malloc() and a precise garbage collector: with the former all objects are fixed. With the latter you can move them around. This means malloc() is more constrained than a GC, and that makes it slower.

The real gains of managing memory manually is not in the speed of malloc(), but in the fact that in practice you can perform far fewer heap allocations.

> The counter itself can have its count updated atomically with a compare & exchange.

At some point you have to consider how that hardware implements atomic variables and cmpxchg, because it is certainly not free.

> Why do C++ programmers always refer to the overhead of "reference counting", when the overhead is not in the counting, but in the memory management:

You’re mistaken. In a multi core or multi processor system, atomic operations necessary for shared RC are relatively expensive. Heap allocation cost is paid for any dynamic object no matter the type of GC/RC used, so that is not what is being compared.

In Inko, the reference counts are regular integers, not atomics. They don't need to be atomic because the same object can't be used by different processes.

Moving objects between processes itself doesn't lead to fragmentation, as processes don't have their own heap in the data structure sense. That is, the structures representing a process don't have some sort of "heap" field. Instead, the OS threads running processes maintain the heaps (each thread has its own heap). This brings several benefits:

1. Since the heap is physically detached from processes, we can move without copying

2. Since the heap is still thread-local, allocations don't need synchronisation

3. Since the heap is detached from the processes, each process is smaller, allowing for more processes to run concurrently

4. Since objects (and their children) can only be owned by one process, we also don't have to worry about multiple processes trying to write into the same object

This is only possible because we statically guarantee that a value `T` can't be _shared_ between processes, and because we'll disallow sending references between processes.

May be it's time to implement hardware CoW for RAM? Or can OS do it efficiently?

I don't understand what you're getting at, but you can implement CoW at the page level with MMU hardware. That's how Redis dumping works, for example (the process forks into two, with one dumping to disk and the other continuing to take updates, CoW'ing pages that get modified and sharing the rest). What would CoW even mean inside a single address space? The idea of persistent data structures (as used in functional programming and other places) is that you never visibly modify anything, but instead make new objects that share structure with the old objects, relying on the GC to clean up data that stops being reachable.

What is CoW?

copy-on-write

I don't see how CoW would work with threads. It doesn't make sense to me.

That sounds an awful lot like the x86 cache coherency protocol.

I don’t know about that, but I am using stlab::copy_on_write in production and it’s amazing. It’s like a cross among a T, a unique_ptr<T>, and a shared_ptr<const T>. https://github.com/stlab/libraries/blob/main/stlab/copy_on_w...

Reply on news.ycombinator.com