insert-sort of a buffer in gen codebox ?

Ruz Kut's icon

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...)

Max Patch
Copy patch and select New From Clipboard in Max.

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).

Ruz Kut's icon

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

Anyone ?

Ruz Kut's icon

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

Graham Wakefield's icon
Max Patch
Copy patch and select New From Clipboard in Max.

Happy holidays!

leafcutter's icon

That's really nice Graham!

Max Patch
Copy patch and select New From Clipboard in Max.

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

Do you know the reason for this?

Cheers,

John.

Graham Wakefield's icon

Hi John,

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.

Max Patch
Copy patch and select New From Clipboard in Max.

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:

Max Patch
Copy patch and select New From Clipboard in Max.

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.

Happy boxing day!

Graham

leafcutter's icon

Happy Boxing Day Graham!

Thanks for those examples - fascinating and illuminating!

All the best for 2016

John.

Ruz Kut's icon

Thank you Graham !
Happy holidays !

slo ~|•'s icon

Hello Graham,

I'm having a similar problem with "gen~: audio processing exception: Too many iterations (runaway loop?)"

I don't quite have the chops to correctly implement your suggestion above, adapted to my use case.

My goal is to blend the contents of the two buffers at various proportions using "phase" as the index so differing buffer lengths won't matter.

Thanks in advance,

Simon

Demo/test patch below:

Max Patch
Copy patch and select New From Clipboard in Max.

EDIT: The problem still exists even with much smaller buffer sizes. I understand a bit better that the values are being stored in History to be carried on in the next vector, but still haven't got it to work for me.

Graham Wakefield's icon

OK so the idea is that you have two input buffers A and B, and you want to fill a third buffer C with some mix of A and B. The buffers can be different lengths, but you want both of them to be effectively stretched to fit the length of C.

So I'd want to go through the length of C sample by sample, call that index. We'll use that to poke to buffer C. I want to do it sample by sample to make sure every single slot in C is filled. For each one I'd derive phase as index/dim(C), and use that phase to do an interpolated phase-based lookup into A and B (via the sample operator), and blend the two values and poke them into C.

The easiest way to start is to do it as a sample-by-sample process. (We can always wrap that into a for loop later to process a bit faster if it is feasible.) That just means making index be a History, and incrementing it by 1 on each sample:

Buffer A, B, C;
Param blend(0.5, min=0, max=1);
History index;

if (index < dim(C)) {
	phase = index/dim(C); // 0..1
	// read the two input buffers at this phase:
	a = sample(A, phase);
	b = sample(B, phase);
	// mix them and write into C at current index:
	s = mix(a, b, blend);
	poke(C, s, index);
	
	index += 1; // move to next sample
}

This also has to happen over the channels of the buffers. I'd loop through the channels that exist in C, and use those to select channels from A and B according to some @channelmode option, probably @channelmode wrap, so that it still works even if A and B have different numbers of channels.

Also it would probably be handy to output a signal to say when it is done:

Buffer A, B, C;
Param blend(0.5, min=0, max=1);
History index;

busy = index < dim(C);
if (index < dim(C)) {
	phase = index/dim(C); // 0..1
	// for each output channel:
	for (c=0; c<channels(C); c+=1) {
		// read the two input buffers at this phase:
		a = sample(A, phase, c, channelmode="wrap");
		b = sample(B, phase, c, channelmode="wrap");
		// mix them and write into C at current index:
		s = mix(a, b, blend);
		poke(C, s, index, c);
	}
	index += 1; // move to next sample
}
out1 = (index >= dim(C)); // output 1 when done. 

That works, but to fill a 1 second buffer~ C it will take 1 second of time. You might want to do things a bit faster. Let's say we want to allow up to 100 writes per sample. Then we can loop this process 100/channels(C) times.

Buffer A, B, C;
Param blend(0.5, min=0, max=1);
History index;

// how much can we advance per sample?
numloops = ceil(100/channels(C));

for (i=0; (i < numloops) && (index < dim(C)); i+=1) {	
	phase = index/dim(C); // 0..1
	// for each output channel:
	for (c=0; c<channels(C); c+=1) {
		// read the two input buffers at this phase:
		a = sample(A, phase, c, channelmode="wrap");
		b = sample(B, phase, c, channelmode="wrap");
		// mix them and write into C at current index:
		s = mix(a, b, blend);
		poke(C, s, index, c);
	}
	index += 1; // move to next sample
}

out1 = (index >= dim(C)); // output 1 when done. 
Max Patch
Copy patch and select New From Clipboard in Max.

slo ~|•'s icon

Thanks much Graham. Super clear and super helpful.