performance.txt

====================
Benchmarks and Speed
====================

:Author:
  Stefan Behnel

.. meta::
  :description: Performance evaluation of lxml and ElementTree:
                fast operations, common pitfalls and optimisation hints.
  :keywords: Python XML parser performance, XML processing, performance comparison,
             lxml performance, lxml.etree, lxml.objectify, benchmarks, ElementTree


lxml.etree is a very fast XML library.  Most of this is due to the
speed of libxml2, e.g. the parser and serialiser, or the XPath engine.
Other areas of lxml were specifically written for high performance in
high-level operations, such as the tree iterators.

On the other hand, the simplicity of lxml sometimes hides internal
operations that are more costly than the API suggests.  If you are not
aware of these cases, lxml may not always perform as you expect.  A
common example in the Python world is the Python list type.  New users
often expect it to be a linked list, while it actually is implemented
as an array, which results in a completely different complexity for
common operations.

Similarly, the tree model of libxml2 is more complex than what lxml's
ElementTree API projects into Python space, so some operations may
show unexpected performance.  Rest assured that most lxml users will
not notice this in real life, as lxml is very fast in absolute
numbers.  It is definitely fast enough for most applications, so lxml
is probably somewhere between 'fast enough' and 'the best choice' for
yours.  Read some messages_ from happy_ users_ to see what we mean.

.. _messages: http://permalink.gmane.org/gmane.comp.python.lxml.devel/3250
.. _happy: http://article.gmane.org/gmane.comp.python.lxml.devel/3246
.. _users: http://thread.gmane.org/gmane.comp.python.lxml.devel/3244/focus=3244

This text describes where lxml.etree (abbreviated to 'lxe') excels, gives
hints on some performance traps and compares the overall performance to the
original ElementTree_ (ET) and cElementTree_ (cET) libraries by Fredrik Lundh.
The cElementTree library is a fast C-implementation of the original
ElementTree.

.. _ElementTree:  http://effbot.org/zone/element-index.htm
.. _cElementTree: http://effbot.org/zone/celementtree.htm

.. contents::
.. 
   1  How to read the timings
   2  Bad things first
   3  Parsing and Serialising
   4  The ElementTree API
   5  Tree traversal
   6  XPath
   7  lxml.objectify


General notes
=============

First thing to say: there *is* an overhead involved in having a DOM-like C
library mimic the ElementTree API.  As opposed to ElementTree, lxml has to
generate Python representations of tree nodes on the fly when asked for them,
and the internal tree structure of libxml2 results in a higher maintenance
overhead than the simpler top-down structure of ElementTree.  What this means
is: the more of your code runs in Python, the less you can benefit from the
speed of lxml and libxml2.  Note, however, that this is true for most
performance critical Python applications.  No one would implement fourier
transformations in pure Python when you can use NumPy.

The up side then is that lxml provides powerful tools like tree iterators,
XPath and XSLT, that can handle complex operations at the speed of C.  Their
pythonic API in lxml makes them so flexible that most applications can easily
benefit from them.


How to read the timings
=======================

The statements made here are backed by the (micro-)benchmark scripts
`bench_etree.py`_, `bench_xpath.py`_ and `bench_objectify.py`_ that come with
the lxml source distribution.  They are distributed under the same BSD license
as lxml itself, and the lxml project would like to promote them as a general
benchmarking suite for all ElementTree implementations.  New benchmarks are
very easy to add as tiny test methods, so if you write a performance test for
a specific part of the API yourself, please consider sending it to the lxml
mailing list.

The timings cited below compare lxml 2.3 (with libxml2 2.7.6) to the
latest developer versions of ElementTree (1.3beta2) and cElementTree
(1.0.6a3).  They were run single-threaded on a 2.5GHz 64bit Intel Core
Duo machine under Ubuntu Linux 9.10 (Karmic).  The C libraries were
compiled with the same platform specific optimisation flags.  The
Python interpreter (2.6.4) was also manually compiled for the
platform.  Note that many of the following ElementTree timings are
therefore better then what a normal Python installation with the
standard library (c)ElementTree modules would yield.

.. _`bench_etree.py`:     https://github.com/lxml/lxml/blob/master/benchmark/bench_etree.py
.. _`bench_xpath.py`:     https://github.com/lxml/lxml/blob/master/benchmark/bench_xpath.py
.. _`bench_objectify.py`: https://github.com/lxml/lxml/blob/master/benchmark/bench_objectify.py

The scripts run a number of simple tests on the different libraries, using
different XML tree configurations: different tree sizes (T1-4), with or
without attributes (-/A), with or without ASCII string or unicode text
(-/S/U), and either against a tree or its serialised XML form (T/X).  In the
result extracts cited below, T1 refers to a 3-level tree with many children at
the third level, T2 is swapped around to have many children below the root
element, T3 is a deep tree with few children at each level and T4 is a small
tree, slightly broader than deep.  If repetition is involved, this usually
means running the benchmark in a loop over all children of the tree root,
otherwise, the operation is run on the root node (C/R).

