recursive function performances

Blitz3D Forums/Blitz3D Programming/recursive function performances

Flanker512

(Posted 2015) [#1]

Hi guys, I have a question about performance according to specific code implementation.

Let's say i have this function :

Function recursiveFunction(variable)

	If variable = True
		; blablabla calling recursiveFunction 1000 times
	Else
		; blablabla calling recursiveFunction 1000 times
	EndIf

End Function

will it be better to implement it like that :

Function mainFunction(variable)

	If variable = True
		; call recursiveFunction1 10 times
	Else
		; call recursiveFunction2 10 times
	EndIf

End Function

Function recursiveFunction1()
	; blablabla calling recursiveFunction1 100 times
End Function

Function recursiveFunction2()
	; blablabla calling recursiveFunction2 100 times
End Function

so basically, is checking "variable = True" 10 times over 1000 worth the effort ?

my recursive function is quite huge and it's not really easy to test the other method :-/

Stevie G

(Posted 2015) [#2]

By 'better' , if you mean faster then it probably makes very little difference.

I think it's important to know what your recursive function actually does?

Flanker512

(Posted 2015) [#3]

yes I mean faster, the recursive function performs basic maths.

the second implementation could avoid a lot of "If variable = True", and I wonder if it can increase performances as it's only a memory read if i'm not wrong.

Stevie G

(Posted 2015) [#4]

I think it's important to know what your recursive function actually does?

Performs basic maths doesn't really help.

Avoiding alot of "if variable = true" conditions is going to make very little, if any difference to the speed of your code.

Flanker512

(Posted 2015) [#5]

The function is a recursive pathfinding designed to be as fast as possible so the implementation is crucial. For example, as a test, if I add "temp = temp + 1" in the "blablabla", I can see a performance decrease, so I'm tracking every operation wich can be avoided. However the "If variable = True" is not as simple in my case, so if it doesn't make a huge difference, I may stick with it. Thx for the help.

Yasha

(Posted 2015) [#6]

This honestly isn't worth worrying about at this stage. For every project, write the code in the form that is clearest to you, and then test the whole program after integrating it; if whole-program performance falls below the threshold of acceptability, make a profile and make changes to the code you've empirically found to be the source of the problem.

By thinking about this before the actual code is in place, you're going to end up writing unnecessarily convoluted code that doesn't perfectly reflect the algorithm and will thus be harder to manage (and risks being slower in the long run as a result, by locking you in). You probably also aren't going to have any significant effect on the performance by trying to pre-empt the results because modern CPU performance is actually pretty complicated.

Things to consider:

-- Blitz3D is not an optimising compiler anyway. The machine code it generates is... well it's not horrible, but it makes no pretence at being "high-performance". By writing in Blitz3D you are already giving away anywhere between 1 and 90 percent of your program's performance (who knows how much it really is; it varies)
-- on modern systems, the number of instructions is a very minor issue. Yes, testing a variable technically involves a memory read and a branch, but in practice caching and branch prediction make both of these operations very cheap. In particular, a branch that almost always goes the same way (i.e. 1000 tests that result in false before the loop ends) are basically going to be equivalent to no-ops; branches are generally only slow if they aren't consistent. So to some extent the hardware has actually started actively compensating for the code.
-- what the hardware can't currently compensate for is the fact that Blitz3D isn't really designed to handle recursion beyond the most basic form, so it means a lot of function calls, local variable initialisation, tromping around in a wide swathe of memory (nuking the call/ret predictor stack and wasting cache), and the risk of stack overflow (1000 invocations of a reasonably-sized function is around the point where you should be becoming worried). Recursion is certainly elegant, but if you care about performance, you could negate all of those issues by using a loop - even a loop with a manually-managed shadow stack - as your implementation's base instead, and likely see a noticeable performance improvement.
-- since Blitz3D doesn't understand e.g. cache, alignment, or prediction, it's perfectly possible to have huge - like 20% - performance variations in exactly the same piece of code, simply because you moved a line up or down somewhere else in the program and had no effect on the logic but the instructions were emitted in a different sequence (this does happen in practice, although it's thankfully not that extreme normally). So it can make even getting a read on where exactly the source of a micro-benchmark's slowdown is difficult.

Machine code is fast. Bad machine code is actually still pretty fast. Unless you know it is something you need to worry about, it's not something you need to worry about. Do whatever you want and you'll probably be fine. (If you're really not, you might want to consider dropping down to C for this bit.)

Flanker512

(Posted 2015) [#7]

Thx for the tips Yasha. I should have done like you tell, would have save me some time... In fact I tried to improve the code before it actually works... And I messed up everything lol Now I'm rewriting it the basic way even if it's not the fastest and I'll improve later if necessary.

CPU seems complicated... I know Blitz3D isn't optimize for such things but I need a simple 3D engine so I'll give it a try.