HomePhabricator

Some Balancer improvements for performance and compatibility
5726c9ceb064Unpublished

Authored by tstarling on Jul 4 2016, 5:15 AM.

Unpublished Commit · Learn More

Publishing Disabled: All publishing is disabled for this repository.

Description

Some Balancer improvements for performance and compatibility

  • Use a doubly-linked list for the AFE list, instead of an array, allowing efficient insertion and removal from the middle, and trivial O(1) lookup of existing elements.
  • Use a hashtable of singly-linked lists for storing Noah's Ark buckets, instead of iterating through the entire AFE list on every push.
  • Store attributes in an array instead of serializing them in the tokenizer. This allows us to avoid sorting them in the output. For the Noah's Ark clause, the array is copied and then sorted on demand.
  • XHTML-style serialization with self-closing tags.
  • Clear the AFE list in stopParsing(), otherwise all the BalanceElement objects are kept alive until after serialization, thus using O(N^2) memory (in stack depth N) since the full serialization is stored at each stack level.

Change-Id: I517129c0658f03eb2ddee61fdf33ffe6fbd48509

Details

Committed
tstarlingJul 12 2016, 4:18 AM
Parents
rMWce081a3d7b5b: Hook up Balancer as a Tidy implementation.
Branches
Unknown
Tags
Unknown
References
refs/changes/29/297229/8
ChangeId
I517129c0658f03eb2ddee61fdf33ffe6fbd48509