Hey all,

I am integrating a Pd patch with an existing sequencer/looper (Seq192) with an OSC interface, where my patch should convert my MIDI controller's button presses to OSC commands and send back MIDI signal out to lighten the controller's LEDs.
I can retrieve periodically the status and details of all clips/sequences and aggregate it into a list of parameters for each sequence. The LED colors and the actions that the next button press will trigger depend on these parameters, so I need to store them for reuse, which I like doing with [text] objects. I am then handling buttons' light status in a [clone 90] (where each instance of the clone handles one button).

This should be running on a fairly low-end laptop, so I'm wondering which of these approaches is the most CPU-efficient - if there is any significant difference at all - and I couldn't come up with a way to properly measure the performance difference:

1. one [text define $1-seq-status] object in each clone, with one single line in each. I compare the new sequence status input with [text get $1-seq-status 0] so that I update only line 0 with [text set $1-seq-status] when I know that the content has changed.
2. one single [text define all-seq-status] object with 91 lines. I compare the new sequence status with

[ <button number> (
|
[text search all-seq-status 0]
|
[sel -1]
       |
       [text get all-seq-status]

and if it has changed, I update a button's line with

[ <new status content> (
|
|      [ <line number> (
|      |
[text set all-seq-status]

The order in which buttons/sequence statuses are listed in the file might change, so I can't really avoid searching at least once per button to update.

3. Should I instead uses simple lists in each clone instance? As far as I could test, getting a value from a list was a bit slower than getting a value from a text, but searching in a text was much slower than both. But I don't know the impact of processing 91 lists or text at the same time...

TL;DR: Is it more efficient to [text search], [text get] and [text set] 91 times in one [text] object, or to [text get] and [text set] 1 time in each of 91 [text] objects? or in 91 [list] objects?

Since you've gone through this long post and I gave a lot of context, I am of course very open to suggestions to do this in a completely different way :D
Thanks!

@zigmhount Unless I was planning on running it on something with a single core I would use [text] since it makes it easier to separate the control stuff from the audio which allows you to stick all the control stuff in its own patch running in a separate instance of pd that does not need DSP enabled and communicate with the audio stuff running in another instance of pd through [netsend]/[netreceive]. I have made it habit to structure my patches with everything audio segregated out into an abstraction, if I start hitting the wall and getting dropouts I just replace the abstraction with a [netsend] and start up another instance of pd, takes about 5 seconds and problem solved.

Hi @oid, thanks for the suggestion (I usually do split audio and control in different patches) but I forgot to mention that I am not processing any audio at all in this patch
And, also, that this patch is only used to interface my MIDI controller with OSC, so real-time performance is actually not really a big deal. So maybe the performance difference between my option will not be noticeable at all.

For reference, the machine I'm running this on has 2 cores at 2GHz, but I'm also running a DAW in parallel to Pd. My previous project was a complete MIDI sequencer, with 24 ticks per beat and relatively fancy UI (moving canvas for sequences progression bars etc.) which lead to relatively heavy load (and low performance), which is why I looked into the [text] topic that I'm asking about here. But I guess that the performance was impacted much more by the continuous UI updates than by the text search

imo the best way would be to use an [array] for the button in each [clone].
If you were to use [text] there are several tradeoffs: if you want to be memory-efficient then using a single [text] might be better. (but at the cost of using more cpu possibly)
(of course using more memory can also cause performance issues in the extreme bc of cache misses etc.. it's complicated..)

The order in which buttons/sequence statuses are listed in the file might change, so I can't really avoid searching at least once per button to update.

why would the order change? why couldn't you just write each button's info to the corresponding line number?

@zigmhount I think in that setup I would not worry much about pd, its load will be tiny compared to a DAW (or most OSes) and that is where I would look for ways to knock CPU use down. Ecasound is a command line DAW which can be completely controlled from pd through various ways (going from memory [command]/[ggee/shell], OSC, UDP), uses much less CPU than the alternatives in my experience and combined with a minimal Slackware system kept me happily running on an old 4-core 1.8gig machine up until about 6 months ago when I decided to get a new computer on a whim.

One thing that can help (depending on your OS?) is isolate a core and run the DAW on that core, can keep the random dropouts from happening but it means everything you do in the DAW has to be doable with a single core. Works better when you have 4 or more cores since you can isolate a core (or two or more) for the none realtime stuff and let the system manage the other cores for the realtime stuff.

actually the most efficient might be a giant array that stores everything. if you're receiving the data per-button then also order the array per-button and calculate the index with (button_number*sequence_size) + sequence_index
(this is essentially a 2-dimensional array)

but I feel like I need a clearer picture of the architecture maybe. (what exactly are the parameters of? how long is a sequence? how often is this being triggered/queried?)

@zigmhount said:

TL;DR: Is it more efficient to [text search], [text get] and [text set] 91 times in one [text] object, or to [text get] and [text set] 1 time in each of 91 [text] objects? or in 91 [list] objects?

Going back to the original question...

In the source code, the function that locates a line by number is text_nthline(). This implements a linear search from the beginning of the text buffer, counting character by character, until it's crossed n newlines (semicolons or commas).

So performance will depend on how many lines, and how long the lines are.

Accessing lines near the end will be slower than accessing lines near the beginning.

For a linear search, you would predict that the time is proportional to the size. I built a benchmark where the lines are all roughly the same size, comparing 10 lines vs 100, 1000 and 10000, doing a million random accesses for each one.

23-0826-text-performance.pd

The smaller buffers are a bit slower than "linear" would predict, but this is probably because of function call overhead and can't be avoided. (x1000 vs x10000 is linear.)

Still, if you're wondering how a single text buffer of ~100 lines would do... 100 ms for 1,000,000 queries is pretty fast. So... don't worry about it...?

Or you could run this yourself on the lower-end laptop that you mentioned. (But... before you do... go into the [pd 1000000_queries] subpatch and change the 1e+06 message box to, say, 10000 or 100000. Otherwise you might be sitting there a while. And be sure to init the buffers first, should be clear where to click.)

I didn't benchmark the performance of accessing multiple separate text objects. Based on the source code, if you access line 0, then text_nthlne() will scan only the one line (to determine the endpoint). I don't know what is the overhead of switching a [text get] between buffers.

Honestly I think the Pd GUI stuff will be a heavier drain on CPU than either [text] approach.

hjh

Also... That 120 ms to populate 11,110 rows seems like a lot. Every "text set" does nthline again... so one row's insertion is O(n), and filling a text with n rows would be O(n^2), which is one of those computer science performance red flags. (If you need high performance, avoid O(n^2) algorithms!)

By contrast, if, in SuperCollider, I made 4 arrays of strings with 10 items, 100, 1000 and 10000 respectively, I'd expect it to go at least an order of magnitude faster, maybe two orders, because array indexing in SC is O(1) (so the entire fill would be O(n) provided that you allocate all the array slots in advance -- since the number is known, that's easy).

[text] just isn't written for maximum performance. Query speed seems acceptable but with a better optimized data structure, it could be even faster. It's why, when I made a scheduler for pd, I had the heap operate on numbers only in an array (fast) and access the text only when needed.

hjh

Thanks for your replies!
My conclusion is indeed that I don't really need to worry about efficiency in this specific case

@seb-harmonik.ar said:

imo the best way would be to use an [array] for the button in each [clone].

Oh interesting, I'll keep that in mind for the next time where I'll have to worry about Pd's performance. I'd have to see if I can handle it all with only numbers (while [text] leaves the possibility to also store and query symbols)..

why would the order change? why couldn't you just write each button's info to the corresponding line number?

The mapping between buttons and sequences may change, e.g. if I shift the buttons to cover the sequences in columns 2 to 9 rather than 1 to 8.

@oid Ecasound is a good suggestion, I looked into it a couple of years ago when I wanted to make music on a 700Mhz single-core Celeron. For the current project I need a graphical LV2 plugin host where I can easily map controller knobs to plugin parameters, side-chain audio outputs and easily insert new busses with synths or soundfonts, i.e. basically the mixer part of a DAW (I'm on Ardour for now, Qtractor could work also) without its timeline, or Non-Mixer if it supported LV2 plugins with their UI. I might consider something modular eventually (e.g. with Carla).

isolate a core and run the DAW on that core, can keep the random dropouts from happening

Also a good idea, I may give it a try. Although so far I've noticed dropouts when enabling synths in Ardour, Pd's calculations are probably negligible in comparison.

@ddw_music Thanks for the benchmark and the explanations, very interesting. Sticking to numbers in arrays rather than text is definitely something to keep in mind for future projects on smaller machines.

@zigmhount said:

Also a good idea, I may give it a try. Although so far I've noticed dropouts when enabling synths in Ardour,

Isolating Ardour might work, depends on how reliant it is on that second core. You could try jalv which loads plugins as standalone jack clients, probably as low as it will get for resource usage if you want UI.

@ddw_music said:

By contrast, if, in SuperCollider, I made 4 arrays of strings with 10 items, 100, 1000 and 10000 respectively, I'd expect it to go at least an order of magnitude faster, maybe two orders, because array indexing in SC is O(1) (so the entire fill would be O(n) provided that you allocate all the array slots in advance -- since the number is known, that's easy).

That turned out to be wrong:

(
var letterA = $a.ascii;

f = { |n| Array.fill(n, { String.fill(50, { (26.rand + letterA).asAscii }) }) };

bench {
    a = [f.(10), f.(100), f.(1000), f.(10000)];
};
)

time to run: 0.06757064 seconds. ~= 0.07

About half. So a lot of the time is spent just generating the strings, I guess, in both environments.

Repeating the array-read benchmark in SC, though... this is what O(1) array lookup looks like:

(
a.do { |array|
    var n = array.size;
    (n.asString ++ " elements: ").post;
    bench {
        1000000.do { array[n.rand] }
    }
}
)

   10 elements: time to run: 0.038383661000012 seconds.
  100 elements: time to run: 0.035132123000039 seconds.
 1000 elements: time to run: 0.033579056999997 seconds.
10000 elements: time to run: 0.034433505999914 seconds.

... no performance degradation for higher sizes.

hjh

@ddw_music (slightly OT) Supercollider might not 'know' enough to pre-allocate the array of strings. Idk what supercollider does but usually in programming languages that don't have explicit memory allocation strings/symbols are stored in some string pool/table. They're hashed and whenever a new string is made it's looked up in the pool to see if it needs to be allocated or if the same one already exists and can be reused.
This is actually good for performance in a lot of cases bc it prevents memory from being wasted when the same strings are used. Plus, the pointers of the strings can be compared instead of comparing every character.
But it can also be bad for performance in others (such as comments, or where the strings will only be used in 1 place)

(that's what pd's gensym function does)
I'm guessing supercollider does something similar, so when it creates all of those strings it actually has to allocate each of them on the heap separately rather than allocating the array with the space for each already included. (plus it would have to know the max size of a string to do that too which would also waste memory in a lot of cases where the data stored was smaller than that)

@seb-harmonik.ar You reminded me of a question I have wondered about but never quite could figure out from the source, all those pointers still confuse me. [text] and [list] allocate memory once their size exceeds 100, do they deallocate when they shrink? If my [list] has 200 items and I delete an item from it does it resize or stay at 200? Can I create a [text] or [list], dump 200 zeros into it and maintain the speed they have for under 100 while also getting the benefits their respective family of objects offers and [array] lacks? It seems sensible they would shrink as well since they could end up eating massive amounts of memory but [text] and [list] are not really designed to deal with large amounts of data like [array] but I don't really know.

Edit; I mean [list store] and not [list] since you can not delete from [list], just make another copy minus what ever which would mean reallocation. So no need to explain that unless I missed something here?

@oid the stored list is freed every time a new one is supposed to be stored (or the object is deleted/freed). The 100 element lists are only used on the stack (non-stored lists). When lists are stored they are always stored on the heap.

e.g.

    /* set contents to a list */
static void alist_list(t_alist *x, t_symbol *s, int argc, t_atom *argv)
{
    alist_clear(x); // <-- clears stored list on the heap

the lists stored on the stack are only used when sending a temporary list to an outlet (like triggering [list append] from its left inlet)

now that I'm looking at it again I'm not sure why getting elements from lists should be slow if using [list store], if you know their indices. bc lists are actually contiguous memory (not linked lists).

edit: when lists are cleared or elements are deleted the memory is freed at that moment

edit2: [array] will probably be more efficient in the majority of compatible cases because memory is only allocated once when it's created, and deallocated once when it's deleted. (at least when there's a reasonable maximum size and it doesn't have to be resized)

@seb-harmonik.ar So will the conclusion be (especially for the OP).....?
An Array (or within [clone] many small arrays) for indexed data storage.
[text get] by index (direct access to one line) for translation to symbols.
David.

@whale-av still not solid on how the data is coming in or accessed in this particular case. From what I can tell yes though I would think per-clone [list store] would be at least similar if not faster. but haven't done any profiling or anything to back that up..
There are a lot of factors w/ all the routing, clones etc that add complexity..
sorry for the slightly OT tangents

@seb-harmonik.ar said:

I'm guessing supercollider does something similar, so when it creates all of those strings it actually has to allocate each of them on the heap separately rather than allocating the array with the space for each already included.

It's a good point, however in SC this is true of the Symbol class. My benchmark is using Strings, which are arrays of characters and not retained in a hash table. (But the hashing overhead might explain why SC built the collections faster.)

(plus it would have to know the max size of a string to do that too which would also waste memory in a lot of cases where the data stored was smaller than that)

For SC Symbols, I'm not sure. For String.fill, the size is given and it can allocate exactly that amount.

hjh

I tried to make a 'microbenchmark' for an equivalent list and text: looks like list is a bit faster, even with a vanilla "get" message (it can be sped up more by using [iem_prepend get] from iemlib.)
at larger sizes it looks like it becomes more pronounced
text-list.pd

my intuition would be that multi-line [text] is probably also not as good as [list] because it has to go through every atom every time a lookup happens. Especially if you have to search as well. (but again it's complex, there are extra messages to route to the clones, maybe memory isn't as contiguous leading to cache misses etc)