Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
up vote 6 down vote accepted

Homogeneous Plain Old Data

Let's say your event data ranges in size from 16 to 64 bytes depending on the event, but never bigger than 64 bytes, and there's no complex logic to destroy an event (i.e., trivial destructor if it was an object).

In that case, I'd suggest just doing this:

struct EventData
{
    // Cram your event data in here.
    // Can turn this into a buffer class which serializes/deserializes
    // data in binary (be careful to watch for alignment of members:
    // easiest way is max align each field or actually do a bit of
    // dirty casting to/from structs or 'memcpys' -- that allows
    // the compiler to deal with field alignment).
    ALIGN_MAX char data[64];
};

Of course you can make that easier and get more type safety with unions and so forth, same idea -- you can make it as easy and as safe as you like provided that we can use a homogeneous representation for all events this way.

You might even be able to use placement new with aligned storage, though I wouldn't recommend this (it just feels dangerous to use placement new over a memory block that is going to end up being deep copied to another memory block. The underlying memory of an object should be pinned, not moving around).

Wasteful?

I'd suggest this even if the range is quite large, like the smallest event requiring 8 bytes and the largest requiring 256 bytes.

struct EventData
{
    // Cram your event data in here.
    // Actually probably better to just use aligned_storage or alignas 
    // here (I just don't know how since I'm still stuck by portability 
    // issues in C++03 land).
    ALIGN_MAX char data[256];
};

As wasteful as this sounds for, say, an event that only requires 8 bytes of memory, the memory dynamics going on here would typically imply that you can initially allocate this 256 bytes on the stack. The top of the stack is super hot with ultra high temporal locality, and stack allocation/deallocation of 256 bytes of only which you use 8 bytes is dirt cheap (typically just incrementing/decrementing a stack pointer register).

Next, you end up deep copying this memory into your concurrent queue -- still pretty cheap (ex: memcpy), especially if your concurrent queue is array based (ex: circular buffer or something resembling std::deque using contiguous chunks but ideally bigger chunks than deque). In that case, its memory will also be super hot (super high temporal locality with the same memory being overwritten repeatedly with constant pushes followed by pops), with pages that are almost always physically-mapped, memory regions that are almost always going to end up in the CPU cache, etc.

So whenever you are dealing with very transient, smallish data (as in hundreds of bytes or so) that is going to be quickly deallocated soon after it's allocated in a performance-critical context, the first thing I'd recommend looking for is a homogeneous representation that allows you to unify the representation of all such data.

While it sounds wasteful, it's likely to be cheaper in practice than involving additional pointer indirections, heap allocation/deallocation, etc. It's analogous to how C programmers often do stuff like this:

void f(...)
{
    char buf[256]; // we might only need 8 bytes sometimes
    ...
}

This is often faster in practice than using the heap, and why std::string in some recent implementations do something similar by using a fixed-size buffer with std::string for small strings. It's often cheaper to just waste bytes if that avoids additional heap allocations and disjointed memory for short-lived data like this. Yet the above approach is only safe if we can guarantee that there are no edge cases that exceed 256 bytes. The small std::string optimization uses a hybrid approach to avoid heap allocation for small strings and only require it for big ones that exceed the fixed-size capacity.

Non-Homogeneous Data: Straightforward Approach

If there is no way to get a homogeneous representation out of this (no practical upper bound, e.g., or it could potentially span many kilobytes or more, or destroying event data is not trivial for all types of events), then the homogeneous representation across different types of events is out.

In that case, your straightforward solution might be a good bet. There's no easy way to avoid dynamic allocation overhead in this case since no upper bound for the size can be anticipated in advance. We can only mitigate it by optimizing around the problem and using memory pools.

In this kind of context of interthread communication, a naive attempt at a memory pool could easily perform worse than just straight calls to throwing operator new. So it's definitely not easy in this context.

Fixed allocators might be easy to implement here (no worry about alignment in between each contiguous element since the compiler deals with that for us with structure padding, only alignment for the pooled blocks which can just use max alignment while only being trivially wasteful). A separate fixed allocator would be needed for each event type that has a different data size.

However, that introduces the need for locking. Here a featherweight spin lock is actually generally going to be your best bet, since the amount of work required to allocate against a fixed allocator is next to nothing (just pop a pointer from the free pool), like so:

void* allocate()
{
    // Spin lock here
    if (free_element)
    {
        // Common case: pop free chunk from free list.
        void* mem = free_element;
        free_element = free_element->next_element;
        return mem;
    }

    // Rare case, allocate new block and push free pointers.
    ...
}

void deallocate(void* mem)
{
    // Spin lock here
    // Push pointer to free list.
    FreeElement* element = static_cast<FreeElement*>(mem);
    element->next_element = free_element;
    free_element = element;
}

