| Title | White segment lookup is slow |
| Status | open |
| Priority | optional |
| Assigned user | Gareth Rees |
| Organization | Ravenbrook |
| Description | The second-stage fix operation on the critical path (_mps_fix2 in trace.c [1]) need to find out if the address it is fixing belongs to a segment that is white for some trace. The sequence of operations to establish this is unnecessarily slow in the general case: 1. Call ChunkOfAddr, which iterates over the chunkRing to discover if the address belong to a chunk. If so: 2. Computes page number within the chunk and look this up in the chunk's allocTable to see if the page is allocated. If it is: 3. See if the tract is white for any trace. If so: 4. The segment is tract->seg. This is well-optimized code: it's mostly macroized, and there is a cache for the mostly recently examined chunk. But there is still an opportunity for a win here by having a specialized lookup. |
| Analysis | See [2] for the initial suggestion. The outline plan is as follows: 1. Create a new module that maintains a data structure mapping address to white segment. 2. When a segment is condemned in TraceAddWhite, add it to the map. 3. When a segment is no longer white for any trace in traceReclaim, remove it from the map. 4. Try alternative implementations of the lookup table (see below for ideas). Measure the result and ensure that it's an improvement. Make sure that the test is realistic. (For example, CET Office on Windows 32-bit, which we believe extends the arena a lot.) 5. There is now no longer any need for tracts to know for which traces they are white: this field can be removed, and so can TractWhite and TractSetWhite. RB did some work on this on branch/2014-02-28/white-cuckoo, using a cuckoo hash table from page to white segment [3] but there is concern that cuckoo hashing has a very bad worst case (it's not clear that it terminates). NB proposed [4] using a radix tree instead. |
| How found | manual_test |
| Evidence | Observations of CET. 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/02/27/13-46-36/0/>[3] < https://info.ravenbrook.com/mail/2014/03/01/02-37-37/0/>[4] < https://info.ravenbrook.com/mail/2014/03/05/15-40-37/0/> |
| Created by | Gareth Rees |
| Created on | 2014-05-15 18:39:57 |
| Last modified by | Gareth Rees |
| Last modified on | 2020-08-30 17:22:59 |
| History | 2014-05-15 GDR Created. |