MPS issue job003554

TitleMPS slows down considerably when arena is extended
Assigned userGareth Rees
DescriptionThe MPS was originally designed with the idea that extending the arena would be a rare event, so although it copes, performance degrades quite rapidly when it happens. But the arena is extended quite often in CET and will definitely need to be extended often on 64-bit CET, because Windows stack unwinding will limit arena chunks to 2GiB.
AnalysisThe main cause of slowdown is in looking up tracts from addresses during fix on the critical path. This works well for a single chunk, but is O(#chunks).

Tract lookup should be generalised to work well across the whole address space, not just in chunks. This would also allow the lookup and protection of roots that are not managed by the MPS. See the thread starting from <> for detailed analysis.

First, ensure that common operations don't have to iterate over the chunk ring:

1. Replace the chunkRing with a Tree of chunks.
2. RING_FOR(node, &arena->chunkRing, next) becomes a call to TreeTraverse if it wants to visit every chunk, or TreeFind if it is looking for a particular address.
3. Measure performance with many chunks.
4. Check that performance with a single chunk is unaffected. There is an opportunity for a macro version of ChunkOfAddr that checks the top node of the tree before calling TreeFind on the left or right child.
5. Be careful about deletion of chunks: not all tree traversal algorithms can cope with deleting nodes while traversing!

(RB did some work on this on branch/2014-01-22/chunk-rtree; GDR picked it up on branch/2014-05-17/chunk-tree and there are preliminary results in [2] and [3].)

Then look at job003796 and job003798.
How foundmanual_test
EvidenceObservations of CET. Need to gather during analysis.
MPS strategy discussion <>
[1] <>
[2] <>
[3] <>
Observed in1.111.0
Created byRichard Brooksby
Created on2013-07-10 15:03:17
Last modified byGareth Rees
Last modified on2014-06-13 14:31:31
History2013-07-10 RB Created.


Change Effect Date User Description
186564 closed 2014-06-13 14:31:31 Gareth Rees Merge branch/2014-05-17/chunk-tree into the master sources.
184783 open 2014-03-13 15:28:06 Richard Brooksby Merging branch/2014-01-17/cbs-tract-alloc into master.