| dfaure |
| Frameworks |
Do a TODO introduced in 4b498196899223692e8a7d334618b2874bb6c77e in 2014.
Don't depend on the internal memory layout of the containers, and get rid of NonMovableFileItem.
Use the new 2 operands < of KFileItem to sort by url.
Sorting lstItems and the use of binary search in findByUrl gets the following results:
adding items to lstItems is almost as fast as before, only 3 msecs slower on average.
findByName is as slow as before.
findByUrl is on average >200x faster.
Pass kio unittests (behind a proxy, therefore ktcpsockettest fails at 261 sec).
Before:
Total Test time (real) = 706.64 sec
After:
Total Test time (real) = 352.63 sec
Using dolphin, in a folder with 15000 files, select them all and rename them to a# (second time to b#), and as soon as it start renaming, go up two directories to not interfere with the refreshes.
Before: 4m 30s to finish
After: 1m 12s to finish
| No Linters Available |
| No Unit Test Coverage |
I unfortunately have no clue how to answer your questions.
| src/core/kcoredirlister.cpp | ||
|---|---|---|
| 825–829 ↗ | (On Diff #27768) | Hmm, this looks weird to me. A more efficient way (but requires you to change the lists this is backed by to a std::vector) is to:
I'm not sure if the benefits of this justify the path of changing the list (dirItem->lstItems) to a std::vector, if possible at all. |
The first patch had 12 unit test failing.
This one has 2 1/2 unit test failing.
I've changed findByUrl, instead of removing the item from the list,
tell the item to refresh.
I do not know why the refreshed mimetype of a file ending in .html becomes
application/x-extension-html instead of text/html.
I couldn't resist, I've removed also the NonMovableFileItem class.
Can someone explain to me how switching from pointers to values is making anything faster, or is a first step towards making anything faster? This step in itself can only make things slower due to more "copying" (refcount updating).
I don't know what the ultimate goal of @jtamate is here (speeding things up, that i do know).
But in general, putting something on the stack (aka, no new) is measurable faster. For small objects and in small quantities that doesn't matter much. But for large objects (KFileItem is large) and in large quantities (also fitting for KFileItem) it could very well be a nice speedup!
The other side of this optimizing story is copies where you don't intent them to happen but they just do. For instance, a std::vector<KFileItem> allocates a bunch ahead of time and then copies it in. Or moves since my move semantics commits and where applicable. If this were a std::vector<KFileItem *> you'd had no such copy or move.
Back on this patch. It might allow faster routes, but it really depends on @jtamate next plans here if the current patch is worth it.
Sounds like we need more info :)
Hi,
To speedup findByUrl, there are strategies like using a QHash for DirItem* or just having it sorted and search using std::binary_search. I guess this will be easier to do if there are less pointers in the path, therefore I'm just trying to remove a TODO: introduced in 4b498196899223692e8a7d334618b2874bb6c77e in 2014. I haven't done any benchmarks on this code yet, first it needs to pass all the tests.
Pass all the unittests, without modifications, finally.
Use as much as possible the recently added move semantics in KFileItem.
no real review, just want to mention that you'll still have heap allocations for every item - now once per container it is in (due to QList and QSet and sizeof the KFileItem)
I've noticed this creates/exposes some crashes in other code/tests, for example in kdirmodeltest the second and later times the test is run.
I'll check all the failing tests (given enough time).
Based on the tests done in D12945 and D11282, the best solution is to have the result of qHash(url) in KFileItem to compare items in the binary search.
In two cases, the KFileItem in the list has to be moved to the right position, this is still faster than before.
Introduce two methods to insert an item into the list and to move the item to the right position.
The crash in kdirmodeltest was due to getting twice the signal of a file changed into a directory.
| src/core/kcoredirlister_p.h | ||
|---|---|---|
| 302 ↗ | (On Diff #27768) | This can be better implemented with std::move and std::move_backward from <algorithm>
if (old_it < new_it) {
std::move(old_it + 1, new_it, old_it); // move downwards
} else {
std::move_backward(new_it , old_it - 1, old_it);
}
*new_it = tmp; |
| src/core/kfileitem.cpp | ||
| 180 ↗ | (On Diff #34708) | You can probably leave this out if you use the following for ordering: bool operator< (const KFileItem& other) {
if m_url.size() != other.m_url.size() {
return m_url.size() < other.m_url.size()
}
return m_url < other.m_url;
}You don't need lexicographical sorting, but just a total ordering for the lookup. |
Removed m_hash, after implementing the right checks it was slower than comparing QUrls.
| src/core/kcoredirlister.cpp | ||
|---|---|---|
| 963 ↗ | (On Diff #27768) | Where did the old code call refresh() (which you now call inside findByUrl)? I don't see it, I only see more specific calls in more specific cases. So this looks slower and possibly incorrect (for non-local-files). |
| 1004 ↗ | (On Diff #27768) | This used to modify the fileitem in dirItem->lstItems, now it's modifying a copy. Is there a call to reinsert missing? |
| 1843 | This used to modify the item in dir->lstItems, so you need to reinsert in order to not lose the changes. | |
| 2042 ↗ | (On Diff #27768) | Needs to be reinserted afterwards. |
The change in kdirmodel is not needed anymore.
The methods that were const are const again.
Better documented the new reinsert method.
Since the goal is to speed up findByUrl, can you add a Q_BENCHMARK for findByUrl?
(there is https://phabricator.kde.org/D12945 but that's more experimental/research, not a benchmark for the production code -- which can still evolve over time)
I do expect it to be faster of course --- a little bit at the expense of the code which modifies items and now has to reinsert them (and that code is hard to benchmark, it's mostly called from async slots...).
Thanks.
| src/core/kcoredirlister.cpp | ||
|---|---|---|
| 2463 ↗ | (On Diff #27768) | The parenthesis around lstNewItems can be removed now. |
| 2476 ↗ | (On Diff #27768) | end() inconsistent with cbegin() on the line just above. Works because the container is const, but still, better be consistent. |
| 2489 ↗ | (On Diff #27768) | The parenthesis around lstNewItems can be removed now. |
| 2691 ↗ | (On Diff #27768) | Is this loop necessary? Can't we return KFileItemList(*allItems) ? There's such a ctor in KFileItemList. |
| src/core/kcoredirlister_p.h | ||
| 308 ↗ | (On Diff #27768) | This is invalid code in case lower_bound() returns end(). If you're sure it "shouldn't happen" because reinsert is always called for items that are already in lstItems, then add a Q_ASSERT. Otherwise if(). |
I've tried to do an automatic benchmark of the rename case, without success.
Changed code as requested.
I think I'm fine with it now, but please wait until next Monday (Oct 8) before pushing, so it doesn't break the upcoming KF5 release. I'm not 100% confident.... (given that earlier versions of the patch had obvious bugs that were not detected by the unittests).
| src/core/kcoredirlister.cpp | ||
|---|---|---|
| 1576–1577 ↗ | (On Diff #27768) | |
I've been able to reproduce the bug:
#10 0x00007f44d257ae1d in qt_assert (assertion=assertion@entry=0x7f44d456fc43 "it != dirItem->lstItems.end()", file=file@entry=0x7f44d456fc10 "/g/5kde/frameworks/kio/src/core/kcoredirlister_p.h", line=line@entry=308) at ../../include/QtCore/../../src/corelib/global/qlogging.h:91 #11 0x00007f44d4535c7a in KCoreDirListerCache::reinsert (this=this@entry=0x7f44d45a5440 <(anonymous namespace)::Q_QGS_kDirListerCache::innerFunction()::holder>, item=..., oldUrl=...) at /g/5kde/frameworks/kio/src/core/kcoredirlister_p.h:310 #12 0x00007f44d452825c in KCoreDirListerCache::renameDir (this=this@entry=0x7f44d45a5440 <(anonymous namespace)::Q_QGS_kDirListerCache::innerFunction()::holder>, oldUrl=..., newUrl=...) at /g/5kde/frameworks/kio/src/core/kcoredirlister.cpp:1584 #13 0x00007f44d452aa29 in KCoreDirListerCache::slotFileRenamed (this=0x7f44d45a5440 <(anonymous namespace)::Q_QGS_kDirListerCache::innerFunction()::holder>, _src=..., _dst=..., dstPath=...) at /g/5kde/frameworks/kio/src/core/kcoredirlister.cpp:969
Let's see if this assert/crash can be avoided without reverting all the patch. Any help is welcome.
| src/core/kcoredirlister.cpp | ||
|---|---|---|
| 825–829 ↗ | (On Diff #27768) | Changed, using the reinsert semantic. |
| 963 ↗ | (On Diff #27768) | Changed to use the reinsert semantic. |
| 1004 ↗ | (On Diff #27768) | Thanks, reinsert has a better semantics than refresh. |
| src/core/kcoredirlister_p.h | ||
| 302 ↗ | (On Diff #27768) | I've looked at those methods, they create a new "undefined" status in the list. I don't want to worry about this new status. |
| src/core/kfileitem.cpp | ||
| 180 ↗ | (On Diff #34708) | I've tried something similar. As QUrl doesn't have a size method, I've tried with path().size(). With findByUrl it is no problem, it gives me 28 msecs vs. 1795 msecs, but inserting in the list gives me 37 msecs vs. the original 19 msecs. |
| src/core/kfileitem.h | ||
| 490 ↗ | (On Diff #34708) | Changed, thanks. Now they match. |
I'm able to reproduce the bug with the following steps:
Next step, transform this into a unit test that always crashes.
Does this valgrind log help?
Invalid read of size 8 at 0x56B5628: QSharedDataPointer<KFileItemPrivate>::QSharedDataPointer(QSharedDataPointer<KFileItemPrivate> const&) (qshareddata.h:92) by 0x56AF5D6: KFileItem::KFileItem(KFileItem const&) (kfileitem.h:47) by 0x575FDFB: KCoreDirListerCache::renameDir(QUrl const&, QUrl const&) (kcoredirlister.cpp:1576) by 0x575B041: KCoreDirListerCache::slotFileRenamed(QString const&, QString const&, QString const&) (kcoredirlister.cpp:969) by 0x577BF39: QtPrivate::FunctorCall<QtPrivate::IndexesList<0, 1, 2>, QtPrivate::List<QString const&, QString const&, QString const&>, void, void (KCoreDirListerCache::*)(QString const&, QString const&, QString const&)>::call(void (KCoreDirListerCache::*)(QString const&, QString const&, QString const&), KCoreDirListerCache*, void**) (qobjectdefs_impl.h:152) by 0x577A630: void QtPrivate::FunctionPointer<void (KCoreDirListerCache::*)(QString const&, QString const&, QString const&)>::call<QtPrivate::List<QString const&, QString const&, QString const&>, void>(void (KCoreDirListerCache::*)(QString const&, QString const&, QString const&), KCoreDirListerCache*, void**) (qobjectdefs_impl.h:185) by 0x5777250: QtPrivate::QSlotObject<void (KCoreDirListerCache::*)(QString const&, QString const&, QString const&), QtPrivate::List<QString const&, QString const&, QString const&>, void>::impl(int, QtPrivate::QSlotObjectBase*, QObject*, void**, bool*) (qobjectdefs_impl.h:414) by 0x75C93BF: QMetaObject::activate(QObject*, int, int, void**) (in /usr/lib/libQt5Core.so.5.12.0) by 0x5798ED3: OrgKdeKDirNotifyInterface::FileRenamedWithLocalPath(QString const&, QString const&, QString const&) (moc_kdirnotify.cpp:224) by 0x579889D: OrgKdeKDirNotifyInterface::qt_static_metacall(QObject*, QMetaObject::Call, int, void**) (moc_kdirnotify.cpp:103) by 0x5798DAB: OrgKdeKDirNotifyInterface::qt_metacall(QMetaObject::Call, int, void**) (moc_kdirnotify.cpp:203) by 0x72B19EE: ??? (in /usr/lib/libQt5DBus.so.5.12.0) Address 0x11350758 is 72 bytes inside a block of size 128 free'd at 0x4839D7B: realloc (vg_replace_malloc.c:826) by 0x7439992: QListData::realloc_grow(int) (in /usr/lib/libQt5Core.so.5.12.0) by 0x7439A3B: QListData::append(int) (in /usr/lib/libQt5Core.so.5.12.0) by 0x576BE43: QList<KFileItem>::insert(QList<KFileItem>::iterator, KFileItem const&) (qlist.h:521) by 0x576B1EC: KCoreDirListerCache::DirItem::insert(KFileItem const&) (kcoredirlister_p.h:422) by 0x576AC8A: KCoreDirListerCache::reinsert(KFileItem const&, QUrl const&) (kcoredirlister_p.h:310) by 0x5760053: KCoreDirListerCache::renameDir(QUrl const&, QUrl const&) (kcoredirlister.cpp:1584) by 0x575B041: KCoreDirListerCache::slotFileRenamed(QString const&, QString const&, QString const&) (kcoredirlister.cpp:969) by 0x577BF39: QtPrivate::FunctorCall<QtPrivate::IndexesList<0, 1, 2>, QtPrivate::List<QString const&, QString const&, QString const&>, void, void (KCoreDirListerCache::*)(QString const&, QString const&, QString const&)>::call(void (KCoreDirListerCache::*)(QString const&, QString const&, QString const&), KCoreDirListerCache*, void**) (qobjectdefs_impl.h:152) by 0x577A630: void QtPrivate::FunctionPointer<void (KCoreDirListerCache::*)(QString const&, QString const&, QString const&)>::call<QtPrivate::List<QString const&, QString const&, QString const&>, void>(void (KCoreDirListerCache::*)(QString const&, QString const&, QString const&), KCoreDirListerCache*, void**) (qobjectdefs_impl.h:185) by 0x5777250: QtPrivate::QSlotObject<void (KCoreDirListerCache::*)(QString const&, QString const&, QString const&), QtPrivate::List<QString const&, QString const&, QString const&>, void>::impl(int, QtPrivate::QSlotObjectBase*, QObject*, void**, bool*) (qobjectdefs_impl.h:414) by 0x75C93BF: QMetaObject::activate(QObject*, int, int, void**) (in /usr/lib/libQt5Core.so.5.12.0) Block was alloc'd at at 0x4839D7B: realloc (vg_replace_malloc.c:826) by 0x7439992: QListData::realloc_grow(int) (in /usr/lib/libQt5Core.so.5.12.0) by 0x7439C1A: QListData::insert(int) (in /usr/lib/libQt5Core.so.5.12.0) by 0x576BE43: QList<KFileItem>::insert(QList<KFileItem>::iterator, KFileItem const&) (qlist.h:521) by 0x576B1EC: KCoreDirListerCache::DirItem::insert(KFileItem const&) (kcoredirlister_p.h:422) by 0x575D78C: KCoreDirListerCache::slotEntries(KIO::Job*, QList<KIO::UDSEntry> const&) (kcoredirlister.cpp:1252) by 0x577C268: QtPrivate::FunctorCall<QtPrivate::IndexesList<0, 1>, QtPrivate::List<KIO::Job*, QList<KIO::UDSEntry> const&>, void, void (KCoreDirListerCache::*)(KIO::Job*, QList<KIO::UDSEntry> const&)>::call(void (KCoreDirListerCache::*)(KIO::Job*, QList<KIO::UDSEntry> const&), KCoreDirListerCache*, void**) (qobjectdefs_impl.h:152) by 0x577AAC8: void QtPrivate::FunctionPointer<void (KCoreDirListerCache::*)(KIO::Job*, QList<KIO::UDSEntry> const&)>::call<QtPrivate::List<KIO::Job*, QList<KIO::UDSEntry> const&>, void>(void (KCoreDirListerCache::*)(KIO::Job*, QList<KIO::UDSEntry> const&), KCoreDirListerCache*, void**) (qobjectdefs_impl.h:185) by 0x5777D4A: QtPrivate::QSlotObject<void (KCoreDirListerCache::*)(KIO::Job*, QList<KIO::UDSEntry> const&), QtPrivate::List<KIO::Job*, QList<KIO::UDSEntry> const&>, void>::impl(int, QtPrivate::QSlotObjectBase*, QObject*, void**, bool*) (qobjectdefs_impl.h:414) by 0x75C93BF: QMetaObject::activate(QObject*, int, int, void**) (in /usr/lib/libQt5Core.so.5.12.0) by 0x5703C23: KIO::ListJob::entries(KIO::Job*, QList<KIO::UDSEntry> const&) (moc_listjob.cpp:236) by 0x57027CE: KIO::ListJobPrivate::slotListEntries(QList<KIO::UDSEntry> const&) (listjob.cpp:154)
@jtamate Does that "let's continue in that other review" mean we should cancel this one? Still shows on the list of reviews to consider
Yes, it should be closed. It was already commited, unfortunately with a bug associated to it, fixed in the other review.