Czy łączenie łańcuchów pojedynczo jest nieefektywne?

Przypominam sobie z moich dni programowania w C, że gdy dwa łańcuchy są połączone, system operacyjny musi przydzielić pamięć dla połączonego łańcucha, następnie program może skopiować cały tekst łańcucha do nowego obszaru w pamięci, a następnie stara pamięć musi ręcznie być uwolnionym. Jeśli więc jest to wykonywane wielokrotnie, tak jak w przypadku dołączania do listy, system operacyjny musi stale przydzielać coraz więcej pamięci, aby ją zwolnić po kolejnej konkatenacji. O wiele lepszym sposobem na zrobienie tego w C byłoby określenie całkowitego rozmiaru połączonych łańcuchów i przydzielenie niezbędnej pamięci dla całej połączonej listy łańcuchów.

Teraz w nowoczesnych językach programowania (na przykład C #) często widzę, jak zawartość kolekcji jest łączona poprzez iterację kolekcji i dodawanie wszystkich ciągów, pojedynczo, do odwołania do jednego ciągu. Czy to nie jest nieefektywne, nawet przy nowoczesnej mocy obliczeniowej?

Twoje wyjaśnienie, dlaczego jest nieefektywne, jest dokładne, przynajmniej w językach, które znam (C, Java, C #), chociaż nie zgadzam się, że wykonywanie masowych konkatenacji ciągów jest powszechne. W kodzie C # i pracować, jest obfite wykorzystanie StringBuilder, String.Formatitp, które są oszczędności techiniques w celu uniknięcia nadmiernej realokacji pamięci.

Aby uzyskać odpowiedź na twoje pytanie, musimy zadać kolejne pytanie: jeśli tak naprawdę nigdy nie jest to problem łączenia łańcuchów, dlaczego klasy miałyby lubić StringBuilderi StringBufferistnieć ? Dlaczego korzystanie z takich klas jest uwzględnione nawet w podręcznikach i klasach dla początkujących? Dlaczego pozornie dojrzałe porady dotyczące optymalizacji byłyby tak widoczne?

Gdyby większość deweloperów łączących łańcuchy opierała swoją odpowiedź wyłącznie na doświadczeniu, większość powiedziałaby, że to nigdy nie robi różnicy i unikałaby używania takich narzędzi na rzecz „bardziej czytelnej” for (int i=0; i<1000; i++) { strA += strB; }. Ale nigdy tego nie zmierzyli.

Prawdziwą odpowiedź na to pytanie można znaleźć w tej odpowiedzi SO , która ujawnia, że ​​w jednym przypadku, łącząc 50 000 ciągów (które w zależności od aplikacji mogą być częstym zjawiskiem), nawet małe, spowodowało 1000-krotny wzrost wydajności .

Jeśli wydajność dosłownie w ogóle nic nie znaczy, to na pewno połączymy się. Ale ja się nie zgadzam, że przy użyciu alternatywnych (StringBuilder) jest trudna lub mniej czytelny , a zatem byłaby rozsądna praktyka programowania, który nie powinna wywoływać przedwczesne „optymalizacji” obrony.

AKTUALIZACJA:

Myślę, że sprowadza się to do znajomości platformy i stosowania najlepszych praktyk, które niestety nie są uniwersalne . Dwa przykłady z dwóch różnych „współczesnych języków”:

1. W innej odpowiedzi SO , dokładnie odwrotne cechy wydajności (array.join vs + =) okazały się czasami prawdziwe w JavaScript . W niektórych przeglądarkach konkatenacja ciągów wydaje się być optymalizowana automatycznie, aw innych przypadkach tak nie jest. Tak więc zaleceniem (przynajmniej w tym pytaniu SO) jest po prostu konkatenacja i nie martwienie się o to.
2. W innym przypadku kompilator Java może automatycznie zastąpić konkatenację bardziej wydajną konstrukcją, taką jak StringBuilder. Jednak, jak zauważyli inni, jest to nieokreślone, nie jest gwarantowane, a użycie StringBuilder nie szkodzi czytelności. W tym konkretnym przypadku odradzałbym stosowanie konkatenacji dla dużych kolekcji lub poleganie na nieokreślonym zachowaniu kompilatora Java. Podobnie w .NET nigdy nie jest przeprowadzana optymalizacja tego rodzaju .

Nie jest to główny grzech, aby nie znać od razu wszystkich niuansów każdej platformy, ale ignorowanie ważnych problemów związanych z platformą byłoby prawie jak przejście z Javy do C ++ i nie dbanie o zwolnienie pamięci.

To nie jest wydajne z grubsza z powodów, które opisałeś. Ciągi w języku C # i Javie są niezmienne. Operacje na łańcuchach zwracają osobną instancję zamiast modyfikować oryginalną, w przeciwieństwie do C. Podczas łączenia wielu łańcuchów na każdym kroku tworzona jest osobna instancja. Przydzielanie, a później wyrzucanie elementów bezużytecznych może spowodować obniżenie wydajności. Tylko tym razem zarządzanie pamięcią jest obsługiwane przez moduł czyszczenia pamięci.

Zarówno C #, jak i Java wprowadzają klasę StringBuilder jako ciąg zmienny specjalnie dla tego typu zadań. Odpowiednikiem w C byłoby użycie połączonej listy połączonych ciągów zamiast łączenia ich w tablicy. C # oferuje również wygodną metodę łączenia na ciągi do łączenia kolekcji ciągów.

Ściśle mówiąc, jest to mniej wydajne wykorzystanie cykli procesora, więc masz rację. Ale co z czasem programisty, kosztami konserwacji itp. Jeśli dodasz do czasu koszt czasu, prawie zawsze bardziej efektywne jest robienie tego, co najłatwiejsze, a następnie w razie potrzeby profilowanie i optymalizacja wolnych bitów.
„Pierwsza zasada optymalizacji programu: nie rób tego. Druga zasada optymalizacji programu (tylko dla ekspertów!): Nie rób tego jeszcze”.

Bardzo trudno powiedzieć o wydajności bez praktycznego testu. Ostatnio byłem bardzo zaskoczony, gdy dowiedziałem się, że w JavaScript naiwne łączenie łańcuchów było zwykle szybsze niż zalecane rozwiązanie „twórz listę i dołącz” (przetestuj tutaj , porównaj t1 z t4). Nadal zastanawiam się, dlaczego tak się dzieje.

Kilka pytań, które możesz zadać, uzasadniając wydajność (szczególnie w odniesieniu do użycia pamięci): 1) jak duży jest mój wkład? 2) Jak inteligentny jest mój kompilator? 3) w jaki sposób moje środowisko wykonawcze zarządza pamięcią? Nie jest to wyczerpujące, ale jest punktem wyjścia.

