8

I wrote some script in Python that creates a giant 2D matrix (1000x1000 or bigger) and fills it with random numbers. And after that, it goes through every element of the matrix and changes the number to another one depending on the current element's neighbours (something like you do in Game Of Life).

And I noticed that if I write the same algorithm of checking the neighbours like

if neighbour on the left has the value of X:
    do Al
    Bl
    and Cl
else:
    do Dl
    El
    and Gl
now if neighbour on the right has the value of X:
    do Ar
    Br
    and Cr
and so on...

this code runs much faster than a version using function calls:

def actionA(x):
    do x

def actionB(x):
    do x

def actionC(x):
    do x

def check(n):
    actionA(n)
    actionB(n)
    actionC(n)

for every neighbour:
    check(neighbour)

I'm wondering why that is so. Is it because the script has to switch between the loop and functions when executing the function's code while it goes line-by-line when running the inlined code?

5
  • 14
    Python doesn't try to be very fast, it's not one of the language's priorities. And that's not really very functional, it's just splitting up the procedural code into multiple functions. An optimising compiler will inline those function calls. Oct 16, 2022 at 7:19
  • @curiousdannii so the functions' intenal code would be unwraped wherever the functions are called? And it's not skipping from where the loop is stored in the memory to where a certain function is stored in the momory and vice versa?
    – devdevdove
    Oct 16, 2022 at 7:35
  • 5
    I took the freedom to correct your misunderstanding of the terms FP and PP in this question, and tried to make the title and wording fit more to what you are really asking here. Please double check. I also added a Python tag, since your question really is Python-specific.
    – Doc Brown
    Oct 16, 2022 at 7:58
  • @DocBrown I'm new to this and still don't fully understand the terminology. Thanks
    – devdevdove
    Oct 16, 2022 at 9:17
  • Don't you think that depends on the code, and the function? How does the Question view RISC coding, please? Oct 16, 2022 at 19:35

5 Answers 5

31

Many language implementations will automatically inline function calls wherever this makes sense and is possible. This is completely normal for “compiled languages” like C, or JIT-compiling runtimes like Java/JVM, .NET/CLR, or JavaScript/V8.

CPython, the Python reference implementation, is not one of those. The insane cost of function calls in that language is well known, though recent Python versions like 3.10 have made function calls significantly faster. In particular, named arguments used to require that dict() objects were created for the function call. CPython performs basically no optimizations to your program, and runs it as-is. If your program contains a function call, CPython will execute that function call and won't inline anything.

So yes, it is entirely believable that your function call version of the program is a lot slower, and in the past I have achieved some major optimizations by removing function calls from very hot loops in Python programs.

However, Python does have a couple of options to get better performance in a scenario like yours where you're operating on a large matrix.

  • You can write the critical code as a C module
    • Possibly by writing the code in a Python-like syntax with Cython
  • You can try a different Python implementation such as PyPy
  • If your Python code conforms to a simple subset of Python, you can JIT-compile it with Numba. While Numba requires you to annotate all functions that should be JIT-compiled, it's often a fairly easy way to get a big performance boost for numerical code.
  • If you can redesign your program to operate on the entire array at once instead of looping through all entries, you can use Numpy. Numpy is very efficient for dealing with large arrays/matrices as long as you avoid Python-level loops. You wouldn't be the first to think about using Numpy's advanced indexing features to efficiently count neighbors for a Game Of Life program.
5
  • 4
    If writing a module in C scares one away, another possibility is to write it in Rust; it does require learning some Rust, but will avoid mystifying crashes. Oct 17, 2022 at 11:00
  • Another possibility is to write it in Python. Mypyc has similar capabilities to Cython, but takes regular ol' Python code as input. (Note that it's currently alpha software.)
    – wizzwizz4
    Oct 17, 2022 at 12:00
  • 1
    If you want the Game of Life in particular to go fast, see lemire.me/blog/2018/07/18/… for an AVX2 version that's 25x faster than simple scalar C (compiled with an optimizing compiler). Which in turn would be many times faster than CPython. Or en.wikipedia.org/wiki/Hashlife for algorithmic optimizations, memoizing some repeating patterns, especially for sparse grids. Oct 17, 2022 at 15:38
  • A function call and return in CPython takes a few hundred CPU cycles. That's expensive compared to many language implementations, but I wouldn't call it "insane".
    – benrg
    Oct 17, 2022 at 22:23
  • 1
    @benrg - an alternative way to put it is that a loop containing a function call can execute 2 to 3 orders of magnitude slower than you'd expect coming from a C-esque language.
    – TLW
    Oct 18, 2022 at 1:40
3

I do not know much about Python specifically but from your code I can tell you use two constructs that will introduce some overhead:

  • The for loop
  • The function calls

Obviously, the more code you have in the loop and in the functions, the less significant this overhead will be. If the code itself is quick you will likely see the impact of the overhead.

What does a loop do?

The most straightforward implementation of a loop increments a counter, checks whether the counter is still below the target number and if so jumps back to the start of the loop. More intricate implementations may use a so called enumerator which is a function that would be called repeatedly, once for each iteration. So looping is not free.

What is a function call?

Before just jumping to the function code, arguments need to be stacked. That is, a set of data is set aside in a way the function's code will be able to access it. Again different implementations are possible, for small and few arguments the passing may be optimized by using processor registers but either way some preprocessing and management will be required before the function code can be executed. Once the function code is executed a result may have to be passed back to the calling code in a similar way. So function calls are not exactly free either.

