5 ms·

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 f

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.

vbezhenar 5y ago
May be it's time to implement hardware CoW for RAM? Or can OS do it efficiently?
- throwaway81523 5y ago
  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.
- hutzlibu 5y ago
  What is CoW?
  - detaro 5y ago
    copy-on-write
- chmike 5y ago
  I don't see how CoW would work with threads. It doesn't make sense to me.
- foota 5y ago
  That sounds an awful lot like the x86 cache coherency protocol.
- BenFrantzDale 5y ago
  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_write.hpp https://github.com/stlab/libraries/blob/main/stlab/copy_on_w...
jonv 5y ago
> 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).
- logicchains 5y ago
  >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.
  - throwaway81523 5y ago
    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.
YorickPeterse 5y ago
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.

vbezhenar 5y ago

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

throwaway81523 5y ago
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.
hutzlibu 5y ago
What is CoW?
- detaro 5y ago
  copy-on-write
chmike 5y ago
I don't see how CoW would work with threads. It doesn't make sense to me.
foota 5y ago
That sounds an awful lot like the x86 cache coherency protocol.
BenFrantzDale 5y ago
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_write.hpp https://github.com/stlab/libraries/blob/main/stlab/copy_on_w...

jonv 5y ago

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

logicchains 5y ago
>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.
- throwaway81523 5y ago
  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.

YorickPeterse 5y ago

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.