Notes on Fractional Indexing

What is it

The need for what is called Fractional Indexing arises if a list of items can be arbitrarily re-ordered and we want an item to have a key representing its position in the order.

The canonical example is a todo-list where a user may change the order (priority) of items at whim.

We start with giving each item a number as a key and use the following algorithm for a new or moved item:

1. prepending: new key = first key in list - 1
2. inserting between key a and key b: new key = (a + b) / 2
3. appending: new key = last key in list + 1

A longer discussion and a description of an algorithm can be found here.

An Unavoidable Problem

Step two has a problem which cannot be avoided: each step moves the least significant bit to the right by one. As an example, consider repeatedly inserting between the first and second element of a list which starts with the keys 5 and 7. We get for the first two keys:

``` 5 7 -> 5 6 -> 5 5+1/2 -> 5 5+1/4 -> 5 5+1/8 ...

``` The $1/{2^N}$ is coded by a 1-bit which moves ever further to the right.

If the insert position degenerates to be always the same for some unforseeable reason, you need n bits of precision after n insertions. Double values provided by most programming languages have a 52 bit mantissa, which means you get rounding errors the latest after 52 insertions. Which is not a lot.

Using infinite precision decimals does not make it much better because the key requires at least n/8 bytes after n insertions. After 1024 insertions which, by bad luck, happen on the same position, the key has a length of at least 128 bytes.

Can this be solved?

There is no remedy if the general case is considered. If users work with a list where the creation of each single item is a manual step, it is hard to imagine they have 1000 insertions at the same place. Yet if it is a todo-list maintained over a few years, the 52 bit mantissa of a double value may actually become a problem.

And it is a problem of the ugly kind. The program may actually work perfectly for months, even years. And when it starts to fail, the failure is subtle as items may or may not be sorted in the wrong place, depending on the "random" order how the comparison of identical keys spits them out.

Conclusion

I spend three days from noticing that I want a manually maintained sort key which does not require re-numbering whenever an item gets inserted between two others, over learning that it is called fractional indexing, reading about it, implementing it myself for the general case, to seeing live from test output how fast degenerate insertion gets bad to writing this piece, finally accepting defeat.

My planned pragmatic solution

1. use just integer keys
2. when appending or prepending, space them by N
3. when inserting, use (a+b)/2 until the result becomes fractional, then re-number with keys spaced by N

The original reason I wanted to avoid re-numbering is that it causes a brief but noticable data-reload in the app I am writing.

How to chose N? Using N=1 means any insert operation has to renumber all following items, the case I wanted to avoid in the first place. The larger the N gets, the longer it takes between re-numbering with pros and cons.

• small N: users may have that small nuisance more often, but may just get used to it
• large N: users will see the reload seldomly and may be irritated each time. Also, if it happens only after a few months, any subtle bug it brings along will be terribly ugly to pin down.

Hmmm?

Ignoring the potential problem

The figma blog somewhat casually brushes over the index length problem saying:

The first drawback (index length) isn’t a concern for us since we don’t need to order huge numbers of elements. The number of reordering operations is bounded by user activity in practice, and normal usage patterns never generate prohibitively-large index lengths.

While I tend to agree, this somewhat reminds me of the year 2000 problem or the year 2038 problem. In my case, the app shall operate on the same data structure potentially for years, and while arbitrary re-ordering is expected, new items tend to be added to the front, which will certainly grow the keys near the front of the list. Adding only a handful of items per day to the front over a year makes already 1825 insertions or, worst case over 200 bytes for the key.

Given modern hardware, these will be handled without problems for a long some time, until it suddenly wrecks somewhere. For my little app, used by only few people, this will not be the end of the world, but it is the general attitude towards good software which is not mine. I wish there were an efficient solution where I would not need to rely on the specific circumstances of the typical use of the app for it not to crash.

When is an Exception an Exception

Recently I said that checked exceptions or not really exceptional. Here is a good example about the tradeoffs.

Consider building a directed acyclic graph (DAG), a dependency graph for example. The Node class has a method to add a child:

class Node {
  public void addChild(Node child) { ... }
}

We must make sure that the graph stays acyclic. So the child node may not be an ancestor of the current node. We add a check to addChild.

class Node {
  public void addChild(Node child) {
    if (child.hasDescendant(this)) {
      /* NOT SUITABLE */
    }
  }
  public boolean hasDescendant(Node other) { ... }
}

What shall we do at NOT SUITABLE? We have three options:

1. Throw an (unchecked) exception (Java, TypeScript, Python) or panic (Rust).
2. Return a special value, say ISPARENT, to tell the caller that the operation is not possible.
3. As a middle ground, in Java we can throw a checked exception.

The arguments:

An unchecked exception indicates a programming error, and there are two diferent situations:

• In the middle of an algorithm which guarantees that no loops are generated, an unchecked exception is just right, basically as an additional guard that we don't fool ourselves.

• If addChild() is an API method, used as part of a user action, it is normal business to get a node which can not be made a child.

  We could require the caller to first call hasDescendant() explicitly, which again would turn the NOT SUITABLE part into a programming error, but addChild() has to call it again to be sure. How silly. As is often the case, first verifying that an operation is possible is the same effort as just running it, possibly being told it cannot be done.

So assume we are in the API situation, not in the algorithm-guarantees-non-fuckup situation.

Throwing a checked exception would be a strong hint that the operation may not succeed on circumstances. Yet, as I argued in the article linked above: this is not exceptional. It is normal business?

