Serializace libovolně dlouhých přirozených čísel

9.6.2018 14:42 | Přečteno: 2769× | Softwarové inženýrství | poslední úprava: 11.6.2018 22:03

Dnes volně navážu na svůj předchozí zápisek Ideální datový formát. Řeším způsob zápisu (serializace) přirozených čísel. Většinou se používají datové typy s pevnou šířkou, které zabírají konstantní počet bajtů/bitů bez ohledu na obsaženou hodnotu. Z výpočetního hlediska to dává smysl, ale má to i svoje nevýhody:

• maximální hodnota je omezená
• malé hodnoty zabírají stejně místa jako ty maximální

V takovém případě se musíme rozhodnout, s jak velkými hodnotami chceme pracovat, a zvolit dostatečně velký datový typ, aby se nám do něj vešlo vše, co potřebujeme, ale zase ne moc velký, aby hodnoty nezabíraly moc místa v paměti a na disku.

Když si např. vybereme typ uint8, tak hodnota zabírá vždy jeden bajt, což je fajn, ale pokud bychom v budoucnu potřebovali zapsat větší hodnoty než 0-255, tak máme smůlu. Resp. museli bychom datový typ změnit – a přinutit ke změně všechny, kteří s danými daty pracují – všechen software by se musel přepsat.

Zamýšlím se tedy nad formátem, který umožní zapsat (více méně) libovolně velké číslo a zároveň malé hodnoty budou zabírat jen nezbytně nutné místo. Stinnou stránkou je vyšší výpočetní náročnost, ale to je náklad, kterého jsem si vědom a se kterým do toho jdu (bude tam navíc if / switch).

Návrh

Malá čísla budou zabírat jeden bajt a větší čísla více. 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. Zbytek prvního bajtu by označoval délku velkého čísla v bajtech. Tyto bajty by následovaly za tímto prvním bajtem (např. v souboru nebo proudu dat přicházejícím po síti). Tzn. číslo by mohlo být až 128 bajtů dlouhé, což mi přijde zbytečně mnoho (pro moje potřeby). Proto bych tu hranici posunul jinam, než na polovinu. Tudíž do jednoho bajtu by se vešly např. hodnoty 0-223 a velká čísla by mohla být dlouhá až 32 bajtů, což je 256 bitů. Vzhledem k tomu, že např. v common.h je definován uint64_t, ale už ne uint128_t, tak mi 256 bitové číslo přijde až až.

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. Našel jsem např. implementaci, která pracuje s dvouprvkovou strukturou, kde první prvek je délka v bajtech a druhý je ukazatel na pole bajtů. Tím jde zapsat větší čísla, ale ta malá zase zabírají minimálně dva bajty (v paměti ještě víc).

K čemu to je?

Ten formát by byl univerzální, nicméně primární zamýšlené užití je označování délky nějakých dat – polí bajtů nebo něčeho jiného, textových řetězců atd.

Proč neukončit řetězec nulovým bajtem?

Přímo se nabízí otázka, proč neukončit (textový) řetězec nulovým bajtem, jako se to dělá v C. Důvod je jednak ten, že řetězec nemusí být jen textový, můžou to být libovolné bajty včetně toho nulového, tudíž by bylo potřeba mít nějakou formu escapování. A jednak ten, že pro načtení nebo přeskočení daného datového pole bychom ho museli celé přečíst bajt po bajtu a hledat, na které pozici je nulový bajt. Zatímco když známe délku předem, můžeme načíst data celá nebo po vhodných kouscích nebo je celá přeskočit, pokud nás nezajímají.

Maximální hodnota ale není libovolná

Maximální hodnota sice není úplně neomezená, ale např. těch 2^(32*8) je 1.1579e+77, což snad bude stačit každému (přeci jen je to víc než 640 kB). Zatím nejvyšší známá jednotka – yottabyte (resp. yobibyte) – je 1.2472e+24, takže by to stačit mělo bohatě. Spíš by šla ta hranice posunout, aby bylo víc místa na malá čísla…

Předčasná optimalizace?

