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?
Bookmarks