As an example, the character code ``(SATR T1)`` states that the benchmark was
running for tree T1, with plain string text (S) and attributes (A).  It was
run against the root element (R) in the tree structure of the data (T).

Note that very small operations are repeated in integer loops to make them
measurable.  It is therefore not always possible to compare the absolute
timings of, say, a single access benchmark (which usually loops) and a 'get
all in one step' benchmark, which already takes enough time to be measurable
and is therefore measured as is.  An example is the index access to a single
child, which cannot be compared to the timings for ``getchildren()``.  Take a
look at the concrete benchmarks in the scripts to understand how the numbers
compare.


Parsing and Serialising
=======================

Serialisation is an area where lxml excels.  The reason is that it
executes entirely at the C level, without any interaction with Python
code.  The results are rather impressive, especially for UTF-8, which
is native to libxml2.  While 20 to 40 times faster than (c)ElementTree
1.2 (which is part of the standard library since Python 2.5), lxml is
still more than 7 times as fast as the much improved ElementTree 1.3::

  lxe: tostring_utf16  (S-TR T1)    9.8219 msec/pass
  cET: tostring_utf16  (S-TR T1)   88.7740 msec/pass
  ET : tostring_utf16  (S-TR T1)   99.6690 msec/pass

  lxe: tostring_utf16  (UATR T1)   10.3750 msec/pass
  cET: tostring_utf16  (UATR T1)   90.7581 msec/pass
  ET : tostring_utf16  (UATR T1)  102.3569 msec/pass

  lxe: tostring_utf16  (S-TR T2)   10.2711 msec/pass
  cET: tostring_utf16  (S-TR T2)   93.5340 msec/pass
  ET : tostring_utf16  (S-TR T2)  105.8500 msec/pass

  lxe: tostring_utf8   (S-TR T2)    7.1261 msec/pass
  cET: tostring_utf8   (S-TR T2)   93.4091 msec/pass
  ET : tostring_utf8   (S-TR T2)  105.5419 msec/pass

  lxe: tostring_utf8   (U-TR T3)    1.4591 msec/pass
  cET: tostring_utf8   (U-TR T3)   29.6180 msec/pass
  ET : tostring_utf8   (U-TR T3)   31.9080 msec/pass

The same applies to plain text serialisation.  Note that the
cElementTree version in the standard library does not currently
support this, as it is a new feature in ET 1.3 and lxml.etree 2.0::

  lxe: tostring_text_ascii     (S-TR T1)    1.9400 msec/pass
  cET: tostring_text_ascii     (S-TR T1)   41.6231 msec/pass
  ET : tostring_text_ascii     (S-TR T1)   52.7501 msec/pass

  lxe: tostring_text_ascii     (S-TR T3)    0.5331 msec/pass
  cET: tostring_text_ascii     (S-TR T3)   12.9712 msec/pass
  ET : tostring_text_ascii     (S-TR T3)   15.3620 msec/pass

  lxe: tostring_text_utf16     (S-TR T1)    3.2430 msec/pass
  cET: tostring_text_utf16     (S-TR T1)   41.9259 msec/pass
  ET : tostring_text_utf16     (S-TR T1)   53.4091 msec/pass

  lxe: tostring_text_utf16     (U-TR T1)    3.6838 msec/pass
  cET: tostring_text_utf16     (U-TR T1)   38.7859 msec/pass
  ET : tostring_text_utf16     (U-TR T1)   50.8440 msec/pass

Unlike ElementTree, the ``tostring()`` function in lxml also supports
serialisation to a Python unicode string object::

  lxe: tostring_text_unicode   (S-TR T1)    2.4869 msec/pass
  lxe: tostring_text_unicode   (U-TR T1)    3.0370 msec/pass
  lxe: tostring_text_unicode   (S-TR T3)    0.6518 msec/pass
  lxe: tostring_text_unicode   (U-TR T3)    0.7300 msec/pass

For parsing, lxml.etree and cElementTree compete for the medal.
Depending on the input, either of the two can be faster.  The (c)ET
libraries use a very thin layer on top of the expat parser, which is
known to be very fast.  Here are some timings from the benchmarking
suite::

  lxe: parse_stringIO  (SAXR T1)   19.9990 msec/pass
  cET: parse_stringIO  (SAXR T1)    8.4970 msec/pass
  ET : parse_stringIO  (SAXR T1)  183.9781 msec/pass

  lxe: parse_stringIO  (S-XR T3)    2.0790 msec/pass
  cET: parse_stringIO  (S-XR T3)    2.7430 msec/pass
  ET : parse_stringIO  (S-XR T3)   47.4229 msec/pass

  lxe: parse_stringIO  (UAXR T3)   11.1630 msec/pass
  cET: parse_stringIO  (UAXR T3)   15.0940 msec/pass
  ET : parse_stringIO  (UAXR T3)   92.6890 msec/pass

