Faster drag&drop in directories with thousands of files
ClosedPublic

Authored by jtamate on Wed, Jan 24, 6:33 PM.

Details

Summary

The check is called when the mouse is moved in a drag&drop operation.

Dragging all files in a directory with 3000 files under callgrind,
moving the mouse to the other panel and then canceling, doing it twice,
callgrind shows that the method urlListMatchesUrl is called around
200 times, spending around 9,30% of the cpu in those calls.
Applying the patch, callgrind tells it uses now 0.31% of the cpu in 1208 calls.

CCBUG: 342056

Diff Detail

Repository
R318 Dolphin
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
jtamate requested review of this revision.Wed, Jan 24, 6:33 PM
jtamate created this revision.
jtamate edited the summary of this revision. (Show Details)Wed, Jan 24, 6:34 PM
elvisangelaccio requested changes to this revision.Mon, Jan 29, 9:44 PM
elvisangelaccio added a subscriber: elvisangelaccio.

This breaks the drag cursor when dropping a folder onto itself, see 99e80c1c7e6e77aa26.
We do need to accept or reject the event in dragMoveEvent(), otherwise the cursor will be always green.

That said, we can probably implement some sort of cache to speed up the URLs matching (by avoiding duplicated work).

This revision now requires changes to proceed.Mon, Jan 29, 9:44 PM
jtamate updated this revision to Diff 26241.Wed, Jan 31, 9:54 AM
jtamate edited the summary of this revision. (Show Details)

It is faster now, from 9.30% to 5.83%.
The ideal should be, for example, in the form of check another list with only the first item of each folder.
But where should that other list be created? deleted in the drop event.

By the way, shouldn't the list be get by calling KUrlMimeData::urlsFromMimeData?

jtamate updated this revision to Diff 26245.Wed, Jan 31, 11:24 AM
jtamate edited the summary of this revision. (Show Details)

Use a cache for the last url list and dest directory and last result.
From 9.30% to 0.31% in normal mouse movement (doing it several times).

Not sure, but maybe QtConcurrent is applicable here.

jtamate updated this revision to Diff 26319.Thu, Feb 1, 2:37 PM

This patch version uses map/reduce.
The cpu is reduced from 9.30% to 2.33% + (3.06%+3.00% from QtConcurrent).

So this version is considerably slower than the previous one?
Is blockingMappedReduced also using the thread pool? The doc doesn't seem say anything about this.
Have you tried using QFuture/QFutureWatcher?

I'm just curious to see those in action. With my javascript background naturally I got hooked, when I heard about QtConcurrent::map() the other day.

So this version is considerably slower than the previous one?

Yes. Because the previous one only checked the list once in a widget.
This one checks the list every move in the widget.
I can mix both. Faster the first time in a widget and do nothing until the widget changes :-)

Is blockingMappedReduced also using the thread pool? The doc doesn't seem say anything about this.

Yes, according to the documentation.

Have you tried using QFuture/QFutureWatcher?

blockingMappedReduced uses QFuture/QFutureWatcher, and when the task is finished returns.

jtamate updated this revision to Diff 26328.Thu, Feb 1, 4:21 PM

Now with Map/Reduce and cache.

anthonyfieroni added inline comments.
src/views/draganddrophelper.cpp
42–44

Don't do that. It's ridiculous, it cannot guarantied that function will be called with same objects. It's enough speed-up with concurrent calls.

Thank you for the clarification.

jtamate updated this revision to Diff 26367.Fri, Feb 2, 8:17 AM

No pointer logic.
No map/reduce because, in my opinion, could be nice to have another parameter with the first value for the reduction.
Filter the list and create a new one with the Urls that match.
There is no memory leak, checked with valgrind.
The cpu, according to callgrind, is reduced to something around 4%-5%.

jtamate marked an inline comment as done.Fri, Feb 2, 8:17 AM
markg requested changes to this revision.Fri, Feb 2, 7:44 PM
markg added a subscriber: markg.

@jtamate, you are trying to make this faster, which is awesome! But i think there is another issue. I just tried to benchmark this as well with a folder of 5000 empty files.
Within DragAndDropHelper::urlListMatchesUrl i see 40.007 calls to QUrl::matches. That smells weird.
Sure, there are probably some extra urls's (don't know where they come from), but that could explain the last 7. But the remaining 40.000 is 8x as much as the number of items that are being dragged. That's wrong!
Note that this is merely with one drag/drop.

