google/gumbo-parser — pull request #258 by nostrademons (2014-09-10 04:35:21+00:00)
Title: Ragel-based char ref handling

This replaces the existing linear search over character entities with a Ragel-generated FSM iterating through all of them at once. It adds Ragel as a dependency for editing the char_ref.rl file, but I'm checking in the generated file as well, so people who aren't editing that one file shouldn't need to deal with it. Compile times have gone up slightly, but execution speed seems to have improved by anywhere from 20% - 2x, depending on how many ampersands are in the document.

Also, this eliminates the order dependence where entities with semicolons must come first; Ragel automatically chooses the longest match possible.

Benchmark results:

Original, including new UTF-8 decoder:

hacker_news.html: 6458 microseconds.
html5_spec.html: 1089517 microseconds.
xinhua.html: 29882 microseconds.
yahoo.html: 33453 microseconds.
google.html: 30734 microseconds.
bbc.html: 9894 microseconds.
arabic_newspapers.html: 8535 microseconds.
wikipedia.html: 68821 microseconds.

With this change:

hacker_news.html: 3498 microseconds.
html5_spec.html: 843017 microseconds.
xinhua.html: 27064 microseconds.
yahoo.html: 25977 microseconds.
google.html: 23526 microseconds.
bbc.html: 9449 microseconds.
arabic_newspapers.html: 7677 microseconds.
wikipedia.html: 46970 microseconds.

I tried a variety of Ragel options; -G2 was about 20-30% faster than this eventual check-in but resulted in unacceptably long compile times, with -F1/-F0/-T1/-T0 were all basically equal.