std::list in the audio thread - bad idea?

DSP, Plugin and Host development discussion.
Post Reply New Topic
RELATED
PRODUCTS

Post

is using std::list for managing polyphony in the high priority thread a bad idea? i.e. for keeping track of held keys and sustaining notes.

Post

If you're not inserting / removing, depending on circumstances, you should be fine.

Post

i use push_back() , remove(), clear(), and erase() relatively infrequently

Post

Expect allocations then.

(edit: alternative I see, sorted std::vector with reserve(), priority queue over binary heap).

Post

The boost library has intrusive containers, which do not require allocations upon insert/remove.

Post

I think in any code where you care about performance, std::list (or any linked list for that matter) is not a good choice. I assume you're constantly traversing the list, which leads to chasing pointers, leading to cache misses every time.

Post

Of course it's not a bad idea. Just learn to use STL algorithms and iterators (anything under #include <algorithm>) with lambdas so you aren't stuck with moronic for-loops.

Although based on your description alone I wouldn't immediately choose a container. More information is needed.

For example unordered_map or depending on your sorting needs maybe even plain map (an associative container in general) might work better. With unordered_map you are guaranteed constant-time access. If you aren't constantly adding new keys, or pre-allocate some known set of keys it might better represent a keyboard and its workload. In pseudocode std::unordered_map<keynumber, keyinfo>.

Post

ponce wrote:Expect allocations then.
Really, we're worried with allocations on a set of 128 (tiny struct consisting several ints) entities? From what year are you posting? Do you guys have Spectrums yet?

Post

If the allocation is only done once, it's not really a problem
If it allocates those 128 at each render callback then you will have threading issue as allocator on the audio thread may wait on allocation on the UI thread.

We are posting from a year where no OS allocator are lock free. Too bad this year is 2014.
Olivier Tristan
Developer - UVI Team
http://www.uvi.net

Post

What's the plus side of using std::list? What does it offer over more efficient implementations? I would personally store held keys in an array. There are only 128 notes.

Post

Insertion in ln(n), so no need to move data if you have to reorder. Otherwise, you have to move at most 127 elements in the vector.

Post

thanks for the info everyone. std::list was indeed overkill for this purpose. I've switched to std::vector, calling reserve(128) in my constructor, to avoid unwanted allocations.

Post

Regarding lamba expressions: those are just syntactic sugar. You have no control over its (in)efficiency. Which is a bad idea in the most inner loop...
We are the KVR collective. Resistance is futile. You will be assimilated. Image
My MusicCalc is served over https!!

Post

Kingston wrote:
ponce wrote:Expect allocations then.
Really, we're worried with allocations on a set of 128 (tiny struct consisting several ints) entities? From what year are you posting? Do you guys have Spectrums yet?
thanks for the info everyone. std::list was indeed overkill for this purpose. I've switched to std::vector, calling reserve(128) in my constructor, to avoid unwanted allocations.

Post

BertKoor wrote:Regarding lamba expressions: those are just syntactic sugar. You have no control over its (in)efficiency. Which is a bad idea in the most inner loop...
Not true at all, also profiled as easily as any other loops or functors. I recommend Scott Meyers' latest (Efficient Modern C++) and some further brushing up on how lambda closures are expanded to functors. I basically shouted in joy when I realised I would no longer have to write anonymous nested for-loops for menial tasks consisting mostly boiler plate. When I say "anonymous" I mean a month later you will have no clue what the inner loops are doing anymore.

(before c++11 you could achieve the same with <algorithm> and functors, but good luck writing let alone maintaining those)

Post Reply

Return to “DSP and Plugin Development”