upb

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.

tricted language subset like LL, LR, etc. can tell you that a grammar is not ambiguous, which is hugely beneficial. If you do not restrict yourself to such a subset, you never know whether your grammar has ambiguities or not. To me, this would be like programming in a language that doesn't give you syntax errors when you make a mistake. Sure, the syntax errors are annoying, but they are your only way of knowing you need to fix something! (By the way, PEGs have the same issue -- by using prioritized choice, you never know when you're covering up an ambiguity. An example of this is C's famous "if/else" ambiguity. It's important to know that this ambiguity exists, because you have to tell your users about it.) Instead of using our extra CPU power to parse with less efficient algorithms, I think we should use our extra CPU power to integrate parsing more deeply into our editors/IDEs. With a fast parsing algorithm, you could parse as a programmer types, unlike the current syntax highlighting editors which use only rough pattern matching instead of having a real parse tree. Imagine seeing syntax errors the moment you type them. Imagine having your cursor inside a struct and having a little "inspector" pane off to the side that says "sizeof(struct MyStruct) = 96". Imagine getting real, context-sensitive completion even for complex languages like C++. That's what we should be spending CPU cycles on IMO. The biggest thing that could be improved about parsing IMO is for grammars to be reusable. There is no reason that people should have to roll their own parser for a common language. There's no way you're going to get all the edge cases right unless you spend a LOT of time on it, but why should you have to do that? IMO there should be a "grammar library" the same way that platforms like the JVM or .NET have a "class library." You should be able to take a C++ parser off-the-shelf and use it in your program, thereby saving yourself literally man-years of work. I've been working for a long time on a project that seeks to achieve this goal. It's tabled right now because of my work on a protocol buffer implementation (the two will be related in a deep way; protocol buffers are an ideal way of specifying parse trees, which are the output of a parser), but I am extremely motivated to return to it. http://www.reverberate.org/gazelle/ https://github.com/haberman/upb/wiki

t time I benchmarked it, was 70-90% of the speed of generated C++.

ays that are convenient for humans. Most humans would rather read 1 + 2 - 3 * 4 than (+ 1 (- 2 (* 3 4))). I strongly believe that the way to bring the power of Lisp to other programming languages is to provide much easier access to parsers and ASTs, and better APIs for them. If we could accomplish that, we could keep writing syntax that works for humans, but have easy access to data structures so that the AST can be very easily inspected, manipulated, generated, compiled, interpreted, or any of those things that Lispers love to do. When I say "better APIs," I mean that you should have lots of flexibility for how you want to consume, process, and store the AST. You should have SAX-like stream processing and data structures like DOM (but something that binds more naturally to programming languages, so you can say foo.bar instead of foo.getElementById("bar")). There should be a convenient serialization format for the AST, and there should be a nice way to specify the schema of the AST (like a more generic version of http://scottmcpeak.com/elkhound/sources/ast/index.html). You might sense this coming, but I've been working for a long time on what I consider a major solution to this problem. There are two parts to it. upb (https://github.com/haberman/upb/wiki/) is a standalone and very minimalist implementation of Google's Protocol Buffers serialization format. I believe Protocol Buffers are an ideal data model for ASTs. Forget for a moment that Protocol Buffers is a serialization format and consider that you can use their schema language to specify something like: message Expr { // Both operands can be either a raw value or another expression. double val1 = 1; Expr expr1 = 2; double val2 = 3; Expr expr2 = 4; // The operator that should be applied to the two values. enum Operator { PLUS = 1; MINUS = 2; MULTIPLY = 3; DIVIDE = 4; } Operator operator = 5; } With that, you can generate data structures (an AST) that can be used in any language, with convenient syntax (expr.operator). Now Protocol Buffers are just a convenient way to create typed trees, just like the Elkhound "AST" project I linked above, but in a way that can be accessed from ANY programming language (that has protobuf support), not just one. upb also will support a streaming interface like SAX. The second part is my somewhat dormant project Gazelle (http://www.gazelle-parser.org/). I mean to resume it once upb is ready. Gazelle uses most of the same parsing theory as ANTLR, but instead of generating code for every parser it has a more VM-like approach. And as its output? You guessed it -- upb and Protocol Buffers. You can consume the parse tree in a streaming way (SAX), as a data structure (DOM), you can serialize the AST itself as a Protocol Buffer. tl;dr: Programming languages are just a human-friendly serialization of an AST. Parsing is simply tree traversal. Protocol Buffers are simply a universal way of specifying and manipulating trees. And I'm working on an attempt to unify it all into a tiny but powerful library that aims to bring the power of Lisp to all programming languages.