So, they've reimplemented reversible debugging by a process of replaying from the start, with some finesse to ensure determinism in the multi-threaded case. Code seems to be here: https://github.com/fred-dbg/fred
It's worth noting that binary search is not necessarily optimal for a 'going back to the start' search. To see that,
assume the cost of an observation is zero: then linear search is clearly optimal. If it is infinite, then binary search is optimal. It it's something in between, then some pivot less than n/2 is the correct choice.
I worked this out once, and came up with the solution that the pivot should satisfy the equation:
It's worth noting that binary search is not necessarily optimal for a 'going back to the start' search. To see that, assume the cost of an observation is zero: then linear search is clearly optimal. If it is infinite, then binary search is optimal. It it's something in between, then some pivot less than n/2 is the correct choice.
I worked this out once, and came up with the solution that the pivot should satisfy the equation:
1+(start_time+observation_cost)/length = log(pivot/length)/log(1-pivot/length).
(except that sometimes a pivot of 1 step is more efficient, because of a special case). But I have lost the derivation of this.