É ineficiente concatenar cadeias uma de cada vez?

Lembro-me dos meus dias de programação em C que, quando duas cadeias são unidas, o sistema operacional deve alocar memória para a cadeia unida, então o programa pode copiar todo o texto da cadeia para a nova área da memória, então a memória antiga deve ser manualmente ser lançado. Portanto, se isso for feito várias vezes, como no caso de ingressar em uma lista, o sistema operacional precisará alocar constantemente mais e mais memória, apenas para liberá-la após a próxima concatenação. Uma maneira muito melhor de fazer isso em C seria determinar o tamanho total das cadeias combinadas e alocar a memória necessária para toda a lista de cadeias unidas.

Agora, nas linguagens de programação modernas (C #, por exemplo), normalmente vejo o conteúdo das coleções unindo-se iterando a coleção e adicionando todas as cadeias, uma de cada vez, a uma única referência de cadeia. Isso não é ineficiente, mesmo com o poder da computação moderna?

Sua explicação sobre por que é ineficiente é precisa, pelo menos nas linguagens que eu conheço (C, Java, C #), embora eu discorde que é universalmente comum executar grandes quantidades de concatenação de cadeias. No código C # eu trabalho, há o uso abundante de StringBuilder, String.Formatetc., que são todos de memória salvar techiniques para evitar o excesso de realocação.

Portanto, para chegar à resposta da sua pergunta, precisamos fazer outra pergunta: se nunca é realmente um problema concatenar strings, por que as classes gostam StringBuildere StringBufferexistem ? Por que o uso de tais aulas está incluído em livros e aulas de programação semi-iniciantes? Por que conselhos de otimização aparentemente pré-maduros seriam tão proeminentes?

Se a maioria dos desenvolvedores de concatenação de strings baseasse sua resposta puramente na experiência, a maioria diria que isso nunca faz diferença e evitaria o uso de tais ferramentas em favor do "mais legível" for (int i=0; i<1000; i++) { strA += strB; }. Mas eles nunca mediram isso.

A resposta real para essa pergunta pode ser encontrada nesta resposta do SO , que revela que, em um caso, ao concatenar 50.000 seqüências de caracteres (que, dependendo do aplicativo, podem ser uma ocorrência comum), mesmo pequenas, resultaram em um desempenho de 1000x .

Se o desempenho literalmente não significa nada, concatenar. Mas eu discordo que o uso de alternativas (StringBuilder) é difícil ou menos legível e, portanto, seria uma prática de programação razoável que não deve invocar a defesa de "otimização prematura".

ATUALIZAR:

Acho que isso se resume a conhecer sua plataforma e seguir suas melhores práticas, que infelizmente não são universais . Dois exemplos de duas "línguas modernas" diferentes:

1. Em outra resposta do SO , as características exatas de desempenho opostas (array.join vs + =) foram algumas vezes verdadeiras no JavaScript . Em alguns navegadores, a concatenação de strings parece ser otimizada automaticamente e, em outros casos, não é. Portanto, a recomendação (pelo menos nessa pergunta do SO) é apenas concatenar e não se preocupar com isso.
2. Em outro caso, um compilador Java pode substituir automaticamente a concatenação por uma construção mais eficiente, como StringBuilder. No entanto, como outros salientaram, isso é indeterminista, não garantido, e o uso do StringBuilder não prejudica a legibilidade. Nesse caso em particular, eu recomendaria não usar a concatenação para grandes coleções ou confiar em um comportamento indeterminista do compilador Java. Da mesma forma, no .NET, nenhuma otimização da classificação é executada .

Não é exatamente um pecado fundamental não conhecer todas as nuances de todas as plataformas imediatamente, mas ignorar questões importantes da plataforma como essa seria quase como mudar de Java para C ++ e não se importar com a desalocação de memória.

Não é eficiente, aproximadamente pelos motivos que você descreveu. Strings em C # e Java são imutáveis. As operações em cadeias retornam uma instância separada, em vez de modificar a original, ao contrário de C. Ao concatenar várias cadeias, uma instância separada é criada a cada etapa. A alocação e a coleta posterior de lixo dessas instâncias não utilizadas pode causar um impacto no desempenho. Somente esse gerenciamento de memória é tratado pelo coletor de lixo.

C # e Java introduzem uma classe StringBuilder como uma sequência mutável especificamente para esse tipo de tarefa. Um equivalente em C seria usar uma lista vinculada de seqüências de caracteres concatenadas em vez de juntá-las a uma matriz. O C # também oferece um conveniente método Join em strings para ingressar em uma coleção de strings.

A rigor, é menos eficiente o uso dos ciclos da CPU, portanto, você está correto. Mas e quanto ao tempo do desenvolvedor, custos de manutenção etc. Se você adicionar o custo de tempo à equação, é quase sempre mais eficiente fazer o que for mais fácil e, se necessário, criar um perfil e otimizar os bits lentos.
"A primeira regra de otimização de programas: não faça isso. A segunda regra de otimização de programas (apenas para especialistas!): Não faça isso ainda."

É muito difícil dizer algo sobre desempenho sem um teste prático. Recentemente, fiquei muito surpreso ao descobrir que, no JavaScript, uma concatenação de seqüências ingênuas era geralmente mais rápida que a solução recomendada "criar lista e associar" (teste aqui , compare t1 com t4). Ainda estou intrigado com o motivo disso acontecer.

Algumas perguntas que você pode fazer ao raciocinar sobre desempenho (especialmente com relação ao uso de memória) são: 1) qual é o tamanho da minha entrada? 2) quão inteligente é meu compilador? 3) como meu tempo de execução gerencia a memória? Isso não é exaustivo, mas é um ponto de partida.

