Fix list-difference swap w/ minimum added bytes

[luwes]

Pretty impressed with how this script performs only the swapping at the moment requires way more extra operations than is needed.

Would be nice to see this fixed with minimum size added.

[luwes]

Snabbdom is pretty much this but it's still quite a bit bigger

[blankhart]

I think the fix is quite small. A swap entails moving one element right and moving another element left. Each element is in the old and new list.

When a swapped element is encountered as you crawl forward in each list, it's not clear where to put the old item at the time you run into it. It has to move right, but you don't know what the rest of the list looks like yet. The new item goes to the current slot.

The current list-difference throws up its hands and stalls on its march through the old list until the element at that counter is encountered in the new list. As a result, it fails to spot that almost all the rest of each list is aligned.

Essentially, the algorithm moves almost every other new element left until it figures out the correct spot for one moving right (which in these benchmarks occurs at the end). At that point though it's not processed as a move right - it just recovers the alignment, controlling for intermediate elements that now show up as null because they moved left.

But you shouldn't have to decide where to put the old list item when you first encounter the swap because you know you will encounter it again when you come across it in the new list. Since you know it has moved right, there is no reason to keep your finger on it in the old list. You can skip it and move it right later once you know where it goes.

        // Element is in both lists, it has been moved
        parent.insertBefore(
          get(a[wantedElmInOld], 1),
          get(a[i], 0) || before
        );
        a[wantedElmInOld] = null;
        if (wantedElmInOld > i) i++; // the only addition
        j++; 

[blankhart]

Although it would add code there actually may be an optimization here which I will describe untested because I am in a long line at the supermarket and it's on my mind.

I suspect this change is still doing too much work in the special case of swapping adjacent nodes because it would process two moves, but in that situation you can get away with only one. After the move left, the old node is already in the right place. So really the test should be whether wantedElmInOld > i + 1.

This case isn't covered by the current benchmarks but could be by, e.g., swapping all odd nodes with the succeeding even node.

It may seem too isolated to be important on its own, but may crop up quite a bit in say the shuffle benchmark if it is generalized to account for the case where the nodes aren't adjacent in the old list, but are adjacent in the mutating child list at the time they are processed due to intervening moves left.

The way to detect this would be to add a guard to the condition to ensure that i isn't incremented if every node between i and wantedElmInOld is null.

[luwes]

thanks @blankhart, this super useful. I updated the script with your edits. I'm leaning to using list-difference for the full sinuous/map since it's so small and fast enough. really awesome