Skip to content

Use intrusive deques for RgObj movelists.

Rika requested to merge runewalsh/source:intrusive_deque into main

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, recordish 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, TLinkedLists allocated by TRgObj are often just as numerous as TMoveInses, so their complete embedding into a TRgObj is not a joke either.

Edited by Rika

Merge request reports

Loading