protobuf

proach resulted in a 2.64% speedup for overall encoding (which includes a lot more than just varints) on mid sized arm cores. I think it's very difficult to beat a single comparison and branch for the 1 byte case for actual encoding forwards or backwards, unless you know there's going to be long runs of one-byte values.

oking up the next field in the common case, because we have already pre-loaded the correct guess. > I haven’t managed to nail down a good algorithm for this yet, but I am working on a system for implementing a type of “branch prediction” for PGO, that tries to provide better predictions for the next fields to try based on what has been seen before. One delightful thing about the tail-call parser design is that the CPU's branch predictor effectively takes over the job of guessing. With a tail call parser, the dispatch sequence ends up looking like this: cmp QWORD PTR [rdi+0x8],rsi # Bounds check jbe .fallback movzx r10d,WORD PTR [rsi] # Load two bytes of tag mov eax,r10d and eax,0xf8 mov r9,QWORD PTR [rcx+rax*2] # Load table data xor r9,r10 mov rax,QWORD PTR [rcx+rax*2+0x8] # Load field parser function jmp rax # Tail call to field parser That "jmp rax" instruction is an indirect branch that can be predicted by the CPU. The CPU effectively guesses for us! And unlike any kind of guess we might have performed ahead-of-time, the branch predictor will constantly adapt to whatever patterns it is seeing in the data. This is good, because statically guessing ahead-of-time is hard.

be prepared to dispatch to any part of the code at any time. This means that the overall structure of a protobuf parser is conceptually a while() loop surrounding a switch() statement, just like a VM interpreter. The tricky part is that the set of "case" labels for a Protobuf parser is message-specific and defined by the fields in the schema. How do we accommodate that? The traditional answer was to generate a function per message and use the schema's field numbers as the case labels. You can see an example of that here (in C++): https://github.com/protocolbuffers/protobuf/blob/f763a2a8608... More recently, we've moved towards making Protobuf parsing more data-driven, where each field's schema is compiled into data that is passed as an argument to a generic Protobuf parser function. We call this "table-driven parsing", and from my read of the blog article, I believe this is what Miguel is doing with hyperpb. The trick then becomes how to make this table-driven dispatch as fast as possible, to simulate what the switch() statement would have done. That question is what I cover at length in the article mentioned above.

the whole codebase.

d to adhere to specific philosophies about the order you make changes in. >In fact it's probably a bit easier to link intentional behavior to a test while you have the spec in front of you and before the code is written. When implementing to a spec you are absolutely right, but a very small amount of software is completely or even mostly specified in advance. >I find people who write test after tend to (not always, but strong tendency) fit the test to the code rather than the requirement. This is really bad. I agree this can lead to brittle tests and lack of spec adherence, but if you are iterating on intermediate state and writing tests as you go, the structure of the code you wrote 30 seconds ago is very much influencing the test you're writing now. Another issue is that fault injection tests basically require coupling to the implementation - "make the Nth allocation fail" etc. The way I prefer to write these is to write the implementation first, then write the fuzz test - add a few bugs in the implementation, and fix/enhance the fuzz test until it catches them. Fuzz testing is one of the best bang-for-buck testing methodologies there is, and in my experience it's very hard to write a really good fuzz test unless you already have most of your implementation, so you can ensure your fuzz tester is actually exercising the stuff you want it to. >Assuming Im understanding you correctly (you're building something like terraform?), I write library code for mobile phones, mostly in Java/Kotlin. I recently did some open source work (warning: I am not actually very proficient with C, any good results are from enormous time spent and my code reviewers, constructive criticism very much welcome). Here's a few somewhat small, contained changes of mine, so we can talk about something concrete: https://github.com/protocolbuffers/protobuf/pull/19893/files This change alters a lock-free data structure to add a monotonicity invariant, when the space allocated is queried on an already-fused arena while racing with another fuse. I didn't add tests for this - I spent a fair bit of time thinking about how to do it, and decided that the type of test I would have to write to reliably reproduce this was not going to be net better at preventing a future bug, given its cost, than a comment in the implementation code and markdown documentation of the data structure. I don't know how I would really have made this change with a TDD methodology. https://github.com/protocolbuffers/protobuf/pull/19933/files This change moves a memory layout - again, I don't know how I would have written a test for this, besides something wild like querying smaps (not portable) to see if the final page of the arena allocation had faulted in. https://github.com/protocolbuffers/protobuf/pull/19885/files This change was written more in the way you recommend - but the whole change is basically a test. I debugged this by reading the code and thinking about it, then wrote up a pretty complicated fuzz test to help find any future races. I'm guessing that you would not consider adding debug asserts to be a violation of "write the test first"? So in this case, I followed TDD's order - not because I was following TDD, but because the code change was trivial and all the hard work was thinking about the data structures and memory model. https://github.com/protocolbuffers/protobuf/pull/19688/files All the tests were submitted before the implementation change here, but not because of TDD - in this case, I was trying to optimize performance, and wrote the whole implementation before any new tests - because changing the implementation required changing the API to no longer expose contiguous memory. But I did not want to churn all the users of the public API unless I knew my implementation was actually going to deliver a performance improvement - so I didn't write any tests for the API until I had the implementation pretty well in hand. Good thing too, because I actually had to alter the new API's behavior a few times to enable the performance I wanted, and if I had written all the tests as I went along, I'd have to go and rewrite them over and over. So in this case I wrote the implementation, got it how I wanted it, wrote and submitted the new API (implemented at first on the old implementation) and added tests, updated all callers to the new API, and then submitted the new implementation. I don't think TDD would have led to better results in these cases, but you sound like a TDD believer and I'm always interested to hear anything that would make my engineering better.