16 ms·
Show HN: Fast C-based HTML 5 parsing for Python
- jszymborski 9y agoThis would replace html5lib in BeautifulSoup nicely :)
- Animats 9y agoNo, no. I don't want some complicated C blob in the middle of my Python system. I don't have time to chase buffer overflows and pointer bugs. Has anyone benchmarked this against html5lib compiled with PyPy? Html5lib is slow in CPython because there are a lot of low-level per-character tests, as required by the HTML5 spec. The spec specifies how bad HTML is to be parsed in great detail, which means a lot of IF statements. CPython is a dog on code like that. PyPy, not so much.
- jgraham 9y ago[I was the original author of much of html5lib] Yes, http://speed.pypy.org/comparison/ http://speed.pypy.org/comparison/ has html5lib parsing (an old, static copy of) the HTML5 spec as a benchmark. It's about 3x faster than CPython, which is to say, still very slow. I agree there's a good argument that writing new parser code in C is not a great idea, but I don't think it's possible — or at least easy — to get reasonable parsing speed in pure Python. My ideal solution here would be bindings to a Rust parser e.g. html5ever, although there is a tradeoff there in terms of ease of distribution. The main missing feature in html5ever for these purposes is the ability to construct the final parse tree in the rust code (c.f. lxml), without which the performance bottlneck becomes constructing the Python objects to represent the document. Of course a streaming API like SAX can be even faster, but often isn't all that useful.
- Animats 9y agoIf just the tokenizer was in Rust, that might help. Much of the HTML5 error handling involves dealing with malformed tokens. Comments that begin "<-" instead of "<--". All that stuff at the beginning of a file for guessing the character set. None of those require creating elaborate Python structures from non-Python code. (I run a web crawler written in Python, which means code exposed to arbitrarily bad HTML. I've had to report and fix bugs in BeautifulSoup and html5lib. At least they fail in a well-defined way. C code can fail in arbitrarily bad ways, and C string processing is notorious for being troublesome.)
- gsnedders 9y ago[I'm the current mostly absentee maintainer of html5lib] https://speed.python.org/comparison/?exe=12%2BL%2Bmaster%2C12%2BL%2B3.5%2C12%2BL%2B3.6%2C12%2BL%2B2.7&ben=633&env=1%2C2&hor=false&bas=12%2BL%2B2.7&chart=normal+bars https://speed.python.org/comparison/?exe=12%2BL%2Bmaster%2C1... has an up-to-date version of html5lib, albeit only on CPython: notably, both 3.6 and the latest 3.7 build are significantly faster than 2.7. That said, I don't think html5lib is going to become massively quicker: string allocations are just going to become an ever bigger issue (i.e., s[1:10] causes an allocation in Python v. just referencing the subsequence), and even using Cython, at least under CPython, isn't going to help with that.
- olau 9y agoCouldn't a little toolbox of helpers take care of those allocations? Or would that turn the whole thing into something too complicated?
- daniel_rh 9y agoI thought you could use memoryview over a string to get rid of that allocation even in 2.7 https://docs.python.org/3/library/stdtypes.html#memoryview https://docs.python.org/3/library/stdtypes.html#memoryview
- nostrademons 9y agoAllocations are challenging for HTML parsers, even in C, because of the presence of entity references and case-normalization of attribute & tag names. That means that a lot of the time when you think you ought to be able to just use a slice or memoryview into the original source text, you can't; for example, if any of your text nodes contains < ('<') or &ldquo (smart double quote), you can't use the original source buffer, because you're supposed to have decoded the entity to a unicode character, which will leave the string a different length. This happens stupidly often in real HTML. I initially had the API for Gumbo use string slices a lot more than the final released API, and then found that I couldn't do it and needed to allocate in order to maintain correctness. I'd done a patch that arena-allocated all memory used in the parse, which gave a fairly significant CPU speedup, but it also bloated max memory usage in ways that some clients found unacceptable, so I never merged it. Small C strings at least are quite lightweight; Python strings have a lot of additional overhead, and much of the PyObject structure itself requires chasing pointers.
- littlestymaar 9y ago> My ideal solution here would be bindings to a Rust parser e.g. html5ever Funny how somebody submitted exactly this on HN a few hours ago : https://news.ycombinator.com/item?id=14591017 https://news.ycombinator.com/item?id=14591017
- aumerle 9y agoYou do know that by default bs4 uses lxml.html to do its parsing, which is also a big blob of C, right? For example, running the following: BeautifulSoup('<p>a') /usr/lib/python3.6/site-packages/bs4/__init__.py:181: UserWarning: No parser was explicitly specified, so I'm using the best available HTML parser for this system ("lxml"). This usually isn't a problem, but if you run this code on another system, or in a different virtual environment, it may use a different parser and behave differently.
- RUTHLESS_RUFUS 9y agoSpeed isn't everything. How permissive is the parser? We look for a compromise here.
- aumerle 9y agoAs permissive as html5lib, which is as permissive as a modern browser, since both are base don the HTML 5 parsing spec.
- exabrial 9y agoOpinion: permissive parsing is bad for the industry. Speed should be king. It's not difficult to write correct html!
- pwdisswordfish 9y agoIsn't it because 'incorrect HTML' has been practically defined out of existence?
- kbutler 9y agoBe strict in what you produce and liberal in what you accept. Strictness works well when you have a small number of active producers and consistent, constantly renewed content. The web is the opposite - a huge number of producers and widely varying content, some of which is 1-2 decades old and will never be updated. You can design and build a great, strict HTML parser - it just won't work well for a significant portion of the www. And if you make one that is popular enough, you can change the direction of evolution of the web! (See mobile safari and flash)
- RUTHLESS_RUFUS 9y agoOpinion: the industry doesn't equate with reality. Pointy-haired MBAs with some PHP background would tell you otherwise, but there's a whole wide world out there.
- deleted 9y ago[deleted]
- pwdisswordfish 9y agoWhy does it bundle a copy of the gumbo library instead of just linking to it?
- aumerle 9y agoBecause it uses a modified version of gumbo to support parsing not-well formed XHTML as well
- pwdisswordfish 9y agoI thought the whole point of XHTML is that non-well-formed documents should generate an error instead of being unpredictably interpreted according to each implementation's whims. And if you really insist on doing that, why not just parse XHTML as HTML? HTML5 parsing rules can already handle some XHTML-like constructs; it's what browsers do when they're served XHTML as text/html. If it's good enough for them, it should be good enough for you.
- aumerle 9y ago:) Try parsing the following snippet using HTML 5 parsing algorithm and see what you get: <html><head><title /></head><body><p>foo
- pwdisswordfish 9y agoHow often does a self-closing <title /> tag appear in the wild?
- aumerle 9y agoI encounter self closed <title> tags in malformed XHTML files all the time. In fact I encounter them so often, I used to use a dedicated sanitization pass before passing int he html to html5lib, for that reason alone.
- nostrademons 9y ago
- sebcat 9y agoI made a pull request[1] for gumbo-parser a while ago. While it is a wonderful project, it seems to be in need of a new maintainer, or a maintained fork. [1] https://github.com/google/gumbo-parser/pull/370 https://github.com/google/gumbo-parser/pull/370
- aumerle 9y agoYes, the lack of maintenance of gumbo-parser was another reason I decided to include a private copy. You are welcome to make your PR against html5-parser's copy of gumbo-parser, and I will review it.
- sebcat 9y agoIf I understand things correctly, gumbo in html5-parser was forked from https://github.com/Sigil-Ebook/sigil-gumbo/ https://github.com/Sigil-Ebook/sigil-gumbo/ at 0830e1145fe08758d6ef24f77dfcbeac4633676f, which in turn was forked from https://github.com/vmg/gumbo-parser/tree/v1.0.0 https://github.com/vmg/gumbo-parser/tree/v1.0.0 which was forked from google/gumbo-parser, pre google/gumbo-parser 0.9.4. There's quite a few changes on the original upstream since then. gumbo_malloc -> gumbo_parser_allocate, free_node -> destroy_node, passing around the parser as an argument, &c.
- aumerle 9y agoYes, since I wrote html5-parser for use in calibre (i.e. to parse the HTML in e-books), sigil-gumbo is a more appropriate upstream for me. I have no objectsion to merging in changes from gumbo-parser that are not in sigil-gumbo over time, but it will need to be done gradually, as there is only so much time I can devote to html5-parser now that it meets the needs of calibre.
- nostrademons 9y agoI think sigil-gumbo also merged in a lot of the changes in 0.9.4 and 1.0.0. Most of them were related to performance & memory allocation; a developer at GitHub did a lot of work to speed up their internal copy of Gumbo, and merged a lot of that work back to master. Kevin Hendricks (sigil-gumbo's maintainer) was involved in a number of those discussions; I believe he applied most of the patches to his own tree as well. I have some doubts that html5-parser would be 30x faster than html5lib without the performance work in 0.9.4; Gumbo up through 0.9.3 was really slow for a C library.
- droithomme 9y agoThe gumbo build uses the flag -Wunused-but-set-variable which was added in gcc 4.6. The build script doesn't check for gcc 4.6 though and simply fails.
- dalf 9y agoHow fast is compare to lxml with the HTML parser ? I know that lxml won't parse as many cases as this module, but in many cases lxml can do the job.
- aumerle 9y agoI have not tested it, but it is probably slower. The advantage of this is that is follows the HTML 5 parsing spec, so it gives you the same results as a browser when parsing malformed HTML
- Paul-ish 9y agoI have found the lxml API in python leaks a considerable amount of memory, but that was while going through a large amount of data though (Wikipedia dump). This is in contrast to a handful of pages. But that was a while ago, it may be different now.
- Buttons840 9y agoWhat do you mean by "leak"? I wrote a scraper that used lxml and a single instance/process ran for month on end in production without any issues. Lxml may have used more memory than some alternatives, but I don't think it was "leaking" memory.
- Paul-ish 9y agoThat is likely true. My experience with it was in 2011/2012 ish. Their FAQ[1] claims memory leaks have been fixed over time. * http://lxml.de/FAQ.html http://lxml.de/FAQ.html
- zaszrespawned 9y agoNote: (on the off chance that someone did not know about this :) ) The author is also the only developer of calibre. https://calibre-ebook.com/ https://calibre-ebook.com/ which is also based on python
- aumerle 9y agoIndeed, I developed html5-parser to eventually replace html5lib in calibre
- samblr 9y agoBig fan of calibre. Really appreciate your work. Have converted many books to put in kindle! Flawless. I have worked on document formats (office, pdf etc) and I understand these standards are simply tedious!
- metalliqaz 9y agoWhere are the test that show it's 30x faster? Otherwise, pretty cool. I only do occasional HTML parsing in scripts, so whatever is builtin and BeautifulSoup is good enough for me, but I can surely imagine a 30x speedup being not only useful but necessary for large processing jobs or a scaled-up user interface.
- aumerle 9y agohttps://html5-parser.readthedocs.io/en/latest/#benchmarks https://html5-parser.readthedocs.io/en/latest/#benchmarks
- samblr 9y ago30x is quick! But still it doesn't appear to be sequential parser. html -> gumbo parse tree -> lxml tree What makes it efficient even with two tree transformations ? Is one of the above trees constructed in sequential way and is less-recursive ?
- nostrademons 9y agoThe short answer to this is that you can do an awful lot of work in C for the cost of a single Python instruction. The slightly longer answer is that the vast majority of time in parsing is spent actually parsing - examining each character and adjusting your state machine accordingly. When I was benchmarking the gumbo-python bindings, it was 95%+ parsing, < 5% spent on tree construction. Speed up the parsing part by 100x (which isn't all that unreasonable, when you consider that a field reference in Python involves hashing a string and looking up an object in a dictionary attached to the object), and you'll get an equivalent speedup in total runtime that can pay for a lot of tree reconstructions. The Gumbo parse tree itself will often fit in L2 cache (IIRC I'd benchmarked it at about 90% of documents use < 400K RAM), so it doesn't take much time to traverse. Doing the Gumbo => lxml translation in C rather than Python gives a similar speedup for tree construction: instead of having to lookup fields in Python as dictionary references, you can do it in C by memory offset.
- 9y ago
- jacquesm 9y agoPython: interactive glue language between high performance C libraries. It's funny how we have converged on this solution, I use it daily so I'm really not complaining but I really didn't see this as one of the logical outcomes of the various programming language streams. But when you think about it it is kind of logical: inner loops and low level code tend to be fairly static and are often re-used so it pays of to write them in a language that maximizes for that use-case, but structure can be executed much slower and re-use is relatively low when going from one application to the next so it pays of to write that in another language. So we get this split roughly halfway down the application stack where we switch from interactive and interpreted high level language to compiled low level language. It's a very interesting optimum.
- penpapersw 9y agoYep. Similar to how we used to write the high performance code in ASM and the business logic in C. Now we write the high performance code in C (or equiv. low-level language) and the high performance code in a slow but expressive dynamic language. My favorite is writing high-level code in some kind of Lisp (previously Clojure, lately Racket) because REPL-driven development makes it incredibly fast to iterate and experiment and then cement/polish it into production code all while having the same state in memory.
- mpweiher 9y agoIt's actually a fairly common pattern: think high performance filters glued together with the shell. Or "steering" of supercomputer codes via Tcl, Squeak Smalltalk doing high performance multi-media (at the time) using a few well-placed primitives and an otherwise run-of-the-mill bytecode interpreter. A very similar split goes right through the middle of Objective-C. Although it is compiled, the "Objective" part always felt pretty close to interactive and is pretty high-level, and C is, well, C. Same concept, less mismatch between the parts. One of Objective-Smalltalk's goals is to invert the Objective-C trade-off: make the interactive, high-level part primary, while still allowing a smooth transition to the low-level parts without resorting to making that transition automatic by either a heldencompiler or super-smart JIT. Yes, it is a very interesting optimum, though I think it is one that can be improved on.
- 9y ago
- ernsheong 9y agoWould it be possible to interface this with other languages? e.g. Go, Ruby, Java, or is there a hard dependency on Python?
- zer01 9y agoMy favorite part about this documentation is actually the "Safety and correctness" section: https://html5-parser.readthedocs.io/en/latest/#safety-and-correctness https://html5-parser.readthedocs.io/en/latest/#safety-and-co... It shows that a good engineer took the time to think about not only speed, but correctness in implementation, and compiling things with `-pedantic-errors -Wall -Werror` is a practice that I very rarely see in the wild, and should be heralded as good practice. It's far too common to see hundreds of warnings zip past while compiling, and sometimes they do tell you about problems you need to solve.
- mrout 9y ago-pedantic-errors -Wall -Werror isn't used in the wild because it breaks whenever a new compiler comes out. New compilers often come out with new warnings, new cases for old warnings, etc. It's not forwards-compatible to make warnings errors. You should release your code with no warnings on the current compiler, but new warnings shouldn't break everything.
- aumerle 9y ago-Werror is used only when building on the continuous integration servers, not in the released code. That way, you get the best of both worlds. Your code wont break on new compiler releases, but it also wont have neglected warnings.
- wooptoo 9y agoAny luck using this with BeautifulSoup?
- aumerle 9y agoSimply pass the argument treebuilder='soup' to the parse function. But note that you wont get as much of a performance boost, because the besutifulsoup tree has to be built in python, not C.