Karmem: A fast binary serialization format faster than Google Flatbuffers | Hacker News Reader

Karmem: A fast binary serialization format faster than Google Flatbuffers

github.com

157 pointssiddontang69 comments

Looking at the source code, this seems to work by generating dedicated parser code for a yiven definition which will copy values in a certain order through a flat copy.

I'm seeing little specifications or conversions regarding endianness so I'm guessing that's out of scope for this project. It seems almost completely backwards incompatible and I'm not too sure about their security validations. I don't think this and Flatbuffers are competing in the same space, really.

I definitely believe this is fast, it's as close to a memcpy to a network packet as you can get. I'd be wary to use this on external data in any native language without any kind of fuzzing first.

That said, I do like the way the generators work.

Generating code per message might not be the right choice anyway: if you have a lot of messages, a table driven approach can save you a lot of code size. Optimizing for speed in microbenchmarks can lead one to pessimize overall program architecture in ways that are hard to undo later.

It depends on your application, but if it's just generated code then I don't really see the problem with code size. As long as it's easy to (de)serialize data or add a nice big facade between the generated code and business logic, the generated backing code can be a complete mess of spaghetti code for all I care.

Size of generated code matters when the target is WASM to run in browsers.

But only if you have a lot of message formats...

Generally, message specifications are written by hand, so even a big project may only have a couple of hundred. Doesn't sound so bad.

Also, presumably, if code size really is a big concern, you can decode this in more code efficient ways too, as long as you are less concerned with performance.

You might be surprised to see how quickly mechanically-generated marshaling code adds up. Look at Android's frameworks.jar one day and see how much is just the same AIDL-generated Parcel-manipulation code over and over again. Cache effects and IO costs are so severe in modern computing that my default (but rebuttable!) position is to prefer table-driven approaches over code generation wherever possible.

Windows COM switched from codegen to table-driven "stubless" marshaling decades ago at no noticeable cost to performance and with a huge code size win.

> Karmem has proven to be ten times faster than Google Flatbuffers

I’d recommend not using the word “proven” here. In computer science this word typically refers to a mathematical proof. In this case it seems that you ran a regular benchmark for some schemas.

I’d also like to see more what the benchmark actually does. A typical trade-off of these formats is how much you do up-front vs on-demand. E.g. accessing fields after multiple variable-length field: Here it’s possible during “decoding” to make sure all fields can be accessed in O(1), or you can do nothing and then every time you access a field you compute the field location. Whether the benchmark accesses the field once or ten times will make a huge difference.

In general: If you’re just telling me that it’s 10 times faster without explaining why I will be skeptical.

Not a native speaker, but I thought that's what the difference between "proven" and "proofed" is. The latter is the type of mathematical proof you are referring to, the former the colloquial attribute of having been used successfully for that purpose.

People don't generally use "proofed" like that—I would always use "proven" to talk about something that had a mathematical proof, and "proofed" only comes up in specialized areas like publishing (where it's used as the past tense of making a proof of something to be printed or as short for "proofread").

proofed is also used at times in a baking context, such as proofing dough (i.e. sufficiently risen due to maturity of the yeast culture)

Otherwise I agree, as a native english speaker I’m not familiar with it being used in engineering/mathematics contexts.

I use "proved" for mathematics. For me (middle-aged British) "proven" sounds a bit pompous and rhetorical, not the sort of language an honest down-to-earth mathematician would use.

I’ve never seen “proofed” used as anything but a hyphenated suffix meaning “protected against”. E.g. sound-proofed.

It’s pretty normal to use “proved” in place of “observed” or “measured” in day-to-day speech though. Usually a few repeatable measurements are enough proof (evidence) for most people to consider something “proven”.

Edit: I forgot the proofread meaning pointed out by the sibling comment.

A reasonable guess but ultimately wrong. "Proofed" is not a word, "proven" is the correct adverb form (as in, "In this paper it shall be proven that..."), "proved"/"proving"/"proves" is the correct verb (depending on tense), all these forms of "proof" can be used in a colloquial sense like you tried, but never in a technical setting where an actual mathematical proof might actually be presented. "Shows"/"demonstrates"/"suggests"/"evidences" all better fit your intended use case. The rules in English are arbitrary and the patterns are inconsistent and misleading (and therefore anyone who obsessively enforces said rules is a petty pedant doing it solely for the enjoyment of acting smarter than others).

