(solved) QSet subtract function is slow
-
Hello,
I have mark a QSet that contains 1000000 instances of my own class. I try to substract an other QSet to it, but it is very slow.
@QSet<MyClass> bigSet;
QSet<MyClass> smallSet;
bigSet.subtract(smallSet);@I have read the internal code of the QSet methode, founded in qset.h. I don't understand the code. Why do we have 2 copy of the set ? Why navigate through a copy of the current set and not the set to subtract ?
Code of the substract methode founded, in qSet.h
@Q_INLINE_TEMPLATE QSet<T> &QSet<T>::subtract(const QSet<T> &other)
{
QSet<T> copy1(*this);
QSet<T> copy2(other);
typename QSet<T>::const_iterator i = copy1.constEnd();
while (i != copy1.constBegin()) {
--i;
if (copy2.contains(*i))
remove(*i);
}
return *this;
}@Indeed, the following loop is 50 times faster than QSet<>::subtract() method on my machine :
@
void mySubtract(QSet<MyClass> &bigSet, const QSet<MyClass> &smallSet)
for(QSetgravDyn::MyClass::iterator it = smallSet.begin();
it != smallSet.end();
++it)
{
bigSet.remove(*it);
}
@Is there a problem with this method ?
Is there any reason why qt's QSet<>::subtract(...) is implemented as it is ?If not, I'll post a bug report (but, well, it would be strange in an old-core-class, so I suspect I am missing a point !)
Thanks
-
One problem is that your code will probably crash if you pass the same object as both bigSet and smallSet, as the iterator can become invalid. Other than that I don't know.
-
Btw. Qt objects are implicitly shared and copied on modification only, so the two "copies" at the top are cheap. Only the first remove actually copies the data.
-
But to avoid crash if the same object is both bigSet and smallSet, I can simply add a test like this :
@if(&bigSet == & smallSet)
{
bigSet.clear();
}
else
...
@Copy2 is cheap but not copy1, as you say the data are copied at the first remove. I think this copy is useless and costly.
-
Hi deac,
[quote author="deac" date="1416558241"]But to avoid crash if the same object is both bigSet and smallSet, I can simply add a test like this :
@if(&bigSet == & smallSet)
{
bigSet.clear();
}
else
...
@Copy2 is cheap but not copy1, as you say the data are copied at the first remove. I think this copy is useless and costly.[/quote]I think your modifications can indeed improve QSet significantly, and I don't see any problems with it. Would you be willing to "submit a patch":http://qt-project.org/wiki/Gerrit-Introduction? Or "submit a request":https://bugreports.qt-project.org?
[quote author="deac" date="1416496534"]it would be strange in an old-core-class, so I suspect I am missing a point ![/quote]It's not that strange; people find ways to improve Qt's performance all the time. Also:
- Qt is a huge library, and
- This isn't a bug
So nobody else noticed it, probably!
-
Hello,
I have submit a request :
https://bugreports.qt-project.org/browse/QTBUG-42810Thanks for your help !
