concatenação em C # com cordas internados

StackOverflow https://stackoverflow.com/questions/812503

Pergunta

Eu sei que esta questão foi Concluído mas eu tenho um toque um pouco diferente para ele. Vários têm apontado que esta é otimização prematura, que é inteiramente verdade se eu estivesse pedindo pelo amor de praticidade e somente amor de praticidade. Meu problema está enraizado em um problema prático, mas eu ainda estou curioso, no entanto.

Estou criando um grupo de instruções SQL para criar um script (como em que serão salvos em disco) para recriar um esquema de banco de dados (facilmente muitas muitas centenas de tabelas, vistas, etc.). Isto significa meu concatenação é append-only. StringBuilder, de acordo com MSDN, funciona mantendo uma reserva interna (certamente um char []) e copiar caracteres da cadeia em que e realocando a matriz, conforme necessário.

No entanto, o meu código tem um monte de cordas de repetição ( "CREATE TABLE [", "GO \ n", etc.), o que significa que eu posso tirar proveito deles ser internado mas não se eu usar StringBuilder uma vez que seriam copiados cada vez. As únicas variáveis ??são nomes essencialmente de mesa e de tal forma que já existem como cordas em outros objetos que já estão na memória.

Assim, tanto quanto eu posso dizer que depois da minha dados são lidos e meus objetos criados que detêm as informações de esquema, em seguida, todas as minhas informações corda pode ser reutilizado por internar, sim?

Assumindo que, então não seria uma lista ou LinkedList de strings ser mais rápido porque retêm ponteiros para cordas internados? Então é apenas uma chamada para String.Concat () para uma única alocação de memória de toda a cadeia que é exatamente o comprimento correto.

A lista teria de corda realocar [] de ponteiros internados e uma lista ligada teria que criar nós e modificar ponteiros, para que eles não são "livres" para fazer, mas se eu sou concatenando muitos milhares de internados cordas então eles parece que eles seria mais eficiente.

Agora eu suponho que eu poderia vir acima com alguma heurística na contagem de caracteres para cada instrução SQL e contar cada tipo e ter uma idéia e pré-definir a minha capacidade de StringBuilder para evitar realocar seu char [], mas eu teria de superação por uma margem justa para reduzir a probabilidade de realocação.

Assim, para este caso, o que seria mais rápido para obter uma string concatenada:

  • StringBuilder
  • List de internados cordas
  • LinkedList de internados cordas
  • StringBuilder com uma heurística capacidade
  • Algo mais?

Como questão em separado (I não pode sempre ir para o disco) ao acima: se um único StreamWriter para um arquivo de saída ser mais rápido ainda? Como alternativa, use uma lista ou LinkedList em seguida, gravá-los em um arquivo da lista em vez de primeiro concatenação na memória.

EDIT: Como requerido, o referência (.NET 3,5) para MSDN. Ele diz: "Nova dados é anexado ao final do buffer se o quarto está disponível, caso contrário, um novo buffer, maior é alocado, dados do buffer original é copiado para o novo buffer, em seguida, os novos dados são anexados para o novo buffer. " isso para mim significa um char [] que é realloced para torná-lo maior (que exige a cópia de dados antigos para a matriz redimensionada), em seguida, acrescentar.

Foi útil?

Solução

Para a sua pergunta separada , Win32 tem um WriteFileGather função, que poderia eficientemente escrever uma lista de strings (internados) para o disco - mas que faria uma diferença notável somente quando está sendo chamado de forma assíncrona, como a gravação de disco vai ofuscar todos, mas extremamente grandes concatenations.

Para a sua principal questão : a menos que você está atingindo megabytes de roteiro, ou dezenas de milhares de roteiros, não se preocupe.

Você pode esperar StringBuilder para dobrar o tamanho de alocação em cada realocação. Isso significaria que cresce um buffer de 256 bytes para 1MB é apenas 12 realocações -. Muito bom, dado que a sua estimativa inicial era de 3 ordens de grandeza fora do alvo

Apenas como um exercício, algumas estimativas: a construção de um tampão de 1MB varrerá cerca de 3 MB de memória (fonte 1MB, alvo de 1MB, 1MB devido à copiando durante realloation).

A ligado implementação lista vai varrer sobre 2MB, (e que é ignorando a 8 byte / objecto sobrecarga por referência cadeia). Então, você está salvando 1 MB de memória lê / escreve, em comparação com uma largura de banda de memória típico de 10 Gbit / s e 1 MB de cache L2).

Sim, a implementação da lista é potencialmente mais rápido, e a diferença importa se seus buffers são uma ordem de magnitude maior.

Para o caso mais comum de pequenas cordas, o ganho algorítmica é insignificante, e facilmente compensado por outros fatores: o código StringBuilder é provável no cache de código já, e um alvo viável para microoptimizations. Além disso, usando uma corda significa internamente nenhuma cópia em todos, se a cadeia final cabe o tampão inicial.

Usando uma lista ligada também irá trazer para baixo o problema realocação de O (número de caracteres) para O (número de segmentos) - sua lista de referências de cordas enfrenta o mesmo problema como uma cadeia de caracteres

