wiki.sortByList should skip an expensive operation when able to

[Arlen22]

https://github.com/Jermolene/TiddlyWiki5/blob/e752ba7c6abcdde229258aa1562e6de518c3556e/core/modules/wiki.js#L564-L634

A discussion on Google Groups about a slow wiki led me to this line, which was the culprit for the slowdown for a tag with 36000 titles.

https://github.com/Jermolene/TiddlyWiki5/blob/e752ba7c6abcdde229258aa1562e6de518c3556e/core/modules/wiki.js#L593

I've been studying this function for a half hour, and it suddenly occurred to me that

• A: if new position is -1 then current position is useless,
• B: because right now if new position is -1, then it is set to current position
• C: immediately after that it checks if they are equal and only splices if they are not.

So, in other words, if new position was set to -1, then it will be set to current position, and therefore is equal to it, and therefore prevents a splice from happening. So we could totally optimize this if new position is still -1 after the first group of if statements and just exit the function if there is nothing instead of looking up the current position first.

if(newPos !== -1) {
  var currPos = titles.indexOf(title);
  if(currPos !== -1) {
    titles.splice(currPos, 1);
    if(newPos >= currPos) newPos--;
    titles.splice(newPos, 0, title);
  }
}

Of course, you still can't use list-before and list-after on 36000 tiddlers, but who has ever done that?

[Arlen22]

The original discussion is here.

https://groups.google.com/d/msg/tiddlywiki/U1ZKK8UIk94/_URkH-GxAwAJ

[Jermolene]

Hi @Arlen22 great stuff, thanks for tracking things down. I think it might be helpful to add some tests before we change this. I think the tests would fit best in https://github.com/Jermolene/TiddlyWiki5/blob/master/editions/test/tiddlers/tests/test-utils.js. Might you be able to put together a PR?

[pmario]

I think the main problem here is, that the tag-operator always does a .sortByList(). ... The "list-field" was introduced at the very beginning of TW development cycle, to get a predictable order for "tagged templates" used with the TW UI.

We rely on the behaviour, because it is convenient.

But I think, it could also be created like this: [tag[test]sortby[list]]

So my proposal would be to create something like a "stripped down" tag-operator, that doesn't do any sorting at all.

This xtag operator may produce unpredictable output order with different browsers, but it would create the fastest possible "speed"

[Arlen22]

@Jermolene Sorry, I don't have time right now to do a PR. As far as tests, isn't it enough to determine that the code path is identical by logical reasoning and rearrange the code accordingly? I'm not sure how to test two identical pieces of code. Here is my proposed change again, in case I somehow miscommunicated, interspersed with comments to show my thought process. Basically if newPos is -1, the expensive currPos check is not needed.

Currently:

//get the current position, which we don't yet know
var currPos = titles.indexOf(title); 
//if we have nowhere to move it ...
if(newPos === -1) { 
  //set newPos to currPos
  newPos = currPos; 
} 
//if it is actually in the list (pedantic) and actually needs to be moved ...
if(currPos >= 0 && newPos !== currPos) { 
  //move it!
  titles.splice(currPos,1); 
  if(newPos >= currPos) newPos--; 
  titles.splice(newPos,0,title); 
 } 

Changed to:

//if we have somewhere to move it ...
if(newPos !== -1) {
  //get the current position, which we don't yet know
  var currPos = titles.indexOf(title);
  //if it is currently in the list (pedantic, but appropriate to check) ...
  if(currPos !== -1) {
    //move it!
    titles.splice(currPos, 1);
    if(newPos >= currPos) newPos--;
    titles.splice(newPos, 0, title);
  }
}

[Arlen22]

@pmario I think it is very appropriate to use the sortByList function, it's just that we get bogged down if there are list-before or list-after fields on all 36000 tiddlers (after this issue is fixed). Having it on only a few tiddlers does not have the same slow-down. And in the current situation we always get bogged down because of the bug I'm describing. Everything else about the sortByList function is relatively fast and optimized, it seems.