> A reasonable guess but ultimately wrong. "Proofed" is not a word

And if it were I’d certainly assume it was a reviewing / publishing concept related to proof copies and proofreading (as in, a proofed copy would have gone through proofreading and no error would’ve been found).

Not related to the logical concept.

"Proofed" is not a word

Well it is, but it has to with a baking technique rather than anything mathematical.

It's also commonly usef for "having proofread", and "made waterproof".

>"Proofed" is not a word

Well, it is. It means several things (but not what the parent guessed).

Among those:

- something having been proofread

- a yeast having been activated

- made something waterproof

No one has successfully connected proof (v) and prove (v) here, though the examples of the former are exhaustive in modern speech.

The difference is the two kinds of proving, one of which is vanishing from the language: the sense of testing something, practically, rather than by reason or evidence. A proof copy is when a type plate is prooved, the rising of dough prooves the culture's activity.

So these irregular noun-to-verb forms exist because proof has largely lost the second meaning.

Beyond what you already said, "faster" can be contextual in the sense that a more terse encoding results in faster transfer over networks or busses, though it's often at a cost in encode/decode speed.

I'm on the side of the original wording here as far as correctness is concerned - "has proven to be" is a common expression for "in our experience, it is", whereas "has been proven to be" would give the connotations of formal proof.

This is just one of those quirks of human language. Yes it's occasionally annoying similar things have very disparate meanings, but English in particular is never going to shake them off.

It's all trade-offs.

Flatbuffers trades off encoding speed, programmer ergonomics and binary size (it produces many bytes and it's awkward and still pretty slow to encode) for decoding speed (almost a no-op if you forego buffer verification, which you shouldn't most of the time). Imho it's not a good choice for network wire formats, but for storage it's pretty good.

Agreed. Given the number of serialization formats available at this point, it feels like anything that doesn't start off with a discussion of the trade offs they've made and how this affects the various aspects of performance is a bit of a red flag that they're not actually bringing anything novel to the table.

Go never really clicked with me, but isn't the point of serialization formats interoperability?

Like, ok, its 10x faster unzipping than another obscure language dependent format, but how is that better than perl storables or python pickles or ruby ser's other than being "faster"?

How do i call this from java or dotNet, and why would i do this other than to make everyone I work with miserable to adopt yet another format?

https://github.com/inkeliz/karmem#languages

    Languages

    Currently, we have focus on WebAssembly, and because of that those are the languages supported:

    AssemblyScript
    Golang/TinyGo
    ~Swift/SwiftWasm~
    Zig
    C

To get accepted in most of the game engines, the author would need to provide a way to override malloc/realloc/free - even better if no need to realloc.

That is an impressive performance claim, almost 10 times faster than flatbuffers.

Where is the flatbuffers native C (or C++) implementation of the benchmark? Are memory allocations avoided/excluded in the benchmark?

Seems the benchmark does read into native structs in both Flatbuffers and this in Go. I am confused by the performance claim too. Seems very similar design v.s. fbs, would be surprised if it is from format differences rather than codegen / Go implementation inefficiencies.

Wonder how it compares to Capn Proto, which claims minimal to no serialization overhead.

You're referring to the fact that Capn Proto claims to be zero copy. That doesn't mean there is no serialisation overhead.

In my experience with Capn Proto, the vast majority of the time the zero copy feature is pointless. The Capn Proto C++ APIs are extremely unergonomic so 99% of the time you end up copying the data into your internal nice C++ structures anyway, completely giving up zero copy.

I've used Capnp quite a lot and I really wouldn't recommend it. It's quite old and complex and the unpleasantness of the API alone is enough to put me off. I would pick Protobufs every day for small amounts of data.

For large amounts you are better off with SQLite or DuckDB.

sqlite is not a serialization format though.

But it makes a perfectly reasonable application file format. Coupled with schema evolution and an ORM it's pretty sublime.

Yes it is. They even have a page about it: https://sqlite.org/appfileformat.html

It's a format. You can serialise data to it. What about it isn't a serialisation format?

Obviously I wouldn't recommend it for small amounts of data, e.g. for RPC calls. But when you need to store lots of data it's much better than JSON or binary JSON style formats.

It's a data format which can be expressed as a contiguous series of bytes and sent/stored; it's a serialization format.

This is not just nit-picking, it's been used precisely as such:

https://phiresky.github.io/blog/2021/hosting-sqlite-database...

Sorry, should have been specific. It's not used as a _wire_ serialization format.

Capn'Proto isn't that bad. I've used the C++ quite a bit, and while the authors code style isn't to my taste it's fairly well designed (nice layering that lets you implement different use cases, like integrating the RPC framework with your own event loop).

There's also not much out there comparable to its capability passing RPC either.

Agree on the zero copy though, and the RPC framework does malloc a lot.

Don't know if the owner will ever read this comment, but please add some sections on:

  * Its design goals and rationale
  * How those decisions are translated into the actual performance
  * What is the trade off made to achieve that
  * Why should/shouldn't anyone else use it

Rather than just a vague performance claim that it's ten times faster than something else. It's not just for this specific library, but applicable to any libraries seeking for broader audiences.

There one commit referencing my favorite data structure [1], the discriminated union (DU) / tagged union / enums with values:

> kmparser: implement id generator

> That is the first step to implement Unions/Interfaces, it's also useful to know what is the expected message type to decode.

I don't see any other mention or plan about DU's in the repo or metadata. I'm curious what their position is on it.

[1]: https://github.com/inkeliz/karmem/commit/626e6d3b380eb5236c9...

I don't even know if it's a proper data structure in the CS sense, but I couldn't agree more with the sentiment. It's a simple concept and together with pattern matching it just makes life so easy it's hard to go back to the alternatives.

Case in point: I used rust for 1-2 years and am now on a project in Go. Even though Go fits my style and my use case better, I miss enums soo much. Both the std lib types like results and option but also the custom ones.

I suspect a lot of the speed comes from structure specific serialization (avoiding reflect). This can probably done with less unsafe code, and for most use cases that'd be a better trade-off.

Yeah. I have found that for message passing systems the tooling around multiple message types is more important in practice than optimizing for a single specific type. You can solve this with unions/tagged enums or some bespoke "message type metadata", but you HAVE to solve it some way. On the receiver end, you need to have a good story for routing different kinds of messages.

side question : what's the popularity of protobuf vs flatbuffer those days ? is flatbuffer gaining a bit of momentum ?

What’s the backwards compatibility story for coding using Karmem? When is it legal to add, modify, or remove a struct field without having to recompile all of the binaries using this format and replace them atomically? When is it legal to add, modify, or remove a struct field without requiring code to be refactored? What about enum variants?

These questions may not matter for every use case (e.g. you ship a single binary from a single codebase) but I think that clearly defining these rules opens up a lot of very cool use cases that are otherwise prohibited.

Very good questions. They do mention:

> In order words: you can't edit the description of one inline struct without breaking compatibility.

and

> Tables: Tables can be used when backward compatibility matters. For example, tables can have new fields append at the bottom without breaking compatibility.

Otherwise, I agree it's rather unclear exactly what you can do with tables.

They say you can append new fields in tables (a type of struct). No mention of enums.

Keeping some context in mind is probably helpful here. The target is WASM. And if you look at the organization the repo own is a part of, it is a web wallet for the cryptocurrency Nano.

So perhaps using a generic message serialization library is too slow for its use case since WASM's data types are just ints and floats since the parsing code can't behave like on a native CPU with things like bytes and C-structs?

It would have been great if they had disclosed links to issues regarding out-of-bounds access for things like Protobuf or Flatbuffer.

Nice tool. What size is the team who created this and what are the plans going forward (maintenance, community growth)?

rkyv and postcard seem to be very promising and have been in development for a little while now

https://rkyv.org/ https://github.com/jamesmunns/postcard

postcard seems like it would be particularly strong for the wasm use case as it produces small messages that are light in memory.

The (admittedly self-reported, but by fucking Google) FlatBuffers benchmarks are here: https://google.github.io/flatbuffers/flatbuffers_benchmarks.....

My anecdotal experience ties out with those FWIW.

10x "faster" than that is something targeting an FPGA, and I don't see any Verilog in the repo.

Come on folks, #1?

Reply on news.ycombinator.com