5
$\begingroup$

When programming with high level languages like Python or Matlab, it is always better to model the problem such as the solution is some kind of vector or matrix multiplication, to avoid loops. But this vector multiplication will itself take each elements from both arrays and multiply them so basically there must be some loops at some level. Is that the case or is there special methods at assembler level that make multiplications of memory blocks with no loops?

$\endgroup$
6
$\begingroup$

When you are using vectorized operations in a high-level language such as Matlab or python, you are not avoiding loops, but rather pushing them from the high-level language (Matlab or python) to a low-level language (C or fortran) which can execute these loops much faster. Loops in Matlab or python are slow for several reasons, the main ones being that these languages are interpreted, that typing is dynamic, and that even basic data types involve a lot of overhead.

Some old supercomputers had a vectorized architecture (for example Crays), but this is no longer the case. Nowadays there are small-scale vectorized instructions which operate on a small number of data points at once (as mentioned in EvilJS's answer), though their use could be rather specialized.

Loop unrolling, mentioned by EvilJS, can be used to cut down the number of conditional jumps, which slow down the execution of the code. The body of the loop is repeated a small number of times, thus reducing the frequency of conditional jumps at the expense of code size (which could be important due to the existence of code caches). Such tricks are better left to the implementors of standard libraries.

$\endgroup$
  • $\begingroup$ Additionally, memory locality reduces cache misses. Leaving it up to the interpreter to perform this allows it to iterate in the best order $\endgroup$ – Outurnate Sep 1 '15 at 22:33
3
$\begingroup$

Underneath there are normal loops, or vectorized instructions (SIMD instructions where possible).
It is not possible to avoid loops at all - you can unwind them if you know number of iterations in advance, otherwise basically you cannot get rid of them.
For example in Matlab if you want to check yourself - after exporting to C there are normal loops, and for those functions that are not exported - they are using some reduction methods to speed up (which should work, but for some reason Matlab is very slow).

As Yuval Filmus correctly stated, loop unwinding is degrading performance, it was only for educational purpose of avoiding loops, never optimise like this (your compiler probably does better job, or you should exhaustively test the code in case you know better).

Also there are some optimisations under the hood, for example taking some matrix features or some kinds of decompositions, so it is hard to tell what is used at the moment.
So if you try to implement straightforward method it may differ from these languages.

Normal loops should use register to loop counter, sometimes they don't.

Side note, you should use Matlab compiler, this speed ups a lot.

$\endgroup$
3
$\begingroup$

Consider the following simple python3 script:

import numpy as np
import numpy.random as npr
import timeit

# Naive implementation of inner product
def inner_product(vec1, vec2) :
    dot = 0
    for ii in range(N) :
        dot += vec1[ii]*vec2[ii]
    return dot

N = 10000
v1 = npr.rand(N)
v2 = npr.rand(N)

# Print v1 dot v2, computed three different ways. There are others.
print (inner_product(v1, v2))
print (sum(v1*v2))
print (np.inner(v1, v2))

# Time those three approaches.
setup="from __main__ import loop_inner_product,v1,v2"
print(timeit.timeit('inner_product(v1, v2)', setup=setup, number=100))

setup="from __main__ import v1,v2"
print(timeit.timeit('sum(v1*v2)', setup=setup, number=100))

setup="from __main__ import np,v1,v2"
print(timeit.timeit('np.inner(v1, v2)', setup=setup, number=100))

The first three print statements print the same value; after all they are computing the same thing (to within numerical precision). However, the results of the next three print statements are very, very different.

On my computer,

  • sum(v1*v2) is three to four times faster than is inner_product(v1,v2).
    That's not bad, but it's not that good either.
  • np.inner_product(v1,v2) is almost 1000 times faster than is inner_product(v1,v2).
    Now that's an improvement.

There are a number of things that make inner_product so very slow. One of them is the loop itself. Each iteration calls a generator function that creates a new python object that contains the integer. All of those objects need to be garbage collected. Another issue is the indexing. This involves a call to the numpy.array.__getitem__ function. This function is rather complex; there are lots and lots of ways to slice and dice a numpy array. Compare that to the C equivalent:

for (int ii=0, size=v1.size; ii < size; ii++) {
    sum += v1[ii]*v2[ii];
}

Here, no new objects are being constantly created and destroyed. No functions are being called over and over again to increment the iterator or to access an element of the array. An optimizing compiler will most likely keep the index, the size, and the sum in registers.

Whenever you find yourself writing a loop in a language such as python or matlab, you should rethink what you're doing. If you rewrite it without a loop and the speedup is only a factor of three or four, you should rethink what you're doing. There's probably a library function implemented in C, C++, or Fortran that does exactly what you want, and that might well result in a speedup of a factor of 1000.

$\endgroup$
2
$\begingroup$

Wrong. You should write your solution (with or without loops) to be as clear and natural as possible. If it is a bunch of nested loops, so be it. This makes your program/script easier to write, easier to check it is correct, and easier to modify later on when the need arises.

If after getting it right you see that it is too slow, then you can start worrying about rewriting those parts you measure to take up most of the running time for speed. This is a judgement call, your time is much, much more valuable than the computer's.

$\endgroup$
  • $\begingroup$ Often you can tell in advance that it is necessary to vectorize your code. Even when it's not clear, in the future you might want to reuse your code with more data, at which point vectorizing becomes necessary. $\endgroup$ – Yuval Filmus Aug 31 '15 at 17:34
  • 2
    $\begingroup$ This is wrong, at least in the world of numerical / scientific programming. In a high order language such as python or matlab, one should know how to use the language and its massive libraries. A naive matrix*matrix function in matlab would use a triply nested loop. Much better is use matlab's powerful multiplication operators. Compared to the loop form, that code would be much shorter, even more obviously correct, and orders of magnitude faster. Loops in high order languages are something to be avoided. They are not pythonic. (What's the matlab equivalent of pythonic?) $\endgroup$ – David Hammen Aug 31 '15 at 20:59
  • 2
    $\begingroup$ @DavidHammen, in such a case the most most natural program (for somebody in the know, at least) will use the libraries. $\endgroup$ – vonbrand Aug 31 '15 at 22:43
  • $\begingroup$ @YuvalFilmus, "bum the code today because you might someday use it with milions of elements" is a classical case of premature optimization... $\endgroup$ – vonbrand Aug 31 '15 at 22:46
  • 1
    $\begingroup$ In some cases you can't even start to think about making a loop because you know it is too slow and won't achieve real-time speeds for processing for example camera images coming at 30 Hz, and loops over pixels in image processing would be qualified as "stupid" $\endgroup$ – Mehdi Sep 1 '15 at 12:39

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.