Edit: I just realized you're talking about creating a new operator rather than changing the current operator. We should also create a sortByList operator which would accept any field as the list field argument and sort the input according to that list. That would massively simplify the list field concept. Or has it been done already?

[pmario]

[tag[test]sortby[list]] should already work

[Arlen22]

Does that handle the list field in a special way? If we're going to add a new operator, we should also add a sortByList operator so that any field can be used as a list, not just the list field. But doesn't [tag[test]] work because it calls sortByList in the tag operator? Or is that a different code path?

[Jermolene]

Hi @Arlen22 I wasn't the author of the current code for sortByList, and I find it pretty hard to follow (the replaceItem() is not helpfully named, for instance!), and I'm not certain that I (a) understand the implications of your proposed changes and (b) can be confident that there are no further worthwhile optimisations. Plus I'm afraid I'm by now highly conservative about unintended consequences of innocuous looking code changes.

@pmario I like the idea of an option for the tag operator to avoid sorting.

[Arlen22]

Replace item just makes sure that the tiddler is before the tiddler in the list-before field OR after the tiddler in the list-after field. list-before takes precedence over list-after, and a blank field that exists takes precedence over a field with a tiddler listed. So if list-after exists but is empty, then list-before with a tiddler specified will not take effect, but otherwise list-before takes precedence.

That's the sum of the first part of the replaceItem function. I couldn't find any other optimizations, but this one is major and does not change the final result of the code as best as I can tell.

[Arlen22]

All I'm trying to say is that the code reads

• get current position
• if new position is -1 set it to current position
• if current position does not equal new position, do the swap

Since it's expensive to lookup the current position, we should check first if new position is -1 since if it is then it gets set to current position and therefore the swap cannot happen.

I just realized to make the code exactly identical, it should look like this

//if newPos is -1, it will never get moved
if(newPos !== -1) {
  //get the current position, which we don't yet know
  var currPos = titles.indexOf(title);
  //still run the same check on currPos
  if(currPos >= 0 && newPos !== currPos) {
    //move it!
    titles.splice(currPos, 1);
    if(newPos >= currPos) newPos--;
    titles.splice(newPos, 0, title);
  }
}

And the original code again for reference interspersed with my comments.

//get the current position, which we don't yet know
var currPos = titles.indexOf(title); 
//if newPos is not set, set it to currPos
if(newPos === -1) { 
  //set newPos to currPos
  newPos = currPos; 
} 
//if newPos is not equal to currPos (if newPos was -1, then it is always equal)
if(currPos >= 0 && newPos !== currPos) { 
  //move it!
  titles.splice(currPos,1); 
  if(newPos >= currPos) newPos--; 
  titles.splice(newPos,0,title); 
}

I'm not trying to be difficult, I'm just very sure that the actual code is identical, if you're still not convinced, that's fine, I understand.

[Arlen22]

I edited my last comment quite a bit, so just letting you know if you're seeing this on email.

[pmario]

@Arlen22 ... Did you try your changes with the wiki listed at: the original discussion?

[Arlen22]

@pmario Good question. I just tried it now, and it does indeed significantly speed up the wiki to pretty much normal when I do the same action I did before and any other actions related to that one filter.

The wiki has other performance problems which are unrelated to this, so I'm continuing to dig into other areas.

[pmario]

Thank you very much, that you contribute so much valuable time to improve the system!!

[flibbles]

I am the last person who worked on this method. I understand the change you're proposing, and I concur that it would not change the output. Also, I wrote tests for this back when I modified it to use an internal recursive method. If you look at the PR, I put them in test-tags (cause I was fixing an issue with tag order, but test-utils might make more sense)

Also, I was the one who called it replaceItem, and I guess we can change the name to something practical, like moveItem or placeItemInList.

[flibbles]

This PR should be good to go. Existing tests already ensure that all combinations of list-after and list-before are managed.

[flibbles]

This can be closed.

[Arlen22]

Looks good to me.