Performance improvement / Diff calculation

[mikeger]

We tried to use the AwesomeTableAnimationCalculator in production for our app, but it did not work out due to performance issues.

We observed the significant CPU usage hit on diff calculation. The diff calculation involves plenty of Array.indexOf() calls, and those cost ~O(n) where n is the size of the array.

I've tried to port the framework to use NSOrderedSet where the lookup is O(1), but did not succeed because ordered set is looking objects up not by hash but by memory address, and as log as the data source objects are copied, the lookup can not be successful.

Possible option could be to use one of implementations of ordered set that are done in swift.

PS: If needed I can provide the port implementation that I've done to try NSOrderedSets

[bealex]

Great case, thanks. I did not try to use the library with large sets, usually I'm dealing with hundred items at most and do not see this problem there.

Give me a couple of days, I'll try to think of something.

[bealex]

@mikeger I've questions regarding your case. How complex is your cell model equality check? How many cells and how many sections are there?

[mikeger]

I am working on chat / communication app similar to Telegram / Skype. It's up to user, max I've seen was 1000 conversations.
The order of conversations is predefined by last message date. Conversations on our side can not be copied as they are NSManagedObjects, so on each reload I also have to "wrap" every conversation into containing object that is inherited from ACellModel.
Equality is checked by NSUUID conversation ID.

[bealex]

And how often do you invoke the calculator?

I'm profiling 100 000 (rather simple) cells right now and they are calculating about 30 seconds on iPod Touch 5th gen. That is very long (and I want to speed it up), but 1000 cells must sort in a fraction of a second.

[mikeger]

Observed delay was around 300-600 ms on iPhone 5s, but it happens on every received message because every update could potentially bring some old chat up

[bealex]

I see.

Thanks for the information. Let's see what can be done here... :-)

[bealex]

One more question. Did you use updateItems to specify items you've added/updated/removed or setItems that updates whole list?

[mikeger]

I've used setItems() because I don't know the updated items, if I would know the updated items then I would not need to use the library to calculate the difference :)

[bealex]

Usually you do know objects that were changed/added/removed, but you do not know where they must be placed in a list and do not know the table transformations you need to perform to get there.

When you use setItems, everything has to be checked. Of course it takes time :)

But anyway, I understand the exact problem now and will try to optimise it.

[vani2]

Hi! Look at this good implementation of Paul Heckel diffing algorithm by Instagram. I thinks it's related.

[bealex]

I need to look into it closely, but looks like there is not the common case. Does he takes into account possibility of several sections and cross-section items moving?