Which leads us to the special-value return. I started to call those an Explainer. It encodes why the operation was not possible, with as much detail as needed. Examples:

• For a Map.get(key) a null return is a good explainer with as enought detail, telling us "no value for 'key'". More is not needed.
• In the example above, we could use OK, NOOP, ISPARENT for the cases "child was added", "child was already added" and "given node is an ancestor so not a suitable child".
• Parsing a string which does not adhere to the necessary structure: the explainer may have details about where the string's structure does not fit and how it deviates.

Did you note how I tried above to not say that an operation "failed". Not easy after being brain-washed for 40 years.😀

In languages with union types, like Python and TypeScript, it is slightly easier to return either a result or an Explainer. In Java it would be some Either<Stuff, Explainer> that needs to be defined.

Is there a case for checked exceptions still? The longer I ponder it the thinner the case gets. It seems nice to ignore the explainer (exception) and let it bubble up. Lets compare:

public Either<Result, Explainer> doStuff() {
  Either<String, Explainer> s = compute(...);
  if (s.isRight()) {
    return Either.ofRight(s.right());
  }
  ...
}

with

public Result doStuff() throws Explainer {  
  String s = compute(...);
  ...
}

The latter is obviously more conscise in Java, though the main eye-strainer for me is more the new Either() necessary to match the result type. In a language with union types, like TypeScript, this is just:

public doStuff(): Result | Explainer {
  const s = compute(...);
  if (s instanceof Explainer) {
    return s;
  }
  ... move on with s
}

The advantage of exception forwarding amounts to the avoidance of a mere if/return combo. Yes, you say, but what if there are four for five of those in a row? Then auto-bubbling looks much better — hmm, until you have to debug at what line exactly in the 😠 code the exception is raised.

What if we made explicit forwarding simpler. If we have union types, like in Python and TypeScript, imagine a syntax like:

const text: string = compute(...) or return;

The compiler would unpack this into

const text: string | Explainer = compute(...);
if (text instanceof Explainer) {
  return text;
}

Easy forwarding, explainers need not come along as exceptions and it is obvious were the code did the short turn, eventually. I am dreaming.

Moving Clock in Special Relativity

What happens to a clock which is moved at some speed for some time. According to special relativity it runs slower on the move. Lets get a bit of an intuitive understanding of this.

Moving a light clock from here to there

I described the light clock earlier and showed how it runs slower when it is moving. Now, what if we have two identical light clocks, synchronized at some position. Then we move one by a distance $d$ and then stop again. Does it now

• run slower,
• lag
• and how much
• and can we actually measure this?

Consider the light speeding at $c$ along the light clock of length $l$ on the left of the diagram between $A$ and $B$.

A second, identical light clock is moved along the distance $d$. For simplicity, assume initially that we move the second clock with a speed $v$ such that it ticks exactly $n/2$ times during the move. A tick is one complete cycle of the clock where the light beam runs from $A$ to $B$ and back to $A$.

What is the speed component $v_l$ of the moving clock along $l$, the vertical axis? We have the speed $c$ along the diagonal $a$ and we have defined to move the clock with $v$ along $b$. Consider the time $T$ to be the time it takes along $a$, then $a/T = c$, $b/T = v$ and $l/T = v_l$. We also have $a^2 = b^2 + l^2$. Divide by $T$ to get $c^2 = v^2 + v_l^2$ or $v_l = \sqrt{c^2 - v^2}$.

How often does the moving clock tick until it reaches the end of the move? Since it moves with $v$ along $d$, the time is $T_d = d/v$. During this time, the total vertical movement of the light beam is $T_d v_l = v_l d/v$. Divide by $2l$ to get the count of the moving clock as $N_d = v_l d/2lv$.

Similarly the count for the stationary clock is $N_0 = cT_d/2l = cd/2lv$. The lag factor $L$ as the factor of how the moving clock ticks slower is therefore $$L=N_d/N_0 = v_l/c = \sqrt{c^2 - v^2}/c = \sqrt{1 - (v/c)^2}\,.$$ Should we not have found the Lorentz factor, not its inverse? No, it is just right, since the Lorentz factor relates the time between two ticks of the moving clock and the stationary. Since we count the ticks, we get its inverse.

Synchronized Clocks

What does this mean for clock synchronization: If I bring a well synchronized clock from here to there, I cannot avoid having the lag factor $L=\sqrt{1-(v/c)^2}$. But look, if the speed $v$ with which we move the clock is (nearly) zero, $L$ is (nearly) $1$, so there is no lag for very slow movement.

But how bad does it get? Can we measure the lag? Suppose we move a clock with an airplane and, for simplicity, assume it can do $\unit{1000}{km/h}$. We then have $$v/c = 1000\cdot1000/3600/299792458 \approx 9.27\cdot10^{-7}\,,$$ for a lag factor of $$L \approx 1-\sqrt{1-(9.27\cdot10^{-7})^2} = 4.3\cdot10^{-13}\,.$$

Now suppose we fly the clock $\unit{1000}{km}$ away, meaning the time of movement is one hour or $\unit{3600}{s}$. After the move, the moved clock lags by $\unit{3600}{s}\cdot 4.3\cdot10^{-13} \approx 1.5\cdot10^{-9}$ or $\unit{1.5}{ns}$.

Once we stop moving the clock, it runs as fast as before, but it is no longer synchronized: it runs with a lag which depends on the velocity of the move and the time it took — or the distance. Here you can experiment with different values.