Opened 10 years ago

Closed 10 years ago

#6700 closed bug (fixed)

item order not stable

Reported by: axeld Owned by: anevilyak
Priority: high Milestone: R1
Component: Applications/Tracker Version: R1/Development
Keywords: Cc:
Blocked By: Blocking:
Platform: All


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.

Change History (9)

comment:1 by anevilyak, 10 years ago

Version: R1/alpha2R1/Development

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.

comment:2 by axeld, 10 years ago

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).

comment:3 by axeld, 10 years ago

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.

comment:4 by anevilyak, 10 years ago

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.

comment:5 by anevilyak, 10 years ago

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?

Last edited 10 years ago by anevilyak (previous) (diff)

comment:6 by axeld, 10 years ago

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).

comment:7 by anevilyak, 10 years ago

Owner: changed from axeld to anevilyak
Status: newassigned

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

comment:8 by anevilyak, 10 years ago

Status: assignedin-progress

comment:9 by anevilyak, 10 years ago

Resolution: fixed
Status: in-progressclosed

Should be fixed in hrev38998

Note: See TracTickets for help on using tickets.