🚀 go-pugleaf

On Friday, October 13, 2017 at 12:42:13 AM UTC+2, Piotr Wyderski wrote:
> 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ął.

Hmmmm. 


> C++ stawia na 2, koślawie łącząc go z 1 i całkowicie ignorując 3.
Chyba masz rację. W QT, jak dla moich potrzeb, budowanie napisu jest
bardzo wygodne, a jak mi mało, to mogę także QTextStream skonstruować
na QStringu.

> 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. 

Do wydajnego przetwarzania dużej ilości drobnicy potrzebny jest 
jakiś szablon obudowujący tablicę o stałym rozmiarze.

template< int MAX_SIZE=32, typename TS=char  >
class String {
  TS string[MAX_SIZE+1];
};


> Ja mówię o miliardach. 
Tak tak.


> 3 sprowadza się do wzbogaconej o lukier syntaktyczny
> std::pair<const char*, std::size_t> i jest wyjątkowo niemedialny.
Przyznaję, brzydkie. Ja bym na powyższym szablonie bazował.


> 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ć. 
No tak.


> 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.
Trochę się zgubiłem, co zrobiłeś?



> 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ę. 
Ale zwróć uwagę, że w przypadku dużej ilości malutkich napisów zazwyczaj
lepiej robić memmove i dopisywać na początek, niż zaczynać napis od
'środka' tablicy. 


> Przyjęto, że na
> końcu. Wydajnie doklejać znaczków na początek się nie da, bo
> trzeba kopiować całe dane w prawo. 
Tak, ale statystycznie rzadziej dokleja się na początku. W przypadku
drobnicy, mało znaczków przerzuca się na koniec. Gdy operacja 
doklejania na początku jest wiodąca w danym programie, to można
napisy trzymać w odwrotnej kolejności znaków. Jeśli dla drobnicy
zarezerwujemy kilka bajtów z przodu, to czasem będzie trzeba 
przerzucić bajty do przodu, aby pisać na końcu. Problemy z drobnicą
są, gdy ilość napisów idzie w miliardy, więc rezerwowanie większej
pamięci może skończyć się brakiem pamięci w systemie. 

O ile program nie jest bardzo specyficzny, to tamten powyższy
template wydaje się uniwersalny do drobnicy.



> 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.

Z pamięci piszę: często realloc umie dodać mały kawałek pamięci na
końcu bez kopiowania całości.


> 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ą. 
By się przydał jakiś autotune string. Mam coś podobnego w
drzewach czerwono czarnych, tyle że nie są auto, ale sam
muszę ustawić flagę jak się drzewo ma przekonfigurować.

Jeśli wiadomo jak string będzie się rozszerzał, to można dostosować
sposób allokacji. A jak nie wiadomo, to lipa.

W Qt jest struktura która automatycznie zmienia się z tablicy 
na stosie w coś podobnego do wektora. Można wydajnie operować 
na małych danych, a jak dojdzie do przekroczenia zakresu, to 
automatycznie zrobi malloc i rozszerza się jak wektor. Ale to
jest rada na sytuację, gdy jest dużo drobnicy, przy czym 
z rzadka z drobnicy robi się długi napis.


> 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.
Czy chodzi o C++ Buildera i TString? Używałem tego tak dawno temu, że
nie pamiętam jakie możliwości mają tam stringi.


> Podczas budowania nie muszę też niczego kopiować, bo nie ma
> najmniejszej potrzeby, by dane tymczasowe znajdowały się w pamięci
> ciągłej. 
W QT wszystkie kolekcje głęboką kopię robią dopiero przy 
modyfikowaniu, za to działają nieznacznie wolniej - wada. Zaleta
jest taka, że można bezkarnie sobie pisać 
duża_struktura1 = duża_struktura2



> 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. 
To jakieś hashe byś musiał trzymać, albo drzewo wyszukiwań. Na QStringu
chyba dobrze zadziałałoby operowanie na samych odnośnikach do tych
samych napisów.


