Add $index() to the context for each item

[brianmhunt]

The current implementation looks to be either O(2^n) or O(n^3) (depending on what you are measuring). In either case the default foreach is practically unusable for larger lists (> 3000 items).

It looks like the fastest we can get an automatically updated $index in the average case is O(n) (more precisely, O(n/2) for random indexes). My thinking is after the processQueue finishes the changes to call a function something like this:

function recalculateIndexes(fromIndex) {
  for (var i = fromIndex, j = this.startNodesList.length; i < j; ++i) {
    ko.contextFor(this.startNodesList[i]).index(i);
    // if contextFor is costly we can keep a list of $contexts parallel to startNodesList.
  } 
}

where each context has a plain observable index, and fromIndex is the lowest index that has been added or deleted in the processQueue. It feel like it would be desperately difficult to improve the performance of this while maintaining synchronicity with the rendering and consistency, but I would welcome being shown otherwise.

I mulled a dependency chain that automatically updated (e.g. each index be computed from a prior) but in the simple cases that leads to either challenges with performance (using a pureComputed) or memory management (using a `computed), and generally incurs a substantial overhead and adds lots of needless complexity.

The case where the dependency chain is substantially faster is when there are no subscribers to the $index properties and so no calculations occur. We could add a flag useIndexes or monitor the subscriber count of the $index properties and only run the index recalculation when there are subscribers.

I believe that without the $index recalculation, our adds and deletes shall be O(1), so it is worth considering how we might (or might not) include an O(n) $index.

[AdamWillden]

See this: http://jsbin.com/tifadi/1 compared with the original http://jsbin.com/dakihezega/2 with regards to the referenced commit above.

I did a long post to describe what I was going to attempt following my previous attempt at tracking indexes with the arrayChange event but my laptop crashed and I lost everything.

[AdamWillden]

Sorry I keep doing commits without my user information and it bugs me so I recommitted and did a force push!

As in the commit message:

It works but performance is lacking when deleting (and I assume adding) items near the beginning of the array due to updating every following index.

Also it is not thoroughly tested although seems to work and passes tests.

It leaves me questioning how the current foreach binding keeps track of item indexes

[brianmhunt]

Thanks @AdamWillden - Sorry you lost your post; I see what you're doing here, and I think it's the right idea.

The performance here could be substantially improved by taking the index update outside the this.changeQueue loop. As it stands, unless I am confused, every successive index is being updated with every add to the loop here i.e. the performance is O(n * n). What we want to do is run through the changeQueue, then update every index from the lowest one changed onwards. e.g.

Around https://github.com/AdamWillden/knockout-fast-foreach/blob/424b6fda08712924ac2dbc2039fbd75bc2cb5a97/index.js#L133

  var lowestUpdatedIndex = this.stateItemList.length;
  ko.utils.arrayForEach(this.changeQueue, function (changeItem) {
    self[changeItem.status](changeItem.index, changeItem.value);
    lowestUpdatedIndex = Math.min(changeItem.index, lowestUpdatedIndex);
  });

  for (var listLen = this.stateItemList.length; lowestUpdatedIndex < listLen; lowestUpdatedIndex++) {
     this.stateItemList[lowestUpdatedIndex].$index(lowestUpdatedIndex);
  }

At least, I think that's roughly the idea of an O(n) performance update to the indexes i.e. for every batch of changes each $index variable is touched at-most once.

The best performance for index calculation is always going to be an issue (O(n) vs O(1)) for deletes & adds near the beginning. When the $index variable is being used, this is unavoidable - unless we arbitrarily up the buffer period/setTimeout; perhaps we may want to expose to the user the option to disable/re-enable $index updating or manual updating, but that might add substantial complexity.

That said, I was hoping there might be a way to make indexes lazy i.e. perform the updates to the indexes only when something is subscribed to a $index . That way if a user wants to use $index it will work as expected, but otherwise there is the massive performance benefit of not re-calculating indexes with every batch of changes.

I thought about making this an option e.g. buildIndexes: [true|false] but the user experience with that is worse and there is the trade-off of not being compatible, out of the box, with the native foreach (or alternatively being compatible with native foreach but not having all the potential performance benefits).

It'd be great to have some tests of this $index variable.

Cheers

[AdamWillden]

I had passed comment on your idea regarding adding a flag/option in my lost post. I appreciate the desire to have it 100% compatible but I also think this is a different binding and an opportunity to 'do better'. So long as the users have the ability to enable the same functionality. Depends on the final goal. Would you hope to port this code into the core if it were a straight swap?

I don't know why I didn't consider just recalculating using a lowestUpdatedIndex technique. That seems easier!

I tried looking at how the foreach binding updates the indexes but if I'm correct (hence the purpose of this fastForEach) the old foreach just re-renders everything when the array changes?

[AdamWillden]

We shouldn't even need to do a Math.min(changeItem.index, lowestUpdatedIndex); we could just use added[0].index and deleted[0].index and compare those. Also if there are consecutive arrayChange events before the queue is processed we can reduce $index processing further.

[AdamWillden]

Oh sorry now I've re-read your proposal I see you're already suggesting that to some degree. I'm catching up slowly 👍

[brianmhunt]

Thanks Adam!

This probably won't get merged into KO proper until this works with IE6 (for the 3.x series), or in a future KO release when IE6 (and maybe IE7) support is dropped. I speculate that'll probably be KO 4.x+. One of the key reasons for KO's popularity on some really big sites is the breadth of browser support, so there is a reluctance to deprecate. That said, there are a lot of issues filed about the current foreach implementation, and this solves some of them, so I think this might be a contender for integration into the core at some point. For that reason, I would like to keep that possibility alive by sticking — as much as possible — to the existing API.

Incidentally, this is where the builtin $index is defined:

https://github.com/knockout/knockout/blob/b6b3a1132fa142539279bcaa698fcc90c6bafdd6/src/templating/templating.js#L176

I believe the builtin foreach re-renders everything on changes (as do all the template bindings, including with, if, and ifnot). While functionally pretty convenient, this can be a big performance gotcha.

[AdamWillden]

Thanks for sharing your vision for this binding.

I should add that I don't personally need this $index functionality. I just thought the problem was an interesting one and that I'd edge it forward a little while sitting in a hotel room! However I will look into making the described changes when I next need a break from what I should be progressing on. Fixing #15 is actually much more important to me right now for my work but I wouldn't know where to begin.

I'll try and get some tests done for this $index when I do come back and make progress.

[cervengoc]

Just a thought to add here: In 99% of my development I find myself using $index observable for 3 use cases: checking it for 0; checking it for [length-1]; checking it for odd/even. To go even further, as I can emember I've never been in a situation where I needed the $index for other use case, doesn't seem to be reasonable to check it for being equal to, let's say 541.

Probably we could offer such kind of context observables like $isFirst, $isLast, etc. Seems to be much easier and efficient to implement.

As for the standard $index feature, I can't imagine currently a more efficient way than what's described in the first post here by @brianmhunt. If there is any, it most likely would add a lot of complexity.

[brianmhunt]

Great thought, @cervengoc – #24

[cervengoc]

I was thinking a bit more about this topic. What exactly is expensive about updating observables? I mean I don't think that O(n) should matter. There is no rerendering, only if a developer binds $index in some fancy way. The most expensive seems to be the retrieval of the context, but that can be worked around by holding all $index observables in an array similar to lastNodesList, and put only a reference to these observables in each context on addition. This way the indexes could be maintained in that array (inserting new ones, updating them, etc.) I think that observables are assigned by reference, but correct me if I'm wrong.

I hope it makes any sense, sorry for just flushing my raw thoughts without too much precision :)

[brianmhunt]

Thanks @cervengoc

I am not averse to an O(n) implementation of $index, and would accept a PR for it, provided there is an option to disable it (for folks seriously concerned about performance on low powered devices).

One option that could significantly improve performance is to debounce the index recalculation.

[cervengoc]

The best way would be to keep it silent by detecting if there is any subscription to it. I will have a look at it in the near future.

[brianmhunt]

Thanks @cervengoc

Having previously given it a bit of thought, I believe a "pull" model where dependencies are silent until subscribed to may be more complex than "pushing" the index updates out on changes. That said I'm open! 😁

[4ver]

Is $index() supposed to be returning undefined when called in the template?

Here's an edited version of your jsbin in the README.md: http://jsbin.com/tuzuwepuya/edit?html,js,output

[brianmhunt]

Thanks @4ver – good catch. The problem occurs when the last node of a template is a text node, which does not have $context. Not strictly a problem with $index, but obviously that's where it'll exhibit. Fixing now & will report back. Cheers.

[4ver]

Great! Thanks @brianmhunt

[brianmhunt]

@4ver fixed in 0.5.2 🎉

Thanks so much for taking the time to report the issue!