Use intrusive deques for RgObj movelists.
This introduces a new variation of doubly-linked list, cclasses.TIntrusiveDeque
, and uses it for RgObj.TRgObj
move lists.
Has no effect on compiling webtbs/tw2242
, but speeds up compiling my application by 0.1%, stacking with !207 to 0.3% (all determine_spill_registers
run in 50 ms down from 70 ms out of 5.5 s, both merge requests subtract own 10 ms).
Now, what’s the point and why it can be useful beyond that.
cclasses.TLinkedList
forces you to have a class
inherited from cclasses.TLinkedListItem
.
First problem with this is efficiency: classes are slightly slower to create/destroy, sometimes slower to work with in general (if their instances could be embedded otherwise), and are extremely unfriendly to custom allocation strategies like using memory regions. Since TMoveIns
is so small, record
ish and numerous, it could benefit from bulk allocations one day, saving both the time on allocations and the memory on heap chunk headers and paddings.
Second problem is flexibility. You can have several intrusive collection nodes built into your object to support its simultaneous belonging to unrelated lists or other collections:
type
TMyObject = class
nodeA, nodeB: TIntrusiveDequeNode;
nodeC: TIntrusiveSearchTreeNode;
end;
var
myObj: TMyObject;
listA, listB: TIntrusiveDeque;
treeC: TIntrusiveSearchTree;
myObj := TMyObject.Create;
listA.Add(@myObj.nodeA);
listB.Add(@myObj.nodeB);
treeC.Add(@myObj.nodeC);
Assert(TMyObject(pointer(treeC.ExtractMin) - PtrUint(@TMyObject(nil).nodeC)) = myObj);
Which is of course impossible with inheritance. The only downside is recovering the original object by the innately unsafe and scary-looking subtraction of offsetof
...
Btw, TLinkedList
s allocated by TRgObj
are often just as numerous as TMoveIns
es, so their complete embedding into a TRgObj
is not a joke either.