> Porównania na równość sprowadzą mi się wtedy do porównania
> wskaźników na bufor, bez konieczności zaglądania w znaczki. 
Tak, to ogromna zaleta unikalności napisów. Ale zwróć uwagę, że
gdy użytkownik wpisze string, to i tak i tak trzeba go 
porównywać z zaglądaniem w znaczki, stosować drzewa poszukiwań i/albo
hashe.


> A to od
> razu dramatycznie przyspiesza kontenery unordered. I mnóstwo innych
> tego typu implikacji.
No tak, porównanie wskaźników jest szybsze niż znaczków. Ale gdy 
mamy dobrą hash-table, to porównań jest mało. Gdy mamy duży zbiór i
losowe strzały (w unorder set są zawsze losowe) w RAM, to wąskim
gardłem jest dostęp do pamięci. Na pewno współdzielone wskaźniki
przyspieszą, ale z powodu losowych strzałów w RAM, tutaj nie
spodziewałbym się dużych przyspieszeń.


> 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. 
Oczywiście. Dlatego zdecydowana większość autorów programów 
szachowych, gdzie wydajność jest bardzo ważna, nie stosuje 
ani jednego kontenera z biblioteki standardowej :D


> 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ł. 
Jak to nazwałeś, synergia, jest kluczową cechą w dużych bibliotekach.
Osobiście najczęściej używam QT i nie narzekam na brak synergii.
Zwróć jednak uwagę, że synergia nie idzie w parze z wydajnością, 
kontenery z QT zazwyczaj są wolniejsze niż z STL.


> 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), 
Ja nie zarządzam czasem życia w helołłerdach. Nawet gdybym
miał 50 wycieków pamięci, ale wiem że program się zakończy 
gdy zabraknie pamięci i mnie to nie obchodzi. Jednak wyciek
mam rzadko, bo QVector i inna hash-table same zwolnią gdy 
wykonanie dojdzie do klamerki.


> a do 
> wielkoskalowych się nie nadaje ze względu na ograniczenia projektowe
> swojej biblioteki standardowej. I trzeba uprawiać rzeźbiarstwo 
> artystyczne...
Czasami trzeba napisać swoją bibliotekę, gdy projekt jest wielkoskalowy, 
to relatywny koszt napisania biblioteki jest mały, a gdy zespół, albo
nawet jedna osoba, piszą po raz któryś podobny system, to dostosowują
biblioteki z poprzednich systemów. Jednym słowem, tutaj bardzo mocno z
Tobą się nie zgodzę.



> > 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ć.
Ja tak używam biblioteki QT. Na standardową prędzej czy później
bluzgam. Ale gdy jest potrzebna duża wydajność, o której czesto
piszesz, to i tak i tak jest potrzebna biblioteka specyficzna, a
taką bibliotekę programista musi sam albo napisać, albo dostosować z
innego podobnego projektu który robił wcześniej.


> A skoro jednak kombinujesz, i do tego nie Ty jeden, to znaczy, że
> z klasą biblioteczną jest coś bardzo nie tak. 
Tak, tylko nie pomieszajmy paradygmatów. Można kombinować, bo w
bibliotece nie ma, jak to ładnie nazwałeś, ani synergii, ani wygody, ani
funkcjonalności, a można kombinować, bo funkcjonalność jest za 
duża, co skutkuje małą wydajnością.



> Własnych wektorów
> jakoś ludzie nie piszą, ani mapek. 
Ależ piszą i to np. dwie różne dla jednej aplikacji!


> 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".

Nie wiem jaka jest prawdziwa przyczyna bibliotecznych wielości 
stringów w C++. Do zwykłego programowania ja używam QStringa i
nawet nie myślę o std::stringu. Gdy mam dużo drobnicy to obudowuję
szablonem stałą tablicę, korzystam z varlenghtarray, itd. Gdy
zobaczyłem jakiś czas temu ile trzeba się namęczyć, aby zrobić
kodowanie std::stringu, to se dałem spokój. QString natywnie 
operuje na utf16, nic nie musi deszyfrować w operacjach typu
'find', a gdy trzeba, to można go eksportować do bardzo wielu
kodowań.

Pozdrawiam