FetchedRecordsController uses gigs of memory, my fault ?

[skrew]

Hi,

I have a problem using FetchedRecordsController, i have read the documentation but don't know if i'm doing anything wrong or if there are a problem with large inserts.

When i insert a second batch of about 1000 items, it consume a lot of memory (i kill it after 20 gigas (on the simulator of course ;p))

Please look my sample code (may need a pod install)

grdb1.zip

Thanks

[groue]

Hello @skrew,

Thanks a lot for your sample project. It clearly demonstrates the very high memory consumption.

No, it's not your fault. When asked to produce detailed changes, FetchedRecordsController uses a Levenshtein diff algorithm which is known to have a high complexity of O(N*M), and to be memory hungry.

I'm thus not quite surprised that it would have difficulties producing detailed changes when there are many rows.

So here is my advice: if your application doesn't need detailed changes, don't ask for them: don't provide the willChange and onChange callbacks:

trackController.trackChanges(
    didChange: { controller in
        ...
    })

When the willChange and onChange callbacks are not provided, FetchedRecordsController uses a much simpler change detection algorithm, which can easily deal with thousands of rows.

[skrew]

Hi @groue

The problem is i need to know which column got updated because i do fine update (eg, if it's an image, i only reload the UIImageView, i don't update all items of the cell...)

But the problem are not so simple...
Sorry people, i have to write in french, my english are too bad and it's late !

Ce que je ne comprend pas, c'est que ca fonctionne très bien lors d'un 1er batch, quelque soit le nombre de rows...
C'est seulement lors du 2ème batch que l'utilisation de la mémoire s'emballe... C'est montré dans mon sample.

Est-ce qu'il y aurait un moyen de faire une sorte de "reset" entre 2 transactions ? Qu'est ce qui fait que la 1ère transaction fonctionne, mais pas la 2ème ?

[groue]

Il est tard ici aussi 😉 À demain pour une réponse plus détaillée !

[skrew]

Pas de problème, je vais pas tarder à me coucher aussi... Je sais qu'on a le même fuseau horaire ! :) Et de toute façon je suis bloqué... Et du coup, ca va être dur de dormir en me disant que s'il y a pas de solution, je vais devoir changer pas mal de choses dans le code ! :)

[groue]

Bonjour !

I'll switch back to English, if you don't mind.

You wonder why your test project easily computes a first diff, and has difficulties computing the second. The answer is that the first diff is computed from an empty array to an array of thousands (easy), while the second is computed from an array of thousands to an array of even more thousands (difficult). This is the consequence of the non-linear complexity of the Levenshtein diffing algorithm, which gets worse and worse as both the number of "old" and "new" rows are big.

je suis bloqué

You're stuck. Let's clear things up.

The amount of work to make FetchedRecordsController able to produce large diffs is really big. This involves eventually finding a more efficient algorithm, if it exists. But also an implementation of this algorithm that performs reasonably well, while keeping memory consumption under control. This most likely involves a disk cache of fetched results. And we'd also need to handle "back pressure", that is to say prevent frequent little transactions from kneeling the application down because it can't compute diffs fast enough. Maybe FetchedRecordsController will eventually get improved this way. But this involves a big amount of time.

If your company considers sponsoring this research task, I would gladly accept that we enter a regular business relationship. Not only would you take profit from the FetchedRecordsController improvements, but other GRDB users as well. Contact me at gr@pierlis.com for more details. Such task could not start before 2018, though.

Meanwhile, let's look at another way out of your issue:

FetchedRecordsController notifies of database changes. This general sentence can be split into fine-grained services:

1. FetchedRecordsController tells that a collection has changed
2. FetchedRecordsController can produce detailed insert/detele/update/move events, so that one can animate cells of a table or collection view.
3. On update and move changes, FetchedRecordsController tells which columns have been modified.

You wrote:

The problem is i need to know which column got updated because i do fine update (eg, if it's an image, i only reload the UIImageView, i don't update all items of the cell...)

It thus looks like your app needs 1 and 3, but I'm not sure about 2.

Let's suppose you can do without cell animations. In this case, you could simply perform reloadData in the didChange callback. This is fast enough even for large collection. What happens then? Does your table/collection view flicks because some remote images do not reload smoothly? What about using an efficient memory-based image cache, then? There are many popular ones on Github.

Do you see what I'm aiming at? It's fixing eventual glitches of reloadData.

Now, if your app really really really needs row animations, then I suggest you have a look at general diff algorithms like tonyarnold/Differ. I've played a little with that one: it has a lower complexity than the Levenshtein algorithm, it produces correct table/collection view animations, but it won't provide the same fine-grained column changes produced by FetchedRecordsController. It may help you, though.

Now it's time for you to sort out what's really important for your app.

[groue]

Note to myself: update the documentation of FetchedRecordsController with a clear warning about large diffs.

[groue]

A last word about the alternative diff algorithm Differ. I've used it as a table view animator in the demo app for the upcoming Swift 4 version of RxRGDB, the reactive extensions to GRDB. This was part of my desire to build reactive table view animations based on GRDB. You may want to have a look at this demo app, because it works pretty well. But it is not as well packaged as FetchedRecordsController, and it only deals with deletions, insertions, and moves (updates are not recognized by Differ, and exposed as a delete/insert pair instead). And I don't know how it behaves when fed with thousands of rows.

[skrew]

Ok thanks, i'd added a diff function for our need, who works but are very specific.
As we started the project with Realm, all "reactive" and changes are based on Realm notifications.
BTW, 2018 are too far for this project ;)

I think i can close.

[groue]

Hello @skrew

As we started the project with Realm, all "reactive" and changes are based on Realm notifications.

If you needed Realm-like notifications, then maybe our long discussion about FetchedRecordsController was not that useful. I can't provide good advice when the reality of the situation is not exposed clearly. Have a look at transaction observers one day.