6
$\begingroup$

I'm wondering specifically in regard to a recursive function such as massive a game tree. I can't specifically say how big yet, but definitely pushing the limits of a given processor or processor array.

Is it correct to say that passing a variable to a function requires an operation. Certainly there must the the flipping of some bits. Does this reduce efficiency?

$\endgroup$
  • 3
    $\begingroup$ For you to know exactly how good or bad it might be to use globals, the best thing you can do is setup two versions of this recursive function. Setup one that uses globals and one that passes parameters. Then time them both individually and see which one is actually better. It can be hard to predict speed-ups since it can be compiler/interpreter dependent, so it's often best to find things empirically. $\endgroup$ – spektr Aug 21 '16 at 11:26
  • $\begingroup$ Depending on processor architecture, nature of the function (e.g. is it a leaf function), and number of function arguments, no operation per se may be required, as the data is simply passed in a register (but ABIs typically require that function arguments be constrained to particular registers in that case). There may be function call overhead if the compiler cannot convert the recursive call into iteration (e.g. when the function is not tail-recursive) $\endgroup$ – njuffa Aug 21 '16 at 12:26
  • $\begingroup$ Thanks for the input! Sounds like the crux of the issue is that I'm working in a high-level language b/c I want to develop it "open source" (there will likely be some kids out there who will want to hack it.) For a weak AI I believe Javascript will be sufficient, but I'm aware that for a strong AI, I'll have to implement with a lower level language. $\endgroup$ – DukeZhou Aug 21 '16 at 21:16
5
$\begingroup$

First of all, note that this forum is for Computational Science, not Computer Science. These are different fields, with Computational Science being scientific computing, more like computational mathematics and scientific simulations. That said, even though the example in question is not relevant to this forum, there are things that should be discussed here.

The inefficiency is not in the passing of values to functions, but in many other places. This is because a global variable can change at anytime. The program can't know if the value will change, and more importantly in a scripting language, they can change types. Because the program doesn't know if the variable changed, the program has to be ready to deal with whatever has happened. Thus all compiler/interpreter optimizations are turned off and any code around the variables has to go into "safe mode"

Example