Další námitka, která se nabízí, je, zda nejde o předčasnou optimalizaci. Disky přece dnes máme velké, sítě rychlé, tak proč řešit, jestli něco zabírá jeden nebo třeba čtyři bajty? Smysl vidím v tom, že pár bajtů samo o sobě sice nic neznamená, ale pokud máme velké množství malých hodnot, režie už může být značná. Ke krátkým hodnotám bychom museli přičíst vždy několik bajtů, což by klidně zdvojnásobilo jejich velikost (nebo bychom třeba místo jednoho bajtu ukládali vždy bajtů pět) a na druhé straně u velkých hodnot bychom mohli narazit na horní limit.

Zlomky – racionální čísla

Další možnost využití jsou zlomky resp. desetinná čísla s libovolnou přesností. Pomocí dvou složek v tomto formátu by šlo zapsat jakýkoli zlomek a hodnoty např. (0 až 223) děleno (0 až 223) by zabíraly pouhé dva bajty. A se zvyšujícími požadavky na přesnost by stačilo plynule přidávat další bajty.

(resp. dělit nulou nelze – je otázka, jestli ty hodnoty neinterpretovat jako 1-224, nebo zda dělení nulou neinterpretovat jako nekonečno nebo jako neznámou hodnotu, nebo prostě tu jednu hodnotu nechat jako nevyužitou/neplatnou)

Závěr, diskuse

Co si o tom myslíte? Existuje takový formát? Má takový formát vůbec smysl? Spočívá relevantní přínos v tom, že známe délku dat ještě před tím, než je celá přečteme? Není lepší data variabilní délky ukončovat nulovým bajtem (obecně oddělovačem), přidat escapování a podložit to nějakým bufferem, který zajistí, že se z disku (nebo obecně ze vstupního proudu) bude číst po větších jednotkách než jeden bajt (tzn. efektivněji).