1. Jak duży jest mój wkład?

   Złożone rozwiązanie często ma ustalony narzut, na przykład w postaci dodatkowych operacji do wykonania lub potrzebnej dodatkowej pamięci. Ponieważ te rozwiązania są zaprojektowane do obsługi dużych przypadków, implementatorzy zwykle nie będą mieli problemu z wprowadzeniem tego dodatkowego kosztu, ponieważ zysk netto jest ważniejszy niż mikrooptymalizacja kodu. Tak więc, jeśli twój wkład jest wystarczająco mały, naiwne rozwiązanie może mieć lepszą wydajność niż złożone, choćby w celu uniknięcia tego narzutu. (trudniejsze jest określenie, co jest „wystarczająco małe”)

2. Jak inteligentny jest mój kompilator?

   Wiele kompilatorów jest wystarczająco inteligentnych, aby „optymalizować” zmienne, które są zapisywane, ale nigdy nie są odczytywane. Podobnie dobry kompilator może również konwertować naiwne łączenie łańcuchów na wykorzystanie biblioteki (rdzeniowej), a jeśli wiele z nich jest wykonywanych bez odczytów, nie ma potrzeby konwertowania ich z powrotem na ciąg między tymi operacjami (nawet jeśli wydaje się, że twój kod źródłowy właśnie to robi). Nie wiem, czy kompilatory tam to robią, ani w jakim stopniu jest to wykonywane (Java AFAIK przynajmniej zamienia kilka konkatek w tym samym wyrażeniu na sekwencję operacji StringBuffer), ale jest to możliwe.

3. Jak mój środowisko wykonawcze zarządza pamięcią?

   We współczesnych procesorach wąskim gardłem zwykle nie jest procesor, lecz pamięć podręczna; jeśli twój kod uzyskuje dostęp do wielu „odległych” adresów pamięci w krótkim czasie, czas potrzebny na przeniesienie całej tej pamięci między poziomami pamięci podręcznej przewyższa większość optymalizacji w użytych instrukcjach. Ma to szczególne znaczenie w środowiskach wykonawczych z generacyjnymi śmieciarkami, ponieważ ostatnio tworzone zmienne (na przykład w tym samym zakresie funkcji) zwykle będą miały ciągłe adresy pamięci. Te środowiska wykonawcze rutynowo przenoszą pamięć tam iz powrotem między wywołaniami metod.

   Jednym ze sposobów, w jaki może to wpływać na łączenie łańcuchów (zastrzeżenie: jest to szalone przypuszczenie, nie jestem wystarczająco kompetentny, aby powiedzieć na pewno), byłoby, gdyby pamięć dla naiwnej została przydzielona blisko reszty kodu, który z niej korzysta (nawet jeśli przydziela i zwalnia go wiele razy), podczas gdy pamięć dla obiektu biblioteki została przydzielona daleko od niego (więc wiele kontekstów zmienia się podczas obliczania kodu, biblioteka zużywa, kod oblicza więcej, itp. generuje wiele braków pamięci podręcznej). Oczywiście w przypadku dużych danych wejściowych OTOH i tak brakuje pamięci podręcznej, więc problem wielokrotnych alokacji staje się bardziej wyraźny.

To powiedziawszy, nie zalecam stosowania tej lub innej metody, tylko to, że testowanie, profilowanie i testy porównawcze powinny poprzedzać jakąkolwiek teoretyczną analizę wydajności, ponieważ większość systemów jest obecnie zbyt skomplikowana, aby w pełni zrozumieć bez głębokiej wiedzy specjalistycznej w tej dziedzinie.

Joel jakiś czas temu napisał świetny artykuł na ten temat. Jak zauważyli inni, jest to w dużej mierze zależne od języka. Ze względu na sposób, w jaki łańcuchy są implementowane w C (zakończone zerem, bez pola długości), standardowa procedura biblioteki strcat jest bardzo nieefektywna. Joel przedstawia alternatywę z niewielką zmianą, która jest znacznie bardziej wydajna.

Czy łączenie łańcuchów pojedynczo jest nieefektywne?

Nie.

Czy czytałeś „The Sad Tragedy of Micro-Optimization Theatre” ?