How to speed up string concatenation in Python?

Question

In the code below concatenation is the bottleneck. As you can see i've tried some sophisticated methods to speed this up, but its bloody slow anyway. I would like to know if there is anything i can do to make it faste.

BTW both plain and secret are data read from binary file and they are quite big (around 1mb)

x = b''
if len(plain) < len(secret*8):
    return False
i = 0

for secByte in secret:
    for j in range(8):
        z = setBit(plain[i],0,getBit(secByte,j))
        #x += bytes([z])
        x = x.join([b"", bytes([z])])
        #x = array.array("B",(int(z) for z in x.join([b"", bytes([z])]))).tostring()
        i = i+1

Answer 1

Python's lists have O(1) append, at least in the amortized sense. Instead of doing the join in the innermost list, you could build one big list and then join them at the end. This will turn your algorithm from O(N^2) to O(N). It's tough to give you working code without knowing exactly what your setBit() and getBit() functions are doing, but something like:

L = []
for secByte in secret:
    for j in range(8):
         z = ...
         L.append(z)
x = b"".join(L)

Answer 2

I don't think you should be using string concatenation at all for this. It would be better to create a mutable bytearray of the full size of the final data and then set each byte. This is very much O(N) and for what you are doing using a bytearray is much more natural than string manipulation:

x = bytearray(len(secret)*8)   # creates an array of zero bytes
i = 0
for secByte in secret:
    for j in range(8):
        x[i] = setBit(plain[i], 0, getBit(secByte, j))
        i += 1