Então, IMO a implementação de StringBuilder é a escolha certa, otimizado para o caso comum, e degrada principalmente para inesperadamente grandes buffers alvo. Eu esperaria uma implementação de lista para degrade para muitos pequenos segmentos primeiros, que é realmente o tipo extremo de cenário StringBuilder está tentando otimizar.

Ainda assim, seria interessante ver uma comparação entre as duas idéias, e quando a lista começa a ser mais rápido.

Outras dicas

Se eu fosse implementar algo como este, eu nunca iria construir um StringBuilder (ou qualquer outro no buffer de memória do seu script). Gostaria apenas transmiti-lo para o arquivo em vez disso, e fazer todas as cordas em linha.

Aqui está um exemplo de código pseudo (não sintaticamente correto ou qualquer coisa): 

FileStream f = new FileStream("yourscript.sql");
foreach (Table t in myTables)
{
    f.write("CREATE TABLE [");
    f.write(t.ToString());
    f.write("]");
    ....
}

Então, você nunca vai precisar de uma representação em memória do seu script, com toda a cópia de strings.

Opiniões?

Na minha experiência, eu alocado corretamente StringBuilder supera a maioria tudo o mais para grandes quantidades de dados de cadeia. Vale a pena perder um pouco de memória, mesmo, por ultrapassar a sua estimativa em 20% ou 30%, a fim de evitar a realocação. Eu ainda não tem números concretos para apoiá-la usando meus próprios dados, mas dê uma olhada em esta página para mais .

No entanto, como Jeff gosta de apontar, não prematuramente otimizar

EDIT: Como @Colin Burnett apontou, os testes que Jeff conduzida não concordam com testes de Brian, mas o ponto de ligar o post de Jeff estava prestes a otimização prematura em geral. Vários comentadores na página de Jeff observou problemas com seus testes.

Na verdade StringBuilder usa uma instância de String internamente. String é na verdade mutável dentro do System montagem, razão pela qual StringBuilder pode ser construído em cima dela. Você pode fazer StringBuilder um pouquinho mais eficaz através da atribuição de um período razoável quando você criar a instância. Dessa forma, você irá eliminar / reduzir o número de operações de redimensionamento.

Cordas internar obras para cordas que podem ser identificados em tempo de compilação. Assim, se você gerar um monte de cordas durante a execução não será internado a menos que você fazê-lo a si mesmo chamando o método internar na corda.

Internar só irá beneficiá-lo se suas cordas são idênticos. faz quase cordas idênticos não beneficiar de internar, por isso "SOMESTRINGA" e "SOMESTRINGB" será duas cordas diferentes, mesmo se eles estão internados.

Se todos (ou a maioria) das cordas sendo concatenados estão internados, em seguida, o seu esquema que lhe pode dar um aumento de desempenho, como poderia potentally usar menos memória, e poderia economizar alguns grandes cópias de cadeia.

No entanto, se é ou não realmente melhora perf depende do volume de dados que estão processando, porque a melhoria é em fatores constantes, não na ordem de grandeza do algoritmo.

A única maneira de realmente dizer é executar seu aplicativo usando os dois lados e medir os resultados. No entanto, a menos que você está sob pressão de memória significativa e precisa encontrar uma maneira de salvar bytes, eu não iria incomodar e só iria usar o construtor de string.

A StringBuilder não usa um char[] para armazenar os dados, ele usa uma string mutável interno. Isso significa que não há nenhum passo adicional para criar a cadeia final, pois é quando você concatenar uma lista de strings, o StringBuilder apenas retorna o string buffer interno como uma seqüência regular.

As realocações que o StringBuilder faz para aumentar os meios de capacidade que os dados é média copiados um extra de 1,33 vezes. Se você puder fornecer uma boa estimativa sobre o tamanho quando você cria o StringBuilder você pode reduzir esse mesmo furter.

No entanto, para obter um pouco de perspectiva, você deve olhar para o que é que você está tentando otimizar. O que levará a maior parte do tempo em seu programa é realmente escrever os dados no disco, assim mesmo se você pode otimizar o tratamento de sua seqüência para ser duas vezes mais rápido usando um StringBuilder (que é muito improvável), a diferença total ainda só ser uma pequena percentagem.

Você considerou C ++ para isso? Existe uma classe biblioteca que já constrói expressões T / SQL, de preferência escritos em C ++.

Slowest coisa sobre cordas é malloc. Leva 4KB por string em plataformas de 32 bits. Considere otimizar número de seqüência de objetos criados.

Se você precisa usar C #, eu recomendo algo como isto: 

string varString1 = tableName;
string varString2 = tableName;

StringBuilder sb1 = new StringBuilder("const expression");
sb1.Append(varString1);

StringBuilder sb2 = new StringBuilder("const expression");
sb2.Append(varString2);

string resultingString = sb1.ToString() + sb2.ToString();

Eu mesmo ir tão longe como deixar o computador avaliar o melhor caminho para a instanciação objeto com estruturas de injeção de dependência, se perf é tão importante.

Não afiliado a StackOverflow
scroll top