| Title | Definalization doesn't scale |
| Status | open |
| Priority | optional |
| Assigned user | Richard Brooksby |
| Organization | Ravenbrook |
| Description | mps_definalize (internally MRGDeregister) loops over all finalizable objects in the heap, and so using it could accidentally be disastrous for performance, for example it could easily turn an O(n) algorithm into a O(n^2) algorithm. |
| Analysis | There's currently no quicker way to find the guardian of an object from a reference to the object. We could return a handle when finalizing, but this would just put a burden on the client. Instead, I suggest turning the linked-list of guardians into a hash table whose key *is* the final reference to the object. This would need to be location-dependent, but a rehash would only occur on a miss during definalize, so there would be little extra overhead. The first definalize might trigger a O(n) rehash, but if the client definalizes many objects together the complexity will be reduced. When this job is resolved, be sure to back out changelist 187123. Consider also fixing job004095 at the same time. |
| How found | unknown |
| Evidence | <https://info.ravenbrook.com/mail/2016/01/19/17-05-55/0/> |
| Introduced in | 1.100.0 |
| Created by | Richard Brooksby |
| Created on | 2016-01-20 11:37:37 |
| Last modified by | Gareth Rees |
| Last modified on | 2018-07-15 18:38:45 |
| History | 2016-01-20 RB Created. |