| Title | MPS slows down considerably when arena is extended |
| Status | closed |
| Priority | essential |
| Assigned user | Gareth Rees |
| Organization | Ravenbrook |
| Description | The 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. |
| Analysis | The 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 < https://info.ravenbrook.com/mail/2012/09/16/14-15-25/0/> 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 found | manual_test |
| Evidence | Observations of CET. Need to gather during analysis. MPS strategy discussion < https://info.ravenbrook.com/mail/2014/05/15/19-19-13/0/>[1] < http://www.ravenbrook.com/project/mps/master/code/trace.c>[2] < https://info.ravenbrook.com/mail/2014/05/17/16-45-11/0/>[3] < https://info.ravenbrook.com/mail/2014/05/19/13-46-13/0/> |
| Observed in | 1.111.0 |
| Created by | Richard Brooksby |
| Created on | 2013-07-10 15:03:17 |
| Last modified by | Gareth Rees |
| Last modified on | 2014-06-13 14:31:31 |
| History | 2013-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. |