And another couple of timings `from a benchmark`_ that Fredrik Lundh
`used to promote cElementTree`_, comparing a number of different
parsers.  First, parsing a 274KB XML file containing Shakespeare's
Hamlet::

  lxml.etree.parse done in 0.005 seconds
  cElementTree.parse done in 0.012 seconds
  elementtree.ElementTree.parse done in 0.136 seconds
  elementtree.XMLTreeBuilder: 6636 nodes read in 0.243 seconds
  elementtree.SimpleXMLTreeBuilder: 6636 nodes read in 0.314 seconds
  elementtree.SgmlopXMLTreeBuilder: 6636 nodes read in 0.104 seconds
  minidom tree read in 0.137 seconds

And a 3.4MB XML file containing the Old Testament::

  lxml.etree.parse done in 0.031 seconds
  cElementTree.parse done in 0.039 seconds
  elementtree.ElementTree.parse done in 0.537 seconds
  elementtree.XMLTreeBuilder: 25317 nodes read in 0.577 seconds
  elementtree.SimpleXMLTreeBuilder: 25317 nodes read in 1.265 seconds
  elementtree.SgmlopXMLTreeBuilder: 25317 nodes read in 0.331 seconds
  minidom tree read in 0.643 seconds

.. _`from a benchmark`: http://svn.effbot.org/public/elementtree-1.3/benchmark.py
.. _`used to promote cElementTree`: http://effbot.org/zone/celementtree.htm#benchmarks

Here are the same benchmarks run under an early alpha of CPython 3.3,
but on a different machine, which makes the absolute numbers
uncomparable.  This time, however, we include the memory usage of the
process in KB before and after parsing (using os.fork() to make sure
we start from a clean state each time).  For the 274KB hamlet.xml
file::

  Memory usage at start: 7288
  xml.etree.ElementTree.parse done in 0.104 seconds
  Memory usage: 14252 (+6964)
  xml.etree.cElementTree.parse done in 0.016 seconds
  Memory usage: 9748 (+2460)
  lxml.etree.parse done in 0.017 seconds
  Memory usage: 11040 (+3752)
  lxml.etree[remove_blank_space].parse done in 0.015 seconds
  Memory usage: 10088 (+2800)
  minidom tree read in 0.152 seconds
  Memory usage: 30376 (+23088)

And for the 3.4MB Old Testament XML file::

  Memory usage at start: 20456
  xml.etree.ElementTree.parse done in 0.419 seconds
  Memory usage: 46112 (+25656)
  xml.etree.cElementTree.parse done in 0.054 seconds
  Memory usage: 32644 (+12188)
  lxml.etree.parse done in 0.041 seconds
  Memory usage: 37508 (+17052)
  lxml.etree[remove_blank_space].parse done in 0.037 seconds
  Memory usage: 34356 (+13900)
  minidom tree read in 0.671 seconds
  Memory usage: 110448 (+89992)

As can be seen from the sizes, both lxml.etree and cElementTree are
rather memory friendly compared to the pure Python libraries
ElementTree and (especially) minidom.  And the timings speak for
themselves anyway.

For plain parser performance, lxml.etree and cElementTree tend to stay
rather close to each other, usually within a factor of two, with
winners well distributed over both sides.  Similar timings can be
observed for the ``iterparse()`` function::

  lxe: iterparse_stringIO  (SAXR T1)   24.8621 msec/pass
  cET: iterparse_stringIO  (SAXR T1)   17.3280 msec/pass
  ET : iterparse_stringIO  (SAXR T1)  199.1270 msec/pass

  lxe: iterparse_stringIO  (UAXR T3)   12.3630 msec/pass
  cET: iterparse_stringIO  (UAXR T3)   17.5190 msec/pass
  ET : iterparse_stringIO  (UAXR T3)   95.8610 msec/pass

However, if you benchmark the complete round-trip of a serialise-parse
cycle, the numbers will look similar to these::

  lxe: write_utf8_parse_stringIO  (S-TR T1)   27.5791 msec/pass
  cET: write_utf8_parse_stringIO  (S-TR T1)  158.9060 msec/pass
  ET : write_utf8_parse_stringIO  (S-TR T1)  347.8320 msec/pass

  lxe: write_utf8_parse_stringIO  (UATR T2)   34.4141 msec/pass
  cET: write_utf8_parse_stringIO  (UATR T2)  187.7041 msec/pass
  ET : write_utf8_parse_stringIO  (UATR T2)  388.9449 msec/pass

  lxe: write_utf8_parse_stringIO  (S-TR T3)    3.7861 msec/pass
  cET: write_utf8_parse_stringIO  (S-TR T3)   52.4600 msec/pass
  ET : write_utf8_parse_stringIO  (S-TR T3)  101.4550 msec/pass

  lxe: write_utf8_parse_stringIO  (SATR T4)    0.5522 msec/pass
  cET: write_utf8_parse_stringIO  (SATR T4)    3.8941 msec/pass
  ET : write_utf8_parse_stringIO  (SATR T4)    5.9431 msec/pass

