Such a simple and efficient approach. Just use a history list of WeakReference to previous values. Remember, the head of the list is a strong-reference, so the current value will always be in memory. We are only talking about the history.
You need to make sure that you retry any transaction when you can't find enough history, but you have to do this in most other solutions anyway.
Between garbage collection (GC) cycles, your history list will grow vey long until something triggers another GC. So you will have lots of history in memory and should not expect any transaction that started after the GC to have a problem getting the correct snapshot value from history. Then at around the time of GC, some transactions may have to retry, but only if they need history values and not the latest value.
This is really nice on the GC as it can just forget all the history (that isn't being used by a transaction that has a strong-reference to the value) and you end up with lots of free memory again. Compare this to holding a buffer-per-Ref of old values, the GC has to look through all those buffers and then copy the values etc... before it can complete. More work for the GC to end up with less free memory.
If you know you have a thread that runs long-running transactions, then you can do a System.gc() to try to force a GC so your long-running transaction will have a good chance of completing before the next GC runs.
Interestingly, if you have to retry a transaction because you could not find enough history, then you know a GC has occurred after you started the transaction, so if you retry immediately without waiting, you are likely to have started just after a GC anyway. Nice... So maybe forcing a System.gc() isn't much of an advantage after all.
For some reason it has taken a long time for me to warm to this idea. Not having strong references to history values just seems wrong. But the more I think about it and the improvement in STM performance I see, the happier I am. Such a simple idea, almost no code and letting the GC do all the work.
The issue is whether future GC implementations will play nicely with this idea or whether they are likely to throw out history data more often. You may have to choose a particular GC implementation or set some options to improve performance.
Interestingly, you could still use this approach with existing buffer-per-Ref type ideas. You just add WeakReference pointing to the previous value - like we described above - then you use your existing buffer approach as normal. When you get to the end of the buffer and you haven't found the value, you start following the WeakReference pointers. It might be simpler to just follow the WeakReference pointers from the start - and maintaining the buffer when new values are added to keep your strong references to the history values. The result is you get another chance at getting more history just by adding a WeakReference to each of your value elements.
Ideally I'd like to do a hybrid solution. You just use the basic WeakReference history list for all your transactions. But if you get a transaction that has retried n times due to lack of history, you dynamically switch to a different approach for a while. Maybe something as simple as blocking other transactions until this troublesome transaction completes. But more probably, a buffer-based approach - probably the global STM buffer approach described in my previous post - or set up large per-Ref buffers. Then some time after that transaction has completed, you can switch back to the faster approach.
The blocking other transaction approach will work fine since it will only want to read the Ref.head and GC will not be an issue as no other transaction will be running. It also means that a transaction will never fail due issues like never being able to commit successfully or not being able to get enough Ref history. It would mean that the Ref's history management code will remain very simple and it will ensure that a transaction can read/write as many Refs as it wants because the fallback for this approach is to grant exclusive access to the transaction. It will mean a period of time where other transactions have to stop, but it is not likely you will get this type of transaction often I guess. If you do then you will have other performance issues with your system anyway.
OK, a 3 stage approach. The pure WeakReference approach. Then if it keeps failing, global buffer approach so we can still have other transactions running. Then if the transaction keeps on failing, just give it exclusive access so it can complete. Then back to the pure WeakReference approach again.