Further investigation shows DragAndDropHelper::urlListMatchesUrl is being called:
6x from KItemListController::dragMoveEvent (the function itself is called 6x)
1x from DragAndDropHelper::dropUrls (the function itself is called 1x)

That's a room for optimization. You could call DragAndDropHelper::urlListMatchesUrl when you start a drag event and simply use those results in subsequent calls till the drag is canceled. That would reduce the number of calls to DragAndDropHelper::urlListMatchesUrl from 7 to 1 (and in effect make it 7x faster :)).

But there is more! Deeper in KIO KFileItemListProperties is filled for this drag/drop event (to determine the common actions).
That object is created 13 times. Each time it's calling setitems (KFileItemListPropertiesPrivate::setItems), that function could use some optimizations. The most costly one in there is the call to KFileItem::isWritable call.
Just reducing the amount of times KFileItemListProperties is created gives an instant performance win as well and might be easier to optimize.

To conclude, please don't optimize this by running it through QtConcurrent. It gives the "appearance" of being faster but you only mask the real issues. As you can see with what i just said, there are quite a few places where you can optimize it which would benefit everyone, not just Dolphin.
I am therefore putting this on "Request Changes".

This revision now requires changes to proceed.Fri, Feb 2, 7:44 PM

@jtamate, you are trying to make this faster, which is awesome! But i think there is another issue. I just tried to benchmark this as well with a folder of 5000 empty files.
Within DragAndDropHelper::urlListMatchesUrl i see 40.007 calls to QUrl::matches. That smells weird.
Sure, there are probably some extra urls's (don't know where they come from), but that could explain the last 7. But the remaining 40.000 is 8x as much as the number of items that are being dragged. That's wrong!
Note that this is merely with one drag/drop.

Further investigation shows DragAndDropHelper::urlListMatchesUrl is being called:
6x from KItemListController::dragMoveEvent (the function itself is called 6x)
1x from DragAndDropHelper::dropUrls (the function itself is called 1x)

One more call with the same list and there you are the 40.000 matches calls.

That's a room for optimization. You could call DragAndDropHelper::urlListMatchesUrl when you start a drag event and simply use those results in subsequent calls till the drag is canceled. That would reduce the number of calls to DragAndDropHelper::urlListMatchesUrl from 7 to 1 (and in effect make it 7x faster :)).

I tried something similar. Take a look at @elvisangelaccio first comment.

I tried to insert some data in the QClipboard to mark that it has been already done, but it is constant. :-(

If someone knows a way to keep an status about the last call, please implement it, I'm out of ideas here.

But there is more! Deeper in KIO KFileItemListProperties is filled for this drag/drop event (to determine the common actions).

And also there is another similar copy of the same method (That I've found today).

That object is created 13 times. Each time it's calling setitems (KFileItemListPropertiesPrivate::setItems), that function could use some optimizations. The most costly one in there is the call to KFileItem::isWritable call.
Just reducing the amount of times KFileItemListProperties is created gives an instant performance win as well and might be easier to optimize.

I'll try that also, but the way I do it is looking for the most expensive calls in callgrind or perf and try to reduce its time or the number of calls it receives, and then do the same with the next one...

To conclude, please don't optimize this by running it through QtConcurrent. It gives the "appearance" of being faster but you only mask the real issues. As you can see with what i just said, there are quite a few places where you can optimize it which would benefit everyone, not just Dolphin.

I just go step by step, I've been lucky up to now, but it is getting much harder.
For example I've spent a week to try to figure out why plasma is blocked when pasting so many files. I think the problem has something to do with the clipboard trying to refill the complete list thousands of times,but the QXcbConnection errors make this hard.

I am therefore putting this on "Request Changes".

markg added a comment.Fri, Feb 2, 11:05 PM

@jtamate how about this patch: https://p.sc2.nl/HyrIiwfIG
The rationale behind it is as follows. If a paste is allowed is checked upon drag enter and upon hovering a different folder within the drag. That value is stored in a bool.
Upon drag leave the value is always reset to false.

I just hacked this together, it seems to work for my simple test case but i don't know if it works in all cases.
Feel free to give it a spin and continue from there on :) You have full permission to use it as you please.

Then for callgrind (i also use that), the calls to DragAndDropHelper::urlListMatchesUrl are now down to 2 with "just" 15.002 calls to QUrl::matches. Still smells spiffy, but much better imho :)
Note, one call from DragAndDropHelper::urlListMatchesUrl comes from DragAndDropHelper::dropUrls which internally again verifies that it can drop. If you guarantee that that function is _only_ being called when a drop is allowed then there is no need for that function to check that again. Thus there you could remove the:

