Czy lepiej jest ponownie użyć StringBuilder w pętli?

101

Mam pytanie związane z wydajnością dotyczące używania StringBuilder. W bardzo długiej pętli manipuluję a StringBuilderi przekazuję go do innej metody, takiej jak ta:

for (loop condition) {
    StringBuilder sb = new StringBuilder();
    sb.append("some string");
    . . .
    sb.append(anotherString);
    . . .
    passToMethod(sb.toString());
}

Czy tworzenie instancji StringBuilderw każdym cyklu pętli jest dobrym rozwiązaniem? I czy zamiast tego wywołanie usuwania jest lepsze, jak poniżej?

StringBuilder sb = new StringBuilder();
for (loop condition) {
    sb.delete(0, sb.length);
    sb.append("some string");
    . . .
    sb.append(anotherString);
    . . .
    passToMethod(sb.toString());
}
Pier Luigi
źródło

Odpowiedzi:

69

Drugi jest około 25% szybszy w moim mini-benchmarku.

public class ScratchPad {

    static String a;

    public static void main( String[] args ) throws Exception {
        long time = System.currentTimeMillis();
        for( int i = 0; i < 10000000; i++ ) {
            StringBuilder sb = new StringBuilder();
            sb.append( "someString" );
            sb.append( "someString2"+i );
            sb.append( "someStrin4g"+i );
            sb.append( "someStr5ing"+i );
            sb.append( "someSt7ring"+i );
            a = sb.toString();
        }
        System.out.println( System.currentTimeMillis()-time );
        time = System.currentTimeMillis();
        StringBuilder sb = new StringBuilder();
        for( int i = 0; i < 10000000; i++ ) {
            sb.delete( 0, sb.length() );
            sb.append( "someString" );
            sb.append( "someString2"+i );
            sb.append( "someStrin4g"+i );
            sb.append( "someStr5ing"+i );
            sb.append( "someSt7ring"+i );
            a = sb.toString();
        }
        System.out.println( System.currentTimeMillis()-time );
    }
}

Wyniki:

25265
17969

Zwróć uwagę, że dotyczy to środowiska JRE 1.6.0_07.


W oparciu o pomysły Jona Skeeta w edycji, oto wersja 2. Jednak te same wyniki.

public class ScratchPad {

    static String a;

    public static void main( String[] args ) throws Exception {
        long time = System.currentTimeMillis();
        StringBuilder sb = new StringBuilder();
        for( int i = 0; i < 10000000; i++ ) {
            sb.delete( 0, sb.length() );
            sb.append( "someString" );
            sb.append( "someString2" );
            sb.append( "someStrin4g" );
            sb.append( "someStr5ing" );
            sb.append( "someSt7ring" );
            a = sb.toString();
        }
        System.out.println( System.currentTimeMillis()-time );
        time = System.currentTimeMillis();
        for( int i = 0; i < 10000000; i++ ) {
            StringBuilder sb2 = new StringBuilder();
            sb2.append( "someString" );
            sb2.append( "someString2" );
            sb2.append( "someStrin4g" );
            sb2.append( "someStr5ing" );
            sb2.append( "someSt7ring" );
            a = sb2.toString();
        }
        System.out.println( System.currentTimeMillis()-time );
    }
}

Wyniki:

5016
7516
Epaga
źródło
4
Dodałem zmianę w mojej odpowiedzi, aby wyjaśnić, dlaczego tak się dzieje. Przyjrzę się dokładniej za jakiś czas (45 minut). Zauważ, że wykonanie konkatenacji w wywołaniach dołączania zmniejsza nieco sens używania StringBuilder w pierwszej kolejności :)
Jon Skeet
3
Ciekawe byłoby również zobaczyć, co się stanie, jeśli odwrócisz dwa bloki - JIT nadal „rozgrzewa” StringBuildera podczas pierwszego testu. Może to być nieistotne, ale warto spróbować.
Jon Skeet
1
Nadal wybrałbym pierwszą wersję, ponieważ jest czystsza . Ale dobrze, że wykonałeś benchmark :) Następna sugerowana zmiana: spróbuj # 1 z odpowiednią pojemnością przekazaną do konstruktora.
Jon Skeet
25
Użyj sb.setLength (0); zamiast tego jest to najszybszy sposób na opróżnienie zawartości StringBuilder przed ponownym utworzeniem obiektu lub użyciem .delete (). Zauważ, że nie dotyczy to StringBuffer, jego kontrole współbieżności niwelują przewagę szybkości.
P Arrayah
1
Nieefektywna odpowiedź. P Arrayah i Dave Jarvis mają rację. setLength (0) jest zdecydowanie najbardziej efektywną odpowiedzią. StringBuilder jest obsługiwany przez tablicę znaków i jest zmienny. W momencie wywołania .toString () tablica char jest kopiowana i używana do odtworzenia niezmiennego ciągu. W tym momencie mutowalny bufor StringBuilder może zostać ponownie użyty, po prostu przesuwając wskaźnik wstawiania z powrotem do zera (przez .setLength (0)). sb.toString tworzy kolejną kopię (niezmienną tablicę znaków), więc każda iteracja wymaga dwóch buforów w przeciwieństwie do metody .setLength (0), która wymaga tylko jednego nowego bufora na pętlę.
Chris
25

W filozofii pisania solidnego kodu zawsze lepiej jest umieścić StringBuilder w pętli. W ten sposób nie wychodzi poza kod, dla którego jest przeznaczony.

Po drugie, największe ulepszenie w StringBuilder polega na nadaniu mu początkowego rozmiaru, aby uniknąć jego powiększania się, gdy pętla działa

for (loop condition) {
  StringBuilder sb = new StringBuilder(4096);
}
Piotr
źródło
1
Zawsze możesz określić zakres całej sprawy za pomocą nawiasów klamrowych, w ten sposób nie masz Stringbuildera na zewnątrz.
Epaga
@Epaga: Nadal jest poza samą pętlą. Tak, nie zanieczyszcza zewnętrznego zakresu, ale jest to nienaturalny sposób pisania kodu poprawiającego wydajność, który nie został zweryfikowany w kontekście .
Jon Skeet
Albo jeszcze lepiej, postaw całość na własną metodę. ;-) Ale słyszę: kontekst.
Epaga
Jeszcze lepiej zainicjuj z oczekiwanym rozmiarem zamiast sumy dowolnej liczby (4096) Twój kod może zwrócić String, który odwołuje się do znaku char [] o rozmiarze 4096 (zależy od JDK; o ile pamiętam, było to w przypadku 1.4)
kohlerm
24

Jeszcze szybciej:

public class ScratchPad {

    private static String a;

    public static void main( String[] args ) throws Exception {
        long time = System.currentTimeMillis();
        StringBuilder sb = new StringBuilder( 128 );

        for( int i = 0; i < 10000000; i++ ) {
            // Resetting the string is faster than creating a new object.
            // Since this is a critical loop, every instruction counts.
            //
            sb.setLength( 0 );
            sb.append( "someString" );
            sb.append( "someString2" );
            sb.append( "someStrin4g" );
            sb.append( "someStr5ing" );
            sb.append( "someSt7ring" );
            setA( sb.toString() );
        }

        System.out.println( System.currentTimeMillis()-time );
    }

    private static void setA( String aString ) {
        a = aString;
    }
}

W filozofii pisania solidnego kodu, wewnętrzne działanie metody powinno być ukryte przed obiektami, które ją używają. Dlatego z punktu widzenia systemu nie ma różnicy, czy ponownie zadeklarujesz StringBuilder w pętli, czy poza pętlą. Ponieważ zadeklarowanie go poza pętlą jest szybsze i nie sprawia, że ​​kod jest bardziej skomplikowany do odczytania, należy ponownie użyć obiektu zamiast go odtworzyć.

Nawet jeśli kod był bardziej skomplikowany i wiesz na pewno, że wąskim gardłem była instancja obiektu, skomentuj go.

Trzy przebiegi z tą odpowiedzią:

$ java ScratchPad
1567
$ java ScratchPad
1569
$ java ScratchPad
1570

Trzy przebiegi z drugą odpowiedzią:

$ java ScratchPad2
1663
2231
$ java ScratchPad2
1656
2233
$ java ScratchPad2
1658
2242

Chociaż nie jest to istotne, ustawienie StringBuilderpoczątkowego rozmiaru bufora da niewielki zysk.

Dave Jarvis
źródło
3
To zdecydowanie najlepsza odpowiedź. StringBuilder jest obsługiwany przez tablicę znaków i jest zmienny. W momencie wywołania .toString () tablica char jest kopiowana i używana do odtworzenia niezmiennego ciągu. W tym momencie mutowalny bufor StringBuilder może zostać ponownie użyty, po prostu przesuwając wskaźnik wstawiania z powrotem do zera (przez .setLength (0)). Te odpowiedzi sugerujące przydzielenie zupełnie nowego StringBuildera na pętlę nie wydają się świadczyć o tym, że .toString tworzy kolejną kopię, więc każda iteracja wymaga dwóch buforów w przeciwieństwie do metody .setLength (0), która wymaga tylko jednego nowego bufora na pętlę.
Chris
12

Okej, teraz rozumiem, co się dzieje i ma to sens.

Miałem wrażenie, że toStringwłaśnie przekazałem element bazowy char[]do konstruktora String, który nie pobrał kopii. Kopia byłaby wtedy wykonywana przy następnej operacji „zapisu” (np delete.). Wydaje mi się, że tak było w przypadku StringBufferniektórych poprzednich wersji. (Teraz nie jest). Ale nie - toStringpo prostu przekazuje tablicę (wraz z indeksem i długością) do publicznej wiadomościString konstruktora, który pobiera kopię.

Tak więc w przypadku „ponownego wykorzystania StringBuilder” naprawdę tworzymy jedną kopię danych na łańcuch, używając przez cały czas tej samej tablicy znaków w buforze. Oczywiście tworzenie nowego za StringBuilderkażdym razem tworzy nowy podstawowy bufor - a następnie ten bufor jest kopiowany (nieco bezcelowo, w naszym konkretnym przypadku, ale robione ze względów bezpieczeństwa) podczas tworzenia nowego ciągu.

Wszystko to prowadzi do tego, że druga wersja jest zdecydowanie bardziej wydajna - ale jednocześnie powiedziałbym, że jest to brzydszy kod.

Jon Skeet
źródło
Tylko trochę zabawnych informacji o .NET, sytuacja jest inna. NET StringBuilder wewnętrznie modyfikuje zwykły obiekt "string", a metoda toString po prostu zwraca go (oznaczając go jako niemodyfikowalny, więc kolejne manipulacje StringBuilder spowodują jego odtworzenie). Tak więc typowa sekwencja "new StringBuilder-> zmodyfikuj to-> do String" nie spowoduje wykonania żadnej dodatkowej kopii (tylko w celu rozszerzenia pamięci lub jej zmniejszenia, jeśli wynikowa długość łańcucha jest znacznie mniejsza niż jego pojemność). W Javie ten cykl zawsze tworzy przynajmniej jedną kopię (w StringBuilder.toString ()).
Ivan Dubrov
Sun JDK pre-1.5 miał optymalizację, którą zakładałeś: bugs.sun.com/bugdatabase/view_bug.do?bug_id=6219959
Dan Berindei
9

Ponieważ wydaje mi się, że nie zostało to jeszcze wskazane, z powodu optymalizacji wbudowanych w kompilator Sun Java, który automatycznie tworzy StringBuilders (StringBuffers przed J2SE 5.0), gdy widzi konkatenacje ciągów, pierwszy przykład w pytaniu jest równoważny:

for (loop condition) {
  String s = "some string";
  . . .
  s += anotherString;
  . . .
  passToMethod(s);
}

Co jest bardziej czytelne, IMO, lepsze podejście. Twoje próby optymalizacji mogą przynieść zyski na jednej platformie, ale potencjalnie stracić inne.

Ale jeśli naprawdę masz problemy z wydajnością, na pewno zoptymalizuj. Zacząłbym jednak od jawnego określenia rozmiaru buforu StringBuilder, według Jona Skeeta.

Jack Leow
źródło
4

Współczesna maszyna JVM jest naprawdę sprytna w takich sprawach. Nie odgadłbym tego po raz drugi i zrobiłbym coś hakerskiego, co jest trudniejsze w utrzymaniu / czytelności ... chyba że wykonasz odpowiednie testy porównawcze z danymi produkcyjnymi, które potwierdzą nietrywialną poprawę wydajności (i udokumentujesz to;)

Stu Thompson
źródło
Gdzie „nietrywialne” jest kluczowe - testy porównawcze mogą pokazać, że jedna forma jest proporcjonalnie szybsza, ale bez żadnej wskazówki, ile czasu zajmuje rzeczywista aplikacja :)
Jon Skeet
Zobacz punkt odniesienia w mojej odpowiedzi poniżej. Drugi sposób jest szybszy.
Epaga
1
@Epaga: Twój test porównawczy niewiele mówi o poprawie wydajności w prawdziwej aplikacji, gdzie czas potrzebny na wykonanie alokacji StringBuilder może być trywialny w porównaniu z resztą pętli. Dlatego kontekst jest ważny w benchmarkingu.
Jon Skeet
1
@Epaga: Dopóki nie zmierzy tego swoim prawdziwym kodem, nie będziemy mieli pojęcia, jak naprawdę jest to ważne. Jeśli jest dużo kodu dla każdej iteracji pętli, podejrzewam, że nadal będzie to nieistotne. Nie wiemy, co jest w „...”
Jon Skeet
1
(Nie zrozum mnie źle, przy okazji - twoje wyniki testów porównawczych są same w sobie bardzo interesujące. Fascynują mnie mikroznakowania. Po prostu nie lubię wyginać mojego kodu z kształtu przed wykonaniem testów w prawdziwym życiu.)
Jon Skeet
4

Opierając się na moim doświadczeniu w tworzeniu oprogramowania w systemie Windows, powiedziałbym, że wyczyszczenie StringBuilder podczas pętli ma lepszą wydajność niż tworzenie instancji StringBuilder z każdą iteracją. Wyczyszczenie go zwalnia tę pamięć do natychmiastowego nadpisania bez konieczności dodatkowego przydziału. Nie jestem wystarczająco zaznajomiony z kolektorem śmieci w Javie, ale myślę, że zwalnianie i brak ponownej alokacji (chyba że twój następny ciąg powiększa StringBuilder) jest bardziej korzystne niż tworzenie instancji.

(Moja opinia jest sprzeczna z tym, co sugerują wszyscy inni. Hmm. Czas to porównać.)

cfeduke
źródło
Chodzi o to, że więcej pamięci i tak musi zostać ponownie przydzielone, ponieważ istniejące dane są używane przez nowo utworzony String na końcu poprzedniej iteracji pętli.
Jon Skeet
Och, to ma sens, myślałem, że toString alokuje i zwraca nową instancję ciągu, a bufor bajtów dla kreatora jest czyszczony zamiast ponownego przydzielania.
cfeduke
Wzorzec Epagi pokazuje, że czyszczenie i ponowne użycie to zysk w stosunku do instancji przy każdym przejściu.
cfeduke
1

Powodem, dla którego wykonanie „setLength” lub „delete” poprawia wydajność, jest głównie to, że kod „uczy się” odpowiedniego rozmiaru bufora, a mniej przy alokacji pamięci. Generalnie zalecam zezwolenie kompilatorowi na optymalizację ciągów . Jeśli jednak wydajność jest krytyczna, często wstępnie obliczam oczekiwany rozmiar bufora. Domyślny rozmiar StringBuilder to 16 znaków. Jeśli przekroczysz to, musisz zmienić rozmiar. Zmiana rozmiaru jest przyczyną utraty wydajności. Oto kolejny mini-test, który to ilustruje:

private void clear() throws Exception {
    long time = System.currentTimeMillis();
    int maxLength = 0;
    StringBuilder sb = new StringBuilder();

    for( int i = 0; i < 10000000; i++ ) {
        // Resetting the string is faster than creating a new object.
        // Since this is a critical loop, every instruction counts.
        //
        sb.setLength( 0 );
        sb.append( "someString" );
        sb.append( "someString2" ).append( i );
        sb.append( "someStrin4g" ).append( i );
        sb.append( "someStr5ing" ).append( i );
        sb.append( "someSt7ring" ).append( i );
        maxLength = Math.max(maxLength, sb.toString().length());
    }

    System.out.println(maxLength);
    System.out.println("Clear buffer: " + (System.currentTimeMillis()-time) );
}

private void preAllocate() throws Exception {
    long time = System.currentTimeMillis();
    int maxLength = 0;

    for( int i = 0; i < 10000000; i++ ) {
        StringBuilder sb = new StringBuilder(82);
        sb.append( "someString" );
        sb.append( "someString2" ).append( i );
        sb.append( "someStrin4g" ).append( i );
        sb.append( "someStr5ing" ).append( i );
        sb.append( "someSt7ring" ).append( i );
        maxLength = Math.max(maxLength, sb.toString().length());
    }

    System.out.println(maxLength);
    System.out.println("Pre allocate: " + (System.currentTimeMillis()-time) );
}

public void testBoth() throws Exception {
    for(int i = 0; i < 5; i++) {
        clear();
        preAllocate();
    }
}

Wyniki pokazują, że ponowne użycie obiektu jest około 10% szybsze niż utworzenie bufora o oczekiwanym rozmiarze.

brianegge
źródło
1

LOL, pierwszy raz widziałem ludzi porównujących wydajność, łącząc string w StringBuilder. W tym celu, jeśli użyjesz „+”, może to być jeszcze szybsze; D. Celem użycia StringBuilder do przyspieszenia pobierania całego ciągu jako koncepcji „lokalności”.

W scenariuszu, w którym często pobierasz wartość String, która nie wymaga częstych zmian, Stringbuilder umożliwia wyższą wydajność pobierania ciągów. I to jest cel używania Stringbuildera ... proszę nie testować MIS podstawowego celu tego ...

Niektórzy mówili, że samolot leci szybciej. Dlatego przetestowałem to na moim rowerze i stwierdziłem, że samolot porusza się wolniej. Czy wiesz, jak ustawiam ustawienia eksperymentu; D

Ting Choo Chiaw
źródło
1

Nie znacznie szybciej, ale z moich testów wynika, że ​​jest średnio o kilka milisek szybszy przy użyciu 1.6.0_45 64 bity: użyj StringBuilder.setLength (0) zamiast StringBuilder.delete ():

time = System.currentTimeMillis();
StringBuilder sb2 = new StringBuilder();
for (int i = 0; i < 10000000; i++) {
    sb2.append( "someString" );
    sb2.append( "someString2"+i );
    sb2.append( "someStrin4g"+i );
    sb2.append( "someStr5ing"+i );
    sb2.append( "someSt7ring"+i );
    a = sb2.toString();
    sb2.setLength(0);
}
System.out.println( System.currentTimeMillis()-time );
johnmartel
źródło
1

Najszybszym sposobem jest użycie „setLength”. Nie będzie wymagać operacji kopiowania. Sposób tworzenia nowego StringBuildera powinien być całkowicie wyłączony . Powolne działanie StringBuilder.delete (int start, int end) jest spowodowane tym, że ponownie skopiuje tablicę dla części zmieniającej rozmiar.

 System.arraycopy(value, start+len, value, start, count-end);

Następnie StringBuilder.delete () zaktualizuje StringBuilder.count do nowego rozmiaru. Chociaż StringBuilder.setLength () po prostu upraszcza aktualizację StringBuilder.count do nowego rozmiaru.

Shen liang
źródło
0

Pierwsza jest lepsza dla ludzi. Jeśli druga jest nieco szybsza w niektórych wersjach niektórych maszyn JVM, to co z tego?

Jeśli wydajność jest tak krytyczna, pomiń StringBuilder i napisz własne. Jeśli jesteś dobrym programistą i weźmiesz pod uwagę sposób, w jaki Twoja aplikacja korzysta z tej funkcji, powinieneś być w stanie zrobić to jeszcze szybciej. Wart? Prawdopodobnie nie.

Dlaczego to pytanie jest traktowane jako „ulubione pytanie”? Ponieważ optymalizacja wydajności to świetna zabawa, bez względu na to, czy jest praktyczna, czy nie.

Dongilmore
źródło
To nie jest tylko kwestia akademicka. Chociaż przez większość czasu (czytaj 95%) wolę czytelność i łatwość konserwacji, są naprawdę przypadki, w których małe ulepszenia powodują duże różnice ...
Pier Luigi
OK, zmienię odpowiedź. Jeśli obiekt udostępnia metodę, która pozwala na jego wyczyszczenie i ponowne użycie, zrób to. Najpierw sprawdź kod, jeśli chcesz się upewnić, że czyszczenie jest wydajne; może zwolni prywatną tablicę! Jeśli jest to efektywne, przydziel obiekt poza pętlę i użyj go ponownie w środku.
Dongilmore
0

Nie wydaje mi się, aby próba optymalizacji wydajności w ten sposób miała sens. Dzisiaj (2019) obie statystyki działają przez około 11 sekund dla pętli 100.000.000 na moim laptopie I5:

    String a;
    StringBuilder sb = new StringBuilder();
    long time = 0;

    System.gc();
    time = System.currentTimeMillis();
    for (int i = 0; i < 100000000; i++) {
        StringBuilder sb3 = new StringBuilder();
        sb3.append("someString");
        sb3.append("someString2");
        sb3.append("someStrin4g");
        sb3.append("someStr5ing");
        sb3.append("someSt7ring");
        a = sb3.toString();
    }
    System.out.println(System.currentTimeMillis() - time);

    System.gc();
    time = System.currentTimeMillis();
    for (int i = 0; i < 100000000; i++) {
        sb.setLength(0);
        sb.delete(0, sb.length());
        sb.append("someString");
        sb.append("someString2");
        sb.append("someStrin4g");
        sb.append("someStr5ing");
        sb.append("someSt7ring");
        a = sb.toString();
    }
    System.out.println(System.currentTimeMillis() - time);

==> 11000 ms (deklaracja wewnątrz pętli) i 8236 ms (deklaracja poza pętlą)

Nawet jeśli uruchamiam programy do dedykowania adresów z kilkoma miliardami pętli, różnica wynosi 2 sekundy. dla 100 milionów pętli nie robi żadnej różnicy, ponieważ te programy działają godzinami. Pamiętaj również, że sytuacja wygląda inaczej, jeśli masz tylko jedną instrukcję append:

    System.gc();
    time = System.currentTimeMillis();
    for (int i = 0; i < 100000000; i++) {
        StringBuilder sb3 = new StringBuilder();
        sb3.append("someString");
            a = sb3.toString();
    }
    System.out.println(System.currentTimeMillis() - time);

    System.gc();
    time = System.currentTimeMillis();
    for (int i = 0; i < 100000000; i++) {
        sb.setLength(0);
        sb.delete(0, sb.length());
        sb.append("someString");
        a = sb.toString();
    }
    System.out.println(System.currentTimeMillis() - time);

==> 3416 ms (pętla wewnętrzna), 3555 ms (pętla zewnętrzna) Pierwsza instrukcja, która tworzy StringBuilder w pętli, jest w tym przypadku szybsza. A jeśli zmienisz kolejność wykonywania, jest to znacznie szybsze:

    System.gc();
    time = System.currentTimeMillis();
    for (int i = 0; i < 100000000; i++) {
        sb.setLength(0);
        sb.delete(0, sb.length());
        sb.append("someString");
        a = sb.toString();
    }
    System.out.println(System.currentTimeMillis() - time);

    System.gc();
    time = System.currentTimeMillis();
    for (int i = 0; i < 100000000; i++) {
        StringBuilder sb3 = new StringBuilder();
        sb3.append("someString");
            a = sb3.toString();
    }
    System.out.println(System.currentTimeMillis() - time);

==> 3638 ms (pętla zewnętrzna), 2908 ms (pętla wewnętrzna)

Pozdrawiam, Ulrich

Ulrich K.
źródło
-2

Zadeklaruj raz i przydziel za każdym razem. Jest to koncepcja bardziej pragmatyczna i nadająca się do ponownego wykorzystania niż optymalizacja.

Peter Mortensen
źródło