Chasing QList detach_helper()

[Cruz]

Hi there,

I am writing high performance code for a real time application. A typical use case in this project is the use of a QList as a queue, where first the queue would be clear()-ed, then an unknown number of elements will be push_back()-ed and pop_front()-ed in succession. One of the bottlenecks I am trying to combat is the costly memory allocation with the new operator, which obviously occurs each time a new element is appended to the list. Since the number of elements is unknown and I cannot possibly allocate the right amount of memory upfront, I follow the strategy of not letting the queue clear(), but reuse the memory blocks it already created by using the [] operator to assign a new value to an already allocated slot. I wrote a little wrapper that does this. Let me show you what it looks like.

template <typename T>
class List
{
    int idxFront;
    int idxBack;
    QList<T> list;
 
public:
    List();
    void clear();
    void push_back(T const&);
    T pop_front();
    T& operator[](int i);
};
 
template <typename T>
List<T>::List()
{
    idxFront = -1;
    idxBack = -1;
}
 
// Clears the list, but not really.
template <typename T>
void List<T>::clear()
{
    idxFront = -1;
    idxBack = -1;
}
 
// Appends a new item to the back of the queue.
template <typename T>
void List<T>::push_back(T const& elem)
{
    //qDebug() << "push_back()" << idxFront << idxBack << list.size();
    if (idxBack == -1)
    {
        if (list.empty())
            list.push_back(elem);
        else
            list[0] = elem;
        idxBack = 0;
        idxFront = 0;
    }
    else if (idxBack < list.size()-1)
    {
        idxBack++;
        list[idxBack] = elem;
    }
    else
    {
        idxBack++;
        list.push_back(elem);
    }
}
 
// Removes the first item from the List.
template <typename T>
T List<T>::pop_front()
{
    //qDebug() << "pop_front()" << idxFront << idxBack << list.size();
    if (idxFront == idxBack)
    {
        int tmpidx = idxFront;
        idxFront = -1;
        idxBack = -1;
        return list.at(tmpidx);
    }
    return list.at(idxFront++);
}
 
// Index based access to the elements in the List.
template <typename T>
T& List<T>::operator[](int i)
{
    return list[idxFront+i];
}

template <typename T>
class List
{
    int idxFront;
    int idxBack;
    QList<T> list;

public:
    List();
    void clear();
    void push_back(T const&);
    T pop_front();
    T& operator[](int i);
};

template <typename T>
List<T>::List()
{
    idxFront = -1;
    idxBack = -1;
}

// Clears the list, but not really.
template <typename T>
void List<T>::clear()
{
    idxFront = -1;
    idxBack = -1;
}

// Appends a new item to the back of the queue.
template <typename T>
void List<T>::push_back(T const& elem)
{
    //qDebug() << "push_back()" << idxFront << idxBack << list.size();
    if (idxBack == -1)
    {
        if (list.empty())
            list.push_back(elem);
        else
            list[0] = elem;
        idxBack = 0;
        idxFront = 0;
    }
    else if (idxBack < list.size()-1)
    {
        idxBack++;
        list[idxBack] = elem;
    }
    else
    {
        idxBack++;
        list.push_back(elem);
    }
}

// Removes the first item from the List.
template <typename T>
T List<T>::pop_front()
{
    //qDebug() << "pop_front()" << idxFront << idxBack << list.size();
    if (idxFront == idxBack)
    {
        int tmpidx = idxFront;
        idxFront = -1;
        idxBack = -1;
        return list.at(tmpidx);
    }
    return list.at(idxFront++);
}

// Index based access to the elements in the List.
template <typename T>
T& List<T>::operator[](int i)
{
    return list[idxFront+i];
}

To copy to clipboard, switch view to plain text mode 

When profiling this code with valgrind embedded in Qt Creator, it turns out that the push_back() operation spends the vast majority of its time calling QList::detach_helper(int). This is bothersome as the QList inside this wrapper should never ever detach(), and because I don't understand why it does. :) In the push_back() method QList::empty(), QList::size(), QList::append(T), and QList::operator[int] are used. size() and empty() are out. When I open the source of QList::append(T), I cannot see any direct or indirect calls to detach_helper(int) occuring. It calls detach_helper_grow(), which is a different function. What remains is the QList::operator[int]. Now this operator does call detach(), which then calls detach_helper() if the list is shared, but why would it be shared? The QList is private inside my List class and nothing else is ever touching it. So why does this call ever occur?

[anda_skoa]

Maybe QList is not the best container to base this on, see https://marcmutz.wordpress.com/effective-qt/containers/

Cheers,
_

[d_stranz]

The QList is private inside my List class and nothing else is ever touching it. So why does this call ever occur?

As the great article linked by anda_skoa says, there are major differences between Qt and STL containers. QList in particular is implicitly shared and will be copied on write. So if one of your List class methods modifies (or by being non-const is interpreted as potentially modifying) the wrapped QList, it could cause a copy.

Your "T & operator[]( int )" for example, causes a copy on write, even if it is on the right-hand side of an expression because it is a mutable operation. If you declared a const version of that, you would avoid the copy when used correctly: "const T & operator[]( int ) const".

[anda_skoa]

QList is also a "node based" container, where each element is basically another object that holds the actual entry.
There are some optimizations for simple types that fit into the space of a pointer, but it is never less.

Cheers,
_

[Cruz]

I have done some performance test on my own with my code and realistic data, and it turns out that using QVector as a base for my List leads to better performance. This is no surprise given that document about the container classes and also the Qt documentation recommends to prefer QVector. I chose QList at first because I thought that the sequential growth will lead to copying the entire vector multiple times during the growth phase, but this doesn't seem to be a problem after all and QVector outperforms QList. I also tried std::deque and it loses badly. What remains a mystery to me is the repeated detachment of the QList. I removed the detach() call in the operator[] in qlist.h and yes, it started performing much better. Since the private QList in my List class is not shared, this detach() call should have no effect. But oh well, since I'm using QVector now, I can't be bothered to follow up on this any further.

Thanks for the help!