Why is the 'all' implementation slower than writing a for loop

Question

I get a list and want to know if all elements are identical. For lists with a high number of elements, that are indeed all identical, the conversion into a set is fast, but otherwise going over the list with early exit is performing better:

def are_all_identical_iterate(dataset):
    first = dataset[0]
    for data in dataset:
        if data != first:
            return False
    return True

# versus

def are_all_identical_all(dataset):
    return all(data == dataset[0] for data in dataset)
# or
def are_all_identical_all2(dataset):
    return all(data == dataset[0] for data in iter(dataset))
# or
def are_all_identical_all3(dataset):
    iterator = iter(dataset)
    first = next(iterator)
    return all(first == rest for rest in iterator)

NUM_ELEMENTS = 50000
testDataset = [1337] * NUM_ELEMENTS # all identical

from timeit import timeit
print(timeit("are_all_identical_iterate(testDataset)", setup="from __main__ import are_all_identical_iterate, testDataset", number=1000))
print(timeit("are_all_identical_all(testDataset)", setup="from __main__ import are_all_identical_all, testDataset", number=1000))

My results: 0.94 seconds, 3.09 seconds, 3.27 seconds, 2.61 seconds

The for loop takes less than have the time (3x) of the all function. The all function is supposed to be the same implementation.

What is going on? I want to know why the loop is so much faster and why there is a difference between the last 3 implementations. The last implementation should have one compare less, because the iterator removes the first element, but that shouldn't have this kind of impact.

You are doing the index lookup `dataset[0]` repeatedly in the `all` call, while you store the result in a local variable in the iteration. — user2390182, Sep 18 '19 at 15:16
@schwobaseggl I tried changing that, it doesn't make much difference. And `are_all_identical_all3` already does not do that. — khelwood, Sep 18 '19 at 15:16
Answers to this question https://stackoverflow.com/questions/56288015/why-is-a-for-loop-so-much-faster-to-count-true-values/56291247#56291247 can answer yours. TLDR: usage of generators inside `all` function is expensive. — sanyassh, Sep 18 '19 at 15:19

FabioL · Answer 1 · 2019-09-19T09:21:57.243

2

As suggested in this other SO post one cause could be that:

The use of a generator expression causes overhead for constantly pausing and resuming the generator.

Anyway I suggest two another approaches that looks faster using map:

def are_all_identical_map(dataset):
    for x in map(lambda x: x == dataset[0], dataset):
        if not x:
            return False
    return True

%%timeit
are_all_identical_map(testDataset)
#7.5 ms ± 64.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

and

%%timeit
(map(lambda x: x == dataset[0], dataset)) and True
#303 ns ± 13.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

edited Sep 19 '19 at 09:21

answered Sep 18 '19 at 15:27

FabioL

932
6
22

1

Your map implementation is fast, because your indentation is wrong. You always return True or False in the first loop cycle, so you're not really looking at all items. After fixing it, it is slow. – cubei Sep 19 '19 at 09:07
Now it's fixed. But the times need to be compared to the other implementation, because I don't know on what kind of machine it runs. And I don't know what your second implementation is supposed to be... – cubei Sep 19 '19 at 09:35
1

Yes, you were right, thank you! I made a quick fix for now. Later I will make a comparison with other solutions. – FabioL Sep 19 '19 at 09:40

Why is the 'all' implementation slower than writing a for loop

1 Answers1