Josh Haberman

SSE 4.2 includes text processing instructions. In the words of Ars Technica:

Intel has added a number of new instructions to Nehalem and it has sped up others. The 4.2 version of Intel’s SSE vector extensions takes the x86 ISA back to the future just a bit by adding new string manipulation instructions. I say “back to the future” because ISA-level support for string processing is a hallmark of CISC architectures that was actively deprecated in the post-RISC years; typically, when a writer wants to give an example of crufty old corners of the x86 ISA that have caused pain for chip architects, string manipulation instructions are what he or she reaches for. But the new SSE 4.2 string instructions are aimed at accelerating XML processing, which makes them Web-friendly and therefore modern (i.e., not crufty).

I chuckled a bit when I read this. I’m not very purist when it comes to hardware. If these instructions will make my parsers faster, then they sound great to me!

The four new instructions are:

• pcmpestri: packed compare of explicit length strings, returning index
• pcmpestrm: packed compare of explicit length strings, returning mask
• pcmpistri: packed compare of implicit length strings, returning index
• pcmpistrm: packed compare of implicit length strings, returning mask

The variants are as follows:

• implicit length strings are NULL-terminated, explicit strings have an explicit length (ie. the whole input register).
• they can return an index into the source string (if you were searching for something) or a mask (if you wanted to test each character of the input

Both let you scan a 128-bit SSE register (treating it as either 16 8-bit characters or 8 16-bit characters) and perform all kinds of searches/comparisons. The instructions are configurable; you supply a control word that specifies all of the different variations of the instructions. For example, are the input values signed or unsigned, are we comparing against ranges or specific values, etc.

The reciprocal throughput of these instructions is high (2 cycles) but the latency is annoyingly slow (9 cycles). This means that you have to wait nine cycles after issuing the instruction before you can use the result. It’s hard to think of too many useful things you can execute in parallel while you’re waiting for that answer. As a side note, these figures come from Intel’s Intel® 64 and IA-32 Architectures Optimization Reference Manual, which says that the latency number is a worst case estimate:

Actual performance of these instructions by the out-of-order core execution unit can range from somewhat faster to significantly faster than the latency data shown in these tables.

I’m not enough of a hardware geek to know what to actually expect.

Still, that’s nine cycles to wait before getting a lot of really useful information. In addition to returning the index or mask, the instructions set several of the flags in useful ways.

So what processors have SSE 4.2? Or in other words, how long will my impatient self have to wait to try them out? Apparently SSE 4.2 is available on Penryn, which is the second-gen Core 2, which debuted in 2007/2008. It uses a “45 nm process”, which I’m sure means something to hardware geeks but not to me. All I know is that it’s not the Core 2 that’s inside the MacBook Pro sitting on my lap. And of course SSE 4.2 is in the new Nehalem.

I’m am very excited to announce the release of Gazelle 0.4! The most notable change in this release is that Gazelle can again handle whitespace. But there are many other changes that put Gazelle well on the path from being a toy to being a tool. See the ReleaseNotes for all the details.

Next up for Gazelle 0.5: operator-precedence parsing and the ability to build parse trees. Following up on my earlier post about Bitcode and Protocol Buffers, I’ve wholeheartedly decided to go the Protocol Buffer route, not only for the bytecode itself, but also for parse trees and abstract syntax trees. More about this later.

While I’m on a roll with these blog entries, I thought I’d share just one more secret that’s been kicking around in my head for a while. I desperately want to see a Gazelle development environment that runs in your web browser.

I first had this idea when I visited the excellent regular expression reanimator. It’s this beautiful little visualization that runs in your browser and shows you how a DFA transitions in response to text. And all you have to do to use it is click that little link!

My dream is that you can develop your grammars interactively. You type rules and as you type you see little graphs build themselves up, state by state. You add a kleene star and you see the extra transitions add themselves to the existing graph. You put some sample text in another textarea and watch it start syntax-highlighting itself as you add the rules to properly recognize its structure. Or you can develop your own syntax highlighting color schemes by typing syntax highlighting rules and again seeing them incrementally take effect on a block of sample text.

None of these ideas are brand-new. ANTLR of course has ANTLRWorks, which is an IDE for developing ANTLR grammars. But I feel that having this on the web would really lower the barrier to entry and make it accessible to more people. And despite how people poo-poo JavaScript and HTML, the web is not such a bad platform these days — especially now that SVG support is getting really good. SVG is the perfect tool for drawing graphs, styling the nodes in various ways, and having them do useful things when you hover/click on them.

So anyway, I really want this. But the hurdles to making this happen are great!

• Gazelle’s compiler is written in Lua. No real way to run Lua in a browser right now. Possible options for doing this in the future: a Lua -> JavaScript compiler, a Lua VM written in JavaScript, porting the Gazelle compiler to JavaScript, running the Lua interpreter inside NativeClent, and running the Lua interpreter inside Alchemy.
• Gazelle’s runtime is written in C. Possible options: port the runtime to JavaScript, run it inside Alchemy, or run it inside NativeClient.
• The Graphviz graph layout package is also written in C. Possible options are the same as the Gazelle runtime. I was seriously considering porting just the layout algorithms to JavaScript and had even started the port, but have recently been realizing how CPU-intensive these algorithms are even in C. In JavaScript they could only be slower. With Alchemy they would be slower than pure C, though it’s hard to say how much. With NativeClient they would run at native speed.

So it pretty much looks like I’m stuck waiting for either Alchemy or NativeClient to be prime-time. While I could always run all this software on the server and AJAX the results in constantly, I don’t think that would provide a smooth enough user experience (not to mention the load it would put on my server — these algorithms are kind of expensive).

As far as Alchemy vs. NativeClient: Alchemy will be slower (2-10x according to them) since it compiles your C/C++ to the Flash VM instead of to machine code, and it will require the Flash plugin. NativeClient will run at roughly native speeds, but will require a plugin download (most people will have flash already) and one that has potentially scary security implications if the NativeClient guys made any mistakes.

Time to play with Alchemy and see if I can get it to work! And hope that NativeClient makes a lot of progress in no time!

While I’m at it, I wanted to take a moment to recognize that I’ve too frequently made claims that are unsupported or premature. The worst example of this was when I claimed to have found an algorithm that computes LL(k) for all k (this is undecidable — my algorithm turned out to be a heuristic). In other cases, what I’ve written is technically true but misleading: for example, in claiming that Gazelle is “more powerful” than ANTLR, this was not taking into account many features that ANTLR has that Gazelle currently does not, like semantic and syntactic predicates.

I’m not proud of this. I’d like to take the opportunity to make a commitment to putting those days behind me. I am extremely proud of Gazelle and what I think it brings to the table, and I’ve tried to consistently acknowledge my debts to prior work, especially ANTLR. Indeed, in the Gazelle manual I say:

Gazelle’s algorithm takes a great deal of inspiration from ANTLR, the LL(*) parser generator written by Terence Parr. While Gazelle seeks to augment the theory that Terence developed, the foundations of Gazelle are strongly based in ANTLR’s achievements. Like ANTLR, Gazelle is a top-down parser that models its lookahead as possibly-cyclic state machines. Gazelle’s algorithm for generating this lookahead is based on ANTLR’s algorithm.

Still, I clearly need to be much more careful not to jump to conclusions, and be less susceptible to bravado. If Gazelle is as good as I think it is, its capabilities should speak for themselves.

Given that whitespace has been relatively painless to implement, I think I’ll tackle a number of smaller things I’ve been meaning to do before releasing 0.4. Like whitespace-handling, these are things that prevent Gazelle from being more than a toy until they’re addressed:

1. when Gazelle encounters a parse error, it should report it to the API in a sane way instead of doing assert(false) or just printing a message to stderr and aborting
2. Gazelle should provide line and column information to the API (this is more complicated than it might sound — read the Wikipedia article on “newline” and the Unicode recommendations on Newline for some of the complications)
3. Gazelle’s C API should be namespaced (with gzl_ or somesuch on all the identifiers) instead of polluting the global namespace with functions called things like “parse”
4. a “make install” target, so that you can just type “gzlc” for the compiler instead of “. lua_path; ./compiler/gzlc”

These sound like a good set of goals for a 0.4 release. I may drop a few or think of a few others.