31

Dúvida

Gostaria de saber que padrões de projeto ou outras coisa "nerds" foram aplicado a essa classe StringBuffer. Por que a String cria novos objetos em uma concatenação? Até onde sei, a String também é uma Array de caracteres (me corrijam se estiver errado).


Fiz uma pergunta semelhante e tive uma boa resposta, StringBuffer e StringBuilder nessa pergunta entendi a necessidade dos espaços Adicionais na "Array".


Baixo verá código e os teste de desempenho, se você programa em Java deveria colocar na prática.


Código do Teste


int loop = 1*100000;

        StringBuffer sb = new StringBuffer();
        long time = System.currentTimeMillis();

        for (int i = 0; i < loop; i++)
            sb.append("a");

        System.out.println("Total execuções: " + loop);
        System.out.println("Tempo total de excecução com StringBuffer: "
                + (System.currentTimeMillis() - time) + "ms.");

        String s = "";
        time = System.currentTimeMillis();
        for (int i = 0; i < loop; i++)
            s += "a";

        System.out.println("Total de execuções: " + loop);
        System.out.println("Tempo total de excecução concatenando strings: "
                + (System.currentTimeMillis() - time) + "ms.");

Resultados dos testes:


Tentativa 1

Total execuções: 100000.
Tempo total de excecução com StringBuffer: 18ms.
Total de execuções: 100000.
Tempo total de excecução concatenando strings: 10556ms.


Tentativa 2

Total execuções: 200000.
Tempo total de excecução com StringBuffer: 23ms.
Total de execuções: 200000.
Tempo total de excecução concatenando strings: 44216ms.


Tentativa 3

Total execuções: 300000.
Tempo total de excecução com StringBuffer: 30ms.
Total de execuções: 300000.
Tempo total de excecução concatenando strings: 94886ms.

0

3 Respostas 3

26

Resolvi responder porque uma das respostas está certa em sua essência mas dá um motivo errado para a lentidão.

Como é formada uma string

