Logarithmically-Spaced Snapshots

When making a series of updates to something, you may wish to also retain a series of snapshots in between updates. For example, you may want to track version history for edits to a document. With limited storage space available, you cannot have a snapshot between every update. You would prefer to have a higher density of recent snapshots and a lower density of long-ago snapshots because it's typically more important to have higher granularity for more recent snapshots.

This algorithm is a simple way to keep a set of snapshots logarithmically-spaced back in history. It only ever keeps around roughly 2 log2(n) snapshots for n updates, doesn't require any complex bookkeeping, and runs in O(1) time per update step.

The algorithm: After each step, add a new snapshot number n and delete the existing snapshot number n - (firstZeroBit(n) << d) where firstZeroBit(x) returns the value of the least significant zero bit of x. The value d is a customizable shift that determines the density of snapshots. It can be set to any positive integer but has been set to 2 for the visualization below. Here is a possible implementation of firstZeroBit:

function firstZeroBit(x) {
  let bit = 1
  while (bit && (x & bit) !== 0)
    bit <<= 1
  return bit
}

Here's a second possible (although less understandable) implementation of firstZeroBit that uses bit tricks and is equivalent to the first:

function firstZeroBit(x) {
  return (x + 1) & ~x
}

The visualization below has one row for each step. Each successive row gains an additional column on the end to represent a new snapshot with the latest edits of the document. A given step has a snapshot when there is a solid square present for that step, and no longer has a snapshot when there is only a dot present for that step. The red-outlined squares represent snapshot deletes. At most one snapshot is deleted at each step. The number for each row is the number of snapshots retained (i.e. the number of remaining snapshots in that row), which is logarithmic in the number of steps.

Density: d = 2