MPS issue job003953

TitleDefinalization doesn't scale
Assigned userRichard Brooksby
Descriptionmps_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.
AnalysisThere'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 foundunknown
Introduced in1.100.0
Created byRichard Brooksby
Created on2016-01-20 11:37:37
Last modified byGareth Rees
Last modified on2018-07-15 18:38:45
History2016-01-20 RB Created.