Is it fast to insert data in QHash<int, megabytes500CustomType> > ?



  • if I insert data like

    QHash<int, megabytes500CustomType>  m_hash;
    m_hash[1] = megabytes500CustomType(T1 arg1, T2 arg2, T3 arg3);
    

    Will it make a copy in memory or just construct object directly?
    If first, how to make it work faster?


  • Lifetime Qt Champion

    Hi,

    It depends on your types. For example are they shared containers ?



  • @SGaist no, it is just big struct of data. Shall I make copy constructor with referene or shall I use move semantics?


  • Qt Champions 2016

    @Kofr
    Neither. Use implicit or explicit sharing. Also int keys for hash tables is somewhat unusual choice. If you can prefer QVector (i.e. if the keys are sequential).


  • Moderators

    QHash is pretty bad at storing big types. This line

    m_hash[1] = megabytes500CustomType(T1 arg1, T2 arg2, T3 arg3);
    

    will actually call:

    • the parametrized constructor of megabytes500CustomType to construct the object
    • a default constructor and a copy constructor of megabytes500CustomType as part of creating a node inside of operator[]
    • an operator= of megabytes500CustomType.

    If all of these methods (the parametrized constructor, default constructor, copy constructor and assignment operator) allocate or copy large amounts of memory this will result in 4 very heavy operations.

    As others mentioned this can be mitigated to some degree with Qt's sharing mechanisms, but some cost will still be there.

    If you don't want the overhead I suggest you take a look at std::unordered_map. You would then be able to use emplace() method which creates the element in-place by only calling its constructor once, e.g.:

    std::unordered_map<int, megabytes500CustomType>  m_hash;
    m_hash.emplace(std::piecewise_construct,
                   std::forward_as_tuple(1),
                   std::forward_as_tuple(arg1, arg2, arg3));
    

  • Qt Champions 2016

    Chris,
    You can mitigate some of it with QHash::insert and constructor's move semantics, but I don't think that's good enough. If at any point you need to move the buckets in memory (depending on the hash table's implementation) ... well, sufficed to say, I'd go with shared data any day.


  • Moderators

    @kshegunov QHash doesn't have move semantics for insertion (there's no && overload of insert) . It will always copy the element. The only thing you can do is make your type implicitly shareable.

    Here's a "benchmark" for a case where the type is at least movable:

    struct Foo
    {
        Foo() { qDebug() << "default constructor"; }
        Foo(int, int) { qDebug() << "param constructor"; }
        Foo(const Foo&) { qDebug() << "copy constructor"; }
        Foo(Foo&&) { qDebug() << "move constructor"; }
        Foo& operator=(const Foo&) { qDebug() << "operator="; return *this; }
        Foo& operator=(Foo&&) { qDebug() << "move operator="; return *this; }
    };
    

    And the results with various approaches:

    QHash<int, Foo> foos;
    foos[1] = Foo(42, 43);
    
    //param constructor
    //default constructor
    //copy constructor
    //move operator=
    
    QHash<int, Foo> foos;
    foos.insert(1, Foo(42, 43));
    
    //param constructor
    //copy constructor
    
    std::unordered_map<int, Foo> foos;
    foos.emplace(std::piecewise_construct,
                 std::forward_as_tuple(1),
                 std::forward_as_tuple(42, 43));
    
    //param constructor
    

    The first case will be even worse if there's no move assignment operator for the type, as a usual assignment operator would be called instead.


  • Qt Champions 2016

    @Chris-Kawa said:

    Hash doesn't have move semantics for insertion (there's no && overload of insert)

    Indeed, you're right. I think such overloads are planned in the future (at least they started putting them in for some classes like QString), but don't hold me to it.

    The only thing you can do is make your type implicitly shareable.

    Or explicitly shareable, depending on the underlying data. But yes, I agree. Thanks for the benchmark, it's certainly curious.
    Still, my original argument stands: if buckets are copied internally for whatever reason, then it doesn't really matter how you fill up the hash table.

    Kind regards.



  • I'm really surprised nobody has suggested the easiest answer yet: use pointers!

    QHash<int, megabytes500CustomType *>  m_hash;
    m_hash[1] = new megabytes500CustomType(T1 arg1, T2 arg2, T3 arg3);
    

    this is very inexpensive, you will just have to remember to call delete in your destructor or, if you don't want to worry about memory management, use smart pointers

    QHash<int, std::shared_ptr<megabytes500CustomType> >  m_hash;
    m_hash[1] = std::make_shared<megabytes500CustomType>(T1 arg1, T2 arg2, T3 arg3);
    

  • Qt Champions 2016

    @VRonin said:
    It was suggested, sort of. Although I grossly dislike the idea of relinquishing control of the memory management, I admit it didn't even occur to me that a shared pointer is a viable alternative. I'm too used to the Qt's pass-by-value-detach-on-write idiom ... :)

    @Kofr

    If it's no secret, what (types) do you hold in megabytes500CustomType?



  • @kshegunov megabytes500CustomType is more like a theoretical question. I have a data structure somthing like 64 bytes. And put it into QHash and I noticed that default constructo is called for this struct before actual needed constructor and even more copy of this. However I like the idea of implicit or explicit sharing but it is more like optimization in case of variable of 64 bytes.
    And it really sucks that QHask does not have emplace()


Log in to reply
 

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