9 ms·

Karmem: A fast binary serialization format faster than Google Flatbuffers

157 points by siddontang 4y ago

raggi 4y ago
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.
- klabb3 4y ago
  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.
benreesman 4y ago
The (admittedly self-reported, but by fucking Google) FlatBuffers benchmarks are here: https://google.github.io/flatbuffers/flatbuffers_benchmarks.html 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?
foxbee 4y ago
Nice tool. What size is the team who created this and what are the plans going forward (maintenance, community growth)?
jerryjerryjerry 4y ago
- cma 4y ago
  This seems to be a spam account, same post on each open source project.
  - jerryjerryjerry 4y ago
    Nope, simply because I always use that web to get some insights on open source project, especially those attracting more attention.
- sa46 4y ago
  That is a neat tool but your comment gives off strong growth-hacking vibes.
  - jerryjerryjerry 4y ago
    Feedback rogered and would pay attention to it.
malkia 4y ago
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.
erwincoumans 4y ago
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?
- liuliu 4y ago
  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.
lalaithion 4y ago
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.
- rixed 4y ago
  They say you can append new fields in tables (a type of struct). No mention of enums.
- scaredginger 4y ago
  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.
judofyr 4y ago
> 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.
- heipei 4y ago
  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.
  - tikhonj 4y ago
    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").
    - gricardo99 4y ago
      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.
      - deleted 4y ago
        [deleted]
infogulch 4y ago
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/626e6d3b380eb5236c9a240978b1451662cb24d9 https://github.com/inkeliz/karmem/commit/626e6d3b380eb5236c9...
- klabb3 4y ago
  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.
scrame 4y ago
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?
- gizzlon 4y ago
  https://github.com/inkeliz/karmem#languages 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
jeroenhd 4y ago
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.
- quotemstr 4y ago
  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.
  - jeroenhd 4y ago
    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.
    - dolmen 4y ago
      Size of generated code matters when the target is WASM to run in browsers.
      - londons_explore 4y ago
        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.
junon 4y ago
Wonder how it compares to Capn Proto, which claims minimal to no serialization overhead.
- IshKebab 4y ago
  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.
  - junon 4y ago
    sqlite is not a serialization format though.
    - nly 4y ago
      But it makes a perfectly reasonable application file format. Coupled with schema evolution and an ORM it's pretty sublime.
    - IshKebab 4y ago
      Yes it is. They even have a page about it: https://sqlite.org/appfileformat.html 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.
    - kortex 4y ago
      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-databases-on-github-pages/ https://phiresky.github.io/blog/2021/hosting-sqlite-database...
nly 4y ago
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.
- remus 4y ago
  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.
summerlight 4y ago
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.
- deleted 4y ago
  [deleted]
bsaul 4y ago
side question : what's the popularity of protobuf vs flatbuffer those days ? is flatbuffer gaining a bit of momentum ?
staticassertion 4y ago
rkyv and postcard seem to be very promising and have been in development for a little while now https://rkyv.org/ https://rkyv.org/ https://github.com/jamesmunns/postcard 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.
no_circuit 4y ago
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.

157 points by siddontang 4y ago

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.

klabb3 4y ago
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.

benreesman 4y ago

The (admittedly self-reported, but by fucking Google) FlatBuffers benchmarks are here: https://google.github.io/flatbuffers/flatbuffers_benchmarks.html 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?

foxbee 4y ago

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

jerryjerryjerry 4y ago

cma 4y ago
This seems to be a spam account, same post on each open source project.
- jerryjerryjerry 4y ago
  Nope, simply because I always use that web to get some insights on open source project, especially those attracting more attention.
sa46 4y ago
That is a neat tool but your comment gives off strong growth-hacking vibes.
- jerryjerryjerry 4y ago
  Feedback rogered and would pay attention to it.

malkia 4y ago

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.

erwincoumans 4y ago

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?

liuliu 4y ago
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.

lalaithion 4y ago

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.

rixed 4y ago
They say you can append new fields in tables (a type of struct). No mention of enums.
scaredginger 4y ago
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.

judofyr 4y ago

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

heipei 4y ago
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.
- tikhonj 4y ago
  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").
  - gricardo99 4y ago
    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.
    - deleted 4y ago
      [deleted]

infogulch 4y ago

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/626e6d3b380eb5236c9a240978b1451662cb24d9 https://github.com/inkeliz/karmem/commit/626e6d3b380eb5236c9...

klabb3 4y ago
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.

scrame 4y ago

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?

gizzlon 4y ago
https://github.com/inkeliz/karmem#languages 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

jeroenhd 4y ago

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.

quotemstr 4y ago
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.
- jeroenhd 4y ago
  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.
  - dolmen 4y ago
    Size of generated code matters when the target is WASM to run in browsers.
    - londons_explore 4y ago
      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.

junon 4y ago

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

IshKebab 4y ago
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.
- junon 4y ago
  sqlite is not a serialization format though.
  - nly 4y ago
    But it makes a perfectly reasonable application file format. Coupled with schema evolution and an ORM it's pretty sublime.
  - IshKebab 4y ago
    Yes it is. They even have a page about it: https://sqlite.org/appfileformat.html 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.
  - kortex 4y ago
    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-databases-on-github-pages/ https://phiresky.github.io/blog/2021/hosting-sqlite-database...

nly 4y ago

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.

remus 4y ago
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.

summerlight 4y ago

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.

deleted 4y ago
[deleted]

bsaul 4y ago

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

staticassertion 4y ago

rkyv and postcard seem to be very promising and have been in development for a little while now https://rkyv.org/ https://rkyv.org/ https://github.com/jamesmunns/postcard 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.

no_circuit 4y ago

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.