Portál AbcLinuxu, 25. dubna 2024 10:55
9.6.2018 16:31
xkucf03 | skóre: 49
| blog: xkucf03
Řešit to takto komplexně má smysl, pokud je skutečně potřeba kódovat čísla od malých po velká s rovnoměrnou distribucí. Pokud je problém ale pouze "velmi malá čísla" versus "velká čísla", můžeme optimalizovat s menší granularitou.To je pravda. Těch 32 (nebo jiný počet) horních hodnot nemusí značit počet bajtů, ale může to být nějaký číselník – pak by šlo mít možnosti:
Nejčastěji je to prostě jeden bit v hlavičceZabývám se teď návrhem formátu pro relační (tabulková data), tzn. na začátku bude hlavička, která říká, kolik je tam sloupců a jaké mají typy, takže při čtení dat už přesně víš, jak ta data mají být dlouhá. Problém je u variabilních typů jako jsou řetězce a pole – délka konkrétního atributu je pak uvedena v něm (tzn. v datech, ne v hlavičce) – a na to právě chci použít tenhle číselný formát.
uint128 (přesahuje běžné limity, po načtení by bylo potřeba rozdělit a uložit třeba jako 2× uint64 nebo pole bajtů)Tady by jistě bylo lepší použít některou z existujících bigint knihoven než to stavět od nuly.
10.6.2018 17:25
xkucf03 | skóre: 49
| blog: xkucf03
Zatím jsem to udělal takhle:
$ for n in 0 1 10 250 251 252 65535 65536 4294967295 4294967296 18446744073709551615; do printf '%20s = ' $n; ./rp-prototype write integer $n | hd | head -n 1; done
0 = 00000000 00 |.|
1 = 00000000 01 |.|
10 = 00000000 0a |.|
250 = 00000000 fa |.|
251 = 00000000 fb fb |..|
252 = 00000000 fb fc |..|
65535 = 00000000 fc ff ff |...|
65536 = 00000000 fd 00 00 01 00 |.....|
4294967295 = 00000000 fd ff ff ff ff |.....|
4294967296 = 00000000 fe 00 00 00 00 01 00 00 00 |.........|
18446744073709551615 = 00000000 fe ff ff ff ff ff ff ff ff |.........|
Láme se to u hodnoty 250 a pak na maximu uint8_t, uint16_t, uint32_t. Větší čísla než maximum uint64_t nejde zapsat (v budoucnu by šlo rozšířit).
Velikost menší tabulky (zakódovaný obsah mého /etc/fstab) tím klesla cca na polovinu (do té doby se na všechno používal uint64_t).
10.6.2018 18:32
xkucf03 | skóre: 49
| blog: xkucf03
Takže je to vlastně takovej vykastrovanej huffman s pevně danou četností hodnot.
A to je špatně?
Není pro hodnotu třeba 4294967297 plýtvání těch nejvyšších nulovejch bajtů?
Však taky původní myšlenka byla, že část toho prvního bajtu by značila délku čísla v bajtech, tzn. šlo by kódovat třeba tříbajtové číslo. Ale od toho jsem upustil a dal přednost tomuhle. Větší význam podle mého má to, že do jednoho bajtu se vejdou hodnoty až do 250 – u takových hodnot očekávám větší četnost (délky řetězců, běžných polí atd.). Naopak to plýtvání není tak hrozné – je to 5 bajtů vs. 4 nebo 9 vs. 6. navíc u velkých čísel, kde se dá čekat buď menší četnost nebo se budou používat jako délka většího množství dat (a pak ta data zabírají mnohonásobně víc než číslo vyznačující jejich délku, takže tam ten jeden nebo tři bajty nehrají roli).
Implementačně je to jednoduché – kód na pár řádků – a ze vstupu se čte vždy počet bajtů odpovídající nějakému běžnému číselnému typu (uint8_t až uint64_t) a nemusí se to nijak složitěji dekódovat.
Napadá tě něco lepšího? Padl tu např. odkaz na Base 128 Varints, ale to mi přijde implementačně složitější a datově méně úsporné.
A to je špatně?Jsi psal, že chceš co nejvíc efektivní uložení. Použití pevně dané četnosti hodnot (vede na délku zakódovaného slova) u prefixového kódu ti nikdy nedá globální maximum efektivnosti.
že do jednoho bajtu se vejdou hodnoty až do 250Kdybys použil prefixy pouze 0xFE a 0xFF, tak se ti do jednoho bajtu vejde až 253 hodnot :-P. A ušetříš ještě víc. To tvoje řešení je neefektivní pro nevyužité hodnoty:
N/A = 00000000 fd 00 00 00 00 ... N/A = 00000000 fd ff ff 00 00 65536 = 00000000 fd 00 00 01 00Kdybys místo těch nevyužitých hodnot dal délky bajtů 0-65535, tak budeš mít tolik místa... Ale to už je, jak píšu potřetí normální prefixový kód. Takový kód bude efektivnější, ale pořád nebude nejefektivnější, protože předpokládá pevnou četnost a zaokrouhluje skupiny na oktet.
Naopak to plýtvání není tak hroznéMě teda nepřijde hrozné ani plývání uint8 v uint32 slovech
.
10.6.2018 21:36
xkucf03 | skóre: 49
| blog: xkucf03
Kdybys použil prefixy pouze 0xFE a 0xFF, tak se ti do jednoho bajtu vejde až 253 hodnot :-P. A ušetříš ještě víc.
Ano, jsou tam spousty nevyužitého místa, pod těmi hranicemi typů. Ale co s tím? Pokud by se nějak používaly, tak to zvýší složitost implementace. Takhle mi to přijde jako celkem rozumný kompromis mezi jednoduchostí a prostorovou efektivitou. Ty nadbytečné hodnoty bych zatím prohlásil za neplatné – díky tomu bude zápis jednoznačný (každou hodnotu půjde zapsat jen jedním způsobem) a v příští verzi by je třeba šlo k něčemu použít (spíš ne – maximálně udělat nějaký rozšířený typ, který by s tímhle mohl sdílet část implementace).
Mě teda nepřijde hrozné ani plývání uint8 v uint32 slovech
Pokud je to jedna hodnota, tak na tom nesejde, protože kolem bude tolik metadat a jiných hodnot, že to nehraje roli. Ale když to bude spousta malých hodnot, tak mi to čtyřnásobné nafouknutí už přijde jako podstatná vada.
Pokud je to jedna hodnota, tak na tom nesejde, protože kolem bude tolik metadat a jiných hodnot, že to nehraje roli.Ještě jsi ale nenapsal na co to chceš použít. Na interprocesovou komunikaci? Ono memcpy do sdílené paměti by mohlo být rychlejší než vybírání, která hodnota je zrovna uint8 uint16 nebo uint32.
10.6.2018 22:08
xkucf03 | skóre: 49
| blog: xkucf03
Nerad bych vymýšlel kolo, proto se chci zeptat, jestli nevíte o nějakém existujícím standardu, který by popisoval takový formát.Jestli nechceš znovu vymýšlet kolo nebo nechceš později vymýšlet interface mezi současným a tvým kolem, tak se koukni do specifikace ukládání čísel v octave nebo GMP.
9.6.2018 17:53
Josef Kufner | skóre: 70
Zlomky, float, komplexní čísla, matice, nekonečna, nečísla (NaN) a další vylomeniny.Jo, třeba necelé číslo s fixed point.
Pokud přecijen je efektivita potřeba, tak typicky je známo, jak ta data vypadají, takže statické typování je v pohodě.Já bych to v takovém případě uložil co nejblíže formátu jaký používá zpracovávající kód. Ušetří se za konverzi.
9.6.2018 19:02
xkucf03 | skóre: 49
| blog: xkucf03
Já bych to v takovém případě uložil co nejblíže formátu jaký používá zpracovávající kód. Ušetří se za konverzi.
Jenže co když je „na každém konci roury“ jiný program psaný klidně v jiném programovacím jazyce, běžící na jiném operačním systému, s jinou architekturou procesoru? Lze se jen přizpůsobit tomu nejrozšířenějšímu (např. endianitou).
9.6.2018 19:59
xkucf03 | skóre: 49
| blog: xkucf03
Data budou vždy zarovnaná na osmibitové bajty tzn. oktety. V některých případech se bude pracovat s bitmapami, bitovými maskami, ale opět to bude zarovnané na celé bajty.
Přemýšlel jsem nad složitostí čtení a zápisu, protože tyhle věci jdou trochu proti sobě, a zvolil jsem si jako prioritu snadný zápis. Tzn. pro vytvoření dat v tomto formátu by ti mělo stačit naprosté minimum kódu a minimum konverzí. Z toho vyplývá širší paleta datových typů a to včetně kódování textu – abys mohl prostě na výstup vyplivnout data tak, jak je máš v paměti. Když tvoje platforma bude používat ISO-8859-2, tak prostě jen deklaruješ textový sloupec s tímto kódováním a zapíšeš data, aniž bys je musel konvertovat. To si udělá ten, kdo data konzumuje nebo nějaký konverzní nástroj v rouře mezi tím. Totéž s endianitou číselných typů. Tudíž můžeš mít relativně hloupého producenta, který umí jen ISO-8859-2 a relativně hloupého konzumenta dat, který umí jen UTF-8 a mezi ně vložíš konvertor, který kódování převede.
Důvodem je to, aby bylo maximálně snadné generovat data v tomto formátu, aby těch producentů bylo co nejvíc. Produkce takových dat je specifická, jsou to různé programy různých autorů. Zatímco transformátory a konzumenti jsou většinou generické programy – stačí je napsat jednou a jsou univerzální. Konzumenti taky většinou poběží na výkonnějším hardwaru a vyspělejších platformách, zatímco producentem může být třeba jednočip připojený přes sériový port. Pokud by to mělo být opačně, stačí mezi ně vložit konvertor, který převede datové typy na nějakou podmnožinu, aby na druhé straně nebylo potřeba podporovat všechny datové typy.
A co další typy čísel? Zlomky, float, komplexní čísla, matice, nekonečna, nečísla (NaN) a další vylomeniny.
V některých oblastech se používají striktně racionální čísla, například podíly vlastníků v katastru, nebo finanční obnosy se zas ukládají v desítkové soustavě (tam je ještě bordel se zaokrouhlováním). Spousty fyzikálních veličin jsou vektory. Pak tu máme velmi časté údaje, které mají číslům velmi blízko, například datum a čas.
Na všechno se dostane. V tomhle zápisku řeším jen jeden dílčí problém. Tzn. efektivní zápis přirozených čísel (typicky délky a počty něčeho).
Pokud jde o serializaci, tak bych se na superefektivní kódování vybod a šoupnul to do JSON
Nerad bych si pozvracel klávesnici a nepřál bych to ani druhým. JSON je pro tento účel nevhodný stejně tak jako třeba takové XML. Soubor se nafoukne a zabírá mnohonásobně víc místa než v něm obsažené hodnoty. Zvlášť při větším množství menších hodnot.
Cíle jsou následující:
cat (resp. ještě lépe, protože tady nebudou problémy s chybějícím koncem řádku na konci souboru nebo třeba s BOMem na jeho začátku)V principu se tomu nejvíc blíží formáty/protokoly, kterými spolu komunikuje klient a server relačních databáze. Ale nevím o tom, že by se některý z nich rozšířil a používal i k něčemu jinému než ke komunikaci mezi klientem a serverem.
Většinu požadavků by mohla plnit některá binární reprezentace XML, ale tam lze těžko čekat jednoduchý parser/generátor.
Why do you pick on Protocol Buffers so much? Because it’s easy to pick on myself. :) I, Kenton Varda, was the primary author of Protocol Buffers version 2, which is the version that Google released open source. Cap’n Proto is the result of years of experience working on Protobufs, listening to user feedback, and thinking about how things could be done better.(Né že bych to kdy použil.)
10.6.2018 11:02
xkucf03 | skóre: 49
| blog: xkucf03
Koukal, jenže tam je potřeba si předem definovat schéma, něco jako:
message Point {
required int32 x = 1;
required int32 y = 2;
optional string label = 3;
}
Totéž u toho Cap’n Proto.
Ale co s tím, když schéma předem neznáme? Nevíme, kolik tam bude tabulek, sloupců, řádků, jaké budou mít datové typy… Šlo by definovat nějaké dostatečně volné schéma, které umožní zapsat libovolná data, něco jako pole map, ale to bude IMHO neefektivní a popírá to smysl toho formátu.
Navíc mě poněkud děsí komplexita podobných nástrojů:
Msgpack:
$ cloc msgpack/msgpack-c/
834 text files.
829 unique files.
14 files ignored.
github.com/AlDanial/cloc v 1.70 T=3.92 s (209.6 files/s, 30446.6 lines/s)
-------------------------------------------------------------------------------
Language files blank comment code
-------------------------------------------------------------------------------
C/C++ Header 710 8754 10663 77637
C++ 70 2228 454 13288
C 10 322 95 1610
CMake 10 89 6 1520
ERB 8 130 0 868
Markdown 4 230 0 664
YAML 2 6 3 295
MSBuild script 1 0 0 187
Bourne Shell 6 47 0 180
-------------------------------------------------------------------------------
SUM: 821 11806 11221 96249
-------------------------------------------------------------------------------
Cap’n Proto:
$ cloc capnproto/capnproto/
374 text files.
373 unique files.
42 files ignored.
github.com/AlDanial/cloc v 1.70 T=2.12 s (157.2 files/s, 79425.4 lines/s)
-------------------------------------------------------------------------------
Language files blank comment code
-------------------------------------------------------------------------------
C++ 155 13921 8739 76561
C/C++ Header 91 8274 8878 39365
Markdown 37 1673 1 4811
Bourne Shell 14 269 195 1126
CMake 8 110 188 772
CSS 2 144 21 765
m4 3 81 39 603
make 1 66 23 425
JavaScript 1 25 0 175
Python 2 30 19 159
XML 2 3 8 143
HTML 7 28 5 142
JSON 2 0 0 89
YAML 4 17 23 79
Protocol Buffers 3 16 60 77
Lisp 1 17 19 39
-------------------------------------------------------------------------------
SUM: 333 24674 18218 125331
-------------------------------------------------------------------------------
Ano, je trochu divné, když to říká člověk, který používá Javu, SQL databáze a vyžívá se v XML :-) Ale opravdu si nemyslím, že potřebuji kolem sta tisíc řádků kódu k tomu, abych serializoval a deserializoval relační (tabulková) data.
A je určitě špatné to schéma definovat?
Obecně je schéma dobré definovat předem, dohodnout si rozhraní. Ale tady chci řešení, které bude mít schéma uvedeno na začátku samotných dat (tzn. je to dynamické i statické schéma zároveň, podle toho, jak se na to díváš). Předem definovat schéma v nějaké příští (zatím mám sotva prototyp) verzi půjde – volitelně (můžeš popsat strukturu tabulek).
Předem neznámá struktura je na úrovni sloupců tabulky, nebo i jednotlivých řádků?
V zásadě to odpovídá výsledku dotazu relační databáze – může vrátit jednu nebo i víc tabulek a každá tabulka má určitý počet sloupců určitých typů, což je uvedeno v záhlaví tabulky.
Než se dotaz provede, tak nevíš, jaké sloupce ti vrátí (pokud si ho sám na straně příjemce neinterpretuješ), ale ve chvíli, kdy už čteš jednotlivé řádky, tak už víš, kolik je sloupců a jaké mají typy.
Pokud bych stavěl protokol na serializaci obecné tabulky, nikoliv obecné posloubnosti hodnot, tak na začátek napíšu schéma tabulky a pak prostě sypu staticky typovaná data s maximální efektivitou.
Přesně tak.
Jen potřebuji nějak signalizovat konec tabulky (aby nedošlo k záměně mezi dalším řádkem a další tabulkou) a mít možnost vyznačit NULL hodnoty, takže na začátku každého řádku musí být jeden bajt + případně bitová maska chybějících hodnot.
Definovat dostatečně volné schéma je ptákovina
XML, JSON, YAML, ASN.1, MessagePack, Protocol Buffers, Cap'n Proto, Thrift, Avro, Flat Buffers… to jsou všechno moc univerzální formáty umožňující zapsat libovolná stromová data. K tomu těžko vzniknou univerzální znovupoužitelné nástroje, které umožní na příkazové řádce pracovat s daty, načíst ze STDIN, nějak transformovat a předat na STDOUT. Tou transformací myslím třeba setřídění podle určitého atributu, filtrování na základě podmínek, volání funkcí – v podstatě to, co děláš běžně v SQL nad relacemi (a nakonec i to samotné SQL dotazy – „databází“ pro tebe bude STDIN a výstup předáš na STDOUT). S obecnou strukturou (stromem) tohle dělat nejde, kdežto s relací (tabulkou) resp. množinou tabulek ano. Proč si třeba každý program musí psát vlastní formátování výstupu, které má vyplivnout lidsky čitelnou tabulku? A proč to většinou vypadá hnusně nebo se to pravidelně rozbíjí? (zarovnání, šířka znaků). Proč některé programy umí výstup v CSV a jiné ne? Proč to CSV má pokaždé trochu jiný formát? Proč nelze data z více vstupů spojit do jednoho proudu prostým zřetězením, aniž by se ztratila hranice mezi nimi? Proč nelze jednoduše předat relační data z výstupu jednoho programu na vstup druhého programu?
Moje hlavní myšlenka je: spojit princip relačních databází a unixových rour.
Asi nejlepší ekosystém má XML – filtrovat se dá přes XPath, transformovat přes XSLT… ale pořád to není ono: ten XPath se ještě dá, ale transformaci nebo JOIN těžko napíšeš na příkazovém řádku, musíš ji uložit do souboru, implementace je poměrně složitá, formát moc obecný (strom), data z více zdrojů nejde řetězit, nemůžu napsat cat a.xml b.xml c.xml | filtr | join | filtr | transformace | výstupní-formátování… navíc data jsou uložena prostorově neefektivně (to by možná vyřešila nějaká binární forma XML).
Spousta těch výše uvedených formátů má monstrózní implementace, třeba sto tisíc řádek kódu – těžko lze čekat, že si to autor nějakého malého prográmku přidá jako závislost nebo že ten formát sám implementuje. Přitom ale ten malý prográmek může poskytovat zajímavá data, která bys chtěl strojově zpracovávat, nebo si je třeba jen naformátovat tak, jak jsi zvyklý nebo jak se ti to zrovna hodí (někdy chceš ta samá data vidět v terminálu jako tabulku obarvenou ANSI sekvencemi, jindy to chceš hodit na web jako XHTML nebo z toho vykreslit graf).
nevýhody EAV
Tady je to mimo téma, ale: EAV má sice nepopiratelné nevýhody, ale přesto bych ho nezavrhoval jako „za všech okolností zlo“. Beru ho jako jeden z návrhových vzorů, který může někdy (byť třeba výjimečně) mít smysluplné využití.
Co dává smysl, pokud je požadována efektivita zpracování velkého množství dat, je za běhu vygenerovat/sestavit schéma, provést optimalizace, vygenerovat nativní kód, … a pak chroupat data ve velkém.
To už je na klientovi, teoreticky si může vygenerovat nějaký bajtkód, použít JIT, zkompilovat si za běhu nativní kód… a tím číst řádky. Ale nepředpokládám, že by se to běžně dělo (i když nic tomu nebrání).
V zásadě to odpovídá výsledku dotazu relační databáze – může vrátit jednu nebo i víc tabulek a každá tabulka má určitý počet sloupců určitých typů, což je uvedeno v záhlaví tabulky.A proč tedy nepoužiješ SQL tabulku (resp. výsledek dotazu)? To co popisuješ v tomto komentáři je úplně jiný problém než ten na začátku v blogu. Jak to tak chápu, tak ti jde o streamovatelnou tabulku – hlavička popisující formát řádků a pak stream řádků v tom definovaném tvaru. Trochu mi to připomíná formát PNG, kde je definována syntaxe bloků a ty bloky pak obsahují různá data a metadata, která jsou pak různě interpretována. Docela by dávalo smysl to udělat podobně. Mít blok, který deklaruje strukturu a pak mít datové bloky, které by jen odkázaly na tu deklarovanou strukturu. Klidně by se pak daly prokládat streamy více tabulek – např. by se deklarovaly třeba tři struktury a pak by se posílaly trojice datových bloků (čímž by se plnily tři tabulky současně). Ale na to bych nevymýšlel něco úplně nového. Použij něco z toho, co jsi teď vyjmenoval, jen doplň ten streamovací protokol okolo.
9.6.2018 19:22
xkucf03 | skóre: 49
| blog: xkucf03
Co se týče možnosti skoku na nějaký záznam kdesi uvnitř, přemýšlel jsem spíš nad nějakou formou volitelných externích indexů, ale není to na pořadu dne – přeci jen to nemá být databáze. Má to být primárně proudové zpracování – tzn. přečíst, transformovat, odeslat dál.
Co se týče samoopravitelnosti, to asi řešit nebudu – bylo by to za moc velkou cenu nafouknutí dat. Když se část dat ztratí, tak je stejně ten soubor rozbitý. Fungoval by mohla nějaká poloautomatická oprava, kde se budou data číst od konce nebo se budou průběžně hledat nějaké parsovatelné kusy dat, které půjde zachránit. To může být výpočetně dost náročné, ale to v tu chvíli nevadí.
Až na to, že JSON parser je cca 2× tak složitější co do počtu řádků, podporuje méně datových typu, neřeší zápis a datové soubory jsou zoufale neefektivní co se týče objemu dat (zabírají několikrát víc než obsažená data), nejde řetězit spojováním souborů. Je vlastně ve všem horší. Kdyby byl tak omezený aspoň ve prospěch jednoduchosti implementace… ale ani to není pravda.
Komprese zvyšuje komplexitu a je otázka, co by to přineslo. Proč bychom měli data zapisovat neefektivně a pak je komprimovat, když je můžeme zapsat efektivně?
public static Byte[] encode(int value) {
List<Byte> result = new ArrayList<>();
for (int i = 0; i < value; i++) {
result.add((byte) 0xFF);
}
result.add((byte) 0x00);
return result.toArray(new Byte[result.size()]);
}
9.6.2018 21:22
xkucf03 | skóre: 49
| blog: xkucf03
hmm, tak to by asi nešlo:
$ javac IntegerTest.java && java IntegerTest 0 | wc
0 0 1
$ javac IntegerTest.java && java IntegerTest 1 | wc
0 0 2
$ javac IntegerTest.java && java IntegerTest 10 | wc
0 0 11
$ javac IntegerTest.java && java IntegerTest 255 | wc
0 0 256
$ javac IntegerTest.java && java IntegerTest 1000 | wc
0 0 1001
$ javac IntegerTest.java && java IntegerTest 1000 | hd
00000000 ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff |................|
*
000003e0 ff ff ff ff ff ff ff ff 00 |.........|
000003e9
Tzn. abych např. vyznačil délku textu dlouhého tisíc bajtů, musím nejdřív zapsat 1001 bajtů dlouhé číslo. Jaký to má smysl? A při čtením musím to číslo číst po bajtu a hledat v něm koncovou nulu.
Většinou tu propaguji méně optimalizovaná řešení, která jsou ale čitelnější a udržovatelnější, ale tohle je extrémně neefektivní, vlastně to jde přímo proti zadání, a navíc implementačně jednoduché nebo čitelné to taky není.
A „optimalizovat se to vždycky“ nedá, protože pokud s tím formátem začnou počítat ostatní, těžko už ho změníš.
(asi to bylo myšleno jako vtip, ale nedalo mi to)
10.6.2018 01:55
Josef Kufner | skóre: 70
10.6.2018 03:58
Jendа | skóre: 78
| blog: Jenda
| JO70FB
To jako, že to spadne, místo toho, aby to bylo jen pomalé?Samozřejmě. A to klidně i na x86.
Pěkné čtení, dík za odkaz.
Jestli jsem to dobře pochopil, tak přetypovat náhodnou pozici v poli bajtů na větší datový typ (např. uint32_t) je problém, ale když budu číst data ze vstupního proudu do lokálních proměnných, tak by to mělo být v pohodě, ne? V mém prototypu to čtu stylem:
integer_t value; input.read(reinterpret_cast<char *> (&value), sizeof (value));Takže nezarovnaný formát znamená, že není možné dělat „zero-copy“ resp. natáhnout si data tak, jak přišla zvenku, do nějakého souvislého úseku v paměti a přistupovat k jednotlivým atributům přes ukazatele na příslušná místa? Nicméně tohle by byl asi i bezpečnostní problém (např. když by ve vstupních datech byla deklarovaná nějaká větší délka řetězce, než kolik dat reálně přišlo, a ten, kdo by to četl by téhle délce věřil a načetl by i jiná data, než jaká přišla ze vstupu).
11.6.2018 00:25
Jendа | skóre: 78
| blog: Jenda
| JO70FB
Takže nezarovnaný formát znamená, že není možné dělat „zero-copy“ resp. natáhnout si data tak, jak přišla zvenku, do nějakého souvislého úseku v paměti a přistupovat k jednotlivým atributům přes ukazatele na příslušná místa?Ano, takhle to chápu. Osobně se mi pro čtení souborů líbí používání mmap a následné libovolné čtení „jako v poli“, kde by toto mohl být problém.
11.6.2018 00:35
Jendа | skóre: 78
| blog: Jenda
| JO70FB
Když nad tím přemýšlím, tak by se dalo po kvalitním kompilátoru požadovat, aby v rámci urychlení detekoval nezarovnáníTohle se dělá u funkcí, kde vstup může být nezarovnaný (např. memcpy). U funkcí, kde jsou parametry zarovnané (by definition, 32b int je zarovnaný na 32 b), to jaksi není potřeba. Jinak už by to nebyl rychlý kompilátor Cčka, ale kompilátor nějakého jazyka podobného Cčku, kde jsi z části UB udělal validní operace
.
ale kompilátor nějakého jazyka podobného Cčku, kde jsi z části UB udělal validní operace .Což by ale byl pořád validní C kompilátor, protože UB může znamenat i správný výpočet. Nesprávné z hlediska by bylo akorát použití UB pro regulérní výpočet. Z tohoto pohledu ale pak ten sum kód není validní C. Na druhou stranu, pokud by u toho char pole, nebo char parametru nastavil direktivu aligned, tak by to měl kompilátor pochopit a buď sestavit pro speciální případy nebo napsat varování při překladu.
10.6.2018 03:56
Jendа | skóre: 78
| blog: Jenda
| JO70FB
10.6.2018 16:15
xkucf03 | skóre: 49
| blog: xkucf03
10.6.2018 17:04
xkucf03 | skóre: 49
| blog: xkucf03
Undefined behaviour.Souhlas. Přijde mi lepší do specifikace napsat: „ve všech ostatních případech má program spadnout“ – než aby to někdy fungovalo a někdy ne.
10.6.2018 18:42
Gilhad | skóre: 20
| blog: gilhadoviny
11.6.2018 00:29
Jendа | skóre: 78
| blog: Jenda
| JO70FB
Přijde mi lepší do specifikace napsat: „ve všech ostatních případech má program spadnout“Jenže tohle znamená, že kompilátor buď některé optimalizace nemůže dělat vůbec, nebo před ně musí vygenerovat kontrolu podmínek - s tím je dobré kompilovat buildy na kterých se spouštějí testy, ale hotový program to může zpomalovat. A pro některé architektury neexistuje kompilátor, který by tyhle testy generovat uměl.
11.6.2018 00:27
Jendа | skóre: 78
| blog: Jenda
| JO70FB
Takže řešit nějaká specifika konkrétních architektur nemá moc smysl.Ano, samozřejmě to je bug. Ale musíš na něj nějak přijít a když to běží někde kde není UBSan, tak to může jít těžko.
(ale vím, často se to dá vypnout).
10.6.2018 03:55
Jendа | skóre: 78
| blog: Jenda
| JO70FB
Nerad bych vymýšlel kolo, proto se chci zeptat, jestli nevíte o nějakém existujícím standarduProtobufs
Jak zapsat, zda je číslo velké nebo malé? Šlo by k tomu použít jeden bit, což by ale znamenalo, že na malá čísla máme jen 128 hodnot.Akorát oni efektivně používají jen těch 7 bitů z každého bajtu. Sice tím půjde zapsat „nekonečně“ velké číslo, ale jinak to moc výhod IMHO nemá. Přijde ti to lepší než #6?
Obávám se, že každý formát určený pro co nejmenší objem dat a co nejrychlejší zpracování počítačem bude pro člověka ošklivý."Dokonalost" ASN.1 a XML spatřuji právě v tom, že jsou ošklivé jak pro počítače, tak pro lidi.
A ošklivější formát se po letech pokusů podařilo vymyslet a dokonce i prosadit – JSON.Souhlasím, to je vážný kandidát :) Hlavně tím, že co parser, to jiná interpretace formátu.
11.6.2018 22:23
xkucf03 | skóre: 49
| blog: xkucf03
ASN.1 je abstraktní – o které serializaci tedy mluvíš?
Ono i to XML (resp. XML Infoset) je abstraktní model a ta textová forma s ostrými závorkami je jen jednou z jeho reprezentací.
ASN.1 je abstraktní – o které serializaci tedy mluvíš?Je to vcelku jedno, hezká není ani jedna :)
18.6.2018 22:38
xkucf03 | skóre: 49
| blog: xkucf03
11.6.2018 11:40
Josef Kufner | skóre: 70
… že jeden bit v každém bytu informuje o tom, jestli následuje další byte nebo ne.Tímto a jakýmkoliv podobným způsobem se zabije možnost zero-copy zpracování. Metadata je potřeba umístit tak, aby nepřekážela. Například by šlo ukládat metadata pro skupiny hodnot spolu a data samostatně. Případně je rozmístit do paddingu při zarovnávání na 32bit. V tomhle se mi líbí přístup Cap'n Proto – na běžných architekturách není potřeba data nijak parsovat, jen se v getterech/setterech kontrolují meze a typy.
V tomhle se mi líbí přístup Cap'n Proto – na běžných architekturách není potřeba data nijak parsovat, jen se v getterech/setterech kontrolují meze a typy.No jo, jenže pak máš overhead v těch getterech/setterech. Takže ten overhead tam taky bude, akorát je těžší ho změřit
Další věc je, že Cap'n'proto má celkem velký overhead velikosti dat. Viz tyhle benchmarky.
Ono je to vždycky něco za něco...
Díky za dosavadní komentáře. Zatím z toho nechci dělat žádný závěr – píši si na seznam otevřených otázek:
Tohle stačí rozhodnout před vydáním verze 1.0, takže to zatím nechám uležet a budu se věnovat jiným věcem v rámci tohoto formátu.
Ad formáty čísel: podporováno by jich mělo být více (různé fixní, různé variabilní), ale jde o to, který by měl být ten základní např. pro vyznačení délky řetězce nebo počtu sloupců či prvků v poli. Teoreticky by i tenhle formát mohl být dynamický, uvedený v hlavičce tabulky, ale to mi přijde už trochu divoké.
Ad zarovnání: líbilo by se mi, kdyby byl formát volitelně zarovnaný – tzn. v hlavičce by bylo uvedeno, zda jde o zarovnanou či nezarovnanou variantu – ale nelíbí se mi, že to zvyšuje komplexitu implementace. A tu zvyšuje i samotné zarovnání.
P.S. přidal jsem ankety.
Tiskni
Sdílej:
ISSN 1214-1267, (c) 1999-2007 Stickfish s.r.o.