Understanding why these few lines are slow

[hakermania]

This code is very slow in execution. By being event->mimeData()->urls().length() 15(so I have 15 urls), it takes almost 3-4 secs for it to execute. I am trying to figure out why, and how would I reduce this time. This is the code:


for(int i=1; i<=event->mimeData()->urls().length(); i++){
item=new QListWidgetItem;
QUrl url = event->mimeData()->urls().takeAt(i-1);
QString file2 = url.toString();
QString file1 = file2.mid(7,file2.length()-2); //removing some things I don't want
QString extension = file1.right(3); //taking last 3 letters from the string..
if(extension=="png" || extension=="gif"){ //add to the listwidget
item->setText(file1);
ui->listWidget->addItem(item);
}
}

I don't think I'm doing something that takes a lot time to be done... I convert QUrl to QString, do some processing to QString and go into an if statement. I am sure that adding items into the listwidget doesn't take too much time, because I have tested and I can add many thousands of files per second.
So....what makes this code slow?

[Lykurg]

Well, to be honest, that code looks terrible to me. Anyway, you are producing a memory leak. I would fix that first!

[Zlatomir]

Since item is only a string, i don't think you need QListWidgetItem and allocated on heap. So first as Lykurg said remove the leak, and i would add remove the heap allocations (they can be expensive in loops), so first try it like this:


for(int i=1; i<=event->mimeData()->urls().length(); i++){
//item=new QListWidgetItem;
QUrl url = event->mimeData()->urls().takeAt(i-1);
QString file2 = url.toString();
QString file1 = file2.mid(7,file2.length()-2); //removing some things I don't want
QString extension = file1.right(3); //taking last 3 letters from the string..
if(extension=="png" || extension=="gif"){ //add to the listwidget
//item->setText(file1);
ui->listWidget->addItem(file1); //use the addItem overload see the link
}
}