(ankety se vztahují k formátu definovaném v komentáři #60)

       

Anketa

Anketa

Komentáře

[Cabrón]

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

Často to vídám v průmyslové automatisaci: RTU v rozvaděči vysílá různorodé zprávy, které mohou být velmi krátké (heartbeat) nebo naopak velmi dlouhé (update firmwaru, posílání logů). Posílat jednobytový heartbeat s uint32_t polem "length" je neekonomické (pohybujeme se tu v řádech stovek, maximálně tisíců bps), tak je obvykle v protokolové hlavičce nějakým způsobem zakódováno schéma paketu a podle něj se pak odvozují typy polí.

Nejčastěji je to prostě jeden bit v hlavičce, který určuje, jestli jde o "krátkou" nebo "dlouhou" zprávu. Krátká má délku v několika málo bitech (nebo má délku dokonce pevnou a v hlavičce o ní informaci žádnou nenese), dlouhá ji kóduje klidně ve více bytech.

[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:

• malé číslo (hodnota je přímo v tom prvním bajtu)
• uint16
• uint32
• uint64
• 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ů)
• uint256 (dtto)
• atd. (?)
• opravdu libovolně dlouhé číslo nebo jiný formát (?)

tudíž by na ta malá čísla zbylo ještě víc pozic.

Sice by bylo nutné délku čísla zaokrouhlit nahoru (na 16, 32, 64… bitů), takže by velká čísla zabírala víc, než je nutné, ale tam už je to asi jedno (zvlášť pokud to číslo značí počet následujících bajtů, tak tam je to úplně jedno).

Nejčastěji je to prostě jeden bit v hlavičce

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

[Cabrón]

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.

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

[pc2005]

Takže je to vlastně takovej vykastrovanej huffman s pevně danou četností hodnot. Není pro hodnotu třeba 4294967297 plýtvání těch nejvyšších nulovejch bajtů?

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

[pc2005]

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 250

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

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

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

[pc2005]

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.

[xkucf03]

Na mezi-procesovou komunikaci, ale primárně přes STDIO.

[pc2005]

Jo ale to je strašně obecný popis použití. Procesor není přenosem přes STDIO nějak extra zatěžován IMO. Resp. nedivil bych se kdyby tím rozbalováním byl zpomalovaný víc než write/read uint32 overheadem. Protože při vkopírování nějakého (nejspíš nezarovnaného) uint32 do cílové proměnné/paměti podle tvého kódování, bude muset procesor udělat dva 32bit memory přístupy a externě zarovnat, kdežto při "všechno uint32" přístupu by udělal jeden. Teda moderní procesory budou mít 64bit sběrnici, ale to je možná ještě horší. Abys mohl vyparsovat třeba uint16, tak budeš muset každý z nich zpracovávat zvlášť v 64bit registru CPU, protože jsou mezi nima ty "escape" kódy.

Pochopil bych kdyby to byla komunikace stovek tisíců dat přes omezenou sběrnici (tím myslím třeba i2c), ale meziprocesová komunikace má k dispozici tu nejrychlejší sběrnici v celém počítači. V tomto případě platí IMO: Keep it simple and stupid.

[retroslava]

Předpokládám že to znáš, ale kdyby náhodou...

https://github.com/msgpack/msgpack/blob/master/spec.md#int-format-family

[xkucf03]

Neznám, díky. Je to podobné, ale některé věci bych řešil jinak.

Nemíchal bych znaménkové a ne-znaménkové typy – podle mého dokážeš říct vždy předem, zda hodnota může mít znaménko nebo nemůže (délka, věk, počet…), takže není problém to zafixovat v definici daného datového pole/atributu. Je sice možnost, že by se např. kladné hodnoty vyskytovaly častěji nebo ve větším rozsahu, zatímco záporné jen zřídka nebo jen pár hodnot (např. chybové kódy), ale do takových optimalizací bych se asi už nepouštěl.

Do jednoho (prvního) bajtu se vejde jen sedmibitové číslo, tzn. 0-127, což mi přijde celkem málo. Např. když tím kóduješ délku řetězce, tak hodně řetězců může mít délky v rozsahu 128-223 a zabírat kvůli nim další bajt mi přijde škoda. Na druhou stranu je to v takovém případě méně než 1% režie, což vlastně tak hrozné není.

BTW: hned nad tím vidím jejich boolean – je nějaký důvod ho kódovat jako 0xC2 a 0xC3? V ASCII to smysl nedává (ještě bych pochopil nějaké Y a N). Že by to bylo kvůli odolnosti proti chybám? Vždyť tam ale stačí přehodit jeden bit a rázem je z toho ta druhá hodnota. Proč zvolili tohle a ne třeba 0x00 a 0x01 nebo 0x00 a 0xFF?

[Cabrón]

Vychází to z jejich type ID systému, tyhle hodnoty byly jednoduše další v řadě.

https://github.com/msgpack/msgpack/blob/master/spec.md#overview

[pc2005]

Záleží na tom, jak moc chceš ty čísla parsovat/dekódovat. Něco jako prefixový kód, který definuje délku opkódu má RISC V. Já bych někam dal nejspíš nějakou proměnnou šířky a ukládal to tak, aby se to mohlo rovnou hodit procesoru (resp tak jsem tu udělal pro pakety, co obsahují sekvenci bitů pro JTAG over TCP).

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.

[luky]

Presne todle se delalo na prvnim cviku/prednasce z X36KOD, takze muzes googlovat a nebo si pocist na odkazu, co mi vyplivnul google: http://voho.eu/wiki/kodovani/ Originalni materialy jsem nenasel.

[xkucf03]

njn, tyhle věci se u nás neučí, tak se tím prokousávám teď…

[Josef Kufner]

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.

Pokud jde o serializaci, tak bych se na superefektivní kódování vybod a šoupnul to do JSONu či něčeho podobného (BSON?). Pokud přecijen je efektivita potřeba, tak typicky je známo, jak ta data vypadají, takže statické typování je v pohodě.

[pc2005]

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.

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

[pc2005]

Jakou úroveň abstraktnosti požaduješ? Protože jsou i architektury, kde oktet popisovaný v předchozím linku nedává smysl.

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

[xkucf03]

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í:

• efektivní formát, který umožní úsporně zapsat i velké množství malých nebo chybějících hodnot (řídká data), např. když tam nasypu milion atributů typu uint8, tak by to mělo mít přibližně megabajt + jen nějakou minimální režii navíc, ne 2 MB nebo 5 MB
• proudové zpracování – před načtením známe délku atributu, ale neznáme množství záznamů ani jejich množin (relací – tabulek), data tedy můžeme odesílat na výstup dřív než máme k dispozici všechna vstupní data
• možnost přidávat data prostým spojováním souborů – stejně jako když spojuješ textové soubory příkazem 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)
• bohatá paleta datových typů (přiměřeně, např. JSON jich má málo, taková ASN.1 je na tom celkem dobře, ale zase obsahuje některé oborově specifické věci, nesmysly nebo archaismy; celkem hezký protokol je Diameter – ale taky bohužel dost oborově specifický a i když byl navržen jako rozšiřitelný, nevím o tom, že by ho někdo použil mimo daný obor/doménu)
• bezschémový resp. schéma je uvedeno na začátku samotných dat – je to struktura tabulky/relace, která obsahuje určitý počet sloupců určitých datových typů, a počet záznamů ani tabulek není předem známý
• minimalistická knihovna pro čtení a zápis (do 1 000 řádků, spíš kolem 500)

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.

