20

In the past, when I've needed array-like indexical  lookups in a tight loop, I usually use tuples, since they seem to be generally extremely performant (close to using just n-number of variables). However, I decided to question that assumption today and came up with some surprising results:

In [102]: l = range(1000)
In [103]: t = tuple(range(1000))
In [107]: timeit(lambda : l[500], number = 10000000)
Out[107]: 2.465047836303711
In [108]: timeit(lambda : t[500], number = 10000000)
Out[108]: 2.8896381855010986

Tuple lookups appear to take 17% longer than list lookups! Repeated experimentation gave similar results. Disassembling each, I found them to both be:

In [101]: dis.dis(lambda : l[5])
  1           0 LOAD_GLOBAL              0 (l)
              3 LOAD_CONST               1 (5)
              6 BINARY_SUBSCR       
              7 RETURN_VALUE    

For reference, a typical 10,000,000 global variable lookup/returns take 2.2s. Also, I ran it without the lambdas, y'know, just in case (note that number=100,000,000 rather than 10,000,000).

In [126]: timeit('t[500]', 't=range(1000)', number=100000000)
Out[126]: 6.972800970077515
In [127]: timeit('t[500]', 't=tuple(range(1000))', number=100000000)
Out[127]: 9.411366939544678

Here, the tuple lookup take 35% longer. What's going on here? For very tight loops, this actually seems like a significant discrepancy. What could be causing this?

Note that for decomposition into variable (e.g. x,y=t), tuples are slightly faster (~6% in my few tests less time) and for construction from a fixed number of arguments, tuples are crazy faster(~83% less time). Don't take these results as general rules; I just performed a few minitests that are going to be meaningless for most projects.

In [169]: print(sys.version)
2.7.1 (r271:86882M, Nov 30 2010, 09:39:13) 
[GCC 4.0.1 (Apple Inc. build 5494)]
4
  • I'm a bit surprised -- though I don't get the 35% difference you claim, closer to 13%.
    – Fred Foo
    Apr 11, 2011 at 19:10
  • Did you use a function call or run timeit with strings? I get closer to 13% (17%) if I wrap them in functions (see the first result). I think there the RETURN_VALUE and maybe LOAD_GLOBAL are bringing the values closer together.
    – Bryan Head
    Apr 11, 2011 at 19:13
  • mac os x leopar, python 3.0, the same code runs: 10.0xx for the list, and 3.5xx for the tuple.
    – khachik
    Apr 11, 2011 at 19:21
  • strings. Python 2.7.1, Windows XP, ancient AMD Sempron.
    – Fred Foo
    Apr 11, 2011 at 20:06

2 Answers 2

24

Tuples are primarily faster for constructing lists, not for accessing them.

Tuples should be slightly faster to access: they require one less indirection. However, I believe the main benefit is that they don't require a second allocation when constructing the list.

The reason lists are slightly faster for lookups is because the Python engine has a special optimization for it:

case BINARY_SUBSCR:
    w = POP();
    v = TOP();
    if (PyList_CheckExact(v) && PyInt_CheckExact(w)) {
        /* INLINE: list[int] */
        Py_ssize_t i = PyInt_AsSsize_t(w);
        if (i < 0)
            i += PyList_GET_SIZE(v);
        if (i >= 0 && i < PyList_GET_SIZE(v)) {
            x = PyList_GET_ITEM(v, i);
            Py_INCREF(x);
        }

With this optimization commented out, tuples are very slightly faster than lists (by about 4%).

Note that adding a separate special-case optimization for tuples here isn't necessary a good idea. Every special case like this in the main body of the VM loop increases the code size, which decreases cache consistency, and it means every other type of lookup requires an extra branch.

2
12

Contrary to this, I have completely different advice.

If the data is -- by the nature of the problem -- fixed in length, use a tuple.

Examples:

  • ( r, g, b ) - three elements, fixed by the definition of the problem.
  • ( latitude, longitude ) - two elements, fixed by the problem definition

If the data is -- by the nature of the problem -- variable, use a list.

Speed is not the issue.

Meaning should be the only consideration.

7
  • I will also add that a 17% difference in performance is rarely a show stopper. Usually, a task that takes 100 seconds to run doesn't become unacceptable when it increases to 117 seconds. Apr 11, 2011 at 19:14
  • For most applications you're building with python, I agree with you, BUT people do build apps that have tight loops where they need performance but don't want to have to take the time to jump down to C (or Cython, etc) to get it. Using lists instead of tuples in some places is a very simple and at least as readable way to squeeze out a little bit. Also, as I noted "construction from a fixed number of arguments, tuples are crazy faster". I'm dealing with mostly variable length sequences here. I had been doing things like "tuple(my_list)" before my big loops.
    – Bryan Head
    Apr 11, 2011 at 19:23
  • @Steven: That was 17% within the lambda. Removing the overhead from function call and return, it was 35%, which can be significant. But, yes, you're right; for most applications, this is a nonissue. Mostly, I just found it really weird.
    – Bryan Head
    Apr 11, 2011 at 19:26
  • 1
    @Bryan You should stop doing micro-optimizations while you code. Write the cleanest code you can, and if its too slow, profile it. Apr 11, 2011 at 19:31
  • @Steven: I'm mostly just curious about language implementation and such. However, in the instance that led me to this question, I am building large immutable lists initially constructed from comprehensions that will be used in a large number of tight loops. Either data structure is appropriate in this case (tuples to enforce immutability, lists for the more readable list comprehension used in construction). This change is trivial, preserves and arguably increases readability, and produces significantly faster code for my application.
    – Bryan Head
    Apr 11, 2011 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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