A good example is to look at Julia. Julia is a recent programming language which, although it "looks like a scripting language", is actually designed to be efficiently compiled at every step of the way. If you write your Julia code correctly (type-stable, etc.), then your code will compile to be the same speed as C/Fortran (and you can use @code_llvm to see that the machine code is the same as what you'd get from a C/Fortran compiler). However, the language has problems with global variables. A large discussion on why is found on Github. The summary is as follows:

In a (just-in-time) compiled language like Julia, the compiler looks at what it currently has and uses a bunch of tricks to optimize the code. However, if it doesn't necessarily know what type the variable is, it has to carry around a bunch of code for making it switch between integers/floats/etc. If the variable is a global, it also has to deal with problems like if some other thread changed the value. This means that a lot of other compiler tricks like inlining are also not able to be done. Thus the resulting compiled code has a lot more steps to check every little detail since the global can do just about anything. This makes dealing with them really inefficient.

As you crawl up the ladder to more dynamic typing, these inefficiencies are more baked into the language. At the bottom, all languages are still running compiled code, so something like MATLAB/R/Python always has this extra code around because their numbers can just change types all the time (Javascript does too, though it's odd since "everything is a float" so it has to have parts convert things to integers at the right times). However, smart interpreters (like the Javascript JITs) will sometimes try to still do some optimizations, but for the same reasons as above, they also cannot optimize too much when there are global variables since there's really no way to know in advance what a global variable will be (both in type and value). When all bets are off, they have to play it safe.

(For an example in the other direction, if you pass a variable in and it looks like an integer, and all of the code looks like it won't modify it, it can JIT compile the function so that it actually is an integer, resulting in much leaner and more efficient machine code. Note that this requires that the compiler can guarantee this variable isn't changing anywhere else, otherwise it will cause breakage.)

Conclusion

This is why the general rule for efficiency is to not use global variables. There's no way for the interpreter/compiler to know what to do with them, so they have to take the safest and least efficient route. Also, since they can change anywhere at any time, they can cause a lot of bugs in programs, and so globals are generally frowned upon for design reasons. In the end, unless you really have to, DO NOT USE GLOBALS.

tldr; passing the variable into the function will cause a lot less problems than a global variable.

$\endgroup$
  • $\begingroup$ Sorry, still very new to this. I was thinking it might be computational science related because I'm going to be working with a game tree ~10^120, which practically, can be vastly reduced to manageable levels. But because it is a novel, non-trivial, combinatorial game, I'll be dealing with computation problems unique to this construct. $\endgroup$ – DukeZhou Aug 21 '16 at 19:32
  • $\begingroup$ Graph theory and "algorithms" tend to fall under computer science, not computational science. Computational science is usually things like differential equations and optimization: more the mathematics of discretizing a problem to get numerical algorithms. It also tends to handle the solving of models which arise from science (which are normally a form of differential or difference equation). Of course the classification is not that easy, but that's the general idea. You may want to ask this kind of question on the Computer Science SE. $\endgroup$ – Chris Rackauckas Aug 22 '16 at 6:23
  • $\begingroup$ Thanks @Chris Rackauckas for kindly taking the time to explain this. (I fell in to this project by accident and, as you can probably tell, I'm more than a little out of my depth;) Just for future reference, am I correct in thinking "optimization" here is not referring to reducing the number of operations in an algorithm? $\endgroup$ – DukeZhou Aug 22 '16 at 17:03
  • 1
    $\begingroup$ No problem. And you're right: mathematical optimization is about problems like "what is the maximum value of f?", which is heavily related to solving f(x)=0. To make things more confusing, you can optimize mathematical optimization algorithms... but that's just to confuse the uninitiated. $\endgroup$ – Chris Rackauckas Aug 22 '16 at 18:19
1
$\begingroup$

This is more of a Stack Exchange or Programmer Exchange question, see : here for C language or PHP, Javascript or C++, and more generally.

Try to avoid global variables. It's better for maintaining your code. Global variables should be parameter, i.e their value should not change during execution. About efficiency, I think it is a micro-optimization that is not very relevant. I'm not an expert but I think that working with function arguments rather than global variables allows more optimizations from the compiler (something with the stack and the registers...). Passing a variable to a function only requires some pointer references in the stack (assuming your global variable is not a huge object), that is very fast and I am not even sure a profiler can detect such a thing.

$\endgroup$
  • $\begingroup$ The code is actually complete. I use globals both for fixed parameters and variables, b/c these variables deal with scoring and make more sense as globals. The code is <32 KB, but the complete game tree might be something like 10^120. This can be vastly reduced, and trees don't have to be fully expressed, but I'll still be looking at going as deep as is feasible for the processor, which will initially be a mobile device. So what I'm really asking about is massive recursion. $\endgroup$ – DukeZhou Aug 21 '16 at 19:27
1
$\begingroup$

From a style point of view, it is usually best to avoid global variables (as already pointed out).

From a performance point of view, the answer depends on your programming language. For example, if your language does not support passing a multidimensional array by reference, then a global/non-local array can help. But I guess that all modern languages used for computing don't have such shortcomings.

Whether it costs more to call a function when it has more arguments is language and compiler-dependent. Often, the extra cost will be zero or negligible, so that a global variable is more likely to hurt than benefit you (as explained in the other answers).

$\endgroup$
  • $\begingroup$ Good answer. "Negligible" is a concern, however, as the total game tree could is something like 10^120, thus even profoundly pruned, there will be a massive amount of recursion. $\endgroup$ – DukeZhou Aug 21 '16 at 21:11
  • 1
    $\begingroup$ @cybermike Can you detail your recursion process ? Your question is very general, can you edit your post and try to explain a bit more your project and your exact problem if not sensitive, maybe a context ? $\endgroup$ – Coriolis Aug 21 '16 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.