D12233: Avoid manipulation of lists with quadratic complexity

This revision was automatically updated to reflect the committed changes. Closed by commit R293:39944a5e4fa4: Avoid manipulation of lists with quadratic complexity (authored by bruns). REPOSITORY R293 Baloo CHANGES SINCE LAST UPDATE https://phabricator.kde.org/D12233?vs=35068=37835

D12233: Avoid manipulation of lists with quadratic complexity

bruns added a comment. Sorry for the noise - apparently, if one requests changes, adopt the revision, does the changes, the "Changes requested" flag is not cleared and can not be cleared ... REPOSITORY R293 Baloo BRANCH arcpatch-D12233 REVISION DETAIL

D12233: Avoid manipulation of lists with quadratic complexity

bruns edited reviewers, added: Baloo; removed: michaelh. REPOSITORY R293 Baloo BRANCH arcpatch-D12233 REVISION DETAIL https://phabricator.kde.org/D12233 To: bruns, mgallien, mpyne, #frameworks, #baloo Cc: #baloo, mpyne, dhaumann, ngraham, kde-frameworks-devel, jtamate, bruns,

D12233: Avoid manipulation of lists with quadratic complexity

bruns removed a reviewer: Baloo. This revision is now accepted and ready to land. Restricted Application added a subscriber: Baloo. REPOSITORY R293 Baloo BRANCH arcpatch-D12233 REVISION DETAIL https://phabricator.kde.org/D12233 To: bruns, michaelh, mgallien, mpyne, #frameworks Cc:

D12233: Avoid manipulation of lists with quadratic complexity

bruns marked 4 inline comments as done. REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233 To: bruns, #baloo, michaelh, mgallien, mpyne, #frameworks Cc: mpyne, dhaumann, ngraham, kde-frameworks-devel, jtamate, bruns, ashaposhnikov, michaelh, astippich, spoorun,

D12233: Avoid manipulation of lists with quadratic complexity

bruns marked an inline comment as done. REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233 To: bruns, #baloo, michaelh, mgallien, mpyne, #frameworks Cc: mpyne, dhaumann, ngraham, kde-frameworks-devel, jtamate, bruns, ashaposhnikov, michaelh, astippich, spoorun,

D12233: Avoid manipulation of lists with quadratic complexity

bruns added a reviewer: Frameworks. REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233 To: bruns, #baloo, michaelh, mgallien, mpyne, #frameworks Cc: mpyne, dhaumann, ngraham, kde-frameworks-devel, jtamate, bruns, ashaposhnikov, michaelh, astippich, spoorun, abrahams

D12233: Avoid manipulation of lists with quadratic complexity

mpyne accepted this revision. mpyne added a comment. I don't use Baloo directly but I've taken a look from a code sanity perspective and agree with @dhaumann that the change is a proper port of the existing logic. REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233

D12233: Avoid manipulation of lists with quadratic complexity

bruns added a comment. In D12233#283521 , @bruns wrote: > In D12233#279389 , @bruns wrote: > > > Still waiting for a final review ... > > > Hello! Anyone at home? Another 2 weeks ...

D12233: Avoid manipulation of lists with quadratic complexity

lbeltrame added a reviewer: mgallien. REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233 To: bruns, #baloo, michaelh, mgallien Cc: dhaumann, ngraham, kde-frameworks-devel, jtamate, bruns, ashaposhnikov, michaelh, astippich, spoorun, abrahams

D12233: Avoid manipulation of lists with quadratic complexity

bruns added a comment. In D12233#279389 , @bruns wrote: > Still waiting for a final review ... Hello! Anyone at home? REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233 To: bruns, #baloo, michaelh Cc:

D12233: Avoid manipulation of lists with quadratic complexity

bruns added a comment. Still waiting for a final review ... REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233 To: bruns, #baloo, michaelh Cc: dhaumann, ngraham, kde-frameworks-devel, jtamate, bruns, ashaposhnikov, michaelh, astippich, spoorun, abrahams

