Swapping bytes is a huge pain in the butt! When reading large binary files, it's so convenient and efficient to be able to mmap and make struct pointers right into the file. You can even deliver those files to web browsers and use JS's TypedArray to get random access into them.
(That requires a bit more than simply little-endian. It requires struct alignment and floating point formats to be the same. But with only a tiny bit of care it can be.)
For new code running in-core in 2018, I think little-endian is quite safe.
> Swapping bytes is a huge pain in the butt! When reading large binary files, it's so convenient and efficient to be able to mmap and make struct pointers right into the file.
No no no don't do this don't do this don't do this. This is how horrors and abominations like .doc, .xls, .psd happen.
The correct way to handle binary data is to unpack it into the struct byte by byte. The reason for this is that when you define a struct in C(++), there are not just endianness issues, but implementation-dependent issues of padding and alignment you have to consider. Recently, most compilers on most architectures standardized on self-alignment rules for all primitive types except char, but this is not guaranteed by the standard, it will bite you in the ass when you least expect it, and it will be decades yet before all the C code in the world is displaced by a single-implementation language like Rust.
The best way to write portable code that will work as intended is to treat all data coming from disk or over the wire as a bag of bytes, and not attempt to alias it to a struct.
I have to disagree with your “No no no”. It all depends on requirements.
When you’re on a PC, and working with files that you can reasonably expect will be exchanged (like doc, xls or pdf) — then your “No no no” heuristic is absolutely correct. As you pointed out, differences between compilers and between e.g. x86/amd64 are very likely to render these formats incompatible.
But when you’re working with files that only your software will access, unpacking it byte by byte will slow down IO by a huge factor compared to both mmap, and read/write of large blocks (the latter will likely translate to DMA i.e. the CPU will be free to do something else). When that’s the case (like for most videogames, even for PC ones), you don’t want to pay that performance penalty, you want to get that data in the memory ASAP.
Requirements can change, sometimes unexpectedly. But if you "know" for a fact that they won't, then doing the hypothetically more-portable thing at the expense of today's performance, is just plain overengineering.
> But when you’re working with files that only your software will access, unpacking it byte by byte will slow down IO by a huge factor compared to both mmap, and read/write of large blocks (the latter will likely translate to DMA i.e. the CPU will be free to do something else).
If:
* you're working with files that only your software will access AND
* you control, and understand, the CPU architecture of any machine that will touch that data structure and you KNOW that it will never change for the entire lifetime of that piece of data AND
* you always use the same version, or an ABI-compatible future version, of the same compiler that you KNOW will always lay out data the same way and you know what that way is AND
* you either don't need to touch this data structure in other programming languages, or you KNOW that this won't be an issue (for example because your programming language implementation was written in C, compiled against the same version of the compiler, and has an FFI that understands C structs)
THEN, you may proceed to mmap structs into memory. In practice these constraints are fairly commonplace; for example, NetBSD wscons device drivers report HID events which are specified in a struct, and because the HID events are likely never to leave the originating machine, only be passed from kernel space to user space, it makes sense to simply read(2) them straight into the struct.
And there's certainly nothing wrong with snarfing a large file into a char[], but when it comes time to extract meaning from it, unless you are absolutely sure that the underlying assumptions regarding data layout will never ever change, it will only cause marginal harm to do everything in byte offsets and shift and OR bytes to yield final values -- and this is the best portable way to access the data therein, agnostic of details about the compiler and CPU architecture.
In general it's a good idea to err on the side of caution by default, profile, and then optimize the hot paths as necessary bearing the constraints you're assuming in mind (and perhaps documenting them for good measure).
Maybe my initial statement was too strong, but I shudder whenever I see comments of the form "It's so convenient to just mmap() that sucker into a struct and access the fields!" Because they've never had to deal with the consequences of trying to access a struct from a Microsoft compiler serialized to disk, and finding out that GNU compilers have a quite different notion of how structure members are to be laid out in memory...
> In general it's a good idea to err on the side of caution by default, profile, and then optimize the hot paths as necessary bearing the constraints you're assuming in mind
In general, changing data formats to something incompatible is one of the most expensive changes you can possibly make to your software. If you’re not sure write a prototype and profile. Implementing knowingly inefficient data format for a performance-critical application isn’t a good idea.
> it will only cause marginal harm to do everything in byte offsets and shift and OR bytes to yield final values
Huge harm, in both runtime performance, and code size & complexity.
P.S. For applications where portability matters and you’re OK paying performance cost of that, the industry has moved towards XML based formats. Not only it fixes byte order issues, also text encodings, globalization, it’s human readable, and it’s fast enough for many practical applications. E.g. doc/xls that you’ve mentioned are deprecated by docx/xlsx, the latter are XML based.
This makes no sense in lots of applications. Today computers have hardware acceleration for moving chunks of data. Big chucks of data, unpack things byte by byte makes not sense on things that have to be efficient. It is like 20.000 times more efficient to do things with blocks.
If you move text around you probably don't care about efficiency and can do it. If you care about efficiency and price(using cheap components) it is a very bad solution.
We use in all our serial-deserial a very fine grained controlled C library and it has been working flawlessly for years. This library is interfaced with C++, java, objC, swift,clojure, rust...
Most compilers have directives for packing structs. What the OP suggests is something that can be done for high performance, but don't expect it to be portable outside of common architectures and compilers. I'd consider it something that shouldn't be done unless you really need the simplicity or performance.
No, dumping internal representations to disk is orthogonal to zero-static data formats. You can have a well defined format that doesn't require byte-by-byte parsing.
Both of those appear to work by deferring the parsing step to access time. You're still treating the thing as a bag of bytes and unpacking stuff out of it bytewise.
That's incorrect. When you load an int64 field from a Cap'n Proto field, you are doing a 64-bit load instruction directly from the source bytes. You are not doing byte-by-byte access nor any sort of translation or "parsing".
Cap'n Proto works by laying out data structures like a C compiler would, but following consistent, portable rules so that the layout is the same on all platforms. It then generates inline-able accessor functions to manipulate these structures which do pointer arithmetic similar to what a compiler would generate for accessing a struct. The end result is that accessing primitive fields from a Cap'n Proto struct is essentially identical in terms of machine instructions to accessing fields of a C struct.
To call that "deferring the parsing to access time" does not make sense.
(Note that for pointers, there are more differences: namely, because data will not always be loaded at the same address, pointers need to be relative rather than absolute. They also need to be bounds-checked for security. This adds a few instructions to pointer accesses, but those instructions look nothing like traditional "parsing" and certainly aren't byte-by-byte operations.)
Your statement earlier:
> The correct way to handle binary data is to unpack it into the struct byte by byte.
This is inaccurate. Byte-by-byte parsing is a valid way to do parsing but not the only way. Byte-by-byte parsers tend to be slow and -- arguably, more importantly -- overly complex and rigid. It is, for example, usually very hard to do "random access" with a byte-by-byte parser, because allowing out-of-order parsing tends to blow the code complexity through the roof.
On the other hand, with Cap'n Proto and similar approaches, you can trivially mmap() a very large data structure and traverse it randomly, and it "just works".
(Disclosure: I'm the author of Cap'n Proto, as well as the author of the first open source release of Google's Protocol Buffers, which does byte-by-byte binary parsing.)
> The end result is that accessing primitive fields from a Cap'n Proto struct is essentially identical in terms of machine instructions to accessing fields of a C struct.
Yes, Cap'n Proto is careful to require that the data is aligned.
(Protobuf, on the other hand, fundamentally doesn't allow for multi-byte loads in the first place since integers use variable-width encoding, so alignment is irrelevant there.)
Now that Cap'n Proto exists, why would you want to handle binary data any other way? Simply standardize on Cap'n Proto across your entire application, and problem solved :)
I only started contributing in '14, so most of what I heard is second hand information, this is all simpkified, and some parts will likely be wrong. It's also all my own opinion, I'm not representing any project here.
Basically, a decade ago a student started to work with some friends on an IRC client that integrates with a custom bouncer. Being a prototype, they just used Qt's serialization protocol between them. Over the years the project grew, at some point nokia funded development, it became Kubuntu's default IRC client (but only in the client+bouncer in one binary version, so without all the advantages), nokia was bought and closed and the department sold to BMW, and at some point.
Now, people tried writing third-party clients for this. And this became a minor issue, because the protocol was never documented. In favt, Qt's serialization was used for storing configs on disk, some blobs in the database, and over the network. It was later wrapped in TLS and deflate, and even at some point array-of-struct was turned into struct-of-array for the pattern during initialisation.
Either way, someone tried writing a mobile client for it, decided the protocol was insane, and instead built his own, almost identical client/bouncer system with an Erlang backend and json as protocol. This grew, and became IRCCloud.
Now, other people again tried developing third party clients for quassel. An android client was developed, but development was messy, and over the years, it stalled, because they reverse engineered the protocol, semi-successfully, and at some point didn't have enough time left, and gave up.
People reversed the protocol partially over the years again for pyquassel and quasselc/quasselbots/quassel-irssi.
Around then, another person tried reversing the protocol, and reimplementing it in JS for a webclient, which after a while became quassel-webserver.
Back then there was a lot of talk about replacing the protocol, but it was never done yet.
I, a user of irccloud around then, was annoyed with the costs (still being in high school myself, I couldn't afford the 4$/month, and the free tier wasn't enough), so I out for alternatives, and found quassel. But I hated the looks of Quasseldroid, so I forked it, and started working on the UI, and on features by reversing the protocol yet again. Not having actually programmed anything except for some delphi and VB.NET stuff, a tiny java project and one C# Windows Phone 7 app, my code was the worst, ever. Seriously, it was bad. After a while, discussion came about about turning this code into a PR, so I threw it all away, and rewrote it again, still bad, but it worked. This was merged, I became maintainer of Quasseldroid (because no one else was working on it anymore), and then, around 2015, I reversed the protocol, read the entire source of every implementation, wrote it all down on paper, studied every file format and every quirks and then I rewrote quasseldroid from scratch, in about 3 months, with every feature of the desktop version. I called this The Next Generation of Quasseldroid, jokingly quasseldroid TNG or later quasseldroid-ng.
A few weeks later, a new Android version came out, introducing Doze, and breaking everything about quasseldroid-ng. And so I rewrote it again, and before release, a new Android version broke it all again.
And that basically repeated, until I decided that it can't continue like this, and if we'll do major changes to the protocol, we might actually get a working version for Android that lasts longer than a few weeks in Beta before Google breaks it. So I learnt C++, and started contributing.
And that is basically my view of the story. Reverse engineering a protocol again and again, seeing variations of variations of the same protocol everywhere used, never properly documented. The Qt documentation is entirely different from what Qt actually puts on the wire. Blobs in the database.
But it also means backwards compatibility in the desktop client/core for every version from the past 10 years, and backwards compatibility on Android for every version of the past 6 years.
And now, maybe, I'll be able to help replace this, bit by bit. After the improvements to tge protocol that added major performance benefits, the next part is replacing the bouncer-side config format entirely, so I can properly containerise it.
TL;DR: no matter how good the support for a non-standard binary serialization format in your favourite language is, 10 years down the road people will reuse your protocol in a dozen more languages, and they'll have to reverse the protocol themselves, and will do a semi-good job at it, and because you never thought about backwards compatibility you now have a mess (we had luck because 99% of what we transmitted were key/value maps, and when reading we always used default values if the key didn't exist and ignored unused keys. Sometimes we did serialize structs, basically, though, and those places still cause me headaches today, and require workarounds to add features, e.g. the latest sendermode implementations)
This is interesting, and thanks for trying to clean up the protocol, but isn't this an orthogonal issue? The problems you are describing seem to be related to using an undocumented protocol, which is unrelated to using a custom serialization format vs building upon an existing one.
Building upon an existing, well-documented, and relatively sane serialization format (protobuf, capn't proto, message pack, json, heck even bencode for all I care) is usually a good thing, and so is decoupling the messages from the details of an implementation's internals. Language and framework internal serializers (such as Python's pickle or, apparently, Qt's serializer) tend to make it harder to achieve both goals.
> Building upon an existing, well-documented, and relatively sane serialization format
The problem with that is that whatever format seems well-documented and relatively sane today might become an obscure, unknown protocol 10 years down the road.
FWIW, Protobuf has now been open source for a decade and has been used for basically everything inside Google since about the turn of the century. Protobuf predates JSON, and I would wager that, worldwide, much more data is stored in Protobuf format and many more cycles are spent parsing Protobuf format than JSON. For Protobuf to die out, Google itself would have to die, as would quite a few other companies that heavily rely on it. It doesn't seem likely to happen any time soon.
I unfortunately am not in a position to make such strong statements about Cap'n Proto. However, implementations exist in C++, Java, JavaScript, Rust, Go, Python, and a bunch of other languages, so it should at least be much easier to deal with than Qt serialization.
(Disclosure: I'm the author of Cap'n Proto and of the first open source release of Protobuf.)
To be fair, DEC was once in the same position as Google; in fact, by employee count, it was twice as big (140k vs. 70k) and by market share of the whole computing market (you could speak of a "computing market" back then), it was significantly larger. In the mid-80s, the idea that a VAX might be supplanted by a massive worldwide computation network of billions of computing devices would've seemed like science fiction. (Note that at its peak, Digital had only sold 400,000 VAX.) You could be fairly confident that storing your data in the OpenVMS filesystem would be fairly future-proof.
When was the last time you saw a filename of the form NODE"accountname password"::device:[directory.subdirectory]filename.type;ver?
> Byte-by-byte parsing is a valid way to do parsing but not the only way. Byte-by-byte parsers tend to be slow and -- arguably, more importantly -- overly complex and rigid. It is, for example, usually very hard to do "random access" with a byte-by-byte parser, because allowing out-of-order parsing tends to blow the code complexity through the roof.
I have to agree here by experiences past. If the format in question has a chance of being performance sensitive, don't use FSM-based encodings [1]. It is inordinately difficult to optimize parsing these encodings even if you only have to handle tiny subsets, and it still won't be fast. A format like msgpack which prides itself on being very fast may be fast compared to JSON and other ways to express essentially arbitrary structures, but is DEAD SLOW compared to any direct encoding (be it a dedicated encoding you developed in literally a few hours or something like capnproto).
[1] Obviously, considering an encoding more complex than FSM means that you're an idiot and your application will almost certainly have security vulnerabilities related to the format in the future.
kentonv introduced the term 'parsing' into the discussion, not me. Originally I wasn't talking about parsing as such, just being explicit about the byte-offset, length, and ordering of any piece of data you fetch or store by doing (ptr[n] << 24) | (ptr[n+1] << 16) | (ptr[n+2] << 8) | ptr[n+3], or the corresponding write operation, if you're working with a chunk of data that came from, or is destined for, a file or the network. And if for whatever reason you want or need to work with structs, don't try to alias them onto the disk or network-bound bits. FSMs don't even come into it. It's just a matter of being a little more careful than mmap()ing into a C struct and hoping for the best.
> When you load an int64 field from a Cap'n Proto field, you are doing a 64-bit load instruction directly from the source bytes. You are not doing byte-by-byte access nor any sort of translation or "parsing".
Assuming little-endian CPU arch. It's followed by a byte reorder on big-endian architectures. (And you assume all Windows instances are little-endian, which probably-is-but-may-not-be the case.) You made the decision to optimize for what you consider the common case, but it does not generalize without added translation code to all cases. You may have hidden the translation code behind CapnProto's generated accessors, but CapnProto's structs are translation-free the way AWS Lambda is "serverless".
> To call that "deferring the parsing to access time" does not make sense.
Except you are deferring translation work (like byte reordering) to access time. Either that or you're hiding it in the serialization APIs. Again, it's like "serverless" computing: just because you've hidden it doesn't mean it's gone away.
> Byte-by-byte parsing is a valid way to do parsing but not the only way. Byte-by-byte parsers tend to be slow and -- arguably, more importantly -- overly complex and rigid.
There's a performance cost, but hopefully you're only doing serialization/deserialization when you intend to hit the disk or wire to read/write into/out of your struct. All in-memory processing happens in whatever endianness and alignment makes your CPU and compiler happy.
There's nothing "overly complex and rigid" about understanding a binary format as a bag of bytes and fetching scalar values (including offsets into the data structure) from it accordingly. This is how shit gets done when it comes to portably handling arbitrary binary formats. CapnProto can score a few wins by assuming things about the target CPU/compiler, restricting the binary format to conform to some of those assumptions, and papering over the rest with code hidden behind some of its APIs. But it's not a general solution to the problem of extracting meaning from an arbitrary hunk of bytes that may or may not have come from a CapnProto-conformant application.
> Assuming little-endian CPU arch. It's followed by a byte reorder on big-endian architectures.
Basically all common CPUs are LE.
(And basically all BE CPUs have dedicated instructions for reading LE data. It's true I haven't yet added the inline assembly to use those instructions in Cap'n Proto's reference implementation, but that's only because no one actually cares about these architectures.)
So in basically all real use, there's no machine-instruction-level difference between accessing a field of a capnp struct and accessing a field of a C struct. If the instructions are identical, then how can you say one is "deferred parsing" and the other isn't? What meaning does any such distinction have?
> There's a performance cost, but hopefully you're only doing serialization/deserialization when you intend to hit the disk or wire to read/write into/out of your struct.
Disk is usually cached, meaning it's already in physical memory and you're wasting time making a copy rather than using the data in-place.
Over the network, within a datacenter, bandwidth is basically infinite (in that your CPU probably can't process bytes as fast as your network interface can). Time spent serializing and parsing is very real and wasteful. I've seen servers spending 30% or more of their CPU time parsing protobufs.
Over the long-haul internet, perhaps the CPU time spent parsing/serializing is not as relevant compared to the time spent transmitting. Still, I'd rather spend my CPU cycles elsewhere -- like in a dedicated compression algorithm -- rather than twiddling bytes needlessly in a parser.
> handling arbitrary binary formats
Yes, we all agree that some binary formats can't be handled any other way. But if you're in control of the format you use, then you can design it in a way that doesn't require a "bag of bytes" model, and your code can be much simpler and more adaptable as a result.
(But the status quo on BE is that it does a load followed by a byte swap, which is probably pretty cheap anyway. The compiler might even already know how to optimize that into the appropriate LE-load instruction.)
(That requires a bit more than simply little-endian. It requires struct alignment and floating point formats to be the same. But with only a tiny bit of care it can be.)
For new code running in-core in 2018, I think little-endian is quite safe.