item order not stable

[axeld]

In list view mode, the item order is no longer stable - if two entries have the same sorting order, they will switch their position in the list arbitrarily.

This is a regression that has been introduced at some point; I am pretty sure that this wasn't the case in the original OpenTracker code.

[anevilyak]

Perhaps the natural sorting/chunking rewrite from a month or two ago is the culprit? That's the only change to the sorting that I can recall in quite some time.

[axeld]

While I might have introduced new bugs with that, the problem existed back then already (it was even one of the reasons to do this, in order to get all digits tested).

[axeld]

Furthermore, it's not a sorting problem - the sort order is indeed arbitrary. The problem is that Tracker does not retain the order in the way originally presented to the user; ie. it obviously resorts the lists at some point, and then gets confused.

[anevilyak]

From a quick look, sorting of the pose list is done via BList::SortItems(), which uses qsort(), which doesn't guarantee stability. Using mergesort() or std::stable_sort() there might fix this issue without too much additional work.

[anevilyak]

Another alternative: if the columns being sorted on don't provide uniqueness between two rows, would it make sense to compare the other available data for that pair of rows until something not-identical is found? At least in theory that should work, since even a BQuery won't allow the same exact entry into the list more than once, though there is the question of the performance impact. I'd estimate the latter to be negligible though since this code path would only have to be taken in the case where the default set of comparisons can't find any ordering between a pair of items, which should be rare. Thoughts?

[axeld]

While the alternative would certainly work, it's way more complex than just using std::stable_sort(), and does not deliver any additional gain, as the order of the files retrieved from the file system is stable as well.

However, I would not just change BList::SortItems(), as this would affect too many apps, and stable sorting has more overhead for little gain (in many use cases).

[anevilyak]

Fair enough, will dig into that during the code sprint then unless you have time to beat me to it.

[anevilyak]

Should be fixed in hrev38998