Preprocessor_Hash: use child arrays instead of linked lists
authorTim Starling <tstarling@wikimedia.org>
Mon, 18 Jul 2016 02:05:13 +0000 (12:05 +1000)
committerOri.livneh <ori@wikimedia.org>
Fri, 22 Jul 2016 05:25:11 +0000 (05:25 +0000)
commitb2f7bb4d76ba29263c9edff1a21807ef7ac917a1
tree7fbba87efdb810787666fad604d3d42559b53849
parent3e433dd09d5f65edc281c140fcd9a4cc056d1d16
Preprocessor_Hash: use child arrays instead of linked lists

The singly-linked list data structure of Preprocessor_Hash was causing
stack exhaustion due to the need for a recursion depth proportional to
the number of children of a given PPNode, in serialize() and on
object destruction. So, switch to array-based storage. PPNode_* becomes
a temporary proxy around the underlying storage, which avoids circular
references and keeps the storage very compact. Preprocessor_DOM uses
similar temporary PPNode objects, so the fact that

  $node->getFirstChild() !== $node->getFirstChild()

should not cause any new problems.

* Increment cache version
* Use JSON serialization of the store array instead of serialize(),
  since JSON is more compact, even after gzipping.
* For efficiency, make $accum a plain array, and use it as an array
  where possible, instead of using helper functions.

Performance and memory usage for typical input are slightly improved:
something like 4% faster for the whole parse, and 20% less memory for
the tree.

Bug: T73486
Change-Id: I0d6c162b790d6dc1ddb0352aba6e4753854f4c56
autoload.php
includes/parser/Preprocessor_Hash.php