For applications that require a high parser throughput of large files,
and that do little to no serialization, both cET and lxml.etree are a
good choice.  The cET library is particularly fast for iterparse
applications that extract small amounts of data or aggregate
information from large XML data sets that do not fit into memory.  If
it comes to round-trip performance, however, lxml is multiple times
faster in total.  So, whenever the input documents are not
considerably larger than the output, lxml is the clear winner.

Regarding HTML parsing, Ian Bicking has done some `benchmarking on
lxml's HTML parser`_, comparing it to a number of other famous HTML
parser tools for Python.  lxml wins this contest by quite a length.
To give an idea, the numbers suggest that lxml.html can run a couple
of parse-serialise cycles in the time that other tools need for
parsing alone.  The comparison even shows some very favourable results
regarding memory consumption.

.. _`benchmarking on lxml's HTML parser`: http://blog.ianbicking.org/2008/03/30/python-html-parser-performance/

Liza Daly has written an article that presents a couple of tweaks to
get the most out of lxml's parser for very large XML documents.  She
quite favourably positions ``lxml.etree`` as a tool for
`high-performance XML parsing`_.

.. _`high-performance XML parsing`: http://www.ibm.com/developerworks/xml/library/x-hiperfparse/

Finally, `xml.com`_ has a couple of publications about XML parser
performance.  Farwick and Hafner have written two interesting articles
that compare the parser of libxml2 to some major Java based XML
parsers.  One deals with `event-driven parser performance`_, the other
one presents `benchmark results comparing DOM parsers`_.  Both
comparisons suggest that libxml2's parser performance is largely
superiour to all commonly used Java parsers in almost all cases.  Note
that the C parser benchmark results are based on xmlbench_, which uses
a simpler setup for libxml2 than lxml does.

.. _`xml.com`: http://www.xml.com/
.. _`event-driven parser performance`: http://www.xml.com/lpt/a/1702
.. _`benchmark results comparing DOM parsers`: http://www.xml.com/lpt/a/1703
.. _xmlbench: http://xmlbench.sourceforge.net/


The ElementTree API
===================

Since all three libraries implement the same API, their performance is
easy to compare in this area.  A major disadvantage for lxml's
performance is the different tree model that underlies libxml2.  It
allows lxml to provide parent pointers for elements and full XPath
support, but also increases the overhead of tree building and
restructuring.  This can be seen from the tree setup times of the
benchmark (given in seconds)::

  lxe:       --     S-     U-     -A     SA     UA  
       T1: 0.0407 0.0470 0.0506 0.0396 0.0464 0.0504
       T2: 0.0480 0.0557 0.0584 0.0520 0.0608 0.0627
       T3: 0.0118 0.0132 0.0136 0.0319 0.0322 0.0319
       T4: 0.0002 0.0002 0.0002 0.0006 0.0006 0.0006
  cET:       --     S-     U-     -A     SA     UA  
       T1: 0.0045 0.0043 0.0043 0.0045 0.0043 0.0043
       T2: 0.0068 0.0069 0.0066 0.0078 0.0070 0.0069
       T3: 0.0040 0.0040 0.0040 0.0050 0.0052 0.0067
       T4: 0.0000 0.0000 0.0000 0.0001 0.0001 0.0001
  ET :       --     S-     U-     -A     SA     UA  
       T1: 0.0479 0.1051 0.1279 0.0487 0.1597 0.0484
       T2: 0.1995 0.0553 0.2297 0.2550 0.0550 0.2881
       T3: 0.0177 0.0169 0.0174 0.0185 0.2895 0.0189
       T4: 0.0003 0.0002 0.0003 0.0003 0.0014 0.0003

While lxml is still a lot faster than ET in most cases, cET can be
several times faster than lxml here.  One of the reasons is that lxml
must encode incoming string data and tag names into UTF-8, and
additionally discard the created Python elements after their use, when
they are no longer referenced.  ET and cET represent the tree itself
through these objects, which reduces the overhead in creating them.


Child access
------------