if (urlListMatchesUrl(event->mimeData()->urls(), destUrl)) {
    return nullptr;
}

Another option (to be more conservative) would be to "let that function know" that things are safe and it can ignore the check. That can be done by using the QDropEvent more smartly by checking if it's accpeted. Using that would be nice imho anyhow :)

markg added a comment.Fri, Feb 2, 11:30 PM

https://p.sc2.nl/S1yjzuGUz (hacked together, test thoroughly please)
Down to 5000 aka, the base testcase, it cannot go down further :) (did i just make it ~8 times faster? hehe)
And i'm using the QDropEvent isAccepted function now to prevent another call to urlListMatchesUrl.

I had to change DolphinView::slotItemDropEvent where a QDropEvent is constructed from a QGraphicsSceneDragDropEvent to include whatever the accepted state was.
I only did it there, you'd have to look over all occurrences of "DragAndDropHelper::dropUrls" to make sure the QDropEvent that is passed in has the accepted value (only an issue if that event is manually re-created from some other event).

Have fun with the patch :)
Now i'm going to dive into the KIO side of this.

jtamate updated this revision to Diff 26426.Sat, Feb 3, 11:37 AM

Uses a Qcache to do the expensive check only once, but keep
the improved check.
Many thanks to markg.

markg requested changes to this revision.Sat, Feb 3, 11:58 AM

Hi,

I don't see why you use a QCache as you're not using any of it's features.
If you want to maintain a mapping of QUrl -> bool, just use a QHash.
I think maintaining a QUrl -> bool mapping is fine. What i did in my patch (only a bool) could have been an issue if you for whatever magical reason have a drag enter event with a different url without first receiving a drag close event - aka corner cases.

Also, please drop the QtConcurrent part as that is not needed anymore.

Are you also going to fix DragAndDropHelper::dropUrls? If not then i will take a look at that one. It should imho not call urlListMatchesUrl at all and only work if "event->isAccepted()" is true.

