xbmc/xbmc — pull request #3677 by bavison (2013-11-18 16:18:50+00:00)
Title: Faster infobool expression evaluation

[This PR depends on PR #3676, but only peripherally. To test in isolation,
simply remove any references to listItemDependent or m_listItemDependent.
Merge #3676 first]

Expession infobools are evaluated at runtime from one or more single infobools
and a combination of boolean NOT, AND and OR operators. Previously, parsing
produced a vector of operands (leaf nodes) and operators in postfix
(reverse-Polish) form, and evaluated all leaf nodes every time the expression
was evaluated. But this ignores the fact that in many cases, once one operand
of an AND or OR operation has been evaluated, there is no need to evaluate the
other operand because its value can have no effect on the ultimate result. It
is also worth noting that AND and OR operations are associative, meaning they
can be rearranged at runtime to better suit the selected skin.

This patch rewrites the expression parsing and evaluation code. Now the
internal repreentation is in the form of a tree where leaf nodes represent a
single infobool, and branch nodes represent either an AND or an OR operation
on two or more child nodes.

Expressions are rewritten at parse time into a form which favours the
formation of groups of associative nodes. These groups are then reordered at
evaluation time such that nodes whose value renders the evaluation of the
remainder of the group unnecessary tend to be evaluated first (these are
true nodes for OR subexpressions, or false nodes for AND subexpressions).
The end effect is to minimise the number of leaf nodes that need to be
evaluated in order to determine the value of the expression. The runtime
adaptability has the advantage of not being customised for any particular skin.

The modifications to the expression at parse time fall into two groups:
1) Moving logical NOTs so that they are only applied to leaf nodes.
For example, rewriting ![A+B]|C as !A|!B|C allows reordering such that
any of the three leaves can be evaluated first.
2) Combining adjacent AND or OR operations such that each path from the root
to a leaf encounters a strictly alternating pattern of AND and OR
operations. So [A|B]|[C|D+[[E|F]|G] becomes A|B|C|[D+[E|F|G]].

I measured the effect while the Videos window of the default skin was open
(but idle) on a Raspberry Pi, and this reduced the CPU usage by 2.8% from
41.9% to 39.1%:

Before After
Mean StdDev Mean StdDev Confidence Change
IdleCPU% 41.9 0.5 39.1 0.9 100.0% +7.0%