4 ms·
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 bytew
by bitwize 9y ago
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.
- kentonv 9y agoThat'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.)
- kuschku 9y ago> 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. As long as the Cap'n Proto or ProtoBuf data is properly aligned within of your custom file format, or you might end up with unusual slowness: https://blogs.msdn.microsoft.com/oldnewthing/20150116-00/?p=43133 https://blogs.msdn.microsoft.com/oldnewthing/20150116-00/?p=...
- kentonv 9y agoYes, 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.)
- kuschku 9y agoYes. For raw cap'n'proto messages. But when writong custom file formats you might end up having cap'n'proto data embedded at an unaligned offset.
- bitwize 9y agoNow 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 :)
- bitwize 9y ago> 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.
- kentonv 9y ago> 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.
- zerokernel 9y ago> 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.
- bitwize 9y agokentonv 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.