Possible further improvements on batch addition

[cervengoc]

While I was debugging, I've noticed that in many cases the batch addition works very well, but there are a few use cases when it's not doing the job right.

The problem shows up when completely changing the array contents. At such type of actions ko sends the change notifications in an order for example like this: deleted 0, added 0, deleted 1, added 1, etc. So this way the current implementation won't notice that actually these additions can be grouped together also.

My idea is to modify the method isAdditionAdjacentToLast in the way that it would not only check the last two changes, but the last three, and in case when the prelast is a deletion, and before it tthere is an addition with adjacent index, it would treat them adjacent too. Then I think we still should care about the order of actions, so if a batch addition is created this way, then I think it should be moved after every deletion. So this way the queue processing would transform into something like this: deleted 0, deleted 1, deleted 2, added 0 1 2 (batch).

This sounds nice, but actually I'm not entirely sure about the correctness. Could you add your thoughts? It would surely improve the performance quite much in these cases, but is it always safe? For me it looks right, but it's after midnight here and I'm losing my courageness at such time :)

Thank you

[cervengoc]

@brianmhunt I've actually fine tuned the detection of a possible batch addition according to my ideas, and at first glance it looks reliable, but I have no idea how to put together a good test for it which would cover as many scenarios as possible.

The modified code looks like this:

function isAdditionAdjacentToLast(changeIndex, arrayChanges) {
  return changeIndex > 0 &&
    changeIndex < arrayChanges.length &&
    arrayChanges[changeIndex].status === "added" &&
    ((arrayChanges[changeIndex - 1].status === "added" &&
    arrayChanges[changeIndex - 1].index === arrayChanges[changeIndex].index - 1) ||
    (changeIndex - 2 >= 0 &&
    arrayChanges[changeIndex - 1].status === "deleted" &&
    arrayChanges[changeIndex - 1].index === arrayChanges[changeIndex].index &&
    arrayChanges[changeIndex - 2].status === "added" &&
    arrayChanges[changeIndex - 2].index === arrayChanges[changeIndex].index - 1));
}

According to my experiences, it improves quite much in many scenarios, especially when one clears and refills an array, which is quite common (at least at me).

What do you think about it? Is this modification safe?

[brianmhunt]

@cervengoc lol, that'll take a bit of staring. Some good comments will undoubtedly make it clearer. I can see a few tests that might illuminate the edge cases, but it'll take me a bit to wrap my head around this.

How much of an improvement is there to the performance?

[cervengoc]

Sorry, the code is technically complex, but logically very simple:

There are two cases when an addition to index j should be treated as adjacent to the last addtion:

1. Previous modificiation is addition two, and has index j-1.
2. Previous modification is a deletion at index j AND the modification before the previous is an addition to index j-1. So this means that there is only a deletion in the middle which "doesn't count" in this sense.

Point 1 is the current implementation, and I just added Point 2 for test. I hope it will be clearer now.

[cervengoc]

It matters quite much in performance in a code like this:

observableArray.valueWillMutate();
observableArray.removeAll();
observableArray.pushAll([2,4,2,1,4,3]);
observableArray.valueHasMutated();

In this case knockout sends the modifications this way: deleted at 0, added 2 at 0, deleted at 1, added 4 at 1 etc. The improvement targets this special case. With the current implementation, the batch addition would not get applied.

I have a strong feeling that the same effect appears when using the splice method on the observable array, which is even more common.

[cervengoc]

I've added the code and an additional test (probably wasn't needed, but just for the case). Also created a pull request here https://github.com/brianmhunt/knockout-fast-foreach/pull/30, seems everythings fine, tests pass. Performance difference was noticable within my project, but didn't have time to put together a jsPerf or so for it.

[brianmhunt]

thinking

[cervengoc]

This can be closed now with #30