This might have a chance of beating a general-purpose allocator even with the spin lock, though it's something that really needs to be measured carefully against a good profiler with a willingness to back out. I've done these types of things a lot, and I'd say there's a reasonable chance of this providing a benefit with a featherweight CAS spinlock, but slim to none otherwise.

Another strategy is a garbage collection strategy which can potentially allow you to dedicate a separate thread to collecting no-longer referenced garbage with thread-local pools, but that's getting pretty elaborate and the benefits of doing this is a gigantic question mark for me since I've never ventured to this territory personally.

Sorta Homogeneous Data

Let's say you have a scenario where the vast majority of your common-case events have a foreseeable upper bound (like 256 bytes or less), but you have a few rare case killer scenarios which are very rare but can require like many kilobytes (or more) of event data.

In that case, you can do like the small string optimization:

struct EventData
{
    EventData(): ptr(0)
    {
        ptr = data;
    }

    ~EventData()
    {
        if (ptr != data)
            free(ptr);
    }
    // Also add copy ctor, copy assignment.

    // Cram your event data in here unless it doesn't fit...
    ALIGN_MAX char data[256];

    // ... in which case, allocate the size needed dynamically and
    // point to the dynamic memory through this:
    char* ptr;
};

This way, you only need to pay for heap allocation in those rare case scenarios, and since they're rare case scenarios for really big buffers, they don't benefit much from a custom allocator anyway.

Non-Homogeneous Data: Lock/Wait-Free Serialization Approach

This following approach I'm going to suggest isn't exactly lock/wait-free, but your concurrent queue needs a lock no matter what (often a CAS spin loop with condition variables to put consumers to sleep when the queue is empty). The idea of being "lock-free" here interweaves the process of writing data into the concurrent queue itself while it's inside a lock. Put another way, it's lock-free/wait-free in the sense that it's introducing no additional locks into the picture.

In this case, your concurrent queue takes on a binary stream design. Client code to push an event might look like this:

queue.begin_push(event_type); // lock here
queue.push_int(...);
queue.push_float(...);
queue.push_string(...);
queue.end_push();             // unlock here, possibly notify 
                              // with condition variable

... for exception-safety, this should be done through a guard:

{
    // "PushGuard": locks on construction, unlocks on destruction.
    PushGuard pusher(queue, event_type);
    queue.push_int(...);
    queue.push_float(...);
    queue.push_string(...);
}

The idea is to turn your concurrent queue into a binary stream/buffer. The code to pop an event might look like this:

// "PopGuard": locks on construction, pops event type, unlocks on destruction.
PopGuard popper(queue);
switch (popper.event_type())
{
    case some_event:
    {
        some_int = queue.pop_int(...)
        some_float = queue.pop_float(...);
        some_string = queue.pop_string(...);
        // Do stuff with data.
        break;
    }
}

This kind of design might be characteristic of a data-oriented design mindset. The interface design of container and "containee" fuse into a single, inseparable interface design concept. There's some reduction of flexibility/generality in doing this (ex: AbstractImage interface vs. vector<unique_ptr<AbstractPixel>>) but it often leaves the most room to iterate towards optimal solutions while reducing the number of ultra-fine-grained, highly-contended locks and so forth.

Note that this is a dangerous design because of how pushes and pops must be perfectly symmetrical to avoid disaster. You can at least impose runtime debugging safety by storing a sentinel, e.g., when end_push is called which you can at least check for in debug builds to make sure that event-processing clients popped all the relevant data in an event before calling end_pop *.

* Apologies, I realized a goof here. I've often implemented things like this in C without exception-safety in mind. Throwing in the middle of a pop (if that can happen) would be completely unsafe. Best would be to store the total size of the buffer (for all fields pushed) as a header preceding the event data. This way, in the case of an exception or in the case that the consumer ignores the event, end_pop can just pop off the remaining data if there is any for basic exception-safety or actually roll back to the point as though no pop occurred at all for strong exception-safety.

The biggest potential pain of this approach is, again, the need for alignment. An easy way is just max align every individual field you push and pop (ex: using 64-bit alignment even if you just push a 2-byte short with 6 bytes of padding). The waste doesn't matter so much since, again, we're talking about very transient, short-lived data being allocated/deallocated through a data structure that is very hot.

Note that this is getting kind of ugly with C-style code and degrades maintainability, obviously, but that's often the cost for getting more performance. It might be a good trade-off, however, if you actually need it. This serialization approach also ends up being arguably much easier than going all the way to attempting to implement memory pools which are more efficient than malloc or default (throwing, non-placement) operator new in a multithreaded context with the straightforward approach.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
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 at 7:46

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.

share|improve this answer
    
+1 I have to check out this ring buffer solution as an alternative to concurrent queues using CAS loops. It sounds very promising. – Ike Jan 3 at 20:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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