In #444 (and #697 ), hash collisions within the unique node table are placed in a linear bucket. Yet, there are several places where we could put it in this bucket.
One could implement each of the above as separate policies (compile-time strategies) which are then provided as part of the type of the node table.
In #444 (and #697 ), hash collisions within the unique node table are placed in a linear bucket. Yet, there are several places where we could put it in this bucket.
At the start?
This is what BuDDy does. The code is also simple and it might prove useful, as the node may be needed soon again.
At the end?
After having checked the entire next chain, we already hold onto the last node. Hence, we don't incur another cache-miss by making a new look-up on the head of the chain. This also leaves long-lived nodes early in the bucket.
Maintain a sorting based on the other child?
The bucket ordering has one child fixed deterministically. Hence, we can keep the list sorted based on the other child. This ensures the node has a deterministic(ish) place in the bucket.
Maintain a sorting based on the parent node's table index?
This would improve cache-locality, since one only jumps forwards with respect to the addresses. Furthermore, one can potentially stop early when looking through the entire bucket.
One could implement each of the above as separate policies (compile-time strategies) which are then provided as part of the type of the node table.