[Josef Kufner]

Koukal jsi na Protocol Buffers?

[Spike]

To mi připomíná: Cap'n Proto

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

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

[Josef Kufner]

A je určitě špatné to schéma definovat? Předem neznámá struktura je na úrovni sloupců tabulky, nebo i jednotlivých řádků?

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. Však tak to dělají SQL databáze už desítky let.

Definovat dostatečně volné schéma je ptákovina – viz nevýhody EAV. 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.

[xkucf03]

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

[Josef Kufner]

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.

[Sten]

Takhle se chová UTF-8, které tedy má další užitečnou vlastnost: umí se synchronizovat (pokud narazíte na číslo v půlce, snadno najdete začátek dalšího). Mírně upravenou variantou, třeba že počáteční bajt neuvádí délku celého řetězu, ale je vždy 11xxxxxx (za cenu toho, že nejde jednoduše skočit na další číslo), lze dosáhnout neomezeně dlouhých čísel.

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

[R]

Smrdi to over-engineeringom.

[gsnak]

Tiez navrhujem pouzit JSON

[xkucf03]

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.

[pc2005]

Co komprimovat přenosový kanál?

[xkucf03]

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ě?

[pc2005]

Protože efektivita přenosového kanálu je jiná vrstva než gramatika dat a formát ala textové JSON/XML je velice abstraktní.

[ehm]

Toto funguje. A opravdu nechci poslouchat žádné komentáře, že by se ta informace možná dala zakódovat trochu efektivněji. Pokud s tím v produkci budou problémy, zoptimalizovat se to dá vždycky.

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()]);
}

[xkucf03]

Příloha:

• IntegerTest.java (631 bytů)

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)

[ehm]

Koho dnes zajímá nějakých tisíc bajtů? Tou optimalizací jsem měl samozřejmě na mysli alokovat pole dopředu a ne to ládovat do listu bez nastavené počáteční velikosti, a pak to ještě kopírovat do nově alokovaného pole. Ale je to zbytečná mikrooptimalizace, která by mohla lidi zbytečně mást, tak je lepší ponechat to takto. Někteří když vidí pole nebo primitivní typy, tak z toho mají panický záchvat. Proto jsem to schoval na konec metody. Optimalizace psychické pohody (severský systém).

[MadCatX]

Na uložení integeru o velikosti 2^31 bude tímto způsobem třeba 2 GiB paměti, takže trošku zoptimalizovat by to asi chtělo.

[ehm]

Pokud někdo pracuje s tak velkými čísly, je jasné, že na to potřebuje dobrý počítač.

[ehm]

A líbí se mi ten experiment, ze kterého je patrné, že pro číslo n bude délka n + 1 bajtů. To jsem z toho kódu na první pohled také nepoznal a je osvěžující to takto vidět naživo.

[Odin]

Podle mne nic o moc lepsiho nez to, co jsi navrhl sam, nevymyslis. A urcite ma smysl to resit. Treba ne v kontextu klasickych internetovych rychlosti, ale v kontextu iot a siti, ktere se pro tat zarizeni nabizeji. Tam je propusnost par bps a tam tato optimalixace zejmena u dlouhych casovych rad dava smysl.

[Josef Kufner]

Jenže takové aplikace mají velmi dobrou představu o tvaru dat a rozsahu hodnot, takže si vystačí s předem danou strukturou, možná tak s proměnlivou délkou.

[Semo]

