lxml.cssselect much slower on 2.3.1
Hi, Thanks to everyone working on lxml. It helped a lot in developing WeasyPrint (http://weasyprint.org) lxml 2.3.1 changes how the descendant selector is implemented in cssselect: https://github.com/lxml/lxml/commit/503d276c79bbe74db7d210814cfd28132fbe2c92... This changes makes matching affected selectors much slower on big documents. On my machine, the following test gives 0.15 seconds with 2.3 but 45 seconds with 2.3.1: import time from lxml import html, cssselect document = html.parse('http://www.w3.org/TR/html5/Overview.html') match = cssselect.CSSSelector('dl dt') t1 = time.time() match(document) t2 = time.time() print t2 - t1 (You may want to download the file and parse that if you want to run the test repeatedly. It’s 4.7 MB of HTML.) Matching all selectors founds in the document’s stylesheets (as WeasyPrint does to render it in PDF) takes about one minute in 2.3. I don’t know about 2.3.1 because I gave up and killed it after one hour. Admittedly this document is bigger than most web pages (99k elements), but this problem also affects performance on smaller documents, though not as dramatically. By reading the changelog I don’t understand why the change was made or what effects it has (other than performance). When is A//B different or preffered to A/descendant::B ? Is the underlying performance problem fixable while keeping A//B? Best regards, -- Simon Sapin
Simon Sapin, 03.11.2011 17:48:
Thanks to everyone working on lxml. It helped a lot in developing WeasyPrint (http://weasyprint.org)
lxml 2.3.1 changes how the descendant selector is implemented in cssselect:
https://github.com/lxml/lxml/commit/503d276c79bbe74db7d210814cfd28132fbe2c92...
This changes makes matching affected selectors much slower on big documents. On my machine, the following test gives 0.15 seconds with 2.3 but 45 seconds with 2.3.1:
import time from lxml import html, cssselect
document = html.parse('http://www.w3.org/TR/html5/Overview.html') match = cssselect.CSSSelector('dl dt') t1 = time.time() match(document) t2 = time.time() print t2 - t1
(You may want to download the file and parse that if you want to run the test repeatedly. It’s 4.7 MB of HTML.)
Thanks for the report, I can reproduce this. I get 7 seconds for the latest version and 0.1 seconds for the version preceding the above commit. That is a rather large regression. This seems to be related: http://markmail.org/message/2dzbkx4n2nogg2ai as is this: http://thread.gmane.org/gmane.comp.python.lxml.devel/4986/focus=4999 Running your example in callgrind shows that 99.4% of the XPath evaluation time is spent in a function called xmlPathNodeSetMergeAndClear() in xpath.c, and pretty much all of it in the inner loop that searches for duplicates in two node sets using a quadratic algorithm. In short, there are cases that perform extremely badly in libxml2's XPath evaluator. I guess the problem is that optimisations (such as a smarter sorting algorithm) are much harder to implement in C than they would be in Cython or Python, so they are simply not implemented in libxml2. For example, if the evaluator could determine that the node sets are distinct because they come from different subtrees (and do not access any parents in their subexpressions), it could simply skip the search for duplicates and concatenate the two node sets in no-time.
Matching all selectors founds in the document’s stylesheets (as WeasyPrint does to render it in PDF) takes about one minute in 2.3. I don’t know about 2.3.1 because I gave up and killed it after one hour.
Admittedly this document is bigger than most web pages (99k elements), but this problem also affects performance on smaller documents, though not as dramatically.
That page clearly makes a pretty good benchmark.
By reading the changelog I don’t understand why the change was made or what effects it has (other than performance). When is A//B different or preffered to A/descendant::B ?
Here's the corresponding ticket: https://bugs.launchpad.net/lxml/+bug/657968
Is the underlying performance problem fixable while keeping A//B?
It might be possible to separate the publicly visible value of the ".path" property from the generated XPath for internal evaluation. The latter could use "descendant::" where the first would show "//". However, the right place to fix this is certainly libxml2 ... Stefan
Stefan Behnel, 03.11.2011 20:26:
Simon Sapin, 03.11.2011 17:48:
By reading the changelog I don’t understand why the change was made or what effects it has (other than performance). When is A//B different or preffered to A/descendant::B ?
Here's the corresponding ticket:
One addition here: the original code converted "dl dt" into descendant-or-self::dl/descendant::dt This is correct as long as "dt" is a concrete tag name. However, the selector expression "dl *:last-child" is in the same way incorrectly converted into descendant-or-self::dl/descendant::*[position() = last()] Here, position() refers to the position in the list of descendants, not in the list of children. The correct translation would be descendant-or-self::dl/descendant-or-self::*/*[position() = last()] It appears that the translation of "dl dt" into descendant-or-self::dl/descendant-or-self::*/dt runs equally fast as the original version, so I think this is the way to go. Stefan
Stefan Behnel, 03.11.2011 22:06:
Stefan Behnel, 03.11.2011 20:26:
Simon Sapin, 03.11.2011 17:48:
By reading the changelog I don’t understand why the change was made or what effects it has (other than performance). When is A//B different or preffered to A/descendant::B ?
Here's the corresponding ticket:
One addition here: the original code converted "dl dt" into
descendant-or-self::dl/descendant::dt
This is correct as long as "dt" is a concrete tag name. However, the selector expression "dl *:last-child" is in the same way incorrectly converted into
descendant-or-self::dl/descendant::*[position() = last()]
Here, position() refers to the position in the list of descendants, not in the list of children. The correct translation would be
descendant-or-self::dl/descendant-or-self::*/*[position() = last()]
It appears that the translation of "dl dt" into
descendant-or-self::dl/descendant-or-self::*/dt
runs equally fast as the original version, so I think this is the way to go.
Here's the obvious patch against 2.3.1, please give it a try. --------------- diff -r 9c0fd06afb18 src/lxml/cssselect.py --- a/src/lxml/cssselect.py Thu Nov 03 18:29:30 2011 +0100 +++ b/src/lxml/cssselect.py Thu Nov 03 22:10:18 2011 +0100 @@ -494,7 +494,7 @@ def _xpath_descendant(self, xpath, sub): # when sub is a descendant in any way of xpath - xpath.join('//', sub.xpath()) + xpath.join('/descendant-or-self::*/', sub.xpath()) return xpath def _xpath_child(self, xpath, sub): --------------- Stefan
Le 03/11/2011 22:14, Stefan Behnel a écrit :
Here's the obvious patch against 2.3.1, please give it a try.
Hi Stefan, Thanks for your quick and detailed response. Here are the results of the same test as in my first message, but on a different machine: lxml 2.3: 0.089 seconds lxml 2.3.1: 11 seconds lxml 2.3.1 with this patch: 0.69 seconds So while not as fast as 2.3, this is much more acceptable than 2.3.1. Do these three XPath expressions have the same meaning or are there cases where they do not give the same results? Which are correct for CSS? Regards, -- Simon
Simon Sapin, 03.11.2011 22:40:
Le 03/11/2011 22:14, Stefan Behnel a écrit :
Here's the obvious patch against 2.3.1, please give it a try.
Thanks for your quick and detailed response.
Here are the results of the same test as in my first message, but on a different machine:
lxml 2.3: 0.089 seconds lxml 2.3.1: 11 seconds lxml 2.3.1 with this patch: 0.69 seconds
So while not as fast as 2.3, this is much more acceptable than 2.3.1.
Do these three XPath expressions have the same meaning or are there cases where they do not give the same results? Which are correct for CSS?
Only the latter two give the correct result in all cases. The regression test suite also is a bit better in 2.3.1, so you'll notice when they break. See the doctests in test_css.txt and test_css_select.txt. It may still be possible to optimise the "simple" cases (those without conditions, or more specifically, those that do not require the position() XPath function in a condition) into using the faster "descendant::" axis, so that "dt dl" would be as fast as before, whereas "dt *:last-child" and maybe also things like "dt .classname" would get a performance hit (the latter could be optimised because, although using a condition, it does not depend on the position() XPath function). However, this requires more time than I can currently invest. I take patches. :) Stefan
Only the latter two give the correct result in all cases. The regression test suite also is a bit better in 2.3.1, so you'll notice when they break. See the doctests in test_css.txt and test_css_select.txt.
It may still be possible to optimise the "simple" cases (those without conditions, or more specifically, those that do not require the
Le 03/11/2011 23:02, Stefan Behnel a écrit : position()
XPath function in a condition) into using the faster "descendant::" axis, so that "dt dl" would be as fast as before, whereas "dt *:last-child" and maybe also things like "dt .classname" would get a performance hit (the latter could be optimised because, although using a condition, it does not depend on the position() XPath function).
However, this requires more time than I can currently invest.
I take patches.:)
Results vary a lot depending on the selector, but translation 1 (in 2.3) can be orders of magnitude faster than translation 3 (you latest patch), while 3 can be orders of magnitude faster than 2 (2.3.1) However if I understand right (pleas correct me if I’m wrong), 1 is wrong with some selectors. So your patch can be safely committed? Additionally, 1 could be use in some cases when it is safe, be deciding so is more difficult. I’m investigate. Thanks again! -- Simon
Le 04/11/2011 00:22, Simon Sapin a écrit :
Results vary a lot depending on the selector, but translation 1 (in 2.3) can be orders of magnitude faster than translation 3 (you latest patch), while 3 can be orders of magnitude faster than 2 (2.3.1)
However if I understand right (pleas correct me if I’m wrong), 1 is wrong with some selectors. So your patch can be safely committed?
... it’s now over yet! Both of these selectors take around 0.16 seconds with all three translations: .bad .bad *:not(.XXX) (still on the HTML5 spec, selector from its stylesheet.) However, they take much longer when joined together with a comma: .bad, .bad *:not(.XXX) 2.3: 1 second 2.3.1: 27 min (I was about to kill it…) 2.3.1 + patch: 7.4 min Not sure what’s going on here... In WeasyPrint’s use case I don’t care about the order of results and I can de-duplicate them myself. Is there a way to tell that to libxml2 so that it does not bother to sort and merge results sets? Would it help with performance? Regards, -- Simon Sapin
Simon Sapin, 04.11.2011 01:28:
Le 04/11/2011 00:22, Simon Sapin a écrit :
Results vary a lot depending on the selector, but translation 1 (in 2.3) can be orders of magnitude faster than translation 3 (you latest patch), while 3 can be orders of magnitude faster than 2 (2.3.1)
However if I understand right (pleas correct me if I’m wrong), 1 is wrong with some selectors. So your patch can be safely committed?
... it’s now over yet!
Both of these selectors take around 0.16 seconds with all three translations:
.bad .bad *:not(.XXX)
(still on the HTML5 spec, selector from its stylesheet.)
However, they take much longer when joined together with a comma:
.bad, .bad *:not(.XXX)
2.3: 1 second 2.3.1: 27 min (I was about to kill it…) 2.3.1 + patch: 7.4 min
Not sure what’s going on here...
You can easily see it with valgrind's call profiler callgrind and the visualiser tool kcachegrind (assuming you're on Linux), e.g. with this command line: valgrind --tool=callgrind --toggle-collect=xmlXPathCompiledEval \ python -c 'from lxml import cssselect,html; \ sel=cssselect.CSSSelector("dl dt"); \ p=html.parse("html5overview.html"); sel(p)' This will (after a while) write a profile to a file callgrind.out.PID, which you can open in kcachegrind. That will quickly tell you where the time is spent. Note that you need debugging symbols enabled, both in libxml2 and lxml (pass -ggdb in CFLAGS), in order to make sense out of it.
In WeasyPrint’s use case I don’t care about the order of results and I can de-duplicate them myself. Is there a way to tell that to libxml2 so that it does not bother to sort and merge results sets? Would it help with performance?
It would help, but libxml2 doesn't allow it. The problem is an internal function that gets called when subresults need to get merged. It won't make much sense to configure that externally, the XPath evaluator itself should detect when duplicates can occur and when removing them is unnecessary. Oh, and the implementation for duplicate removal could be a lot better as well. I really think we should move this discussion to the libxml2 mailing list by now. Stefan
Stefan Behnel, 04.11.2011 10:46:
Simon Sapin, 04.11.2011 01:28:
Le 04/11/2011 00:22, Simon Sapin a écrit :
Results vary a lot depending on the selector, but translation 1 (in 2.3) can be orders of magnitude faster than translation 3 (you latest patch), while 3 can be orders of magnitude faster than 2 (2.3.1)
However if I understand right (pleas correct me if I’m wrong), 1 is wrong with some selectors. So your patch can be safely committed?
... it’s now over yet!
Both of these selectors take around 0.16 seconds with all three translations:
.bad .bad *:not(.XXX)
(still on the HTML5 spec, selector from its stylesheet.)
However, they take much longer when joined together with a comma:
.bad, .bad *:not(.XXX)
2.3: 1 second 2.3.1: 27 min (I was about to kill it…) 2.3.1 + patch: 7.4 min
Not sure what’s going on here...
You can easily see it with valgrind's call profiler callgrind and the visualiser tool kcachegrind (assuming you're on Linux), e.g. with this command line:
valgrind --tool=callgrind --toggle-collect=xmlXPathCompiledEval \ python -c 'from lxml import cssselect,html; \ sel=cssselect.CSSSelector("dl dt"); \ p=html.parse("html5overview.html"); sel(p)'
This will (after a while) write a profile to a file callgrind.out.PID, which you can open in kcachegrind. That will quickly tell you where the time is spent. Note that you need debugging symbols enabled, both in libxml2 and lxml (pass -ggdb in CFLAGS), in order to make sense out of it.
In WeasyPrint’s use case I don’t care about the order of results and I can de-duplicate them myself. Is there a way to tell that to libxml2 so that it does not bother to sort and merge results sets? Would it help with performance?
It would help, but libxml2 doesn't allow it. The problem is an internal function that gets called when subresults need to get merged. It won't make much sense to configure that externally, the XPath evaluator itself should detect when duplicates can occur and when removing them is unnecessary. Oh, and the implementation for duplicate removal could be a lot better as well.
I really think we should move this discussion to the libxml2 mailing list by now.
http://thread.gmane.org/gmane.comp.gnome.lib.xml.general/16829 Stefan
participants (2)
-
Simon Sapin -
Stefan Behnel