Hacker News Reader

Comment by haberman | Hacker News Reader

I've found that a lot of the tricky edge cases in lock free programming can be reduced to the following case:

Imagine that a thread reads a pointer, then immediately (before it dereferences it) gets scheduled out and frozen for arbitrarily long.

To keep the thread from crashing or performing incorrect logic when it wakes up, to have to make sure this pointer remains valid for arbitrarily long.

You have to accommodate the fact that a thread can get frozen basically forever.

View on HN

I've done quite a bit of lock free programming and getting into this situation should mean that the design isn't going to work in the first place. To start, using pointers to objects is a red flag to me. What you are really working with is data. Indexing that data in an array or lock free map can work.

This is also ignoring the issue that global heap memory allocation locks anyway, so allocating a new object is already taking a lock every time. That is rarely what you would want for performance on a single core, but definitely not what you want for a lock free data structure.

How do you think a lock-free map works?

Pretty much every fundamental lock-free data structure is built around pointers. It's true that a static array can work if you're willing to commit to a fixed size up-front (and pre-allocate that entire fixed size), but that is often too limiting for practical use.

> This is also ignoring the issue that global heap memory allocation locks anyway, so allocating a new object is already taking a lock every time.

Any memory allocator optimized for multi-threaded performance will have a thread-local or CPU-local cache that can allocate without taking a lock.

Not all lock free maps work the same. The ones I've written didn't use pointers.

Even an allocator with a thread local cache will still have to lock to map in more memory. This might be unavoidable all together, but allocating memory from a heap and using the pointer not only is inefficient because of the allocation itself as well as the huge increase in the number of times a system call has to be made, but also due to the fact that access now means you have to jump around in memory to find anything.

Resizing contiguous memory is a separate problem, not a show stopper. Multiple buffers with an atomic switch is one way to confront it. Having all writes go to a new buffer while reads try the new buffer first but try the old buffer second if they can't find anything is one way to ensure that all reads stay lock free.

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.

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

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

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.

So how did they solve it?

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.

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

Reply on news.ycombinator.com