Pri implementacii si daj pozor, ze architektury ine nez Intel maju velmi nerady pristup do pamate na nezarovnane adresy. Kedysi som si na tom pri portovani jedneho projektu z Windows na SPARC Solaris pekne nabil drzku a dost dlho hladal, preco to cele pada (ked uvidis SIGILL, tak vitaj v klube).

[xkucf03]

To jako, že to spadne, místo toho, aby to bylo jen pomalé?

Předpokládaný/typický scénář je čtení nebo zápis proudu bajtů na STDIO (případně do souboru nebo přes síť, ale primárně jde o to STDIO). S tím snad problém nebude, ne?

Uložení v paměti bude spíš v nějakých nativních strukturách daného programovacího jazyka, než že by se přistupovalo k původním datům. I když by bylo fajn, kdyby mohla existovat i zero-copy varianta implementace.

[Jendа]

To jako, že to spadne, místo toho, aby to bylo jen pomalé?

Samozřejmě. A to klidně i na x86.

[xkucf03]

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

[Jendа]

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.

[pc2005]

No ten příklad teda nic moc kvalita algoritmu. Já bych to z hlediska portability počítal po oktetech a čekal, že to kompilátor vektorizuje (článek jsem četl rychle stylem, aha má pole oktetů, který přetypuje na nezarovnaný int a kompilátor mu tam nacpe instrukci, co vyvolá exception když není zarovnáno).

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í a buď skočil do větve s variantou movdqa anebo do větve s movdqu (opkud bude tedy ten test nezarovnanosti + urychlení movdqa rychlejší než všude nacpat movdqu).

[Jendа]

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 .

[pc2005]

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.

[Jendа]

Když to crashne, je to ještě dobré. Já jsem potkal architekruru, která pointer tiše zaokrouhlila, takže se ta hodnota zapsala třeba o dva bajty jinam.

[elenril]

Tady se někde skrývá ponaučení o tom že UB je lepší nedělat.

[xkucf03]

UB?

[elenril]

Undefined behaviour. Unaligned access je UB na úrovni C - compiler má dovoleno s takovým kodem udělat naprosto cokoliv. Takže řešit nějaká specifika konkrétních architektur nemá moc smysl.

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

[Gilhad]

Zase "nasal demons" jsou mnohem barvitější řešení, bohužel jsem nenašel podrobnější popis, jak vyvolat zrovna tento konkrétní legalní efekt ...

[Jendа]

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.

[Jendа]

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.

[pc2005]

Njn klasický RISC, ten často ani nemá ty dva (32bit) spodní bity adresy zapojený. Ale teda architektura nic moc, unaligned exception to mohlo aspoň vyhodit (ale vím, často se to dá vypnout).

[Jendа]

Nerad bych vymýšlel kolo, proto se chci zeptat, jestli nevíte o nějakém existujícím standardu

Protobufs

[xkucf03]

To je vlastně podobné tomu, co mě napadlo jako první:

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?

[Martin Mareš]

Efektivitu je těžké soudit, dokud nic nevíte o tom, jak velká čísla se budou typicky přenášet (přesněji řečeno neznáte-li pravděpodobnostní rozdělení všech možných hodnot v dané aplikaci).

Režie 1/8 u varintů (ať už těch protobufových, nebo podobné konstrukce z LibUCW je myslím pro většinu aplikací velmi dobře snesitelná.

Samozřejmě se dá vylepšit, ale už to stojí trochu komplikací při kódování a dekódování. Zajímavý přístup (velmi blízký teoretického optima) je třeba SOLE Encoding z tohoto článku (Dodis, Patrascu, Thorup: Changing Base Without Losing Space).

[Filip Jirsák]

Např. ASN.1. Používá se např. ve formátech pro PKI.

[Martin Mareš]

ASN.1 opravdu dosahuje dokonalosti. Přes léta pokusů se už nikomu nepodařilo vymyslet nic ošklivějšího. Byť autoři XML by měli dostat minimálně cenu útěchy za úpornou snahu *grin*

Pokud chcete rozumný self-describing formát, nabízí se například CBOR.

[Filip Jirsák]

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ý. A ošklivější formát se po letech pokusů podařilo vymyslet a dokonce i prosadit – JSON.

[Martin Mareš]

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.

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

[Martin Mareš]

ASN.1 je abstraktní – o které serializaci tedy mluvíš?

Je to vcelku jedno, hezká není ani jedna :)

