9

Suppose there are two threads, which communicate by asynchronously sending data messages to each other. Each thread has some kind of message queue.

My question is very low level: What can be expected to be the most efficient way to manage the memory? I can think of several solutions:

  1. Sender creates the object via new. Receiver calls delete.
  2. Memory pooling (to transfer the memory back to the sender)
  3. Garbage collection (e.g., Boehm GC)
  4. (if the objects are small enough) copy by value to avoid heap allocation completely

1) is the most obvious solution, so I'll use it for a prototype. Chances are that it is already good enough. But independent of my specific problem, I wonder which technique is most promising if you are optimizing for performance.

I would expect pooling to be theoretically the best, especially because you can use extra knowledge about the flow of information between the threads. However, I fear that it is also the most difficult to get right. Lots of tuning... :-(

Garbage collection should be quite easy to add afterwards (after solution 1), and I would expect it to perform very well. So, I guess that it is the most practical solution if 1) turns out to be too inefficient.

If the objects are small and simple, copy by value might be the fastest. However, I fear that it forces unnecessary limitations on the implementation of the supported messages, so I want to avoid it.

9

If the objects are small and simple, copy by value might be the fastest. However, I fear that it forces unnecessary limitations on the implementation of the supported messages, so I want to avoid it.

If you can anticipate an upper bound char buf[256], e.g. A practical alternative if you cannot which only invokes heap allocations in the rare cases:

struct Message
{
    // Stores the message data.
    char buf[256];

    // Points to 'buf' if it fits, heap otherwise.
    char* data;
};
3

It is going to depend on how you implement the queues.

If you go with an array (round robin style) you need to set an upper bound on size for solution 4. If you go with a linked queue, you need allocated objects.

Then, resource pooling can be done easily when you just replace the new and delete with AllocMessage<T> and freeMessage<T>. My suggestion would be to limit the amount of potential sizes T can have and round up when allocating concrete messages.

Straight up garbage collection can work but that might cause long pauses when it needs to collect a large part, and will (I think) perform a bit worse than new/delete.

3

If its in C++, just use one of the smart pointers - unique_ptr would work well for you, as it won't delete the underlying object until no-one has a handle on it. You pass the ptr object to the receiver by value and never need to worry about which thread should delete it (in cases where the receiver doesn't receive the object).

You'd still need to handle locking between the threads but performance will be good as no memory gets copied (only the ptr object itself, which is tiny).

Allocating memory on the heap isn't the fastest thing ever, so pooling is used to make this much faster. You just grab the next block from a pre-sized heap in a pool, so just use an existing library for this.

  • 2
    Locking is usually a much bigger problem than memory copying. Just saying. – tdammers Dec 30 '12 at 15:26
  • When you write unique_ptr, I guess you mean shared_ptr. But while there is no doubt that using a smart pointer is good for resource management, it doesn't change the fact that you're using some form of memory allocation and deallocation. I think this question is more low-level. – 5gon12eder Jan 2 '16 at 7:46
3

The biggest performance hit when communicating an object from one thread to another is the overhead of grabbing a lock. This is on the order of several microseconds, which is significantly more than the average time a pair of new/delete takes (on the order of a hundred nanoseconds). Sane new implementations try to avoid locking at nearly all costs to avoid their performance hit.

That said, you want to ensure that you don't need to grab locks when communicating the objects from one thread to another. I know two general methods to achieve this. Both work only unidirectionally between one sender and one receiver:

  1. Use a ring buffer. Both processes control one pointer into this buffer, one is the read pointer, the other is the write pointer.

    • The sender first checks if there is room to add an element by comparing the pointers, then adds the element, then increments the write pointer.

    • The receiver checks if there is an element to read by comparing the pointers, then reads the element, then increments the read pointer.

    The pointers need to be atomical as they are shared between the threads. However, each pointer is only modified by one thread, the other needs only read access to the pointer. The elements in the buffer may be pointers themselves, which allows you to easily size your ring buffer to a size that won't make the sender block.

  2. Use a linked list that always contains at least one element. The receiver has a pointer to the first element, the sender has a pointer to the last element. These pointer are not shared.

    • The sender creates a new node for the linked list, setting its next pointer to nullptr. Then it updates the next pointer of the last element to point to the new element. Finally, it stores the new element in its own pointer.

    • The receiver watches the next pointer of the first element to see if there is new data available. If so, it deletes the old first element, advances its own pointer to point to the current element and starts processing it.

    In this setup, the next pointers need to be atomic, and the sender must be sure not to dereference the second last element after it has set its next pointer. The advantage is, of course, that the sender never has to block.

Both approaches are much faster than any lock-based approach, but they require careful implementation to get right. And, of course, they require native hardware atomicity of pointer writes/loads; if your atomic<> implementation uses a lock internally, you are pretty much doomed.

Likewise, if you have several readers and/or writers, you are pretty much doomed: You may try to come up with a lock-less scheme, but it will be tricky to implement at best. These situations are much easier to handle with a lock. However, once you grab a lock, you can stop worrying about new/delete performance.

  • +1 I have to check out this ring buffer solution as an alternative to concurrent queues using CAS loops. It sounds very promising. – user204677 Jan 3 '16 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.