D12233: Avoid manipulation of lists with quadratic complexity

ngraham added a comment. In D12233#270663 , @dhaumann wrote: > I would give a ship-it - but maybe another review would be good? @ngraham maybe? I'm afraid I don't really consider myself qualified to review this kind of change. I'm more

D12233: Avoid manipulation of lists with quadratic complexity

bruns added inline comments. INLINE COMMENTS > dhaumann wrote in pendingfilequeue.cpp:69 > Did you check? This is certainly correct for i++ if i is an int. But for > iterators, which are classes, this is often not the case, but I may be wrong > here. In any case, this is a minor nitpick you

D12233: Avoid manipulation of lists with quadratic complexity

dhaumann added a comment. I would give a ship-it - but maybe another review would be good? @ngraham maybe? INLINE COMMENTS > bruns wrote in pendingfilequeue.cpp:69 > GCC generates identical code for both ... Did you check? This is certainly correct for i++ if i is an int. But for

D12233: Avoid manipulation of lists with quadratic complexity

bruns added inline comments. INLINE COMMENTS > dhaumann wrote in pendingfilequeue.cpp:69 > ++it is faster. GCC generates identical code for both ... REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233 To: bruns, #baloo, michaelh Cc: dhaumann, ngraham,

D12233: Avoid manipulation of lists with quadratic complexity

bruns edited the summary of this revision. REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233 To: bruns, #baloo, michaelh Cc: dhaumann, ngraham, kde-frameworks-devel, jtamate, bruns, ashaposhnikov, michaelh, astippich, spoorun

D12233: Avoid manipulation of lists with quadratic complexity

