python - Where does the performance boost of map or list comprehension implementations over calling a function over a loop come from?

Question

I understand that you could be more efficient with memory in the implementation of map than in how you might do it over a loop. However, I see that using a map function over calling a function iterating over a loop has a speed boost as well.

Is this coming from some optimization in where to store the memory? One example of what I mean by this is placement of memory done in such a way that it is contiguous. Also I can see that if the operations were being in run in parallel then there would also be a speed boost, but I don't think this is the case. Examples from any known optimizations for map implementations from any language/package are very welcome!

-- Edit: I feel as if the example I had previously did not illustrate my question very well.

MAY NOT BE COMPLETELY FAIR COMPARISON. For example, I test the a loop implementation, list comprehension, and the map function. Would you have any ideas of what would make one faster than the other? NOT NECESSARILY PYTHON; this is more a question about implementation of more efficient algorithms for applying a function over an iterable object. A valid answer might be that "typically for every map/list comprehension style of code, you would be able to make a loop implementation faster than that". Or for some case, the list comprehension is faster, but this relates to the implementation details and that is what I am interested in.

import time
import numpy as np


def square2(x):
return x*x


def main():
    foobar = np.linspace(1, 300, 300)

    start_time = time.time()
    res = [0] * len(foobar)
    for i, foo in enumerate(foobar):
        res[i] = square2(foo)
    print("{} {} runtime seconds {}".format("-"*8, time.time()-start_time, "-"*8))

    res = [0] * len(foobar)
    start_time = time.time()
    res = [square2(foo) for foo in foobar]
    print("{} {} runtime seconds {}".format("-"*8, time.time()-start_time, "-"*8))

    start_time = time.time()
    res = list(map(square2, foobar))
    print("{} {} runtime seconds {}".format("-"*8, time.time()-start_time, "-"*8))

The output is:

-------- 6.175041198730469e-05 runtime seconds --------
-------- 5.984306335449219e-05 runtime seconds --------
-------- 5.316734313964844e-05 runtime seconds --------

Answer 1

So, the issue with function-calls in loops, in a dynamic language like Python, is that the interpreter has to evalute the refernces each time, and that is costly, especially for global variables. However, notice what happens when you make things local:

import time
def square(x):
    return x*x

def test_loop(x):
    res = []
    for i in x:
        res.append(square(i))
    return res


def test_map(x):
    return  list(map(square,x))

def test_map_local(x, square=square):
    return  list(map(square,x))


def test_loop_local(x, square=square):
    res = []
    for i in x:
        res.append(square(i))
    return res

def test_loop_local_local(x, square=square):
    res = []
    append = res.append
    for i in x:
        append(square(i))
    return res

def test_comprehension(x):
    return [square(i) for i in x]

def test_comprehension_local(x, square=square):
    return [square(i) for i in x]

x = range(1,10000000)

start = time.time()
test_loop(x)
stop = time.time()
print("Loop:", stop - start,"seconds")

start = time.time()
test_loop_local(x)
stop = time.time()
print("Loop-local:", stop - start, "seconds")

start = time.time()
test_loop_local_local(x)
stop = time.time()
print("Loop-local-local:", stop - start, "seconds")

start = time.time()
test_map(x)
stop = time.time()
print("Map:", stop - start, "seconds")

start = time.time()
test_map_local(x)
stop = time.time()
print("Map-local:", stop - start, "seconds")

start = time.time()
test_comprehension(x)
stop = time.time()
print("Comprehesion:", stop - start, "seconds")

start = time.time()
test_comprehension_local(x)
stop = time.time()
print("Comprehesion-local:", stop - start, "seconds")

Results:

Loop: 3.9749317169189453 seconds
Loop-local: 3.686530828475952 seconds
Loop-local-local: 3.006138563156128 seconds
Map: 3.1068732738494873 seconds
Map-local: 3.1318843364715576 seconds
Comprehesion: 2.973804235458374 seconds
Comprehesion-local: 2.7370445728302 seconds

So, making the function look-up in map local doesn't really help, as I would expect because map does a single look-up at the beginning. What really surprised me is that there seems to be a non-negligible difference between a comprehension and a comprehension with the function made local. Not sure if this is just noise, however.