The same reason makes operations like collecting children as in
``list(element)`` more costly in lxml.  Where ET and cET can quickly
create a shallow copy of their list of children, lxml has to create a
Python object for each child and collect them in a list::

  lxe: root_list_children        (--TR T1)    0.0079 msec/pass
  cET: root_list_children        (--TR T1)    0.0029 msec/pass
  ET : root_list_children        (--TR T1)    0.0100 msec/pass

  lxe: root_list_children        (--TR T2)    0.0849 msec/pass
  cET: root_list_children        (--TR T2)    0.0110 msec/pass
  ET : root_list_children        (--TR T2)    0.1481 msec/pass

This handicap is also visible when accessing single children::

  lxe: first_child               (--TR T2)    0.0699 msec/pass
  cET: first_child               (--TR T2)    0.0608 msec/pass
  ET : first_child               (--TR T2)    0.3419 msec/pass

  lxe: last_child                (--TR T1)    0.0710 msec/pass
  cET: last_child                (--TR T1)    0.0648 msec/pass
  ET : last_child                (--TR T1)    0.3309 msec/pass

... unless you also add the time to find a child index in a bigger
list.  ET and cET use Python lists here, which are based on arrays.
The data structure used by libxml2 is a linked tree, and thus, a
linked list of children::

  lxe: middle_child              (--TR T1)    0.0989 msec/pass
  cET: middle_child              (--TR T1)    0.0598 msec/pass
  ET : middle_child              (--TR T1)    0.3390 msec/pass

  lxe: middle_child              (--TR T2)    2.7599 msec/pass
  cET: middle_child              (--TR T2)    0.0620 msec/pass
  ET : middle_child              (--TR T2)    0.3610 msec/pass


Element creation
----------------

As opposed to ET, libxml2 has a notion of documents that each element must be
in.  This results in a major performance difference for creating independent
Elements that end up in independently created documents::

  lxe: create_elements           (--TC T2)    1.1640 msec/pass
  cET: create_elements           (--TC T2)    0.0808 msec/pass
  ET : create_elements           (--TC T2)    0.5801 msec/pass

Therefore, it is always preferable to create Elements for the document they
are supposed to end up in, either as SubElements of an Element or using the
explicit ``Element.makeelement()`` call::

  lxe: makeelement               (--TC T2)    1.2751 msec/pass
  cET: makeelement               (--TC T2)    0.1469 msec/pass
  ET : makeelement               (--TC T2)    0.7451 msec/pass

  lxe: create_subelements        (--TC T2)    1.1470 msec/pass
  cET: create_subelements        (--TC T2)    0.1080 msec/pass
  ET : create_subelements        (--TC T2)    1.4369 msec/pass

So, if the main performance bottleneck of an application is creating large XML
trees in memory through calls to Element and SubElement, cET is the best
choice.  Note, however, that the serialisation performance may even out this
advantage, especially for smaller trees and trees with many attributes.


Merging different sources
-------------------------

A critical action for lxml is moving elements between document contexts.  It
requires lxml to do recursive adaptations throughout the moved tree structure.

The following benchmark appends all root children of the second tree to the
root of the first tree::

  lxe: append_from_document      (--TR T1,T2)    2.0740 msec/pass
  cET: append_from_document      (--TR T1,T2)    0.1271 msec/pass
  ET : append_from_document      (--TR T1,T2)    0.4020 msec/pass

  lxe: append_from_document      (--TR T3,T4)    0.0229 msec/pass
  cET: append_from_document      (--TR T3,T4)    0.0088 msec/pass
  ET : append_from_document      (--TR T3,T4)    0.0291 msec/pass

Although these are fairly small numbers compared to parsing, this easily shows
the different performance classes for lxml and (c)ET.  Where the latter do not
have to care about parent pointers and tree structures, lxml has to deep
traverse the appended tree.  The performance difference therefore increases
with the size of the tree that is moved.

This difference is not always as visible, but applies to most parts of the
API, like inserting newly created elements::

  lxe: insert_from_document       (--TR T1,T2)    7.2598 msec/pass
  cET: insert_from_document       (--TR T1,T2)    0.1578 msec/pass
  ET : insert_from_document       (--TR T1,T2)    0.5150 msec/pass

or replacing the child slice by a newly created element::

  lxe: replace_children_element   (--TC T1)    0.1149 msec/pass
  cET: replace_children_element   (--TC T1)    0.0110 msec/pass
  ET : replace_children_element   (--TC T1)    0.0558 msec/pass

as opposed to replacing the slice with an existing element from the
same document::

  lxe: replace_children           (--TC T1)    0.0091 msec/pass
  cET: replace_children           (--TC T1)    0.0060 msec/pass
  ET : replace_children           (--TC T1)    0.0188 msec/pass

While these numbers are too small to provide a major performance
impact in practice, you should keep this difference in mind when you
merge very large trees.


deepcopy
--------

