(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


  • Moderators

    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.


  • Moderators

    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.


  • Moderators

    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-42810

    Thanks for your help !


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.