When removing items from lists Baloo uses an implementation with quadratic complexity,
i.e. O(m*n) - m: removed items, n: items in list.
Use std::remove_if/std::partition and erase instead.
Details
- Reviewers
mgallien mpyne - Group Reviewers
Frameworks Baloo - Maniphest Tasks
- T8502: Avoid manipulation of lists with quadratic complexity
- Commits
- R293:39944a5e4fa4: Avoid manipulation of lists with quadratic complexity
make test
Diff Detail
- Repository
- R293 Baloo
- Lint
Automatic diff as part of commit; lint not applicable. - Unit
Automatic diff as part of commit; unit tests not applicable.
src/file/fileindexscheduler.cpp | ||
---|---|---|
148 | You can put the lambda into the remove_if invocation: auto tail = std::remove_if(list.begin(), list.end(), [&dir](const QString& file) { return file.startsWith(dir); }); | |
150 | tail instead of it ? | |
src/file/pendingfilequeue.cpp | ||
76 | You are missing the m_pendingFiles.remove(...) and m_recentlyEmitted.remove(...) calls here. Variant A: Variant B: Variant A is definitely the much cleaner approach. |
src/file/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(), list.end(), [&dir](const QString& file) { return file.startsWith(dir); }), list.end()); | |
src/file/pendingfilequeue.cpp | ||
76 | Ooops. |
src/file/fileindexscheduler.cpp | ||
---|---|---|
148 | Following Qt coding style, the [] () { should go on a separate line, as written above I think having list.erase as a separate statement makes reading simpler. |
src/file/fileindexscheduler.cpp | ||
---|---|---|
148 | indent by 4, please. And align }); with [&dir] |
src/file/pendingfilequeue.cpp | ||
---|---|---|
68 | According to std::partition |
src/file/pendingfilequeue.cpp | ||
---|---|---|
68 | Good catch, std::remove_if places the elements where the predicate returned false into the first "partition", std::partition shows the opposite behavior. As we have to discard the second part (for O(1) behavior), the correct fix is to inverse the return value of the predicate. Probably rename the the predicate to "preserveFile" or something like that. |
You could commandeer it and finish it yourself I guess. :-(
I'll see if I can contact Michael.
src/file/pendingfilequeue.cpp | ||
---|---|---|
69 | GCC generates identical code for both ... |
I would give a ship-it - but maybe another review would be good? @ngraham maybe?
src/file/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 can simply ignore, so please go ahead :-) |
src/file/pendingfilequeue.cpp | ||
---|---|---|
69 | Yes, objdump output is identical. |
I'm afraid I don't really consider myself qualified to review this kind of change. I'm more of a front-end developer, and code like this makes my head hurt! :)
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.
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 ...