The main performance issue with this module is the time spent in pointer lookups in the main memory table every time a pointer is deallocated. A linear search (as implemented in xmemory until version 2.0) is likely to slow the module down too much. Binary searches or equivalent algorithms would unfortunately require the memory table to be sorted by increasing or decreasing pointer values, which also involves time-consuming tasks. The solution implemented here avoids table lookups completely.
The aim is to be able to retrieve the place where a pointer is stored in the main memory table in the shortest possible time. The idea is to store the index in the main memory table together with the pointer, i.e. in the memory block itself.
When a request for an allocation of N bytes is received, the allocator tries to allocate N bytes plus the size for two integers. If the allocation succeeds, the first extra int is set to a magic number, the pointer is added to the global memory table and the pointer index in this table is stored in the second extra int allocated in the block.
This is illustrated here:
The trick of allocating a little bit more memory than requested to store extra information is not completely safe. If a normal pointer (one that does not contain these extra informations) is passed to the deallocator, the module may be unlucky enough to encounter the magic number and believe the following int is an index. This is covered by extra tests to ensure that if the deallocation is not consistent with the table, a linear search is launched anyway.
This memory marking can unfortunately not be used for VM files or mapped input files, but this kind of memory involves slow disk accesses anyway so a linear table search is not likely to be noticed.