🚀 go-pugleaf

M.M. wrote:

> Mogę poprosić jakieś przykłady na poparcie tego? Proszę, bo chcę
> zrozumieć co masz na myśli.

Są zasadniczo trzy główne przypadki użycia danych tekstowych:

1. Budowanie napisu.
2. Pełnoskalowe użycie zbudowanego napisu, z funkcjami wyszukiwania,
regexpami itp.
3. Ograniczone użycie zbudowanego napisu, które traktuje jego zawartość
jako całość i gdzie nie interesuje nas, skąd się napis wziął.

C++ stawia na 2, koślawie łącząc go z 1 i całkowicie ignorując 3.
Tak się jednak składa, że to 3. jest kluczowe dla wydajnego
przetwarzania danych wielkoskalowych, a 2. służy do pokazywania
studentom i zastosowań nieistotnych w rodzaju program_options itp.
drobnicy, gdzie stringów jest maksymalnie kilka tysięcy. Ja mówię
o miliardach. 3 sprowadza się do wzbogaconej o lukier syntaktyczny
std::pair<const char*, std::size_t> i jest wyjątkowo niemedialny.
Pozwala jednak zrobić cuda, w razie potrzeby nawet na zatarcie
źródła pochodzenia danych -- treść może pochodzić z std::string,
mogę sobie skonstruować ten wrapper na gołej tablicy bajtów w pamięci
itp. -- po stronie konsumenta danych tego nie widać. W C++17
(wreszcie!) wprowadzono string_view, choć jak to w komitecie
bywa, zatrzymali się w połowie drogi i nie wyciągnęli kluczowych
wniosków. Choćby takich, że taka warstwa prezentacji jest generyczna
i nadaje się do wszelkich innych koncepcyjnie równoważnych rzeczy,
np. do wyjęcia gołej zawartości std::vector<double>. Trzeba
było wprowadzić std::view<T> i specjalizować go dla znaków.
Ja coś takiego zrobiłem kilka lat temu i nazwałem segmentem.
Sprawdza się znakomicie.

Przyjęcia 2 jako wersji wiodącej i połączenie jej z 1 narzuca
na 1 dramatyczne ograniczenia, które rykoszetem odbijają się na 2.
Pomijając już sprawę wielowątkowości, z chęci redukcji narzutu 
pamięciowego i ogólnych własności takiej konstrukcji wynika,
że string może rosnąć tylko w jedną stronę. Przyjęto, że na
końcu. Wydajnie doklejać znaczków na początek się nie da, bo
trzeba kopiować całe dane w prawo. Ale skoro string może
rosnąć i dane są trzymane w obszarze ciągłym, to kiedyś ten
obszar się wyczerpie i trzeba będzie go powiększać. Kiedy?
Jeśli chcemy oszczędzać pamięć, a w przypadku danych o dużym
wolumenie nawet musimy, to rezerwa musi być mała. Idealnie
jednoznakowa. No ale wtedy na append() kopiuję cały string
co znaczek i budowanie stringa wybucha mi do czasu kwadratowego.
Genialne. No to od drugiej strony: powiększam rezerwę wykładniczo,
co mi złożoność worst case redukuje do O(n log n). Ale moje
dane mogą mieć długość paskudnie interferującą z algorytmem
powiększania i po systemie latają wielkie bufory z krótką
treścią. A ja nie mam na nie miejsca. Można stosować różne
kompromisy między tymi skrajnościami i nawet się z nich doktoryzować,
ale rozwiązaniem poprawnym jest zauważenie, że budowanie stringa
i jego użycie to dwie zupełnie różne czynności i każda z nich
powinna być zaimplementowana optymalnie. Builder nie nakłada
na mnie żadnych ograniczeń na to, od której strony buduję finalny
napis, trywialna implementacja równie dobrze poradzi sobie z obiema.
Podczas budowania nie muszę też niczego kopiować, bo nie ma
najmniejszej potrzeby, by dane tymczasowe znajdowały się w pamięci
ciągłej. Skończy mi się buforek, to sobie dodam następny, jak
w std::deque. Otrzymuję funkcjonalność znacznie bogatszą niż
oryginał przy gwarantowanej i bardzo niskiej złożoności czasowej
operacji. Jeśli alokator poza standardowym API wspiera też pewne
specjalne konstrukcje, np. alokację bloków o ustalonej wielkości,
to gwarancje złożonościowe mogą być nawet formalne, a nie tylko
spodziewane. A gdy wreszcie string powstaje, mogę sprawdzić, czy
już takiego nie budowałem i zwrócić gotowy element, a nie alokować
duplikat. Porównania na równość sprowadzą mi się wtedy do porównania
wskaźników na bufor, bez konieczności zaglądania w znaczki. A to od
razu dramatycznie przyspiesza kontenery unordered. I mnóstwo innych
tego typu implikacji.

Tylko tu trzeba wyjść od skali rzeczywistego zastosowania i popatrzeć
na problem całościowo, bo rozwiązanie opiera się na efekcie synergii
wynikającej z dostosowania różnych składowych biblioteki, a nie z 
ulepszania jednej klasy. Tylko z efektów można wywnioskować, że
komitet nie ma zwyczaju tak działać i wolą się bawić modelowaniem
pojedynczego stringa, by w przykładach ładnie wyglądał. Problem w tym,
że C++ nie ma większego sensu w projektach małoskalowych (wygodniej
przetworzysz sobie swoje dane w Javie lub innym Pythonie, choćby 
dlatego, że nie musisz zarządzać czasem życia obiektu), a do 
wielkoskalowych się nie nadaje ze względu na ograniczenia projektowe
swojej biblioteki standardowej. I trzeba uprawiać rzeźbiarstwo 
artystyczne...

> Hmmm, ja nie wiem. Dla mnie string to string, biorę i używam. A
> jeśli działa za wolno, to coś kombinuję samemu.

Właśnie od tego jest biblioteka standardowa, byś nie musiał robić
samemu, tylko wziąć gotowiec z pudełka i z zadowoleniem używać.
A skoro jednak kombinujesz, i do tego nie Ty jeden, to znaczy, że
z klasą biblioteczną jest coś bardzo nie tak. Własnych wektorów
jakoś ludzie nie piszą, ani mapek. Wzajemnie niezgodnych mutacji
stringa jest za to zatrzęsienie i wcale nie dlatego, że kontener
do napisów jest niesamowicie interesującą problematyką, tylko
wersja referencyjna stwarza więcej problemów niż rozwiązuje
i ludzie sobie to obchodzą jak umieją. "Po owocach ich poznacie je".

	Pozdrawiam, Piotr