src/kitemviews/kitemlistcontroller.h
355 ↗(On Diff #26426)

initialize this member in the class constructor initializer list.

This revision now requires changes to proceed.Sat, Feb 3, 11:58 AM
jtamate updated this revision to Diff 26431.Sat, Feb 3, 12:35 PM
  • Faster drag&drop in directories with thousands of files

Using QHash instead of QCache.
Dropped the concurrent part.
Used markg fix for dropUrls (I missed this part)

jtamate updated this revision to Diff 26433.Sat, Feb 3, 1:00 PM
  • Faster drag&drop in directories with thousands of files

I forgot to remove the now innecesary check in dropUrls

elvisangelaccio requested changes to this revision.Sat, Feb 3, 4:32 PM

Looks better, but I spotted another regression: try to drop a folder on empty space in the view. Old code shows the drop menu with "Copy Here" and "Link Here", new code doesn't.

src/kitemviews/kitemlistcontroller.cpp
62

Not needed, default constructor is automatically called.

940

m_dropAccepted is a bit misleading as name for the member variable. Maybe m_dropAcceptable could work better.

src/kitemviews/kitemlistcontroller.h
32 ↗(On Diff #26433)

No longer necessary

This revision now requires changes to proceed.Sat, Feb 3, 4:32 PM

I have a question.
As the regression is in dropUrls, and we try to avoid a new call to urlListMatchesUrl
The include "dolphin_export.h" and DOLPHIN_EXPORT means that they have to conserve API or ABI compatibility?
I mean, can I add freely another parameter to dropUrls method or should I create a new method?

I have a question.
As the regression is in dropUrls, and we try to avoid a new call to urlListMatchesUrl
The include "dolphin_export.h" and DOLPHIN_EXPORT means that they have to conserve API or ABI compatibility?
I mean, can I add freely another parameter to dropUrls method or should I create a new method?

Yes, don't worry about API/ABI compatibility. The export macro just means that this code can be called from outside the dolphinprivate library (as the name suggests, this is not a public library).

markg added a comment.Sat, Feb 3, 5:52 PM

Ho, wait.

You already have all the information you need. It's just incomplete when it arrives in DragAndDropHelper::dropUrls.

Look at my patch again (https://p.sc2.nl/S1yjzuGUz), i did something there in DolphinView::slotItemDropEvent which is important.
You did not do that so the accepted value is the default which is false. In other words, the QDropEvent isn't filled with all data you need.

I also mentioned that (if you go this route, which you are now) you should follow all occurrences DragAndDropHelper::dropUrls to make sure the QDropEvent that is passed is properly filled with values. It only occurs only a few times in Dolphin so it's not a bit task ;)

If you follow that you don't need a new argument in there at all.

jtamate updated this revision to Diff 26473.Sun, Feb 4, 3:00 AM
  • Faster drag&drop in directories with thousands of files

If the cache is about DragAndDropHelper, implement it there.

Added one method to clear the cache when the drag is initiated
in dolphin. It is not notified if the drag starts in nautilus,
but in any case, the drop in the same folder is rejected.

Thanks for your patience.

markg added inline comments.Sun, Feb 4, 3:26 AM
src/views/draganddrophelper.cpp
36–47

You now have a double lookup in the m_cacheUrlListMatchesUrl hash. It's fast, so not that big of a deal.
But since we're in the optimizing mood here.. :)

auto result = m_cacheUrlListMatchesUrl.find(destUrl);
if (result != m_cacheUrlListMatchesUrl.end()) {
  return *m_cacheUrlListMatchesUrl.insert(destUrl,
    std::find_if(urls.constBegin(), urls.constEnd(), [destUrl](const QUrl& url) {
      return url.matches(destUrl, QUrl::StripTrailingSlash);
    }) != urls.constEnd() );
} else {
  return *result;
}

The if statement is _really_ ugly now :P
Something along those lines should work.
Note that you can directly return from the insert, it gives an iterator back and that is - if i'm right - the iterator of the just inserted data.

jtamate updated this revision to Diff 26498.Sun, Feb 4, 1:01 PM
  • Faster drag&drop in directories with thousands of files

Removed the double lookup.
Hopefully, QHash will have someday a setDefault method like python, that
would simplify a lot the code.

The problem with nautilus was already present before the patch.
But the dragEnterEvent is called.

markg accepted this revision.EditedSun, Feb 4, 1:29 PM

+1 from me.
Don't ship it yet though. Wait for at least @elvisangelaccio for his opinion about it.

I think you've found a nice non-invasive approach to improve efficiency! Much more elegant than my initial hack approach.

After this patch it would probably be best to fix the QMimeData that is being fed into dropUrls to be fixed as well (so with a filled accepted value) and using that in dropUrls like one of your previous patches did.
It does not "fix" more or speed things up more but just makes it act correctly. Your caching mechanism is good regardless.

Almost there, I could not find regressions this time :)

Please fix the coding style and then it's good to go from my side.

src/views/draganddrophelper.cpp
36–46

Please use constFind()

38–47

This is really hard to read, and the comments only add more noise. How about doing it like this:

bool DragAndDropHelper::urlListMatchesUrl(const QList<QUrl>& urls, const QUrl& destUrl)
{
    auto iteratorResult = m_cacheUrlListMatchesUrl.constFind(destUrl);
    if (iteratorResult != m_cacheUrlListMatchesUrl.constEnd()) {
        return *iteratorResult;
    }

    const bool destUrlMatches = (std::find_if(urls.constBegin(), urls.constEnd(), [destUrl](const QUrl& url) {
        return url.matches(destUrl, QUrl::StripTrailingSlash);
    }) != urls.constEnd());

    return *m_cacheUrlListMatchesUrl.insert(destUrl, destUrlMatches);
}
56

Unrelated whitespace change

src/views/draganddrophelper.h
61

Please call it clearUrlListMatchesUrlCache(), to make it slightly more descriptive.

jtamate updated this revision to Diff 26532.Sun, Feb 4, 8:23 PM
  • Faster drag&drop in directories with thousands of files

Addressed style coding, now it is clearly more clear (even without comments).
There are no more superfluous empty lines removals.

jtamate marked 7 inline comments as done.Sun, Feb 4, 8:24 PM
elvisangelaccio accepted this revision.Sun, Feb 4, 8:26 PM

Thanks :)

This revision is now accepted and ready to land.Sun, Feb 4, 8:26 PM
markg accepted this revision.Sun, Feb 4, 9:08 PM
This revision was automatically updated to reflect the committed changes.