Python buffer copy speed - why is an array slower than a string?

Question

I have a buffer object in C ++ that inherits from std::vector<char> . I want to convert this buffer to a Python string so that I can send it over the network via Twisted protocol.transport.write.

Two ways I thought to do: (1) creating a string and filling it char with char:

 def scpychar(buf, n): s = '' for i in xrange(0, n): s += buf[i] return s 

and (2) creating a char array (since I know how big the buffer is), filling it and converting it to a string

 def scpyarr(buf, n): a = array.array('c','0'*n) for i in xrange(0, n): a[i] = buf[i] return a.tostring() 

I would think that (1) should create a new string object every time s += buf[i] called and copy the contents of the old string. Therefore, I expected (2) to be faster (1). But if I test this with timeit, I find that (1) is actually about twice as fast as (2).

I was wondering if anyone can explain why (1) is faster?

Bonus points for an even more efficient way of converting from a std::vector<char> string to a Python string.

Answer 1

CPython can sometimes optimize the += line to be in place if it can determine that no one supports the link to the old line. Algorithm (1) probably caused optimization, so it did not suffer from the square runtime, which otherwise would have been. However, this behavior is not guaranteed, and other Python implementations may not support it.

Try

 ''.join(buf) 

It should offer linear performance in any Python implementation, unlike (1) and faster than (2).

Answer 2

import and look at dis.dis (scpyarr) and dis.dis (scpychar). scpychar has fewer interpreter operations.

 >>> import dis >>> def scpyarr(buf, n): ... a = array.array('c','0'*n) ... for i in xrange(0, n): ... a[i] = buf[i] ... return a.tostring() ... >>> dis.dis(scpyarr) 2 0 LOAD_GLOBAL 0 (array) 3 LOAD_ATTR 0 (array) 6 LOAD_CONST 1 ('c') 9 LOAD_CONST 2 ('0') 12 LOAD_FAST 1 (n) 15 BINARY_MULTIPLY 16 CALL_FUNCTION 2 19 STORE_FAST 2 (a) 3 22 SETUP_LOOP 37 (to 62) 25 LOAD_GLOBAL 1 (xrange) 28 LOAD_CONST 3 (0) 31 LOAD_FAST 1 (n) 34 CALL_FUNCTION 2 37 GET_ITER >> 38 FOR_ITER 20 (to 61) 41 STORE_FAST 3 (i) 4 44 LOAD_FAST 0 (buf) 47 LOAD_FAST 3 (i) 50 BINARY_SUBSCR 51 LOAD_FAST 2 (a) 54 LOAD_FAST 3 (i) 57 STORE_SUBSCR 58 JUMP_ABSOLUTE 38 >> 61 POP_BLOCK 5 >> 62 LOAD_FAST 2 (a) 65 LOAD_ATTR 2 (tostring) 68 CALL_FUNCTION 0 71 RETURN_VALUE >>> def scpychar(buf, n): ... s = '' ... for i in xrange(0, n): ... s += buf[i] ... return s ... >>> dis.dis(scpychar) 2 0 LOAD_CONST 1 ('') 3 STORE_FAST 2 (s) 3 6 SETUP_LOOP 37 (to 46) 9 LOAD_GLOBAL 0 (xrange) 12 LOAD_CONST 2 (0) 15 LOAD_FAST 1 (n) 18 CALL_FUNCTION 2 21 GET_ITER >> 22 FOR_ITER 20 (to 45) 25 STORE_FAST 3 (i) 4 28 LOAD_FAST 2 (s) 31 LOAD_FAST 0 (buf) 34 LOAD_FAST 3 (i) 37 BINARY_SUBSCR 38 INPLACE_ADD 39 STORE_FAST 2 (s) 42 JUMP_ABSOLUTE 22 >> 45 POP_BLOCK 5 >> 46 LOAD_FAST 2 (s) 49 RETURN_VALUE >>> 

Compare this:

  51 LOAD_FAST 2 (a) 54 LOAD_FAST 3 (i) 57 STORE_SUBSCR 

a plus

  >> 62 LOAD_FAST 2 (a) 65 LOAD_ATTR 2 (tostring) 68 CALL_FUNCTION 0 

vs

  38 INPLACE_ADD 39 STORE_FAST 

The load is slow. CALL_FUNCTION is slow.

I saw in a question a month ago that ''.join(b) was the fastest way to combine an array of characters into a single line.