Now, before you start unrolling all your existing code to make it faster please ask yourself whether it makes sense to do so. Readability will suffer and if speed really were a concern, Python would not be the way to go in the first place.

13
  • 1
    Enumerator might be better replaced with Iterator for searchability: that's the term used in Python, and I think more broadly (not seen Enumerator outside of .NET personally) for this construct Oct 16, 2022 at 9:00
  • 5
    @devdevdove: loop unrolling and inlining function calls are standard optimizations in compilers for many programming language implementations. So usually don't have to do this by yourself, it just happens "under the hood" (in CPython, however, not).
    – Doc Brown
    Oct 16, 2022 at 9:23
  • 3
    @devdevdove: This optimization does not have anything to do with the language. It depends purely on whether the implementor put in the work to implement it or not. PyPy, GraalPython, IronPython, and Jython will very likely inline all the function calls in your code. Oct 16, 2022 at 9:46
  • 2
    It also depends on the nature of the call. The OP's may well be inlined as the runtime can predict which function will be called; however, dynamic/virtual calls generally cannot be inlined directly because there may be multiple implementations (e.g. you can inline common cases, but in Python require per-invocation (because the implementation can change during runtime) checks to ensure the common case applied). In general, python is chock full of dynamic invocations which makes inlining 'harder', but this applies to various extents in any language which supports late-binding/dynamic dispatch. Oct 16, 2022 at 10:04
  • 2
    In principle there is no difference between interpreted and compiled language, but in practice there are languages that are intended to be compiled to native code that works without extensive runtime library and are virtually never run in an interpreter or virtual machine, and those that for which this is near impossible to do efficiently and are virtually always run in an interpreter or virtual machine. CPython compiles to bytecode, not native code.
    – ojs
    Oct 16, 2022 at 15:43
0

Function calls in Python are relatively expensive, and due to Pythons dynamic nature, it is not possible for the compiler to inline function calls.

In typical code this is not an issue, but if a block of code is executed a million times as in your example, it could be a significant speedup to eliminate the function calls.

7
  • 5
    "due to Pythons dynamic nature, it is not possible for the compiler to inline function calls" – I am 100% convinced that at least IronPython, Jython, GraalPython, and PyPy will inline all function calls in the OP's code. That's 4 out of 5 of the most popular implementations. Oct 16, 2022 at 9:45
  • 7
    @JörgWMittag: I am pretty sure in most cases when people talk about Python without mentioning the implementation, you can safely assume they have CPython in mind.
    – Doc Brown
    Oct 16, 2022 at 9:56
  • 3
    @DocBrown: In that case, the statement is still wrong, but for a different reason: there is nothing dynamic about CPython, and it is precisely CPython's static nature that prevents it from optimizing these function calls. Oct 16, 2022 at 10:00
  • 5
    @JörgWMittag: Yes I am talking about CPython. In the Python community, CPython can generally be assumed if no other implementation is specifically mentioned.
    – JacquesB
    Oct 16, 2022 at 12:01
  • 3
    I think the point Jörg was making that "due to Pythons dynamic nature, it is not possible for the compiler to inline function calls" isn't exactly the case, as evidenced by several other implementations that do make this optimization. Of course, much in the design and implementation of languages is an exercise in trade-offs, but that doesn't make it "impossible". Oct 17, 2022 at 9:28
0

When processing a function call, the system has to record that it's made the function call (and where it needs to return to), perform validation/type conversions on the function parameters, etc, etc, etc.

So fundamentally, Function calls are generally more expensive than inline code, unless the compiler is able to convert said function calls into inline code. Some compilers can implicitly perform this conversion, while some languages (e.g. C/C++) have special keywords which can be used to instruct the compiler to convert functions into inline code.

https://www.greenend.org.uk/rjk/tech/inline.html

It's worth bearing in mind that similar applies to the various forms of control structures: "unrolling the loop" is a popular optimisation, especially when it comes to low-level assembler and the like:

https://en.wikipedia.org/wiki/Loop_unrolling

Generally though, I'd advise against trying to manually second-guess the compiler - if you do want to dive into the world of micro-optimisations, you're probably best off using profiling to target specific bottlenecks!

Saying that, it's always worth structuring your code to make sure that you process the lowest-cost and/or highest-probability actions first, since the compilers generally don't have that sort of high-level "domain" knowledge.

E.g. most languages/compilers will stop evaluating a boolean chain if a operand comes out as false. So it's worth structuring your if() calls accordingly.

(booleanFlag || stringValue == 'example' || functionCall()) // "fail-fast"
(functionCall() || stringValue == 'example' || booleanFlag) // "fail-slower"

Similarly, if dealing with multiple if/case statements, then it's worth putting the highest-probability items at the very top:

switch (handle) {
    case '50_percent':  do_somethingA(); break;
    case '20_percent':  do_somethingB(); break;
    case '10_percent':  do_somethingC(); break;
    case '5_percent':  do_somethingD();  break;
    case '1_percent':  do_somethingE();  break;
    ...
}

But again, fine-tuning code is generally best done via profiling tools!

0

Not necessarily. A small anecdote to illustrate the point. Many years ago, I was engages in a friendly competition to write the fastest algorithm to calculate generations for Conway's "game of life".

I wrote an extreme inline version, based on a set of macros (this was a machine language program) that exploded the entire inner loop into an large inline function. With no function calls, that had to be the fastest, right? Wrong!

I was beaten by a small function that did the same calculation in a compact loop with lots of function calls.

Analysis showed that my version was too large to fit in the memory cache, so it was getting 100% cache misses and ran very slowly.

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