Link (http://doc.qt.nokia.com/latest/qlistwidget.html#addItem)

[Lykurg]

and i would add remove the heap allocationsHave you? You don't see it in your code but:
void QListWidget::insertItem(int row, const QString &label)
{
Q_D(QListWidget);
d->listModel()->insert(row, new QListWidgetItem(label));
}
And as you might guess, addItem is just a convenient function for insertItem, so you could at least save one function call by using insertItem direct. But the real problems, to point them out, are in the takeAt() like, the "incorrect" use of mid(), the loop itselfs...

[hakermania]

Thx both for the replies!
I removed it, and, actually, this isn't the problem. I tried with 57 urls and it takes around 7 seconds to add them(!)
And, the code posted is the only code inside the function... I begin to believe that string comparison takes too long?

[Lykurg]

Well I don't will write you the code but, wouldn't it be smarter to check the extension first, before removing something from the front? (Just came now in my mind...)

[hakermania]

Thanks, you're right, just did it:


for(int i=1; i<=event->mimeData()->urls().length(); i++){
QUrl url = event->mimeData()->urls().takeAt(i-1);
QString file2 = url.toString();
QString extension = file2.right(3);
if(extension=="png" || extension=="gif"){
QString file1 = file2.mid(7,file2.length()-2);
ui->listWidget->addItem(file1);
}
}

I removed the string comparison for testing and it's the same without it, so it hasn't to do with it....hmmm...

[Lykurg]

Ok, next, have a look at the sources of QMimeData::urls() and decide if it is a wise decision to call it all over again and again...

[tbscope]

It sure is not a good idea (a serious flaw indeed) to alter a list inside a loop where one of the loop parameters is based on that list.
In other words, do not call a list size when you change that list inside the loop! Nasty things happen.
(Might not be related to your problem though)

[wysota]

Line #3 removes an item from a copy of the list that is immediately discarded. I don't know if that's relevant, what it is supposed to do and why you start iterating from 1. It's surely not very optimal. And I would like to know how come you deduced this loop takes three seconds to execute.

[Sven]

Try this :



QList<QUrl> urlList = event->mimeData()->urls();

for (QList<QUrl>::const_iterator i = urlList.begin();
i != urlList.end();
i++)
{
QString strFile2 = (*i).toString();
if (strFile2.endsWith(".png") || strFile2.endsWith(".gif")) {
QString strFile1 = strFile2.mid(7, strFile2.length() - 2);
ui->listWidget->addItem(strFile1);
}
}

[Lykurg]

Try thisWe should encourage people to think about problems and to came up with a solution of their own. There is no benefit of simply paste a better code/solution. Furthermore, can you explain me the meaning of subtraction of 2 in this line:
QString strFile1 = strFile2.mid(7, strFile2.length() - 2);?

[Sven]

We should encourage people to think about problems and to came up with a solution of their own. There is no benefit of simply paste a better code/solution. Furthermore, can you explain me the meaning of subtraction of 2 in this line:
QString strFile1 = strFile2.mid(7, strFile2.length() - 2);?

Ok I have looked into the code again and i see that this makes no sense. For example we have got:


http://mycoolwebsite.de/image.png/
http:// -> 7


So , i guess he wants to remove the http:// and the extension ?
If so, that

QString strFile1 = strFile2.mid(7, strFile2.length() - 2);

makes no sense. Maybe this solution would be better: (we have checked already for .png and .gif, so this should be correct)


QString strFile1 = strFile2.mid(7, strFile2.lastIndexOf("."));

[Lykurg]

To say it: First parameter indicates the starting point, last the length of the "resulting" string, so strFile2.length() - 2 is too long since only strFile2.length() - 7 left. Thus one should simply pass -1 as a last parameter. That is what I was trying to tell. Furthermore QString::remove() is probably better for his intention - I guess.

[hakermania]

Thank all of you, Sven's solution worked, but Lykurg's right, I don't understand why the code provided is better than my first posted, so i really want to understand my mistake in order to avoid it to the feature?

[d_stranz]

Here's your original code:



for(int i=1; i<=event->mimeData()->urls().length(); i++){
item=new QListWidgetItem;
QUrl url = event->mimeData()->urls().takeAt(i-1);
QString file2 = url.toString();
QString file1 = file2.mid(7,file2.length()-2); //removing some things I don't want
QString extension = file1.right(3); //taking last 3 letters from the string..
if(extension=="png" || extension=="gif"){ //add to the listwidget
item->setText(file1);
ui->listWidget->addItem(item);
}
}




I don't understand why the code provided is better than my first posted, so i really want to understand my mistake in order to avoid it to the feature?


And so you're saying you still don't understand why it runs so slowly?

OK, others have pointed this out, but maybe it wasn't clear. Aside from all the strange stuff you are doing to the string once you get it out of the URL, the main reason why your original code runs slowly is this:


event->mimeData()->urls()

You're calling this string of methods *twice* for every time through the loop, once when counting the length of the urls in the for statement, and again when you retrieve the QUrl.

You're making three method calls in that single line: retrieving the mimeData from the event, then retrieving the urls from the mimeData, then doing something with the urls (like getting the length or a specific URL).

One (or more) of those three calls is very time intensive. Maybe it's getting the mimeData from the event, maybe it's parsing the mimeData to retrieve the URLs. Doesn't matter. It's the cause of the slowness. String manipulations and comparisons are blindingly fast compared to that.

What does matter is that information is what is called "loop invariant". It is essentially a constant for the entire duration of the loop. So, move it outside the loop as Sven first suggested. Then, you retrieve the mimeData from the event exactly once, and you parse the mimeData into the urls exactly once, and all the rest of the loop simply deals with the urls collection. If I were writing it, I'd even retrieve the urls length into a local variable (int nUrls = urls.length()) and use that as the loop termination condition instead of calling length() repeatedly. I'd also use a more descriptive name for the loop iterator (instead of a generic "i") so that next time I read the code, it is clear to me that I am iterating over urls and not something else.



const QList<QUrl> & urlList = event->mimeData()->urls();
int nUrls = urlList.length();

for ( int nUrl = 0; nUrl < nUrls; nUrl++)
{
// ...
}


Hope this helps. No flames please from those who would complain that I'm "doing someone's homework". I think the OP really doesn't understand why his original code is slow despite all the other help.

[nightghost]

I also like foreach (http://doc.qt.nokia.com/latest/containers.html#the-foreach-keyword) because its easy to use, avoids unnecessary copying and very readable and the performance is ok (http://labs.qt.nokia.com/2009/01/23/iterating-efficiently/):



foreach(const QUrl& url, event->mimeData()->urls()) {
//work
}

[kornicameister]

As the documentation says
Qt automatically takes a copy of the container.

So make me correct, but isn't foreach loop something useful when iterating through the container holding pointers not entire objects, because in other way we use 2 times original_container_size amount of memory ?

[wysota]

As the documentation says .

So make me correct, but isn't foreach loop something useful when iterating through the container holding pointers not entire objects, because in other way we use 2 times original_container_size amount of memory ?

It depends on the container. All Qt containers are implcitly shared so only a shallow copy of the container is made, the real data is not copied. If you create your own container (or use some 3rd party code) that doesn't share data between its copies then foreach will cause an immediate overhead in both memory and time because the container will have to be copied.