4 ms·

Why would you ever free an object if something else might be pointing at it?

by smegel 9y ago

cfallin 9y ago
The tricky bit isn't making sure you don't free pointed-to objects; the tricky bit is knowing which objects can be pointed-to. A consequence of GP's point is that because there can be an arbitrary delay between reading a pointer and dereferencing it, any pointer ever exposed to other threads must be considered in-use indefinitely (the reader could sleep indefinitely then wake up and deref) unless one can prove that the pointer is no longer held by any potential readers. There are a few common ways to do that. Hazard pointers are one: every thread updates some per-thread pointer indicating what object it is reading, and other threads check this (for every live thread) before freeing an object. GC also solves the problem because any multithreaded GC must somehow examine live roots in every thread -- so it will see the still-live reference in the sleeping reader. The main point, though, is that it's harder than the lock-synchronized case because one no longer has the guarantee that a reader will hold the lock as long as it's examining the pointed-to object.
xenadu02 9y ago
>Why would you ever free an object if something else might be pointing at it? Hi, welcome to programming /s This is the crux of the entire issue for high-performance multi-threaded programs: how to tell when memory can safely be freed without introducing expensive synchronization? The simple solutions are obvious: 1. Don't share memory 2. Use a lock The real tricks are in forms of reference counting or garbage collection that avoid taking locks as much as possible. For really high performance you also need to avoid atomic operations and fences as much as possible. A "pause the world" garbage collector is easy (relatively) to get right and you can be confident it will work. Doing a concurrent pauseless GC is another matter entirely. Inserting a memory fence on every write is not great for performance. For both GC and reference counting schemes weak references are an additional wrinkle. Swift's original weak reference scheme solved this by inverting control and maintaining parallel reference counts: when the last strong reference is released it ran deinit and set a flag in the object header but otherwise left the memory allocated. Only once every weak reference was touched (or itself deallocated) was the memory actually freed. That's trading greater high-water memory usage for performance. (I don't know off-hand why the implementation was changed though).
- smegel 9y ago
  > 1. Don't share memory 2. Use a lock 3. Have a concept of ownership and make sure all your code follows some basic rules? E.g. if a consumer reads a pointer from a look free queue, it is then responsible for freeing that memory. OP seems to be saying let some other thread free it on some racy assumption that the consumer will be done with it within N nanoseconds. That's not how I would code it.
  - haberman 9y ago
    The problem is inside the lock-free queue. How do you remove something from a lock-free queue? Usually by reading a pointer to the queue node, then doing a CAS to remove the node from the queue. But another thread can remove that same node and free it before you can do the CAS! If you're just using a lock-free queue, then the hardest part of the problem has been solved for you already. But the person who wrote the lock-free queue had to think about and solve these really tricky problems.
    - smegel 9y ago
      So how did they solve it?
      - haberman 9y ago
        There are a number of techniques for solving this: 1. use a GC'd language 2. hazard pointers 3. epoch-based GC 4. collect nodes when a user destroys the structure (user is required to guarantee that destruction is single-threaded). There are probably others.
InclinedPlane 9y ago
OK, sure. But now you have a system that has only a monotonically increasing memory footprint. In other words, it's leaking memory. This is undesirable because memory is finite. This is the core issue behind a lot of the differences between competing programming languages. Languages like C and C++ allow you to manage memory on your own. If you can guarantee through your own program constraints that some piece of memory won't be referenced, then go ahead and free it if you need to. Other programming languages like Java, C#, Python, Javascript, etc. use a managed memory design. A runtime keeps track of memory usage and does "garbage collection" of memory that it can prove is not still in use. The overhead of the runtime and especially of garbage collection is a big sticking point in performance comparisons between such languages and C/C++. Other languages use still other techniques. Rust, for examples, uses a "borrow checker".

Why would you ever free an object if something else might be pointing at it?

by smegel 9y ago

Why would you ever free an object if something else might be pointing at it?

The tricky bit isn't making sure you don't free pointed-to objects; the tricky bit is knowing which objects can be pointed-to. A consequence of GP's point is that because there can be an arbitrary delay between reading a pointer and dereferencing it, any pointer ever exposed to other threads must be considered in-use indefinitely (the reader could sleep indefinitely then wake up and deref) unless one can prove that the pointer is no longer held by any potential readers. There are a few common ways to do that. Hazard pointers are one: every thread updates some per-thread pointer indicating what object it is reading, and other threads check this (for every live thread) before freeing an object. GC also solves the problem because any multithreaded GC must somehow examine live roots in every thread -- so it will see the still-live reference in the sleeping reader. The main point, though, is that it's harder than the lock-synchronized case because one no longer has the guarantee that a reader will hold the lock as long as it's examining the pointed-to object.

xenadu02 9y ago

>Why would you ever free an object if something else might be pointing at it? Hi, welcome to programming /s This is the crux of the entire issue for high-performance multi-threaded programs: how to tell when memory can safely be freed without introducing expensive synchronization? The simple solutions are obvious: 1. Don't share memory 2. Use a lock The real tricks are in forms of reference counting or garbage collection that avoid taking locks as much as possible. For really high performance you also need to avoid atomic operations and fences as much as possible. A "pause the world" garbage collector is easy (relatively) to get right and you can be confident it will work. Doing a concurrent pauseless GC is another matter entirely. Inserting a memory fence on every write is not great for performance. For both GC and reference counting schemes weak references are an additional wrinkle. Swift's original weak reference scheme solved this by inverting control and maintaining parallel reference counts: when the last strong reference is released it ran deinit and set a flag in the object header but otherwise left the memory allocated. Only once every weak reference was touched (or itself deallocated) was the memory actually freed. That's trading greater high-water memory usage for performance. (I don't know off-hand why the implementation was changed though).

smegel 9y ago
> 1. Don't share memory 2. Use a lock 3. Have a concept of ownership and make sure all your code follows some basic rules? E.g. if a consumer reads a pointer from a look free queue, it is then responsible for freeing that memory. OP seems to be saying let some other thread free it on some racy assumption that the consumer will be done with it within N nanoseconds. That's not how I would code it.
- haberman 9y ago
  The problem is inside the lock-free queue. How do you remove something from a lock-free queue? Usually by reading a pointer to the queue node, then doing a CAS to remove the node from the queue. But another thread can remove that same node and free it before you can do the CAS! If you're just using a lock-free queue, then the hardest part of the problem has been solved for you already. But the person who wrote the lock-free queue had to think about and solve these really tricky problems.
  - smegel 9y ago
    So how did they solve it?
    - haberman 9y ago
      There are a number of techniques for solving this: 1. use a GC'd language 2. hazard pointers 3. epoch-based GC 4. collect nodes when a user destroys the structure (user is required to guarantee that destruction is single-threaded). There are probably others.

InclinedPlane 9y ago

OK, sure. But now you have a system that has only a monotonically increasing memory footprint. In other words, it's leaking memory. This is undesirable because memory is finite. This is the core issue behind a lot of the differences between competing programming languages. Languages like C and C++ allow you to manage memory on your own. If you can guarantee through your own program constraints that some piece of memory won't be referenced, then go ahead and free it if you need to. Other programming languages like Java, C#, Python, Javascript, etc. use a managed memory design. A runtime keeps track of memory usage and does "garbage collection" of memory that it can prove is not still in use. The overhead of the runtime and especially of garbage collection is a big sticking point in performance comparisons between such languages and C/C++. Other languages use still other techniques. Rust, for examples, uses a "borrow checker".