{"action":"created","issue":{"url":"https://api.github.com/repos/servo/html5ever/issues/60","labels_url":"https://api.github.com/repos/servo/html5ever/issues/60/labels{/name}","comments_url":"https://api.github.com/repos/servo/html5ever/issues/60/comments","events_url":"https://api.github.com/repos/servo/html5ever/issues/60/events","html_url":"https://github.com/servo/html5ever/pull/60","id":50087154,"number":60,"title":"Implements zero-copy html parsing.","user":{"login":"cgaebel","id":128969,"avatar_url":"https://avatars.githubusercontent.com/u/128969?v=3","gravatar_id":"","url":"https://api.github.com/users/cgaebel","html_url":"https://github.com/cgaebel","followers_url":"https://api.github.com/users/cgaebel/followers","following_url":"https://api.github.com/users/cgaebel/following{/other_user}","gists_url":"https://api.github.com/users/cgaebel/gists{/gist_id}","starred_url":"https://api.github.com/users/cgaebel/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cgaebel/subscriptions","organizations_url":"https://api.github.com/users/cgaebel/orgs","repos_url":"https://api.github.com/users/cgaebel/repos","events_url":"https://api.github.com/users/cgaebel/events{/privacy}","received_events_url":"https://api.github.com/users/cgaebel/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":6,"created_at":"2014-11-25T21:36:48Z","updated_at":"2015-06-10T15:32:41Z","closed_at":"2015-06-10T15:32:41Z","pull_request":{"url":"https://api.github.com/repos/servo/html5ever/pulls/60","html_url":"https://github.com/servo/html5ever/pull/60","diff_url":"https://github.com/servo/html5ever/pull/60.diff","patch_url":"https://github.com/servo/html5ever/pull/60.patch"},"body":"Instead of using strings, html5ever now uses Iobufs and Spans over\r\nIobufs to represent the raw html data. This allows us to do all of\r\nthe parsing without copying the HTML into a tree of strings: it can\r\nbe Spans and Iobufs all the way down.\r\n\r\nThere were several performance hacks done to get this faster. Most\r\nof them were to work around rustc failures as chronicled in:\r\n\r\nhttp://discuss.rust-lang.org/t/the-sad-state-of-zero-on-drop/944\r\n\r\nHere's a little list of transformations done for performance reasons:\r\n\r\n  - State machine states are now functions. Rustc isn't smart enough\r\n    to properly handle large-ish things on the stack in different\r\n    match arms. This does mean that it's sane to inline the jump\r\n    table into `feed`, which had a nice impact on performance. Jump\r\n    tables inside loops are especially efficient because it's just\r\n    a bigger jump table!\r\n  - Things which get atomized anyhow (except for doctypes, which\r\n    weren't hot enough for me to bother changing) use the old String\r\n    parsing method, since it ends up being a lot faster for small\r\n    strings and doesn't cause O(tags) allocations, thanks to truncation.\r\n  - A custom Option called `FastOption` which doesn't zero on `take`\r\n    and can't be matched on, but still maintains safety.\r\n  - No utf-8 decoding of the chars is avoided unless absolutely\r\n    necessary. For most parsing, we just need the utf-8 length,\r\n    which is much easier to calculate (a branch, and a LUT on the\r\n    first byte in the \"slow\" path).\r\n  - Chars and Runs are parsed into a \"shared\" location every time,\r\n    because rustc is really bad at generating code for types which\r\n    Drop a lot in a loop. See the discuss post at the top.\r\n  - A new temp_buf has been introduced, because it is no longer\r\n    performant to just append random characters to spans. Consider\r\n    a partially-consumed comment start: `<-`. If the next character\r\n    is an `a`, the <- needs to be emitted. The second temporary\r\n    buffer is used to handle cases like that.\r\n  - Similar to above, but when parsing char refs: the '&' and '#'\r\n    are saved in case of backout.\r\n  - Dashes at the end of a comment `----->` need to be saved and\r\n    shuffled as we keep reading more dashes, so that we always\r\n    emit the \"right\" ones to keep the span continuous. This\r\n    required a little 2-element \"queue\": `first_comment_end_dash`\r\n    and `second_comment_end_dash`.\r\n  - Some of the tokenizer fields were reordered for cache\r\n    efficiency.\r\n  - Some inliner guidance was done in `get_char` and\r\n    `get_preprocessed_char`, to keep fast paths fast.\r\n  - `clone_from` to get data out of the input buffers is used\r\n    where it makes sense, preventing a bunch of bad rustc codegen.\r\n\r\nAs a result of these optimizations (and zero-copy parsing in general):\r\n\r\n===\r\n\r\nzero-copy\r\n\r\ntest tokenize uncommitted/html5.html       ... bench: 124076195 ns/iter (+/- 9519897)\r\ntest tokenize uncommitted/lipsum-1M.html   ... bench:   1989708 ns/iter (+/- 405327)\r\ntest tokenize uncommitted/sina.com.cn.html ... bench:   7210262 ns/iter (+/- 1391972)\r\ntest tokenize uncommitted/strong.html      ... bench:  30002001 ns/iter (+/- 3375152)\r\ntest tokenize uncommitted/webapps.html     ... bench:  99264377 ns/iter (+/- 8138989)\r\ntest tokenize uncommitted/wikipedia.html   ... bench:   3841740 ns/iter (+/- 612645)\r\n\r\noriginal\r\n\r\ntest tokenize uncommitted/html5.html       ... bench: 153991836 ns/iter (+/- 7196531)\r\ntest tokenize uncommitted/lipsum-1M.html   ... bench:   2393385 ns/iter (+/- 450953)\r\ntest tokenize uncommitted/sina.com.cn.html ... bench:   8837605 ns/iter (+/- 1238217)\r\ntest tokenize uncommitted/strong.html      ... bench:  44153393 ns/iter (+/- 5076161)\r\ntest tokenize uncommitted/webapps.html     ... bench: 136860951 ns/iter (+/- 8137049)\r\ntest tokenize uncommitted/wikipedia.html   ... bench:   4868854 ns/iter (+/- 797178)\r\n\r\nSUMMARY\r\n\r\nhtml5.html:       19%\r\nsina.com.cn.html: 14%\r\nstrong.html:      47%\r\nwebapps.html:     27%\r\nwikipedia.html:   21%\r\nlipsum-1M.html:   17%\r\n\r\n====\r\n\r\nr? @kmcallister"},"comment":{"url":"https://api.github.com/repos/servo/html5ever/issues/comments/110797866","html_url":"https://github.com/servo/html5ever/pull/60#issuecomment-110797866","issue_url":"https://api.github.com/repos/servo/html5ever/issues/60","id":110797866,"user":{"login":"kmcallister","id":444997,"avatar_url":"https://avatars.githubusercontent.com/u/444997?v=3","gravatar_id":"","url":"https://api.github.com/users/kmcallister","html_url":"https://github.com/kmcallister","followers_url":"https://api.github.com/users/kmcallister/followers","following_url":"https://api.github.com/users/kmcallister/following{/other_user}","gists_url":"https://api.github.com/users/kmcallister/gists{/gist_id}","starred_url":"https://api.github.com/users/kmcallister/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kmcallister/subscriptions","organizations_url":"https://api.github.com/users/kmcallister/orgs","repos_url":"https://api.github.com/users/kmcallister/repos","events_url":"https://api.github.com/users/kmcallister/events{/privacy}","received_events_url":"https://api.github.com/users/kmcallister/received_events","type":"User","site_admin":false},"created_at":"2015-06-10T15:32:41Z","updated_at":"2015-06-10T15:32:41Z","body":"Now #141."}}