GNOME Bugzilla – Bug 316288
xsltDocumentSortFunction performance
Last modified: 2005-09-14 12:35:52 UTC
Please describe the problem: Due to an unoptimized sorting algorithm in xsltDocumentSortFunction in xsltutils.c a <xsl:copy-of select="node()"/> on a node with some thousand children takes minutes to complete. Steps to reproduce: Take this simple stylesheet <xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"> <xsl:template match="data"> <xsl:copy-of select="node()"/> </xsl:template> </xsl:stylesheet> and transform a file like: <data> text<br/> text<br/> text<br/> text<br/> ... text<br/> text<br/> text<br/> text<br/> </data> with some thousand lines. Actual results: The transformation takes really long. 500 lines (1000 nodes) 2.6 secs 1000 lines (2000 nodes) 34 secs 2000 lines (4000 nodes) 319 secs (on a dual P-III 600 MHz) This even looks like O(N^3) Expected results: A running time of O(N), because there actually is no sorting to do, and O(N*log(N)) for cases where sorting is needed. Does this happen every time? Yes. Other information:
Created attachment 52218 [details] The example stylesheet mentioned above
Created attachment 52219 [details] An example XML file with 4000 child nodes
Okay the call isn't even necessary since the XPath evaluator already returns a node-set in document order. The patch is just to remove that call (I checked with more complex selct expressions to make sure). This is a remain of the very early times on libxslt work :-) paphio:~/XSLT/libxslt -> xsltproc -o res --timing ~/52218.xsl ~/52219.xml Parsing stylesheet /u/veillard/52218.xsl took 0 ms Parsing document /u/veillard/52219.xml took 3 ms Running stylesheet and saving result took 400 ms paphio:~/XSLT/libxslt -> compiled with debug etc ... Fixed in CVS, thanks for the report, Daniel