Unexpected Interpreter slowness

Questions
1

Hello!
I am experiencing an unexpected problem with the Interpreter running very slowly when executing what seems to me to be a very simple algorithm (producing an Array with a specified number of elements extracted from the Fibonacci sequence).

The code is shown below:

~arraySize = 5 ;
~arraySize = 10 ;
~arraySize = 20 ;
~arraySize = 30 ;
~arraySize = 40 ;
~arraySize = 48 ;

(
~fib = { |k|
    if (k < 2) { k } { (~fib.(k-1) + ~fib.(k-2)) }
} ;
)

~seq = Array.fill(~arraySize, { |i| ~fib.(i) }) ;

The more I increase ~arraySize, the slower the computation becomes. Until it completely freezes at 48.
The only way to restore SC to normal is to reboot the Interpreter.

Can anyone help me? :grinning:

2

And very inefficient!

Try adding a print statement inside fib and see how many times it is called.

There are many ways to improve this, you could try adding some caching.

3

Thanks Jordan. Can you suggest a solution to make everything more efficient? Thank you.

4

sclang has two built‑in .fib methods:

Array.fib(5);
// -> [1.0, 1.0, 2.0, 3.0, 5.0]

5.fib;
// -> [1.0, 1.0, 2.0, 3.0, 5.0]


Array.fib(5, 2, 32);
// -> [32, 34, 66, 100, 166]

5.fib(2, 32);
// -> [32, 34, 66, 100, 166]


Array.fib(10);
// -> [1.0, 1.0, 2.0, 3.0, 5.0, 8.0, 13.0, 21.0, 34.0, 55.0]

10.fib;
// -> [1.0, 1.0, 2.0, 3.0, 5.0, 8.0, 13.0, 21.0, 34.0, 55.0]


Array.fib(20);
// -> [1.0, 1.0, 2.0, 3.0, 5.0, 8.0, 13.0, 21.0, 34.0, 55.0, 89.0, 144.0, 233.0, 377.0, 610.0, 987.0, 1597.0, 2584.0, 4181.0, 6765.0]

20.fib;
// -> [1.0, 1.0, 2.0, 3.0, 5.0, 8.0, 13.0, 21.0, 34.0, 55.0, 89.0, 144.0, 233.0, 377.0, 610.0, 987.0, 1597.0, 2584.0, 4181.0, 6765.0]


Array.fib(20, 1, 0);
// -> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

20.fib(1, 0);
// -> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

(There is no particular reason for the initial values to be floats; using integers is more appropriate, I think.)
← This thought is wrong. See:

For efficiency:

Integer : SimpleNumber {
	...
		fib { arg a=0.0, b=1.0;
		^Array.fib(this, a, b);
	}
	...
}


SequenceableCollection : Collection {
	...
	*fib { arg size, a=0.0, b=1.0;
		var i=0, temp;
		var obj = this.new(size);
		while { i < size }{
			obj.add(b);
			temp = b;
			b = a + b;
			a = temp;
			i = i + 1;
		};
		^obj
	}
	...
}

  • From this implementation:

    (
~fib = { |size, a=0, b=1|
	var i=0, temp, obj = Array.new(size);
	while { i < size }{
		obj.add(b);
		temp = b;
		b = a + b;
		a = temp;
		i = i + 1;
	};
	obj
}
)

~fib.(10) // -> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

{~fib.(50000)}.bench    // time to run: 0.0026973749999968 seconds.
{~fib.(500000)}.bench   // time to run: 0.033219833000032 seconds.
{~fib.(5000000)}.bench  // time to run: 0.25788545800003 seconds.
{~fib.(50000000)}.bench // time to run: 2.44957925 seconds.

  • Your algorithm:

     (
 ~seq = { |size|
 	var fib = { |k|
 		if (k < 2) { k } { (fib.(k-1) + fib.(k-2)) }
     };
     Array.fill(size, { |i| fib.(i) })} ;
 )
 
 ~seq.(10) // -> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
 
 {~seq.(20)}.bench // time to run: 0.0019504589999997 seconds.
 {~seq.(25)}.bench // time to run: 0.024087957999996 seconds.
 {~seq.(30)}.bench // time to run: 0.242529875 seconds.
 {~seq.(35)}.bench // time to run: 2.662359917 seconds.

The iterative approach (sclang’s implementation) simply repeats the same operation while updating the result, whereas the recursive approach (your code) performs a great deal of duplicated work, causing the computation to grow exponentially

1 Like
5

TL;DR For raw speed here, avoid recursion:

(
var n = 48;
f = Array(n);
bench {
	n.do { |i|
		if(i < 2) {
			f.add(i)
		} {
			f.add(f[i-2] + f[i-1])
		}
	};
};
f
)

time to run: 2.3352999988902e-05 seconds.
-> [0, 1, 1, 2, 3, 5, 8, 13, 21, ..... ]

0.0002 seconds :wink:

So why is the recursive way so slow here?

Let’s talk about O(). At the top level, you’ve got ~seq = Array.fill(~arraySize, ...). fill does one thing n times, so that’s O(n).

Then the ~fib recursively iterates k times, where the largest k is n. In O() we don’t care about counting the number of iterations exactly; we only care about the order. ~fib is also O(n), so the entire loop is O(n^2).

That is, the execution time increases with the square of n – first time is proportional to 1^2, second time 2^2, third time 3^2, 48th time 48^2.

a = Array.fill(30, { |i|
	bench { Array.fill(i+1, { |j| ~fib.(j) }) }
});

a.plot

sc-fib-recursion-performance
sc-fib-recursion-performance400×300 5.06 KB

The source of the problem here is that ~fib is doing the same work repeatedly. Take ~fib.(4) for example:

  • ~fib(4) calls
    • ~fib(3) for k-1
      • ~fib(2)
        • ~fib(1), non recursive
    • ~fib(2) for k-2
    • ~fib(1), non recursive

Then… ~fib.(5) repeats all of that (twice).

The Fibonacci sequence is trivial to calculate if you remember the past results. My non-recursive approach looks up f[i-1] and f[i-2] rather than recalculating them every time.

If you still want to use recursion without the wasted effort, we could borrow the idea of memoizing from functional programming: the ~fib function can cache the results of every past time it was called; every cache hit reduces O(n) to O(1) and saves a lot of time.

(
var memo = Array.newClear(48);  // all nil's

~fib = { |k|
	var result = memo[k];
	// non-nil result means we hit cache;
	// we'll drop out of the 'if' and just use the cached result
	if(result.isNil) {
		if(k < 2) {
			result = k;
		} {
			result = ~fib.(k-1) + ~fib.(k-2);
		};
		// does the cache array have enough space?
		if(memo.size < (k+1)) {
			memo = memo.extend(k+1, nil)
		};
		memo[k] = result;  // save it
	};
	result
};
)

bench { ~seq = Array.fill(~arraySize, { |i| ~fib.(i) }) };
-> time to run: 2.2704999992129e-05 seconds.

hjh

3 Likes
6

Thank you for your reply and for the very clear examples! I didn’t know there was a .fib method. I wasted a lot of time for nothing, but at least thanks to the help of SC users like you, I can always learn new things. Long live scsynth.org!

1 Like
7

Thank you, James! It is a real honour for me to receive such a comprehensive, clear and detailed response from someone I consider to be a SuperCollider legend. I love your Pattern Guide, and as I use SuperCollider mainly to produce patterns, it has been an invaluable guide in expanding my knowledge.

Once again, long live to this community, one of the best out there! :heart: