upb

ate a link ensures that no reference cycle spans groups. This is imprecise and relatively wasteful if the group grows really large. But you can make it totally precise for any subgraph of refcounted objects that you're willing to freeze. At freeze time, compute strongly-connected components, and each SCC becomes a refcounted group. For any frozen subgraphs, the refcounting is totally precise. And unfrozen objects can reference frozen ones (but not the other way around). If your application ends up freezing most of the graph, this works great. Or if you're ok with the collection being pretty coarse for your groups of objects, it also works great. If you have an application that can't freeze the graph and wants pretty precise collection, this doesn't work so well. More info about my scheme is in comments in these headers: https://github.com/haberman/upb/blob/master/upb/refcounted.h https://github.com/haberman/upb/blob/master/upb/refcounted.c I always was curious if the semantics of this scheme would play nicely with the ownership system in Rust.

hese "virtual arenas" by computing strongly-connected components at freeze time. This makes the scheme optimal for frozen objects. For mutable objects, the groups are computed more conservatively and objects may not get freed as often as they otherwise would with a perfect scheme (ie. the same downside of an arena). I would love to know how this scheme might possibly be modeled in Rust. Since Rust also has strong semantics around mutability and immutability, it seems possible that a very nice idiomatic Rust interface could be implemented around this scheme, giving more precise cleanup than an arena while still allowing circular structures.

/github.com/haberman/upb). Instead of using static code generation, I use a JIT approach where I generate specialized code on-the-fly. This approach is particularly important when you are wrapping the library in an interpreted language like Python/Ruby/Lua/JavaScript, because users of these languages don't have a compile cycle at all, so adding one is a large inconvenience. My library isn't ready for prime time but I'm hoping to have something ready to use this year.

that's doing register allocation and optimization. Writing this sort of JIT that uses a static register allocation and a fixed instruction sequence for each bytecode op doesn't seem that much more work than writing an interpreter in assembly language (especially if you use Mike Pall's excellent framework DynASM: http://luajit.org/dynasm.html). > Its certainly common to use a single indirect branch. However, it is suboptimal. I don't believe that a single indirect branch is a priori slower; while replicated dispatch makes better use of the branch predictor, it also results in less optimal i-cache usage (the LuaJIT code notes this trade-off, but observes that replicated dispatch is 20-30% faster in practice: http://repo.or.cz/w/luajit-2.0.git/blob/2ad9834df6fe47c7150d...). I'm not saying switch is better, what I'm saying is that you can't reliably replicate dispatch in C (at least according to Mike's message that I cited earlier), which makes switch() a totally reasonable choice for interpreters written in C. By the way, I'm not just making stuff up, I have written a JIT of my own: https://github.com/haberman/upb/blob/master/upb/pb/decoder_x...

ve this. My library performs no I/O (it's buffers in, buffers out), is completely resumable (so you can suspend the state machine at any point and resume it later), is completely composable (so you can create pipelines that feed the output of one parser to the input of another), loosely coupled, small (<5k loc in the core library), easy to bind to high-level languages, minimal enough that it can run inside the Linux kernel, and FAST (can parse protocol buffers at almost 1.5GB/second). And it's open-source. Don't be misled by the fact that it's advertised as a Protocol Buffer library; that's how it started, but I'm working on generalizing it to be capable of arbitrary parsing and serializing. Though Protocol Buffers schemas are used to specify the structure of any structured data that a parser wants to produce or a serializer wants to consume. https://github.com/haberman/upb/wiki

good C programs use these sparingly and clearly mark the macro with an UPPER_CASE_IDENTIFIER. C++ is much harder to "see through." Any function call could end up throwing an exception which does a non-local exit from the function. Any addition, assignment, pointer dereference, etc could actually be an overloaded operator. Any function call could be performing a user-defined implicit conversion on any of its parameters. For overloaded functions, the compiler decides what function is actually called by applying non-trivial pattern matching rules. The runtime will automatically invoke any static initialization code (like constructors of global statics) pre-main in an undefined order. etc. etc. I intend to get a thorough security review of my library once its design stabilizes. I asked Tavis Ormandy (a fellow Googler and security badass) which language is easier to audit for security and he said C for the reasons of transparency I listed above. People often say that you can just avoid using the parts of C++ that you don't like. That is true, but hard to enforce, especially on a multi-person project. If you're asking others to follow your set of rules, you have to write those rules down in meticulous detail, leading to something like the Google C++ style guide (http://google-styleguide.googlecode.com/svn/trunk/cppguide.x...), and at that point you're asking your contributors to study and internalize a large and complicated list of what is and isn't allowed just for the privilege of contributing to your project. I don't think this approach scales to lots of projects that are all choosing a different subset of C++. There are definitely things I miss by not having C++'s facilities. Constructors and an implicit "this" parameter are both really nice. Constructors are remarkable in that you can write a single function that gives you three different construction patterns for free (direct construction, heap construction with "new", construction in an arbitrary location with placement new). Automatic upcasts are nice and totally safe. Inheritance and public/private specifiers let you express directly lots of things you can only express with comments in C. But overall I think that using straight C is the right choice for a project like my library UPB.

e author asks "How would you do that in Python?" The answer is that it would be something like this: import ast class MyTransformer(ast.NodeTransformer): pass # Implement transformation logic here. node = MyTransformer().visit(ast.parse("x = 1")) print ast.dump(node) This works alright, but what I'm after is a more universal solution. With syntax trees there's a lot of support functionality you frequently want: a way to specify the schema of the tree, convenient serialization/deserialization, and ideally a solution that is not specific to any one programming language. My answer to this question might surprise some people, but after spending a lot of time thinking about this problem, I'm quite convinced of it. The answer is Protocol Buffers. It's true that Protocol Buffers were originally designed for network messaging, but they turn out to be an incredibly solid foundation on which to build general-purpose solutions for specifying and manipulating trees of strongly-typed data without being tied to any one programing language. Just look at a system like http://scottmcpeak.com/elkhound/sources/ast/index.html that was specifically designed to store AST's and look how similar it is to .proto files. (As an aside, programmers have spent the last 15 years or so attempting to use XML in this role of "generic language-independent tree structured serialization format," but it wasn't the right fit because most data is not markup. Protocol Buffers can deliver on everything people wanted XML to be). Why should manipulating syntax trees require us to write in syntax trees? The answer is that it shouldn't, but this is non-obvious because of how inconvenient parsers currently are to use. One of my life's goals is to help change that. If you find this intriguing, please feel free to follow: https://github.com/haberman/upb/wiki https://github.com/haberman/gazelle

arser that improves performance in two ways: - it is an event-based parser (like SAX) instead of the protobuf generated classes which are a more DOM-like approach (always parsing into a tree of data structures). With my parser you bind fields to callbacks, and you can parse into any data structure (or do pure stream processing). - I wrote a JIT compiler that can translate a Protocol Buffer schema directly into x86-64 machine code that parses that schema. Without the intermediate C++ step, I can generate better machine code than the C++ compiler does. In an apples-to-apples test, I beat the generated C++ by 10-40%. If you do more pure stream parsing the win is even greater. My protobuf work is open source: https://github.com/haberman/upb > I'm not sure I could have won much by counting the cycles it took me to pull (say) an NBO integer out of a packet. That's certainly different experience than mine. I don't know much about routers.

buf/source/browse/trunk/src/go... [2] https://github.com/acg/lwpb [3] https://github.com/haberman/upb

u can use Protocol Buffers as your data analysis platform even if your on-the-wire data is JSON. The benefits are greater efficiency (protobufs can be stored as structs instead of hash tables) and convenient type checking / schema validation. This question of how to represent and serialize data in an interoperable way is a path that began with XML, evolved to JSON, and IMO will converge on a mix of JSON and Protocol Buffers. Having a schema is useful: you get evidence of this from the fact that every format eventually develops a schema language to go along with it (XML Schema, JSON Schema). Protocol Buffers hit a sweet spot between simplicity and capability with its schema definition. Once you have defined a data model and a schema language, serialization formats are commodities. Protocol Buffer binary format and JSON just happen to be two formats that can both serialize trees of data that conform to a .proto file. On the wire they have different advantages/disadvantages (size, parsing speed, human readability) but once you've decoded them into data structures the differences between them can disappear. If you take this idea even farther, you can consider column-striped databases to be just another serialization format for the same data. For example, the Dremel database described by Google's paper (http://static.googleusercontent.com/external_content/untrust...) also uses Protocol Buffers as its native schema, so your core analysis code could be written to iterate over either row-major logfiles or a column-major database like Dremel without having to know the difference, because in both cases you're just dealing with Protocol Buffer objects. I think this is an extremely powerful idea, and it is the reason I have put so much work into upb. To take this one step further, I think that Protocol Buffers also represent parse trees very well: you can think of a domain-specific language as a human-friendly serialization of the parse tree for that DSL. You can really nicely model text-based protocols like HTTP as Protocol Buffer schemas: message HTTPRequest { enum Action { GET = 0; POST = 1; // ... } optional Action action = 1; optional string url = 2; message Header { optional string name = 1; optional string value = 2; } repeated Header header = 3; // ... } Everything is just trees of data structures. Protocol Buffers are just a convenient way of specifying a schema for those data structures. Parsers for both binary and text formats are just ways of turning a stream of bytes into trees of structured data.