dhaumann added a comment. Looks good to me. INLINE COMMENTS > pendingfilequeue.cpp:69 > +const auto droppedFilesBegin = std::partition(m_cache.begin(), end, > keepFile); > +for (auto it = droppedFilesBegin; it != end; it++) { > +m_pendingFiles.remove(it->path());

D12233: Avoid manipulation of lists with quadratic complexity

bruns marked 2 inline comments as done. REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233 To: bruns, #baloo, michaelh Cc: ngraham, kde-frameworks-devel, jtamate, bruns, ashaposhnikov, michaelh, astippich, spoorun

D12233: Avoid manipulation of lists with quadratic complexity

bruns commandeered this revision. bruns edited reviewers, added: michaelh; removed: bruns. REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233 To: bruns, #baloo, michaelh Cc: ngraham, kde-frameworks-devel, jtamate, bruns, ashaposhnikov, michaelh, astippich, spoorun

D12233: Avoid manipulation of lists with quadratic complexity

bruns updated this revision to Diff 35068. bruns added a comment. Fix remaining issue (inverse condition in std::partition), cleanup REPOSITORY R293 Baloo CHANGES SINCE LAST UPDATE https://phabricator.kde.org/D12233?vs=32595=35068 BRANCH arcpatch-D12233 REVISION DETAIL

D12233: Avoid manipulation of lists with quadratic complexity

ngraham added a comment. You could commandeer it and finish it yourself I guess. :-( I'll see if I can contact Michael. REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233 To: michaelh, #baloo, bruns Cc: ngraham, kde-frameworks-devel, jtamate, bruns,

D12233: Avoid manipulation of lists with quadratic complexity

bruns added a comment. Restricted Application edited subscribers, added: kde-frameworks-devel; removed: Frameworks. Apparently @michaelh is MIA - how do we proceed here? REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233 To: michaelh, #baloo, bruns Cc:

D12233: Avoid manipulation of lists with quadratic complexity

bruns requested changes to this revision. bruns added inline comments. This revision now requires changes to proceed. INLINE COMMENTS > jtamate wrote in pendingfilequeue.cpp:68 > According to std::partition > > what matches isDescendant

D12233: Avoid manipulation of lists with quadratic complexity

jtamate added inline comments. INLINE COMMENTS > pendingfilequeue.cpp:68 > +const auto startRemoving = std::partition(m_cache.begin(), end, > isDescendant); > +for (auto it = startRemoving; it != end; it++) { > +m_pendingFiles.remove(it->path()); According to

D12233: Avoid manipulation of lists with quadratic complexity

michaelh updated this revision to Diff 32595. michaelh added a comment. - Indent REPOSITORY R293 Baloo CHANGES SINCE LAST UPDATE https://phabricator.kde.org/D12233?vs=32322=32595 BRANCH remove-if (branched from master) REVISION DETAIL https://phabricator.kde.org/D12233 AFFECTED

D12233: Avoid manipulation of lists with quadratic complexity

bruns added inline comments. INLINE COMMENTS > fileindexscheduler.cpp:148 > + [](const QString& file) { > +return file.startsWith(dir); > +}); indent by 4, please. And align `});`

D12233: Avoid manipulation of lists with quadratic complexity

michaelh marked 2 inline comments as done. REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233 To: michaelh, #baloo Cc: bruns, #frameworks, ashaposhnikov, michaelh, astippich, spoorun, ngraham

D12233: Avoid manipulation of lists with quadratic complexity

michaelh marked 4 inline comments as done. REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233 To: michaelh, #baloo Cc: bruns, #frameworks, ashaposhnikov, michaelh, astippich, spoorun, ngraham

D12233: Avoid manipulation of lists with quadratic complexity

michaelh updated this revision to Diff 32322. michaelh added a comment. - Apply suggested change REPOSITORY R293 Baloo CHANGES SINCE LAST UPDATE https://phabricator.kde.org/D12233?vs=32285=32322 BRANCH remove-if (branched from master) REVISION DETAIL

D12233: Avoid manipulation of lists with quadratic complexity

bruns added inline comments. INLINE COMMENTS > michaelh wrote in fileindexscheduler.cpp:148 > I suppose developers on my level will appreciate code to be most > self-explanatory. I'm not objecting though, we might al well go "all the way": > > list.erase(std::remove_if(list.begin(),

D12233: Avoid manipulation of lists with quadratic complexity

michaelh added inline comments. INLINE COMMENTS > bruns wrote in fileindexscheduler.cpp:148 > You can put the lambda into the `remove_if` invocation: > > auto tail = std::remove_if(list.begin(), list.end(), > [](const QString& file) { >

D12233: Avoid manipulation of lists with quadratic complexity

michaelh updated this revision to Diff 32285. michaelh added a comment. - Include omissions - Const! REPOSITORY R293 Baloo CHANGES SINCE LAST UPDATE https://phabricator.kde.org/D12233?vs=3=32285 BRANCH remove-if (branched from master) REVISION DETAIL

D12233: Avoid manipulation of lists with quadratic complexity

bruns added inline comments. INLINE COMMENTS > fileindexscheduler.cpp:148 > +return file.startsWith(dir); > +}; > + You can put the lambda into the `remove_if` invocation: auto tail = std::remove_if(list.begin(), list.end(), [](const QString& file) {

D12233: Avoid manipulation of lists with quadratic complexity

michaelh added a comment. If this is correct, I can extend. REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233 To: michaelh, #baloo Cc: #frameworks, ashaposhnikov, michaelh, astippich, spoorun, ngraham, bruns, alexeymin

D12233: Avoid manipulation of lists with quadratic complexity

michaelh created this revision. michaelh added a reviewer: Baloo. Restricted Application added projects: Frameworks, Baloo. Restricted Application added a subscriber: Frameworks. michaelh requested review of this revision. REVISION SUMMARY When removing items from lists Baloo uses an

D12233: Avoid manipulation of lists with quadratic complexity

michaelh added a task: T8502: Avoid manipulation of lists with quadratic complexity. REPOSITORY R293 Baloo REVISION DETAIL https://phabricator.kde.org/D12233 To: michaelh, #baloo Cc: #frameworks, ashaposhnikov, michaelh, astippich, spoorun, ngraham, bruns, alexeymin