Trotting Forward

I am in vacation in Brazil, mostly in an apartment building facing the ocean, but I had little chance to enjoy the water so far. There are several reasons for this, the most important being that Helena was sick the past week and still receives antibiotics. It is also raining a lot and is somewhat cold (24 °C) for my taste.
But I have the nights for creative work, so I picked up my recent idea and started fleshing out the design.
I succeeded in writing a QuickCheck generator for randomly creating Insert/Remove sequences steering the lifetime of a Value's def/use chain. I am able to update a given chain according to a history and check that it has still consistently set up waymarks that lead back to the Value.

I am pretty happy with the results so far.

Now it is time to enter the second phase and proactively optimize worn-off waymarks. As discussed in the other blog post the stretchy/shrinky nature of def/use chains leads to deterioration of the waymarks because Stop marks may be punched into the valid (fixed-length) clusters of Zeros/Ones. This happens at Insert events. On the other hand, Remove events may reduce clusters, thus invalidating them. So it is important to refresh the waymarks when longer islands of invalid marks are encountered. The twist is to retain O(1) complexity, which is not too challenging, but given the volatility of the chain some cleverness is needed.

I have a smallish plan how to do it: Since I expect that the volatility mostly occurs at the head of the chain (short-lived Use object getting inserted and soon removed), I intend to adjust the waymarks as far to the end as possible. So I have to keep a pointer to the start to invalid cluster immediately preceding a found valid cluster (or FullStop) and refresh the waymarks if there are enough elements present to form a valid cluster. Alternatively I could use the Prev members to walk backwards (in the C++ implementation, since these do not appear in Haskell).

But I expect that only a nice histogram of a usage statistics will help to find the optimal strategy anyway.