One Synth Challenge #192: Six Sines by BaconPaul (johnkhf Wins!)

[ElVincente]

Awesome! Thanks Baconpaul

[doctorbob]

I just found it and have a fix coming

Well done ...

"Code a linked list" is an interview question I've given a hundred times, but apparently can't pass myself in critical code. Sigh.

I always liked the double linked list myself

[Taron]

... the best of us... no worries!
YAY!

[empphryio]

https://soundcloud.com/anotherjaysherma ... al_sharing
OSC legal Six Sines track. I don't normally post 3 tracks but I'm just liking this one too much to not share. I really like this synth. Maybe this one is pretty weird but damn I love it.

Edit: I was having such a strange euphoric response to this music yesterday. Today the one almost drone note is a lttle bit sibilant/harsh. I may try to soften it or alter it a bit.

2nd edit: All good now.

[baconpaul]

"Code a linked list" is an interview question I've given a hundred times, but apparently can't pass myself in critical code. Sigh.

I always liked the double linked list myself

It is a double linked list! One of the fun things about working 100% in the open like we do in surge-land is that you can't hide embarrassing things though, like, when you add a previously unregistered node to the list and don't remember to check if it is the head of a one element list, so add it to itself and get an infinite cycle. Which made the fix very small (https://github.com/surge-synthesizer/ss ... 8ad08eb34a) but very important!

(That code is how i manage to have 128 midi smoothers runnable for CC, but usually traverse none if no smoothing is active and also not allocate at smoothing time by pre-allocating dormant smoothers)

[doctorbob]

Ho ho. Yup, not doing that initial test to see if it's the head node or not can sure cause list problems! ... "if (!head) then addnode (id)" etc?? I wrote a similar scheme for adding "work nodes" for a graphics system to create custom graphics projected whilst under control of an on stage sax player (using various sensors, gesture recognition etc). The audience was all sitting in a 3D ambisonic cube of speakers, with all audio, player and computer, being moved around the inscribed sphere. Back in 2004!
dB

[] Peter:H []

"Code a linked list" is an interview question I've given a hundred times, but apparently can't pass myself in critical code. Sigh.

I always liked the double linked list myself

It is a double linked list! One of the fun things about working 100% in the open like we do in surge-land is that you can't hide embarrassing things though, like, when you add a previously unregistered node to the list and don't remember to check if it is the head of a one element list, so add it to itself and get an infinite cycle. Which made the fix very small (https://github.com/surge-synthesizer/ss ... 8ad08eb34a) but very important!

(That code is how i manage to have 128 midi smoothers runnable for CC, but usually traverse none if no smoothing is active and also not allocate at smoothing time by pre-allocating dormant smoothers)

okay in 2024/25 we still do lists impls on our own? I would always use libraries for commodity ... I bet the std containers are not coded by complete dorks.
https://en.cppreference.com/w/cpp/conta ... containers afair there's even bidi iterators if that would be needed at all.

[baconpaul]

okay in 2024/25 we still do lists impls on our own? I would always use libraries for commodity ... I bet the std containers are not coded by complete dorks.
https://en.cppreference.com/w/cpp/conta ... containers afair there's even bidi iterators if that would be needed at all.

I'm pretty sure your comment is made in bad faith and you are just a jerk. But for other people reading here, the answer to your question is, if you actually read the code I linked, that we have the following constaints in this class

1. We cannot allocate, since it's the audio thread, so I need to pre-allocate necessary smoothers. Note the allocation api in std::list
2. It is usually the case that no smoother is active
3. When an event comes in we need to quickly determine if a smoother is active

I thought about doing that with std::list but it makes the first hard. std::list insert can allocate space o the list. It also makes the third tricky. Determining if an item is a member of a std::list is an O(n) not an O(1) check so, while in the midi cc case that wouldn't be too bad, in the case of param smoothing it is.

So I need a data structure which is a non-allocating, maintains an active subset of the pre-allocated set, and which iterates across it quickly and allows rapid insert, remove, and detection of whether its inserted. There's no particularly easy way to do that with std::list unless you retain the inserted iterator as a member on your item to check for insertion and then manage it yourself on deletion, which is basically equivalent code to the code I had a bug with. (That is, if lag has a member called `std::list<Lag>::iterator position` or a bool active state perhaps which you remember to set and clear when you add and remove in the same ifs where I set and clear the next/prev, once you have addressed the allocation issue)

If I'm wrong - that you are trying to be constructive and not just a forum troll - and you would like to modify this little bit of code to use std::list that way, I apologize and look forward to your PR improving the codebase! An especially nice result of this would be you contributing a fixed size std lib allocator, which I need elsewhere in the voice manager where I need to solve this problem for some more complex data structures and currently have occasional allocations, alas.

[baconpaul]

Actually maybe I’ll take today and write that allocator and solve my other problem then backport here as an example, assuming you are not actually going to do so. Thanks for prodding me to get that done!

[] Peter:H []

okay in 2024/25 we still do lists impls on our own? I would always use libraries for commodity ... I bet the std containers are not coded by complete dorks.
https://en.cppreference.com/w/cpp/conta ... containers afair there's even bidi iterators if that would be needed at all.

I'm pretty sure your comment is made in bad faith and you are just a jerk. But for other people reading here, the answer to your question is, if you actually read the code I linked, that we have the following constaints in this class

1. We cannot allocate, since it's the audio thread, so I need to pre-allocate necessary smoothers. Note the allocation api in std::list
2. It is usually the case that no smoother is active
3. When an event comes in we need to quickly determine if a smoother is active

I thought about doing that with std::list but it makes the first hard. std::list insert can allocate space o the list. It also makes the third tricky. Determining if an item is a member of a std::list is an O(n) not an O(1) check so, while in the midi cc case that wouldn't be too bad, in the case of param smoothing it is.

So I need a data structure which is a non-allocating, maintains an active subset of the pre-allocated set, and which iterates across it quickly and allows rapid insert, remove, and detection of whether its inserted. There's no particularly easy way to do that with std::list unless you retain the inserted iterator as a member on your item to check for insertion and then manage it yourself on deletion, which is basically equivalent code to the code I had a bug with. (That is, if lag has a member called `std::list<Lag>::iterator position` which you remember to set and clear when you add and remove in the same ifs where I set and clear the next/prev, once you have addressed the allocation issue)

If I'm wrong - that you are trying to be constructive and not just a forum troll - and you would like to modify this little bit of code to use std::list that way, I apologize and look forward to your PR improving the codebase! An especially nice result of this would be you contributing a fixed size std lib allocator, which I need elsewhere in the voice manager where I need to solve this problem for some more complex data structures and currently have occasional allocations, alas.

Okay, you put that out and expect more contructive input? Even after telling everybody you did the impl wrong on a basic invariant check on a list impl ... that is way to funny for a single day.
Yeah the real funny thing is that std is just an example of pro optimized stuff, like another one is boost. Though I be Dev for over 20 years would never come close to any of the modern data structure impls the real wizards - not the feel once - implement. things like striving for look-free impls requires lots of wizardy optimization, that the bread and butter dev has no time for. Lock-free is for instance sth I would look for if I'd go CLAP threadpool. That's why I'd never do commodity "basic" DS on my own. The pros have always been and allways will be better, even if I have one of these days I feel very clever. And if you only read std:list really carefully it gives you a lot of gurantees like constant insert O and stuff. you might have missed that. It might have even advanced after you last read through it. But hey, what do know. I now know you know it better.
https://www.boost.org/doc/libs/1_69_0/d ... mance.html

[baconpaul]

No I expected no constructive input from you, Peter. The problem is entirely allocation. The STL doesn't meet realtime constraints with the standard allocators. You must know that if you write realtime systems right?

[Taron]

How I dearly hate to squeeze into that conversation... ...but I can't help myself from wondering how healthy linked lists are for performance like in an audio plug-in, considering that any change to them (beyond some given threshold), as far as I remember, makes them (re)allocate memory to do all the needed back and forth copying. We just don't see that happening or feel like it's all taken care of, but it scares me deeply.
Now I have done something likely insane with Lord of the Springs, but it was a vastly different concept, allowing me to do that with no worries, simply having allocated all necessary memory for what it needed, never to look back, so to say. As a result I had a fixed array where simply the content could get swapped out and no further re-allocations or the likes were necessary during the runtime, I suppose. But I honestly don't remember everything anymore. It's been many years ago.

Now I'm trying to remember, and I think I always made one pass through the array, looking for still active notes to assemble an index list for them, which then would go into the actual processing.

Anyway, just something that crossed my mind.

[baconpaul]

How I dearly hate to squeeze into that conversation... ...but I can't help myself from wondering how healthy linked lists are for performance like in an audio plug-in, considering that any change to them, as far as I remember, makes them allocate memory to do all the needed back and forth copying. We just don't see that happening or feel like it's all taken care of, but it scares me deeply.

Anyway, just something that crossed my mind.

So that's exactly what I'm saying Taron. If you read the code in question it pre-allocates the set of data in a std::array and then uses pointers in a list-style to manage the active sub-set. If you use `std::list` it will allocate and deallocate nodes when inserting and removing so not realtime safe. I was hoping Peter would have a solution to that but ... well you see the above. The solution is to write a matching-fixed-size STL allocator.

A list *where it makes nodes as you insert* definitely is allocating. that's what std::list does and that''s not the data structure I need here. What i need is a list tracking the active subset of a pre-allocated array.

I think I've actually typed more about this class on this forum now than the characters in the class. LOL

With `std::list` writing the allocator is way more code than just managing the pointers (even though I should have written a test and I got it wrong! I kinda wish I had never jokingly apologized for the bug so clearly). With other data structures the structure is more work than the allocator, which is why having a custom allocator is useful. I'm actually writing it now and need it in a few other places - especially the voice manager which uses unordered maps in a couple of places which I know is allocating

[Taron]

AHAHAHAHA! Yeah, that's because you're an amazingly sweet guy, Paul!
Yeah, sounds pretty much like what I'd have done, too. And I'd like to even add: Of Course!

Still would like to figure out what could still hang...there's still something left that causes trouble.
Anyway, you're doing a mighty fine job, never doubt that! And I'm on the edge of my seat for every step forward.

[baconpaul]

Yeah if you have something still hanging up let me know. Github probably better than here.

The critique of my list-set-overlya is I could have written it as a template base class at least. Perhaps I'll do that. Because writing the STL allocator is really a pain (as i'm remembering this morning by trying to fix the voice manager allocation pattern!)