Not Invented at Google (NIG)

10.1. 03:33 | Přečteno: 690× | flame

Každé porušení základních pravidel SW vývoje se vám jednoho dne vymstí a pravidla č.1. - nikdy, za žádných okolností, nepoužívejte knihovny od Google (a nejlépe SW od Googlu vůbec, jak dodává Ladislav Stroupežnický) obzvlášť!

Bohužel i já jsem se takového přešlapu kdysi, v mladické nerozvážnosti, dopustil když jsem z lenosti v Qt MVT pluginu použil Googlí protobufs a následky - celý ten Googlí bastl sestavovat pro 4 platformy - za to nesl po celý zbytek života. Ale s příchodem nejnovější, abseilem prolezlé, verze co se v AppVeyor CI buildu nepřeloží ani za hodinu do vcpkg je i s mojí bezbřehou trpělivostí konec!

Invented here, not at Google. Aneb zbavujeme se protobufs

Příbuzné a souborové formáty si člověk nevybírá, takže co dělat, když vám nějaký hipster protobufs vnutí do projektu? Napsat si vlastní parser! A na příkladu "Mapbox Vector Tile Specification" si dnes ukážeme jak na to.

Krok číslo jedna - přepíšeme protobuf definici (v barvě):

package vector_tile;

option optimize_for = LITE_RUNTIME;

message Tile {

        // GeomType is described in section 4.3.4 of the specification
        enum GeomType {
             UNKNOWN = 0;
             POINT = 1;
             LINESTRING = 2;
             POLYGON = 3;
        }

        // Variant type encoding
        // The use of values is described in section 4.1 of the specification
        message Value {
                // Exactly one of these values must be present in a valid message
                optional string string_value = 1;
                optional float float_value = 2;
                optional double double_value = 3;
                optional int64 int_value = 4;
                optional uint64 uint_value = 5;
                optional sint64 sint_value = 6;
                optional bool bool_value = 7;

                extensions 8 to max;
        }

        // Features are described in section 4.2 of the specification
        message Feature {
                optional uint64 id = 1 [ default = 0 ];

                // Tags of this feature are encoded as repeated pairs of
                // integers.
                // A detailed description of tags is located in sections
                // 4.2 and 4.4 of the specification
                repeated uint32 tags = 2 [ packed = true ];

                // The type of geometry stored in this feature.
                optional GeomType type = 3 [ default = UNKNOWN ];

                // Contains a stream of commands and parameters (vertices).
                // A detailed description on geometry encoding is located in 
                // section 4.3 of the specification.
                repeated uint32 geometry = 4 [ packed = true ];
        }

        // Layers are described in section 4.1 of the specification
        message Layer {
                // Any compliant implementation must first read the version
                // number encoded in this message and choose the correct
                // implementation for this version number before proceeding to
                // decode other parts of this message.
                required uint32 version = 15 [ default = 1 ];

                required string name = 1;

                // The actual features in this tile.
                repeated Feature features = 2;

                // Dictionary encoding for keys
                repeated string keys = 3;

                // Dictionary encoding for values
                repeated Value values = 4;

                // Although this is an "optional" field it is required by the specification.
                // See https://github.com/mapbox/vector-tile-spec/issues/47
                optional uint32 extent = 5 [ default = 4096 ];

                extensions 16 to max;
        }

        repeated Layer layers = 3;

        extensions 16 to 8191;
}

do C++ (v barvě)

class Data
{
public:
	enum GeomType {
		UNKNOWN = 0,
		POINT = 1,
		LINESTRING = 2,
		POLYGON = 3
	};

	struct Feature
	{
		Feature() : id(0), type(UNKNOWN) {}

		quint64 id;
		QVector<quint32> tags;
		GeomType type;
		QVector<quint32> geometry;
	};

	struct Layer
	{
		Layer() : version(1), extent(4096) {}

		quint32 version;
		QByteArray name;
		QVector<Feature> features;
		QVector<QByteArray> keys;
		QVector<QVariant> values;
		quint32 extent;
	};

	bool load(const QByteArray &ba);
	const QVector<Layer> &layers() const {return _layers;}

private:
	QVector<Layer> _layers;
};

V našem případě tedy do Qt/C++, variantu pro stl si čtenář může udělat za domácí úkol. Výsledek je "API" prakticky totožné s tím, co vypadne z protobuf kompilátoru (protoc), tedy žádná magie. Ta přijde až v kroku č. 2. - píšeme parser.

Protobuf parser

Ač to na první pohled nevypadá, protobuf binární formát (wire format) má poměrně jednoduchou strukturu. V zásadě jde o posloupnost záznamů "klíč - hodnota", kde hodnota může být jeden ze čtyř základních typů: VARINT, I64, LEN, I32. Dle historek rodových stařešin údajně ještě existují dva typy: SGROUP a EGROUP, ale "jejich příběh my neznáme a tak o něm nezpíváme". VARINT je integer s variabilní délkou, I32 a I64 4(8)B typy (uint32/float/..., uint64/double/...) a LEN je (pomocí VARINT) zakódovaná délka dat pro struktury a stringy. Umíte-li dekódovat tyto čtyři typy, umíte dekódovat libovolný protobuf stream.

Tedy ne tak docela, ještě potřebujete znát jeho strukturu. Existují sice tooly jako protoscope, co se tváří, že to umí bez ní, ale ty fungují na základě odhadů. My ale schéma známe a tak můžeme napsat jednoduchý pseudo-LL1 parser, který binární data rozebere do naší připravené struktury.

