Problema
Existe um problema que um dos criadores desse site (SO) chama de Shlemiel the painter's algorithm.
Um pintor vai pintando a faixa de ultrapassem de uma rodovia. Ele começa muito bem, com alta produtividade. Mas cada dia ele produz menos, até que depois de algumas iterações seu trabalho fica inviável.
Isso ocorre porque ele mantém a lata de tinta em lugar fixo, então ele pinta uma porção da faixa e tem que voltar ao ponto inicial para molhar o pincel. Cada dia ele está mais afastado da lata e demora mais tempo no trajeto do que na pintura.

Imagine esse padrão crescendo dezenas, centenas ou milhares de vezes. Rapidamente inviabiliza.
É o que costuma acontecer com concatenações de coleções de dados, especialmente string. Conforme ela vai crescendo e não cabe no espaço que existia para a versão anterior, precisa ser feita uma nova alocação para suportar todo o tamanho da nova versão. E tem que desalocar a anterior que virou lixo. E vai fragmentando a memória. Tudo isso é custo de tempo. Em algumas linguagens a situação é pior já que uma alteração que nem estoure o limite de tamanho atual já causa uma realocação (por uma boa causa). É o caso de Python.
Solução
O jeito correto é descobrir o tamanho final, ou pelo menos uma aproximação disso e alocar tudo o que precisa, pode ir colocando os textos nessa área alocada. Obviamente que precisa ser feito em uma estrutura que aceita o texto ser alterado, o que não é o caso do tipo string
que é imutável, ou seja, qualquer alteração gera um novo objeto.
O join()
faz exatamente isso que descrevi. Ele descobre o tamanho total necessário - pegando os tamanhos de todas strings que serão concatenadas - aloca todo espaço necessário e vai jogando os textos nesse espaço que ainda não é uma string. No final ele transforma isso em string. Aí o custo é equivalente ao tamanho total do texto que é bem mais curto que andar tudo de novo em cada concatenação.
Note que para poucas concatenações, tipicamente até 4, a concatenação pode ter mesmo desempenho ou até melhor que o join()
. Claro que em volume tão pequeno tanto faz qual é mais rápido.
Alternativas
É claro que o join()
não é a única forma de fazer isso. Você pode fazer manualmente se precisa de algo uma pouco mais complexo que o join()
não atende. Talvez usando um bytearray ou uma lista padrão que são mutáveis (ajuda, mas não é ótimo porque pode precisar de novas alocações, ainda que minimizadas, não precisa em cada alteração, depende da habilidade do programador).
A página do Python também mostra como usar %s
para obter resultado semelhante. A formatação ocorre em uma função que manipula tudo em outra estrutura de dados e só no final que é gerado a string final.
Há quem goste de usar o tipo StringIO
que cuida disso.
Respondi isso em mais detalhes para outras linguagens como Java. E também C#.
Coloquei no GitHub para referência futura.