1. Qual é o tamanho da minha opinião?

   Uma solução complexa geralmente possui uma sobrecarga fixa, talvez na forma de operações extras a serem executadas ou talvez na memória extra necessária. Como essas soluções são projetadas para lidar com casos grandes, os implementadores geralmente não têm problemas em introduzir esse custo extra, pois o ganho líquido é mais importante do que otimizar o código. Portanto, se sua entrada for suficientemente pequena, uma solução ingênua pode ter um desempenho melhor que o complexo, mesmo que seja apenas para evitar essa sobrecarga. (determinar o que é "suficientemente pequeno" é a parte mais difícil)

2. Quão inteligente é meu compilador?

   Muitos compiladores são inteligentes o suficiente para "otimizar" variáveis ​​gravadas, mas nunca lidas. Da mesma forma, um bom compilador também pode converter uma concatenação de seqüência de caracteres ingênua em uso de uma biblioteca (principal) e, se muitas delas são feitas sem nenhuma leitura, não há necessidade de convertê-la novamente em uma seqüência de caracteres entre essas operações (mesmo se seu código fonte parece fazer exatamente isso). Não sei dizer se algum compilador faz isso ou não, ou até que ponto isso é feito (o AFAIK Java pelo menos substitui vários concats na mesma expressão por uma sequência de operações StringBuffer), mas é uma possibilidade.

3. Como meu tempo de execução gerencia a memória?

   Nas CPUs modernas, o gargalo geralmente não é o processador, mas o cache; se o seu código acessar muitos endereços de memória "distantes" em pouco tempo, o tempo necessário para mover toda a memória entre os níveis de cache supera a maioria das otimizações nas instruções usadas. Isso é de particular importância em tempos de execução com coletores de lixo geracionais, pois as variáveis ​​criadas mais recentemente (dentro do mesmo escopo de função, por exemplo) geralmente estarão em endereços de memória contíguos. Esses tempos de execução também rotineiramente movem a memória para frente e para trás entre as chamadas de método.

   Uma maneira de afetar a concatenação de strings (exoneração de responsabilidade: esse é um palpite, não sei o suficiente para ter certeza) seria se a memória do ingênuo fosse alocada perto do restante do código que o utiliza (mesmo se ele o aloca e libera várias vezes), enquanto a memória do objeto da biblioteca foi alocada longe dele (portanto, o contexto muda enquanto o código calcula, a biblioteca consome, o código calcula mais, etc, gera muitas falhas de cache). Obviamente, para grandes entradas OTOH, o cache perde de qualquer maneira, então o problema de várias alocações se torna mais pronunciado.

Dito isso, não estou defendendo o uso deste ou daquele método, apenas que testes, perfis e benchmarking devem preceder qualquer análise teórica sobre desempenho, uma vez que a maioria dos sistemas hoje em dia é muito complexa para entender completamente sem uma profunda experiência no assunto.

Joel escreveu um ótimo artigo sobre esse assunto há um tempo. Como alguns outros apontaram, é fortemente dependente do idioma. Devido à maneira como as strings são implementadas em C (zero terminado, sem campo de comprimento), a rotina da biblioteca strcat padrão é muito ineficiente. Joel apresenta uma alternativa com apenas uma pequena mudança que é muito mais eficiente.

É ineficiente concatenar cadeias uma de cada vez?

Não.

Você leu 'A triste tragédia do teatro de micro-otimização' ?