Výsledky

Ač primárním účelem celého cvičení nebyl pokus o zrychlení kódu, výsledek je 2% zrychlení zpracování dlaždic. To se může zdát málo, ale z Amdahlova zákona a faktu, že parsování dat dělá pouze ~10% celého zpracování plyne, že náš "custom" parser je výrazně rychlejší, než ten od Googlu. Výsledná binárka je navíc o 15% menší a/nebo bez závislosti na libprotobuf-lite a asi 25 abseil* knihovnách. Zde je nicméně potřeba přiznat, že důvodem, proč jsme rychlejší je kromě podstatně jednoduššího kódu než "padá" z protoc "kompilátoru" především to, že můžeme parser podstatně lépe propojit s Qt a použít třeba trik s "bezkopírovacími" QByteArray.

Závěr

Zbavit se "oseru" s protoc, libprotobuf a "rakovinným" abseilem není tak těžké, jak by se na první pohled mohlo zdát. Ustojíte-li, že se vám hipsteři budou smát, že píšete SW zcela proti moderním trendům (pomalejší, větší a s více závislostmi), dostanete za trochu snahy s implementací a především odladěním detailů, o kterých jsem zde taktně pomlčel, celkem slušnou alternativu, která se v dlouhodobém horizontu bohatě zaplatí.

       

Komentáře

[kralyk z abclinuxu]

Úplně nerozumim tomu východisku. To neexistuje nějaký parser protobufů pro C++ bez abseilu? A k čemu vlastně vůbec potřebuješ v tom pluginu protobuf?

[Martin Tůma]

Úplně nerozumim tomu východisku. To neexistuje nějaký parser protobufů pro C++ bez abseilu?

AFAIK existují i nějaké alternativní knihovny na protobufy, ale budou mít podobnou sadu problémů (snad kromě prolezlosti abseilem). Bude potřeba nějaký "kompilátor" proto souborů a 3rd party knihovna v runtime. Když už to člověk řeší, tak tentokrát už rovnou pořádně. Pokud se za cenu ~350 řádků kódu můžu obojího zbavit (navíc s benefitem vyššího výkonu), tak to rád udělám.

A k čemu vlastně vůbec potřebuješ v tom pluginu protobuf?

MVT je formát navržený hipsterskými diletanty, takže jednotlivé dlaždice jsou tak přímo specifikovány/zakódovány. Mezi "lidmi od JavaScriptu" je to celkem rozšířený myšlenkový pochod, že souborový formát je prostě soubor s protobufy. Ten formát má ale i mnohé další problémy, které by vydaly na samostatný flame. Největší diletantství například je, že v každé dlaždici chybí jeden jediný byte se zoomem a s MVT se tak nedá pracovat jako s běžnými rastrovými/vektorovými obrázky a vytvářet pro něj standardní obrázkové pluginy jako existují pro PNG, JPEG či SVG...

[kralyk z abclinuxu]

Pokud se za cenu ~350 řádků kódu můžu obojího zbavit (navíc s benefitem vyššího výkonu), tak to rád udělám.

Ok. Jenom mě to zajímalo. Je pravda že v práci na to taky máme vlastní parser co generuje přesně to, co potřebujeme...

MVT je formát navržený hipsterskými diletanty, takže jednotlivé dlaždice jsou tak přímo specifikovány/zakódovány. Mezi "lidmi od JavaScriptu" je to celkem rozšířený myšlenkový pochod, že souborový formát je prostě soubor s protobufy.

To mi nepřijde zas až tak hrozný. Určitě lepší než další random binární formát, který si někdo vycucá z prstu komplet...

Stížnost na chybějící zoom level chápu.

[Martin Tůma]

To mi nepřijde zas až tak hrozný. Určitě lepší než další random binární formát, který si někdo vycucá z prstu komplet...

Mě na tom, kromě pár technických věcí, vadí především to, že tím člověku vnutí i celý ten šílený Googlí ekosystém. Nebo přesněji skoro vnutí, protože jak se ukazuje a je o tom i ten blog, jde to i bez Googlu. Ale když o tom tak přemýšlím, tak máš pravdu, že může být ještě mnohem hůř. Když MVT člověk srovná třeba s S57(ENC) mapama s jejich ISO 8211 je MVT ještě zlatý. O Garminu s jeho IMG ani nemluvě, to už je vyloženě mimo jakoukoliv stupnici zvrácenosti - to není formát ale exponenciální stavový prostor speciálních případů...

[včera 23:49 luky]

btw Garmin pouziva tundle protobuf knihovnu https://jpa.kapsi.fi/nanopb/ Nevim teda presne k cemu.

[Martin Tůma]

To je z bláta do louže. Jak už jsem psal výše, stále to znamená nutnost nějakého "kompilátoru" proto souborů a závislost na externí knihovně. Sice ne rakovinným abseilem prolezlé, ale zase poměrně obskurní.

A tím, že něco používá GARMIN, tím bych radši vůbec neargumentoval, to je spíš vyloženě varování. Ta firma je nekvaliním SW vysloveně vyhlášená čemuž se vůbec nedivím, protože když tam do vývoje pustí lidi, co jsou v jednom souborovém "formátu" schopni vymyslet asi tak 25 různých způsobů jak zakódovat integer do 1-4 bytů, tak z toho nakonec nic jiného než katastrofa vypadnout nemůže...