Ruz Kut

I've managed to translate the ascending insert-sort algorithm into GenExpr, but there are issues to be solved.

Mainly, it seems like it always miss some values, resulting in a semi-sorted buffer... ?

Do you think is a problem related to signed floating values ?

Is there a way to create an integer variable (not a constant) in GenExpr so the for-loops are more precise ?

I've also tried with [data] before with the same code, but It always gives me weird errors (gen~ kernel, unable to compile, etc...)

btw I'm doing this in order to modify the gen-chopper-repeat patch so that I can play grains by reading an index sorted by RMS values, so of course the more precise is the sorting the better. (the concept is that of grain-tagging, something like CataRT by IRCAM).

Hi all !
I'm no expert in code whatsoever
BUT
I've managed to translate the ascending insert-sort algorithm into GenExpr, but there are issues to be solved.
Mainly, it seems like it always miss some values, resulting in a semi-sorted buffer... ?

Do you think is a problem related to signed floating values ?
Is there a way to create an integer variable (not a constant) in GenExpr so the for-loops are more precise ?
I've also tried with [data] before with the same code, but It always gives me weird errors (gen~ kernel, unable to compile, etc...)

btw I'm doing this in order to modify the gen-chopper-repeat patch so that I can play grains by reading an index sorted by RMS values, so of course the more precise is the sorting the better. (the concept is that of grain-tagging, something like CataRT by IRCAM).


insert-sort-of-a-buffer-in-gen-codebox

Forgot to link my reference for insert-sorting

http://mathbits.com/MathBits/CompSci/Arrays/Insertion.htm

Forgot to link my reference for insert-sorting
http://mathbits.com/MathBits/CompSci/Arrays/Insertion.htm

If only someone fluent with codebox could give my patch a look I'd appreciate it :)

I noticed one thing though, if you try and work with longer buffers the sorting contains less samples than the input.

Yes -- the Max console hints at why: "gen~: audio processing exception: Too many iterations (runaway loop?)"

For safety, gen~ forces a limit on how many loop iterations can happen on each vector -- this limit is currently defined as 100000 * vector size. The reason for doing this is that too many iterations can cause an audio dropout, and infinite iterations will lock up the entire audio thread (possibly crashing it). Per Turing, there's no way to know in advance if a given piece of code will loop forever, so we work around this by having the loop iteration limit and bailing out of audio processing when this limit is reached -- and printing the warning to the Max console.

Although the buffer size in your patcher is 44100 samples long, and thus less than the loop limit, the insert-sort algorithm can cause millions of iterations due to the nested loop. This really is too many to process within one signal vector, and would cause audio dropouts.

To process millions of samples in gen~, the solution is to distribute processing over time. Sadly there's not an easy way to convert the code to do this -- but after a bit of manual work, here it is working. What I found interesting in this is that the semantics of the code became a bit more obvious:

Note that if you want it to sort faster, you can wrap that final if() block in a for loop, but this will increase the CPU load:

Another option is to process the insertion sort via some non-gen~ solution. If you still want to use GenExpr, you could actually achieve it via jit.gen and jit.buffer~, but I don't think insertion sort is the best sorting algorithm to use, as it can't take advantage of the parallelism of cell-based processing. sample-sort, quick-sort, aa-sort etc. might work better.

Although the buffer size in your patcher is 44100 samples long, and thus less than the loop limit, the insert-sort algorithm can cause millions of iterations due to the nested loop. This really is too many to process within one signal vector, and would cause audio dropouts. 

Thanks for those examples - fascinating and illuminating!

insert-sort of a buffer in gen codebox ?