Deep copying a tree is fast in lxml::

  lxe: deepcopy_all              (--TR T1)    5.0900 msec/pass
  cET: deepcopy_all              (--TR T1)   57.9181 msec/pass
  ET : deepcopy_all              (--TR T1)  499.1000 msec/pass

  lxe: deepcopy_all              (-ATR T2)    6.3980 msec/pass
  cET: deepcopy_all              (-ATR T2)   65.6390 msec/pass
  ET : deepcopy_all              (-ATR T2)  526.5379 msec/pass

  lxe: deepcopy_all              (S-TR T3)    1.4491 msec/pass
  cET: deepcopy_all              (S-TR T3)   14.7018 msec/pass
  ET : deepcopy_all              (S-TR T3)  123.5120 msec/pass

So, for example, if you have a database-like scenario where you parse in a
large tree and then search and copy independent subtrees from it for further
processing, lxml is by far the best choice here.


Tree traversal
--------------

Another area where lxml is very fast is iteration for tree traversal.  If your
algorithms can benefit from step-by-step traversal of the XML tree and
especially if few elements are of interest or the target element tag name is
known, lxml is a good choice::

  lxe: getiterator_all      (--TR T1)    1.6890 msec/pass
  cET: getiterator_all      (--TR T1)   23.8621 msec/pass
  ET : getiterator_all      (--TR T1)   11.1070 msec/pass

  lxe: getiterator_islice   (--TR T2)    0.0188 msec/pass
  cET: getiterator_islice   (--TR T2)    0.1841 msec/pass
  ET : getiterator_islice   (--TR T2)   11.7059 msec/pass

  lxe: getiterator_tag      (--TR T2)    0.0119 msec/pass
  cET: getiterator_tag      (--TR T2)    0.3560 msec/pass
  ET : getiterator_tag      (--TR T2)   10.6668 msec/pass

  lxe: getiterator_tag_all  (--TR T2)    0.2429 msec/pass
  cET: getiterator_tag_all  (--TR T2)   20.3710 msec/pass
  ET : getiterator_tag_all  (--TR T2)   10.6280 msec/pass

This translates directly into similar timings for ``Element.findall()``::

  lxe: findall              (--TR T2)    2.4588 msec/pass
  cET: findall              (--TR T2)   24.1358 msec/pass
  ET : findall              (--TR T2)   13.0949 msec/pass

  lxe: findall              (--TR T3)    0.5939 msec/pass
  cET: findall              (--TR T3)    6.9802 msec/pass
  ET : findall              (--TR T3)    3.8991 msec/pass

  lxe: findall_tag          (--TR T2)    0.2789 msec/pass
  cET: findall_tag          (--TR T2)   20.5719 msec/pass
  ET : findall_tag          (--TR T2)   10.8678 msec/pass

  lxe: findall_tag          (--TR T3)    0.1638 msec/pass
  cET: findall_tag          (--TR T3)    5.0790 msec/pass
  ET : findall_tag          (--TR T3)    2.5120 msec/pass

Note that all three libraries currently use the same Python
implementation for ``.findall()``, except for their native tree
iterator (``element.iter()``).


XPath
=====

The following timings are based on the benchmark script `bench_xpath.py`_.

This part of lxml does not have an equivalent in ElementTree.  However, lxml
provides more than one way of accessing it and you should take care which part
of the lxml API you use.  The most straight forward way is to call the
``xpath()`` method on an Element or ElementTree::

  lxe: xpath_method         (--TC T1)    0.7598 msec/pass
  lxe: xpath_method         (--TC T2)   12.6798 msec/pass
  lxe: xpath_method         (--TC T3)    0.0758 msec/pass
  lxe: xpath_method         (--TC T4)    0.6182 msec/pass

This is well suited for testing and when the XPath expressions are as diverse
as the trees they are called on.  However, if you have a single XPath
expression that you want to apply to a larger number of different elements,
the ``XPath`` class is the most efficient way to do it::

  lxe: xpath_class          (--TC T1)    0.2189 msec/pass
  lxe: xpath_class          (--TC T2)    1.4110 msec/pass
  lxe: xpath_class          (--TC T3)    0.0319 msec/pass
  lxe: xpath_class          (--TC T4)    0.0880 msec/pass

Note that this still allows you to use variables in the expression, so you can
parse it once and then adapt it through variables at call time.  In other
cases, where you have a fixed Element or ElementTree and want to run different
expressions on it, you should consider the ``XPathEvaluator``::

  lxe: xpath_element        (--TR T1)    0.1669 msec/pass
  lxe: xpath_element        (--TR T2)    6.9060 msec/pass
  lxe: xpath_element        (--TR T3)    0.0451 msec/pass
  lxe: xpath_element        (--TR T4)    0.1681 msec/pass