Está correta a ideia que uma string em Java (o mesmo vale para C# e várias outras linguagens) internamente é representada por um array de chars, sendo que este tipicamente possui 2 bytes (que individualmente não necessariamente representam caracteres, mas isso é outro assunto). Veja comentário abaixo do hkotsubo que há otimização em versões mais recentes que pode ocupar apenas 1 byte.

Imutabilidade

Inicialmente um array, que tem tamanho fixo, é alocado para guardar o texto da string. Acontece que uma string é imutável. Toda vez que você vai alterar qualquer parte da string, precisa ocorrer outra alocação de memória. Imagine que fazer 100 mil alocações de memória não é nada barato. E pior, não é só a alocação que ocorre, todos os elementos do array anterior precisam ser copiados para o novo array alocado, com a devida alteração ocorrendo no meio deste processo.

Alocações em demasia

Isto se torna especialmente problemático quando você está aumentando o tamanho da string sucessivamente. Isto é chamado de Shlemiel the painter's algorithm(en). Onde 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 seu trabalho fica inviável. Isto 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.

Mostra que cada vez que anda fica mais longe

O problema é o garbage collector?

Claro que um volume de alocações enorme que logo em seguida já não possuem referências vivas permitem que o garbage collector possa coletá-las. Isso é uma possibilidade que pode aumentar ainda mais a lentidão. Mas note que o garbage colletor faz a coleta de uma vez só, então esta coleta não consome tanto tempo assim. E isto normalmente só ocorre quando você realmente está com falta de memória. É possível que nenhuma coleta ocorra até seu término, em um programa simples.

Portanto o GC não é o motivo para a lentidão e sim as alocações e cópias na memória. 100 mil alocações com cópia custam absurdamente mais que todo o algoritmo do GC liberando a memória, já que ele é otimizado para fazer isso de uma vez em cada chamada usando um método generacional de coleta(en).

Usando o StringBuilder

O StringBuilder resolve isso fazendo pré-alocações de memória e permitindo que o conteúdo seja mutável. Ou seja, ele evita muitas alocações quando você está apenas querendo mudar uma porção da string e principalmente quando está aumentando seu tamanho sucessivamente.

Ele já possui uma porção de memória alocada minimizando bastante a quantidade de alocações necessárias. O algoritmo mais comum usado para determinar o tamanho é que toda vez que o novo texto não caiba na alocação atual, ele cria uma nova com o dobro do tamanho da anterior. Isto já minimiza muito a quantidade de alocações e consequentemente a cópia de dados.

Adicionalmente você pode determinar o tamanho inicial do array utilizado pelo StringBuilder através do construtor StringBuilder(int capacity) quando já tem uma noção do tamanho que a string terá. Obviamente também pode mudar o tamanho da alocação no meio do processo com o método expandCapacity(int minimumCapacity), quando se justifique.

A grosso modo a string é um algoritmo O(n), o StringBuilder é O(log n).

Por ser uma estrutura mutável e pré-alocada, não ocorre o problema do pintor de rodovia. A lata está sempre próxima do pintor.

Existem outras técnicas para evitar alocações extras, mas a mais conhecida e mais universal é o StringBuilder. Não sei se o Java faz alguma otimização, mas o C#, por exemplo, pode otimizar um código string texto = "abc" + "def" + "ghi" + "jkl";. Mesmo um string texto = str1 + str2 + str3 + str4; pode ser otimizado pelo compilador como string texto = string.concat(str1, str2, str3, str3); onde a alocação ocorrerá uma única vez.

Escolhendo a melhor estrutura de dados

Por padrão usamos a string normal, e em casos de otimização o StringBuilder passa ser útil. Pode dar vontade de usar sempre ele, mas ele tem seus malefícios (já citados pelo Math e utluiz). Não devemos fazer otimização prematura.

Padrões de projeto são criados para facilitar o trabalho de algo que se repete com frequência. Desde "sempre" adotamos padrões de projeto. Alguns padrões de projeto são apenas recomendações, são exemplos que devem ser seguidos. Outros se transformam em biblioteca, como é o caso do StringBuilder. Outros são tão úteis que se transformam em construções de linguagem.

Como isto parece não estar claro para todos, respondi outra pergunta já existente sobre o assunto.

Coloquei no GitHub para referência futura.

2
  • 1
    “Não sei se o Java faz alguma otimização”. Para ficar completa a resposta e tirar qualquer dúvida: sim, Java otimiza as concatenações “óbvias” feitas com o operador +. Se todas as strings são constantes, elas são concatenadas em tempo de compilação. Se existem variáveis, o compilador gera um código que usa o próprio StringBuilder para cada expressão de concatenações com +. A vantagem de o programador criar o StringBuilder manualmente está em loops ou qualquer concatenação que ocorra em expressões separadas (o compilador geraria um novo StringBuilder a cada vez, o que é custoso).
    – marcus
    Commented 16/09/2016 às 23:12
  • "sendo que este possui 2 bytes sempre" - a partir do Java 9, não é mais "sempre": baeldung.com/java-9-compact-string#java
    – hkotsubo
    Commented 29/04/2021 às 21:07
22

Tanto String quanto StringBuilder internamente trabalham com vetor de caracteres, basta olhar na classe delas:

String.java

public final class String
    implements java.io.Serializable, Comparable<String>, CharSequence {
    /** The value is used for character storage. */
    private final char value[];

AbstractStringBuilder.java (superclasse da StringBuilder e StringBuffer)

abstract class AbstractStringBuilder implements Appendable, CharSequence {
    /**
     * The value is used for character storage.
     */
    char[] value;

    /**
     * The count is the number of characters used.
     */
    int count;

A eficiência da StringBuilder se dá justamente por causa dos espaços a mais que ela deixa de reserva em seu vetor, esse espaço permite que na maioria dos casos seja colocado mais conteúdo dentro dele sem que se exceda sua capacidade, quando o tamanho do vetor passa a não ser suficiente ele aumenta para poder comportar esse novo valor. De acordo com o código:

AbstractStringBuilder.java

private void ensureCapacityInternal(int minimumCapacity) {
    // overflow-conscious code
    if (minimumCapacity - value.length > 0)
        expandCapacity(minimumCapacity);
}

void expandCapacity(int minimumCapacity) {
    int newCapacity = value.length * 2 + 2;
    if (newCapacity - minimumCapacity < 0)
        newCapacity = minimumCapacity;
    if (newCapacity < 0) {
        if (minimumCapacity < 0) // overflow
            throw new OutOfMemoryError();
        newCapacity = Integer.MAX_VALUE;
    }
    value = Arrays.copyOf(value, newCapacity);
}

vemos que o tamanho do novo vetor é 2*(tamanho do vetor anterior)+2, se mesmo assim esse tamanho não for o suficiente ele define seu novo tamanho como o mínimo necessário para armazenar o novo valor. Em seguida o conteúdo do vetor antigo é copiado para o novo vetor.

Respondendo suas perguntas:

Gostaria de saber que padrões de projeto ou outras coisa "nerds" foram aplicado a essa classe

Padrões de projeto geralmente se referem a estrutura das classes, ou seja, não existe nada de padrões de projeto relacionado ao fato do StringBuilder se expandir conforme o necessário. Qualquer aplicação de padrão de projeto na StringBuilder e superclasses não são relevantes para o assunto em questão

Por que a String cria novos objetos em uma concatenação?

Por que a String é imutável, logo seu propósito não é ficar expandindo a cada concatenação, para isso existe o StringBuilder.

Existem alguns benefícios em ser imutável, olhando nessa pergunta Why do we need immutable class? eu transcrevo alguns para cá uma vantagem em ser imutável:

  • Thread-safe: Objetos imutáveis podem ser compartilhados com segurança entre múltiplas threads.

  • Simplicidade: cada classe tem um estado apenas.

  • Robustez: se você passa um objeto imutável para um método você não corre o risco de que esse método mude o valor de seu objeto. Pois do mesmo jeito que você passa primitivos para um método e sabe que esses primitivos não podem ter seu valor alterado a String se comporta da mesma maneira, assim como as classes wrappers dos primitivos: Integer, Double, Float, Boolean, etc.

17

A hierarquia

As classes java.lang.StringBuffer e java.lang.StringBuilder estendem a classe abstrata java.lang.AbstractStringBuilder e possuem exatamente a mesma interface.

Analisando o código da classe abstrata AbstractStringBuilder, vemos que ela possui dois atributos principais:

char value[];
int count;

Ali são armazenados os caracteres e o tamanho real do mesmo.

Sobre o buffer

Todos sabem que String é um tipo que armazena um conjunto de caracteres. No Java, uma String é imutável, isto é, não pode ter o conteúdo modificado, assim como seu tamanho.

O problema com isso é que para criar novas Strings, por exemplo, através da concatenação de duas ou mais Strings, uma nova String como o tamanho total delas deve ser criada em memória. Se várias dessas operações forem executadas em sequência, a JVM precisará alocar novos blocos de memória e executar o Garbage Collector para desalocar o que não é usado a todo momento. Isso é muito "custoso" em termos de desempenho.

Então, o StringBuffer surge para resolver o problema. Um StringBuffer nada mais é do que uma String com um Buffer, isto é, um espaço reservado para novos caracteres que pode ser modificado e torna desnecessário, até certo ponto, alocar mais memória a todo momento.

Dessa forma, se alguém quer somar 100 Strings, cada uma com aproximadamente 10 caracteres, ao invés de fazer 99 concatenações de String, basta criar um StringBuffer com um buffer de 1000 caracteres e adicionar todas as Strings lá, sem overhead de alocação e coletamento.

O tamanho inicial

Em muitas situações é importante definir o tamanho inicial do buffer com um tamanho médio do que se pretende usar.

Ao fazer new StringBuffer() ou new StringBuilder(), isto é, sem definir um tamanho inicial, estamos subutilizando a classe. A capacidade inicial do buffer é de apenas 16 caracteres:

public StringBuilder() {
    super(16);
}

Isso significa que, se adicionarmos mais de 16 caracteres, um novo buffer terá que ser alocado.

Aumentando o tamanho

Mas não é o fim do mundo. O sistema de expansão é um tanto "inteligente".

Se você estoura a capacidade do buffer, quanto ele vai alocar a mais? Vai pelo menos dobrar!

Veja o cálculo da nova capacidade do buffer no método expandCapacity da classe AbstractStringBuilder:

void expandCapacity(int minimumCapacity) {
    int newCapacity = (value.length + 1) * 2;
    if (newCapacity < 0) {
        newCapacity = Integer.MAX_VALUE;
    } else if (minimumCapacity > newCapacity) {
        newCapacity = minimumCapacity;
    }
    value = Arrays.copyOf(value, newCapacity);
}

StringBuffer ou StringBuilder?

Ohe o Javadoc (links estão no início da resposta) e note que ambas tem exatamente a mesma interface. Qual a diferença?

Dizemos que a classe StringBuffer é sincronizada, enquanto a classe StringBuilder não é sincronizada.

Isso significa que a primeira pode ser usada concorrentemente por múltiplas threads, mas também terá o desempenho reduzido pela sincronização e pelos bloqueis, quanto a segunda deve ser reservada para uso exclusivo por uma thread, porém maximizando o desempenho.


Para maiores detalhes, ver minha outra resposta aqui no SO.

1
  • 1
    As três respostas @math, bigown e utluiz, me ajudaram a entender mais detalhadamente. E espero que ajude outros.
    – noNihongo
    Commented 16/05/2014 às 18:24

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .