Nie (nad)używaj String.split
Kolejny wpis o tym, jak pracować z danymi. We wpisie o przepełnieniu wspomniałem, że używanie String.split do
dzielenia rekordu csv nie jest najlepszym wyborem z punktu widzenia wydajności. Dziś o tym, dlaczego i co w zamian.
Jak podzielić ciąg znaków?
Najprostsze zadania rekrutacyjne mają gdzie w sobie wszyte dzielenie Stringa na części. Zazwyczaj też, gdy dochodzi do potrzeby podzielenia ciągu
znaków, to kod wygląda mniej więcej tak:
Listing 1. Przykładowy podział ciągu
@Benchmark
@Warmup(iterations = LOOP, time = TIME)
@Measurement(iterations = LOOP, time = TIME)
@Fork(FORK)
public void simpleSplitByComa(Blackhole blackhole) {
lines.forEach(line -> {
final String[] split = line.split(COMA);
blackhole.consume(split);
});
}
Używam JMH, żeby nie było :) Uruchomimy i dostaniemy jakieś wyniki. O nich za chwilę. Co jednak stanie się, gdy nasz plik z jakiegoś powodu zamiast
przecinka , używa pipe | jako separatora?
Listing 2. Przykładowy podział ciągu z |
@Benchmark
@Warmup(iterations = LOOP, time = TIME)
@Measurement(iterations = LOOP, time = TIME)
@Fork(FORK)
public void simpleSplitByComa(Blackhole blackhole) {
linesPipe.forEach(line -> {
final String[] split = line.split(PIPE);
blackhole.consume(split);
});
}
Tu zaczyna się robić ciekawie. Popatrzmy na wyniki (LOOP=10, TIME=1s, FORK=5, COMA=",", PIPE="|"):
Listing 3. Wyniki pierwszych testów
Benchmark Mode Cnt Score Error Units
SplitBenchmark.simpleSplitByComa thrpt 50 528.728 ± 3.788 ops/s
SplitBenchmark.simpleSplitByPipe thrpt 50 50.193 ± 0.469 ops/s
Dlaczego jest taka duża, dziesięciokrotna, różnica? Tajemnica leży w sposobie implementacji String.split w Javie. Metoda ta przyjmuje jako parametr
wyrażenie regularne, ale ma wszyte pewne optymalizacje. Jeżeli wyrażenie jest jednoelementowe i nie jest znakiem specjalnym, czyli jednym
z .$|()[{^?*+\, to wywoływany jest uproszczony mechanizm podziału. W skrócie odpalana jest pętla.
Własna pętla z ArrayList
Napiszmy zatem kawałek kodu, który będzie wykorzystywał pętlę:
Listing 4. Kod z wykorzystaniem pętli i ArrayList
String[] splitWithArrayList(String line, String splitter) {
int currentIndex = -1;
int previousIndex = 0;
ArrayList<String> el = new ArrayList<>();
do {
previousIndex = currentIndex;
currentIndex = line.indexOf(splitter, currentIndex + 1);
el.add(line.substring(previousIndex + splitter.length(), currentIndex >= 0 ? currentIndex : line.length()));
} while (currentIndex != -1);
return el.toArray(new String[el.size()]);
}
Nie jest on idealny, ale działa całkiem przyjemnie. Jeżeli teraz odpalimy testy podobne do tych z listingów 1 i 2, ale z wykorzystaniem naszego rozwiązania dostaniemy:
Listing 5. Wyniki drugiej rundy testów
Benchmark Mode Cnt Score Error Units
SplitBenchmark.simpleSplitByComa thrpt 50 528.728 ± 3.788 ops/s
SplitBenchmark.simpleSplitByPipe thrpt 50 50.193 ± 0.469 ops/s
SplitBenchmark.splitWithArrayListByComa thrpt 50 556.154 ± 18.611 ops/s
SplitBenchmark.splitWithArrayListByPipe thrpt 50 584.662 ± 3.904 ops/s
O! Ciekawe! Prawda?
Nasza pętla jest jakieś 10% szybsza niż ta w API dla przecinka, ale dla pipe jest już 11 krotnie szybsza. W dodatku czas jest, mniej więcej stały niezależnie od znaku podziału.
Co można jeszcze zrobić?
Czysto teoretycznie poprzedni kod jest wystarczający. W miarę stabilny jeśli chodzi o wydajność i dość prosty w użyciu. Spróbujmy jednak zrobić coś jeszcze. Czy da się go bardziej „docisnąć”? I czy wpłynie to znacząco na wyniki.
Krok pierwszy zmieńmy implementację listy
Tworzenie ArrayList nie jest kosztowne, ale jeżeli elementów jest więcej niż inicjalna wielkość listy, to musimy powiększać tablicę, która jest pod
spodem. Ta operacja jest już kosztowna. Zmieńmy więc kod z listingu 4 na taki trochę bardziej uniwersalny, a test zamienimy na trzy niezależne testy:
Listing 6. Bardziej uniwersalny kod
private String[] splitWithList(String line, String splitter, List<String> el) {
int currentIndex = -1;
int previousIndex = 0;
do {
previousIndex = currentIndex;
currentIndex = line.indexOf(splitter, currentIndex + 1);
el.add(line.substring(previousIndex + splitter.length(), currentIndex >= 0 ? currentIndex : line.length()));
} while (currentIndex != -1);
return el.toArray(new String[el.size()]);
}
//…
String[] splitWithArrayList(String line, String splitter) {
return splitWithList(line, splitter, new ArrayList<>());
}
String[] splitWithUndersizedArrayList(String line, String splitter) {
return splitWithList(line, splitter, new ArrayList<>(1));
}
String[] splitWithLinkedList(String line, String splitter) {
return splitWithList(line, splitter, new LinkedList<>());
}
Pomysł jest następujący. Pierwszy test pozostaje bez zmian. Drugi test inicjujemy za małą tablicą. Wymusimy więc jej przeskalowanie. W trzecim
teście podamy na wejście LinkedList, która może swobodnie rosnąć, ale przepisanie jej do tablicy jest kosztowniejsze niż w przypadku ArrayList.
Listing 7. Wyniki po zmianie implementacji listy
Benchmark Mode Cnt Score Error Units
SplitBenchmark.simpleSplitByComa thrpt 50 528.728 ± 3.788 ops/s
SplitBenchmark.simpleSplitByPipe thrpt 50 50.193 ± 0.469 ops/s
SplitBenchmark.splitWithArrayListByComa thrpt 50 556.154 ± 18.611 ops/s
SplitBenchmark.splitWithArrayListByPipe thrpt 50 584.662 ± 3.904 ops/s
SplitBenchmark.splitWithUndersizedArrayListByComa thrpt 50 450.623 ± 29.186 ops/s
SplitBenchmark.splitWithUndersizedArrayListByPipe thrpt 50 497.201 ± 2.932 ops/s
SplitBenchmark.splitWithLinkedListByComa thrpt 50 635.944 ± 11.953 ops/s
SplitBenchmark.splitWithLinkedListByPipe thrpt 50 615.200 ± 19.024 ops/s
Użycie LinkedList daje nam od 5 do 15% wydajności. Jednocześnie użycie zbyt małej ArrayList powoduje, że tracimy 15-20%. To może spróbujmy
określić, jak duża powinna być ta lista?
Krok drugi – usunięcie listy
Efektywnie nie potrzebujemy listy. Możemy od razu stworzyć tablicę i do niej dodać elementy. Pytanie, jak duża powinna być tablica? Możemy na początek spróbować naiwnej implementacji. Policzmy, ile elementów dzielących jest w ciągu, a następnie podzielmy ciąg znaków:
Listing 8. Naiwna implementacja bez użycia listy
String[] splitWithoutList(String line, String splitter) {
int currentIndex = -1;
int previousIndex = 0;
int count = 0;
while ((currentIndex = line.indexOf(splitter, currentIndex + 1)) != -1) {
count++;
}
String[] el = new String[count + 1];
currentIndex = -1;
for (int i = 0; i < count; i++) {
currentIndex = line.indexOf(splitter, currentIndex + splitter.length());
el[i] = line.substring(previousIndex, currentIndex);
previousIndex = currentIndex + splitter.length();
}
el[count] = line.substring(previousIndex);
return el;
}
Od razu widać problem z tym podejściem. Każdy ciąg obrabiamy dwa razy. W testach jednak przyspieszyliśmy o prawię połowę
Listing 9. Wyniki po usunięciu listy
Benchmark Mode Cnt Score Error Units
SplitBenchmark.simpleSplitByComa thrpt 50 528.728 ± 3.788 ops/s
SplitBenchmark.simpleSplitByPipe thrpt 50 50.193 ± 0.469 ops/s
SplitBenchmark.splitWithArrayListByComa thrpt 50 556.154 ± 18.611 ops/s
SplitBenchmark.splitWithArrayListByPipe thrpt 50 584.662 ± 3.904 ops/s
SplitBenchmark.splitWithUndersizedArrayListByComa thrpt 50 450.623 ± 29.186 ops/s
SplitBenchmark.splitWithUndersizedArrayListByPipe thrpt 50 497.201 ± 2.932 ops/s
SplitBenchmark.splitWithLinkedListByComa thrpt 50 635.944 ± 11.953 ops/s
SplitBenchmark.splitWithLinkedListByPipe thrpt 50 615.200 ± 19.024 ops/s
SplitBenchmark.splitWithoutListByComa thrpt 50 687.346 ± 30.577 ops/s
SplitBenchmark.splitWithoutListByPipe thrpt 50 713.126 ± 6.620 ops/s
Krok trzeci – znamy wygląd danych
Pliki CSV mają swoją strukturę. Rekordy mają tyle samo elementów. Możemy zatem zaryzykować i założyć, że znamy rozmiar tablicy przed przystąpieniem do podziału. Wystarczy lekko przerobić kod z listingu 8:
Listing 10. Implementacja ze znanym rozmiarem rekordu
String[] splitWithConstantSize(String line, String splitter, int expectedSize) {
int currentIndex = -1;
int previousIndex = 0;
String[] el = new String[expectedSize];
for (int i = 0; i < expectedSize - 1; i++) {
currentIndex = line.indexOf(splitter, currentIndex + 1);
el[i] = line.substring(previousIndex, currentIndex);
previousIndex = currentIndex + splitter.length();
}
el[expectedSize - 1] = line.substring(previousIndex);
return el;
}
I przyjrzyjmy się teraz testom:
Listing 11. Wyniki dla stałej wielkości tablicy
Benchmark Mode Cnt Score Error Units
SplitBenchmark.simpleSplitByComa thrpt 50 528.728 ± 3.788 ops/s
SplitBenchmark.simpleSplitByPipe thrpt 50 50.193 ± 0.469 ops/s
SplitBenchmark.splitWithArrayListByComa thrpt 50 556.154 ± 18.611 ops/s
SplitBenchmark.splitWithArrayListByPipe thrpt 50 584.662 ± 3.904 ops/s
SplitBenchmark.splitWithUndersizedArrayListByComa thrpt 50 450.623 ± 29.186 ops/s
SplitBenchmark.splitWithUndersizedArrayListByPipe thrpt 50 497.201 ± 2.932 ops/s
SplitBenchmark.splitWithLinkedListByComa thrpt 50 635.944 ± 11.953 ops/s
SplitBenchmark.splitWithLinkedListByPipe thrpt 50 615.200 ± 19.024 ops/s
SplitBenchmark.splitWithoutListByComa thrpt 50 687.346 ± 30.577 ops/s
SplitBenchmark.splitWithoutListByPipe thrpt 50 713.126 ± 6.620 ops/s
SplitBenchmark.splitWithConstantSizeByComa thrpt 50 950.738 ± 5.649 ops/s
SplitBenchmark.splitWithConstantSizeByPipe thrpt 50 949.535 ± 4.591 ops/s
Zrobiło się praktycznie dwa razy szybciej. Ale naprawdę ciekawie zrobi się za chwilę.
Jak wyglądają dane?
Otóż rekord ma postać ID, INT, INT lub ID| INT| INT. Pomiędzy separatorem a wartością jest spacja. Możemy zatem uruchomić nasze testy z trochę
innym zestawem parametrów, czyli LOOP=10, TIME=1s, FORK=5, COMA=", ", PIPE="| " i zobaczymy, co się stanie:
Listing 12. Wyniki po zmianie separatora
Benchmark Mode Cnt Score Error Units
SplitBenchmark.simpleSplitByComa thrpt 50 129.491 ± 0.855 ops/s
SplitBenchmark.simpleSplitByPipe thrpt 50 47.856 ± 0.299 ops/s
SplitBenchmark.splitWithArrayListByComa thrpt 50 549.743 ± 15.154 ops/s
SplitBenchmark.splitWithArrayListByPipe thrpt 50 550.466 ± 20.599 ops/s
SplitBenchmark.splitWithUndersizedArrayListByComa thrpt 50 472.255 ± 10.419 ops/s
SplitBenchmark.splitWithUndersizedArrayListByPipe thrpt 50 436.556 ± 16.904 ops/s
SplitBenchmark.splitWithLinkedListByComa thrpt 50 606.787 ± 12.394 ops/s
SplitBenchmark.splitWithLinkedListByPipe thrpt 50 622.788 ± 5.220 ops/s
SplitBenchmark.splitWithoutListByComa thrpt 50 705.784 ± 5.939 ops/s
SplitBenchmark.splitWithoutListByPipe thrpt 50 699.103 ± 10.082 ops/s
SplitBenchmark.splitWithConstantSizeByComa thrpt 50 938.579 ± 8.510 ops/s
SplitBenchmark.splitWithConstantSizeByPipe thrpt 50 937.464 ± 8.676 ops/s
Jak wspomniałem wcześniej. Jeżeli ciąg ma więcej niż jeden znak, to String.split nie wchodzi w szybką ścieżkę i traktuje cały ciąg, jak wyrażenie
regularne. Procesowanie wyrażeń regularnych jest wolne.
Podsumowanie
To kiedy używać String.split? Odpowiedź nie jest oczywista. Napisanie kodu, który będzie nam dzielił ciągi, nie zostanie miło przyjęte w czasie code
review. Możemy wykorzystać bibliotekę Apache Commons-Lang3 i znajdującą się tam metodę StringUtils.split. Jej działanie jest zbliżone do wersji
z ArrayList:
Listing 13. Wyniki dla StringUtils.spit
Benchmark Mode Cnt Score Error Units
SplitBenchmark.splitCommonsLang3ByComa thrpt 50 502.572 ± 18.569 ops/s
SplitBenchmark.splitWithCommonsLang3ByPipe thrpt 50 514.341 ± 12.676 ops/s
# i dla separatorów dłuższych niż jeden znak
SplitBenchmark.splitCommonsLang3ByComa thrpt 50 211.362 ± 4.979 ops/s
SplitBenchmark.splitWithCommonsLang3ByPipe thrpt 50 212.413 ± 5.620 ops/s
Choć zauważalnie wolniejsze w przypadku dłuższych separatorów. Cóż… koszty. Jednocześnie String.split sprawdzi się jeżeli chcemy dzielić dane według
wzorca, który nie jest stałym tekstem. W tym momencie użycie wyrażeń regularnych jest bardzo dobrym rozwiązaniem.
To, co tutaj opisałem, to oczywiście mikrooptymalizacje, które powinny być wykonywane już na samym końcu. Przy przetwarzaniu plików, prędzej urwiesz 30-40% czasu wykonania za pomocą rozsądnie zrobionego wczytywania, czy wykorzystując szybsze dyski, niż kombinując ze sposobem dzielenia poszczególnych rekordów. Pamiętaj też, że wdrażając tego typu poprawki, musisz zmierzyć czy rzeczywiście wnoszą one zasadniczą wartość. Bez tego tylko skomplikujesz sobie kod, bo przecież będziesz musiał go utrzymywać.