While it looks slightly slower, creating an XPath object for each of the
expressions generates a much higher overhead here::

  lxe: xpath_class_repeat   (--TC T1)    0.7451 msec/pass
  lxe: xpath_class_repeat   (--TC T2)   12.2290 msec/pass
  lxe: xpath_class_repeat   (--TC T3)    0.0730 msec/pass
  lxe: xpath_class_repeat   (--TC T4)    0.5970 msec/pass


A longer example
================

... based on lxml 1.3.

A while ago, Uche Ogbuji posted a `benchmark proposal`_ that would
read in a 3MB XML version of the `Old Testament`_ of the Bible and
look for the word *begat* in all verses.  Apparently, it is contained
in 120 out of almost 24000 verses.  This is easy to implement in
ElementTree using ``findall()``.  However, the fastest and most memory
friendly way to do this is obviously ``iterparse()``, as most of the
data is not of any interest.

.. _`benchmark proposal`: http://www.onlamp.com/pub/wlg/6291
.. _`Old Testament`: http://www.ibiblio.org/bosak/xml/eg/religion.2.00.xml.zip

Now, Uche's original proposal was more or less the following:

.. sourcecode:: python

  def bench_ET():
      tree = ElementTree.parse("ot.xml")
      result = []
      for v in tree.findall("//v"):
          text = v.text
          if 'begat' in text:
              result.append(text)
      return len(result)

which takes about one second on my machine today.  The faster ``iterparse()``
variant looks like this:

.. sourcecode:: python

  def bench_ET_iterparse():
      result = []
      for event, v in ElementTree.iterparse("ot.xml"):
          if v.tag == 'v':
              text = v.text
              if 'begat' in text:
                  result.append(text)
          v.clear()
      return len(result)

The improvement is about 10%.  At the time I first tried (early 2006), lxml
didn't have ``iterparse()`` support, but the ``findall()`` variant was already
faster than ElementTree.  This changes immediately when you switch to
cElementTree.  The latter only needs 0.17 seconds to do the trick today and
only some impressive 0.10 seconds when running the iterparse version.  And
even back then, it was quite a bit faster than what lxml could achieve.

