a,b = b,a in python vs std::swap() in C++

Question

I know that a,b = b,a is basically assigning a tuple (a,b) the values of another tuple (b,a). This is, essentially, swapping the values form a to b and from b to a. Thus, causing a "swap".

This is the functionality of the swap() function in C++.

From research, I have seen that C++'s swap() function uses a third temporary variable to perform the swap. I haven't been able to find how is a,b = b,a implemented in python.

How is a,b = b,a implemented?

Does python also use a third temporary variable? If it doesn't, how does it work?

How do both operations compare in terms of speed? I'm guessing that if python also uses a third variable, the difference in execution time would be due to python being interpreted.

Edit: All answers are great, but the community seems to think that Sapan's is the best one. Also thanks to a_guest, whom, although didn't post an answer, gave us a great deal of information in the comments. Also: everyone seems to agree that swap() is faster just because its C++. I don't necessarily agree with that. Python can be very fast if run as a frozen binary.

As you mentioned, the "temporary" variable is the tuple that you create. Also note that `b, a =` is actually referred to as [unpacking](https://www.python.org/dev/peps/pep-3132/). — a_guest, Aug 24 '18 at 07:23
@a_guest That seems a decent answer. Would you like to make one? — Yunnosch, Aug 24 '18 at 07:24
It exists in C++: [`std::tie(a, b) = std::tuple{b, a};`](http://coliru.stacked-crooked.com/a/91a5d9d52b25678f). But `swap`ing is highly preferable. — YSC, Aug 24 '18 at 07:30
@Yunnosch I'd make one if it addressed all the aspects of the OP but I haven't checked (compared) the performance aspect. Though it might be difficult to get reliable results here since other aspects might dominate the swapping time. — a_guest, Aug 24 '18 at 07:31

score 14 · Accepted Answer · answered Aug 24 '18 at 07:27

14

For tuple assignments, Python uses the stack structure directly:

>>> import dis
>>> def abc(a, b):
...     a, b = b, a
... 
>>> dis.dis(abc)
  2           0 LOAD_FAST                1 (b)
              3 LOAD_FAST                0 (a)
              6 ROT_TWO             
              7 STORE_FAST               0 (a)
             10 STORE_FAST               1 (b)
             13 LOAD_CONST               0 (None)
             16 RETURN_VALUE

In python, assignments in a target list on the left-hand side are done from left to right.

answered Aug 24 '18 at 07:27

Sapan Zaveri

490
7
18

Very interesting, so no tuple is being created here, i.e. the swapping is optimized in that sense. Compare with `def foo(a, b): c = b, a; a, b = c` which creates an additional tuple. Also CPython seems to make use of that optimization only for up to three values (e.g. `a, b, c = c, b, a`). Using `def bar(a, b, c, d): a, b, c, d = d, c, b, a` reveals that an intermediate tuple is being created. – a_guest Aug 24 '18 at 07:38

Jonas Adler · Answer 2 · 2018-08-24T07:57:48.913

How is a,b = b,a implemented?

First, b, a creates a tuple. You can verify this using e.g.

>>> tmp = 1, 2
>>> tmp
(1, 2)

Then, the assignment uses sequence unpacking, overwriting the names a, b. Hence the code is basically

>>> tmp = (a, b)
>>> b, a = tmp

How do both operations compare in terms of speed?

This would depend on your implementation of python. If you use CPython (the standard version), then C++ would likely be much faster since it is compiled and optimized.

CPython implementation details

In CPython, the swap is sometimes optimized. For small swaps (<4 elements) it uses an optimized swap

>>> def swap(a, b):
>>>     a, b = b, a
>>> dis.dis(swap)
  3           0 LOAD_FAST                1 (b)
              3 LOAD_FAST                0 (a)
              6 ROT_TWO
              7 STORE_FAST               0 (a)
             10 STORE_FAST               1 (b)
             13 LOAD_CONST               0 (None)
             16 RETURN_VALUE
>>> def swap(a, b, c):
>>>     a, b, c = c, b, a
>>> dis.dis(swap)
  3           0 LOAD_FAST                2 (c)
              3 LOAD_FAST                1 (b)
              6 LOAD_FAST                0 (a)
              9 ROT_THREE
             10 ROT_TWO
             11 STORE_FAST               0 (a)
             14 STORE_FAST               1 (b)
             17 STORE_FAST               2 (c)
             20 LOAD_CONST               0 (None)
             23 RETURN_VALUE

For swaps of 4 or more elements it does exactly what I wrote above, without optimization.

>>> def swap(a, b, c, d):
>>>     a, b, c, d = d, c, b, a
>>> dis.dis(swap)
  3           0 LOAD_FAST                3 (d)
              3 LOAD_FAST                2 (c)
              6 LOAD_FAST                1 (b)
              9 LOAD_FAST                0 (a)
             12 BUILD_TUPLE              4
             15 UNPACK_SEQUENCE          4
             18 STORE_FAST               0 (a)
             21 STORE_FAST               1 (b)
             24 STORE_FAST               2 (c)
             27 STORE_FAST               3 (d)
             30 LOAD_CONST               0 (None)
             33 RETURN_VALUE

Much more insightful now :-) – user2390182 Aug 24 '18 at 08:31 — user2390182, Aug 24 '18 at 08:31
Thank you for your help in improving the answer! – Jonas Adler Aug 24 '18 at 08:41 — Jonas Adler, Aug 24 '18 at 08:41

score 5 · Answer 3 · answered Aug 24 '18 at 07:58

Adding to Sapan's answer:

In C++ it might conceptionally use a third variable to swap. But you can see here that the compiler can produce the same assembly as the one shown from python:

void foo(int& a, int& b)
{
    std::swap(a, b);
}

turns into

foo(int&, int&):
    mov     eax, DWORD PTR [rdi]
    mov     edx, DWORD PTR [rsi]
    mov     DWORD PTR [rdi], edx
    mov     DWORD PTR [rsi], eax
    ret

https://godbolt.org/g/dRrzg6

score 4 · Answer 4 · answered Aug 24 '18 at 11:09

Not exactly answer about implementation of python but important background about std::swap.

C++ std::swap will not simple swap two variables using third one. It will use knowledge of internal state to speed it up.

Some example for std::array and std::vector: https://gcc.godbolt.org/z/MERLGZ

In both cases it will not use third variable to copy whole object but will directly swap internal representation of both types.

In case of array we have branch for case if array have correct alignment or not. If yes then will swap whole object using two xmm registers, if not it will swap each element separately.

In case of vector we swap internal pointers between two objects.

Another important thing for std::swap is std::move, this is C++11 addition that allow to easy swap two variables that normally can't be copied like std::unique_ptr.

Right now generic version of std::swap look like:

template<typename Tp>
inline void swap(Tp& a, Tp& b)
{
    Tp tmp = std::move(a);
    a = std::move(b);
    b = std::move(tmp);
}

If your type need memory allocation for coping and it support move then no memory allocation will be done there.

Probably most of this things that C++ do, do not apply to how python handle its objects.

a,b = b,a in python vs std::swap() in C++

4 Answers4

CPython implementation details