New SMR design

So! I don’t think this idea works, because to make it work the performance would be too poor, but…

You have a main state, and a per-thread state.

Each per-thread state registers with the main state.

The main state holds a counter, the “current counter”, which begins at 0. Every time a thread adds an element to its reuse candidate list, it stores in the reuse candidate the value of the main counter, and atomically increments the main counter. (On a busy system, the contention on that counter would drive performance into the ground – however, there is a scalable counter design…)

There is another counter in the main state, the “safe counter”, which also begins at 0 – it begin safe to reuse elements up to this value.

Every time a thread exits a read section, it stores the current value of that main counter in its thread state.

When we come to check to see if we can advance the safe counter, we iterate over the thread states, looking at their counter (the value of the main state current counter when they last exited a read section), and find the lowest value of them all (ignore idle threads for a moment). We then advance the safe counter to this lowest value – i.e. this is the point after which not all threads have exited a read section, and so the reuse candidates cannot yet be reused.

To deal with idle threads, we keep a flag in the thread state, which is raised when the thread enters a read section and lowered when we check to advance the safe counter. If the flag is lowered, then the thread has been idle.

In conceptual terms, ignoring actual practial performance, the design has high fidelity with regard to knowing which elements can be reused. As each element has its own generation count, and we know to which generation count we’re safe to re-use elements, we reuse every possible element we can.

What strikes me now though is that perhaps another way is to invert the paradym; rather than assuming we can’t advance, and then checking to see how far it is safe to advance (and so having trouble with idle threads, since they are silent), what about assuming we can advance (and so idle threads naturally say the right thing), with blockers in the way for the points beyond which we cannot advance?

Have to think about this, might just be crazy in the first instance, will see.