[JS1]

+N za CBOR, to pouzit v praxi.

Pokud ten problem chce (autor blogpostu) resit teoreticky, pak je potreba si ujasnit, jake predpokladane rozdeleni maji prislusne hodnoty (cela cisla). Nejcastejsi moznosti jsou asi geometricke nebo zipfovo rozdeleni, ale i ty maji jeste parametr (ktery urcuje stredni hodnotu delek, tedy dvojkoveho logaritmu). A na zaklade toho zvolit prislusne optimalni prefixove kodovani.

Nebude existovat zadne optimum na vsechny problemy; zalezi to na rozdeleni hodnot.

[xkucf03]

Měl jsem snahu to optimalizovat ve prospěch lidmi běžně tvořených dat, tzn. délek textových řetězců, počtů sloupců, počtů prvků v poli… a to tak, aby se jich co nejvíc vešlo do prvního bajtu. Nakonec z toho vyšel rozsah 0-250, což by ve většině těchto případů mělo stačit a zbytek se rozloží do více bajtů.

Nicméně teď se spíš kloním k tomu, že bych jako základní formát variabilních čísel použil ten varint/base128, který sice do prvního bajtu nacpe jen hodnoty 0-128, ale pro vyšší čísla je efektivnější a funguje v principu pořád stejně až do nekonečna, což má svoje kouzlo. A i ten rozsah 0-128 by měl být poměrně dostatečný (128 sloupců v tabulce je až až, textový řetězec o téhle délce taky pojme většinu běžných atributů, pro prvky v nějakém menším poli to taky stačí) a v těch ostatních případech má režii 1/8 bitů, což není až takové plýtvání.

[Ivorne]

Tvůj přístup má problém v tom, že je příliš složitý a přitom je efektivní jen pro ty jednobajtové hodnoty. Když chceš zakódovat hodnotu větší než 1 byte tak ti to zabere vždy o jeden byte víc než má původní hodnota (první byte nese pouze informaci o tom, že se nejedná o jednobajtovou hodnotu a kolik že bajtů to má).

Ten protocol buffers přístup mi přijde lepší. Vyrobili to v Googlu pro extra úsporné přenosy dat, takže tam bych věřil, že se nad tím docela zamysleli. Mají tam udělané kódování i pro další datové typy i pro kódování celé zprávy (takže to umí i optional hodnoty a pole). Takže jak ses ptal, jestli už někdo něco takového neudělal, abys znovu nevymýšlel kolo, tak bych řekl, že tohle je ono.

Ty varinty (https://developers.google.com/protocol-buffers/docs/encoding) fungují, jak už se tu zmiňovalo, tak, že jeden bit v každém bytu informuje o tom, jestli následuje další byte nebo ne. Podle mě to dává smysl - počet bitů využitých pro zakódování informace o délce zprávy je úměrný délce zprávy, takže malá čísla neplýtvají tolik místa kódováním délky. Je pravda, že u velkých čísel to má potenciál vyplýtvat více místa než by bylo třeba. Ale horší efektivitu než tvé navrhované řešení to má až u čísel s devíti bajty. A jak často se někde objevuje číslo větší než 9 bajtů a není to float?

Taky by ta efektivita těch varintů šla upravit tak, že se řekne, že první 4 bajty obsahují po jednom extra bitu informující o tom, jestli existuje následující bajt, dále to jde tak, že vždy dva bajty mají jeden bit informující o tom, jestli existují následující dva bajty, po čtyřech takových dvojicích budou následovat čtyři čtveřice obsahující po jednom extra bitu a tak dále - vždy po čtyřech skupinách se zdvojnásobí velikost skupiny. Tohle by víceméně zachovalo efektivitu varintů pro malá čísla a přitom by to naprosto potlačilo (teoretický) problém s extra velkými čísly. Při tom by se jen lehce zhoršila situace číslům s nějakými 5 - 8 bajty.

[Josef Kufner]

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

[kralyk z abclinuxu]

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

[xkucf03]

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:

• základní formát pro značení délek atributů a počty prvků
• zarovnaný či nezarovnaný formát

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.