Since then, lxml has matured a lot and has gotten much faster.  The iterparse
variant now runs in 0.14 seconds, and if you remove the ``v.clear()``, it is
even a little faster (which isn't the case for cElementTree).

One of the many great tools in lxml is XPath, a swiss army knife for finding
things in XML documents.  It is possible to move the whole thing to a pure
XPath implementation, which looks like this:

.. sourcecode:: python

  def bench_lxml_xpath_all():
      tree = etree.parse("ot.xml")
      result = tree.xpath("//v[contains(., 'begat')]/text()")
      return len(result)

This runs in about 0.13 seconds and is about the shortest possible
implementation (in lines of Python code) that I could come up with.  Now, this
is already a rather complex XPath expression compared to the simple "//v"
ElementPath expression we started with.  Since this is also valid XPath, let's
try this instead:

.. sourcecode:: python

  def bench_lxml_xpath():
      tree = etree.parse("ot.xml")
      result = []
      for v in tree.xpath("//v"):
          text = v.text
          if 'begat' in text:
              result.append(text)
      return len(result)

This gets us down to 0.12 seconds, thus showing that a generic XPath
evaluation engine cannot always compete with a simpler, tailored solution.
However, since this is not much different from the original findall variant,
we can remove the complexity of the XPath call completely and just go with
what we had in the beginning.  Under lxml, this runs in the same 0.12 seconds.

But there is one thing left to try.  We can replace the simple ElementPath
expression with a native tree iterator:

.. sourcecode:: python

  def bench_lxml_getiterator():
      tree = etree.parse("ot.xml")
      result = []
      for v in tree.getiterator("v"):
          text = v.text
          if 'begat' in text:
              result.append(text)
      return len(result)

This implements the same thing, just without the overhead of parsing and
evaluating a path expression.  And this makes it another bit faster, down to
0.11 seconds.  For comparison, cElementTree runs this version in 0.17 seconds.

So, what have we learned?

* Python code is not slow.  The pure XPath solution was not even as fast as
  the first shot Python implementation.  In general, a few more lines in
  Python make things more readable, which is much more important than the last
  5% of performance.

* It's important to know the available options - and it's worth starting with
  the most simple one.  In this case, a programmer would then probably have
  started with ``getiterator("v")`` or ``iterparse()``.  Either of them would
  already have been the most efficient, depending on which library is used.

* It's important to know your tool.  lxml and cElementTree are both very fast
  libraries, but they do not have the same performance characteristics.  The
  fastest solution in one library can be comparatively slow in the other.  If
  you optimise, optimise for the specific target platform.

* It's not always worth optimising.  After all that hassle we got from 0.12
  seconds for the initial implementation to 0.11 seconds.  Switching over to
  cElementTree and writing an ``iterparse()`` based version would have given
  us 0.10 seconds - not a big difference for 3MB of XML.

* Take care what operation is really dominating in your use case.  If we split
  up the operations, we can see that lxml is slightly slower than cElementTree
  on ``parse()`` (both about 0.06 seconds), but more visibly slower on
  ``iterparse()``: 0.07 versus 0.10 seconds.  However, tree iteration in lxml
  is increadibly fast, so it can be better to parse the whole tree and then
  iterate over it rather than using ``iterparse()`` to do both in one step.
  Or, you can just wait for the lxml developers to optimise iterparse in one
  of the next releases...


lxml.objectify
==============

The following timings are based on the benchmark script `bench_objectify.py`_.

Objectify is a data-binding API for XML based on lxml.etree, that was added in
version 1.1.  It uses standard Python attribute access to traverse the XML
tree.  It also features ObjectPath, a fast path language based on the same
meme.

Just like lxml.etree, lxml.objectify creates Python representations of
elements on the fly.  To save memory, the normal Python garbage collection
mechanisms will discard them when their last reference is gone.  In cases
where deeply nested elements are frequently accessed through the objectify
API, the create-discard cycles can become a bottleneck, as elements have to be
instantiated over and over again.


ObjectPath
----------

ObjectPath can be used to speed up the access to elements that are deep in the
tree.  It avoids step-by-step Python element instantiations along the path,
which can substantially improve the access time::

  lxe: attribute                  (--TR T1)    4.8928 msec/pass
  lxe: attribute                  (--TR T2)   25.5480 msec/pass
  lxe: attribute                  (--TR T4)    4.6349 msec/pass

  lxe: objectpath                 (--TR T1)    1.4842 msec/pass
  lxe: objectpath                 (--TR T2)   21.1990 msec/pass
  lxe: objectpath                 (--TR T4)    1.4892 msec/pass

  lxe: attributes_deep            (--TR T1)   11.9710 msec/pass
  lxe: attributes_deep            (--TR T2)   32.4290 msec/pass
  lxe: attributes_deep            (--TR T4)   11.4839 msec/pass

  lxe: objectpath_deep            (--TR T1)    4.8139 msec/pass
  lxe: objectpath_deep            (--TR T2)   24.6511 msec/pass
  lxe: objectpath_deep            (--TR T4)    4.7588 msec/pass

Note, however, that parsing ObjectPath expressions is not for free either, so
this is most effective for frequently accessing the same element.


Caching Elements
----------------

A way to improve the normal attribute access time is static instantiation of
the Python objects, thus trading memory for speed.  Just create a cache
dictionary and run:

.. sourcecode:: python

    cache[root] = list(root.iter())

after parsing and:

.. sourcecode:: python

    del cache[root]

when you are done with the tree.  This will keep the Python element
representations of all elements alive and thus avoid the overhead of repeated
Python object creation.  You can also consider using filters or generator
expressions to be more selective.  By choosing the right trees (or even
subtrees and elements) to cache, you can trade memory usage against access
speed::

  lxe: attribute_cached           (--TR T1)    3.8228 msec/pass
  lxe: attribute_cached           (--TR T2)   23.7138 msec/pass
  lxe: attribute_cached           (--TR T4)    3.5269 msec/pass

  lxe: attributes_deep_cached     (--TR T1)    4.6771 msec/pass
  lxe: attributes_deep_cached     (--TR T2)   24.8699 msec/pass
  lxe: attributes_deep_cached     (--TR T4)    4.3321 msec/pass

  lxe: objectpath_deep_cached     (--TR T1)    1.1430 msec/pass
  lxe: objectpath_deep_cached     (--TR T2)   19.7470 msec/pass
  lxe: objectpath_deep_cached     (--TR T4)    1.1740 msec/pass

Things to note: you cannot currently use ``weakref.WeakKeyDictionary`` objects
for this as lxml's element objects do not support weak references (which are
costly in terms of memory).  Also note that new element objects that you add
to these trees will not turn up in the cache automatically and will therefore
still be garbage collected when all their Python references are gone, so this
is most effective for largely immutable trees.  You should consider using a
set instead of a list in this case and add new elements by hand.


Further optimisations
---------------------

Here are some more things to try if optimisation is required:

* A lot of time is usually spent in tree traversal to find the addressed
  elements in the tree.  If you often work in subtrees, do what you would also
  do with deep Python objects: assign the parent of the subtree to a variable
  or pass it into functions instead of starting at the root.  This allows
  accessing its descendents more directly.

* Try assigning data values directly to attributes instead of passing them
  through DataElement.

* If you use custom data types that are costly to parse, try running
  ``objectify.annotate()`` over read-only trees to speed up the attribute type
  inference on read access.

Note that none of these measures is guaranteed to speed up your application.
As usual, you should prefer readable code over premature optimisations and
profile your expected use cases before bothering to apply optimisations at
random.