[Qgis-developer] STL vs. Qt containers

[Martin Dobias]

Hi Mateusz,

thanks for your mails. I'll try to address them all here.

To note first, I'm not much an enthusiast of standard C++ library and
I know just a small part of it. Therefore please excuse my claims
about STL if they are wrong :-)

I've found an interesting (and very similar) debate on kdevelop
mailing list where two sides argue about the usage of STL:
http://lists.kde.org/?t=114531790700001&r=1&w=2
(starting at about 5th mail or so)

Another thread (on Qt4-preview-feedback) mailing list there are
reasons of creating / using Qt containers by some Trolltech
developers:
http://lists.trolltech.com/qt4-preview-feedback/2004-09/msg00019.html


On 10/29/06, Mateusz Loskot <mateusz at loskot.net> wrote:
> > -- STL --
> >
> > std::list<int> lst;
> > ...
> > std::list<int>::iterator it;
> > for (it = lst.begin(); it != lst.end(); it++)
> -----------------------------------------^^^^^^
>
> It's a bad idea to use post-increment with iterators!

Actually, why is it a bad idea?

> First, in this particular example following should be preferred
> for best performance and optimization:
>
> std::list<int>::const_iterator end = lst.end();
> for (std::list<int>::const_iterator it = lst.begin(); it != end; ++it)

Well, lst.end() is a constant operation, isn't it?

Honestly, what time savings can we get with the optimization shown
above for e.g. one milion items? 1 milisecond - or more?

With time and some programming experience I tend to use these rules:
1. Don't optimize
2. If it's slow, profile it and optimize it at high-level

> Finally, what's simpler and less error prone comparing to this?
>
> std::copy(lst.begin(), lst.end(),
>           std::ostream_iterator<int>(std::cout, "\n"));

Sorry but for me this is nearly unreadable without an explanation what
does it do. I know that's just my ignorance of learning the C++
library, but consider that great amount of people don't know from it
much more than just basic usage of iostreams, strings, lists and
vectors.

> > -- Qt --
> >
> > QList<int> lst;
> > ...
> > QListIterator<int> it( lst );
> > while ( it.hasNext() )
> > {
> >  std::cout << it.next() << std::endl;
> > }
>
>
> Unfortunately, after I've read Trolltech's doc about their containers, I
> have to say there is quite much of FUD.
> Second, even they point that Java iterators are expected to be slower:
>
> "They are more convenient to use than the STL-style iterators, at the
> price of being slightly less efficient"

Yes, I've read that also. It might be interesting to see how much goes
the performance down with them... But IMHO it's quite a problem to do
a good benchmark that would test all important things. Also it may
give different results for different OSes.

> For me, the FUD are statements like "more convenient to use".
> Why Trolls compare their containers with STL containers only?
> It's a wrong approach from the basis.

Maybe I haven't understood your note, but to which containers other
than STL should they compare it?

> STL, a part of C++ Standard Library, is *not* only a set of containers!
> It's very *incorrect* to talk only about STL containers and how they
> are cool or not.
> STL is the _whole_system_ of types and operations:
> container + iterators + algorithms + allocators.
> STL design, concepts, interface and performance should be analyzed
> including all these 4 types of STL elements.
>
> Why STL iterators interface is defined as it is?
> Because iterators are indirection layer that makes it possible to
> operate on containers using common algorithms definition.
> The main idea here is to provide deep interface consistency with
> very good performance.

You're right. But all this great stuff is useless when people don't
tend to use it extensively.


> One controversial question comes to my mind, why not to switch to Java
> completely if STL interface is considered as hard and error prone?
> I'm sorry, but it's hard to understand for me.

I'm not saying that STL is hard and error prone, I just say that Qt
stuff is simpler and easier to learn and use. And that's just "IMHO",
a matter of taste.


> > But my primary idea is to decide which type of containers to adapt (or
> > at least which type for public API), because now we use both STL and
>
> I agree, consistency is important.

So what's your opinion on how to achieve API consistency?


On 10/29/06, Mateusz Loskot <mateusz at loskot.net> wrote:
> I'd like also to suggest to measure performance of QT and STL containers
> with basic algorithms.
>
> What QT is supposed to be used, 4.1 or 4.2?

Qt 4.1 for 0.8 release, Qt 4.2 or higher for next releases (because of
QGraphicsView).
Maybe Qt 4.2 could be set as minimal version also for 0.8 as it fixes
some bugs from the 4.1.x series.

> For example, in QT 4.1 there is no QSet::find algorithm,
> so iterator-based searching is
> - 16 times slower in searching for present value (100000)
> - 56 times slower in searching for not present value in a set (600000)
>
> // myqset contains values from 0 to 399999
> int n = 0;
> int idle = 100000;
> QSet<int>::const_iterator end = myqset.end();
> for (QSet<int>::const_iterator it = myqset.begin(); it != end; ++it)
> {
>    if (idle == *it)
>       n = *it;
> }

Ok, let's say that in Qt4.1 there's no find() function. But is it
really that necessary? You can always use contains() to see whether
the object is in the set. You just don't get the iterator.


> If QGIS is supposed to work with all QT 4.x versions, then it's
> required to use old API, compatible with all versions and it's not
> possible to use ie. QSet::find algorithm.
> That may increase performance significantly and 4.2 users won't be able
> to use new and robust versions because QGIS needs to work with QT 4.1, etc.
> Such problems does not exist if STL is used.

However, do you see any places in QGIS code that would benefit from
using QSet::find() function?


> I'm just trying to point as much issues as possible, that I believe
> should be considered before making decision to move to QT containers
> completely.

That's right - it's good to hear all pros and cons.

> I think, simple voting is a bad idea :-) because it's about engineering,
> so measurements are the only way to select one solution over another.

I think it's more about the preferences as both libraries provide set
of classes (templates) good enough to use in QGIS. If Qt containers
were not performing well, why would they use it in whole Qt?


On 10/29/06, Mateusz Loskot <mateusz at loskot.net> wrote:
> Martin Dobias wrote:
> > For these new containers there's no such note that it's good only for
> >  platforms without STL.
>
>
> Martin,
> Can you point a platform with C++ compiler that does not support
> C++ standard library?

No I can't. But there must have been some compilers with poor C++
standard library, otherwise Trolls wouldn't create own classes. But my
comment was intended to be a comparison between Qt3 and Qt4.

Of course it has no importancy for us as platforms we support all have
at least GCC with its c++ library.


On 10/29/06, Mateusz Loskot <mateusz at loskot.net> wrote:
> Martin Dobias wrote:
> > But second, more important - why to do that? QGIS is based on Qt. Once we have
> > such dependency why not to use it extensively? My opinion is that
> > converting some code to be Qt-independent wouldn't bring any benefits
> > - Qt also works as compatibility layer between the platforms. Why to
> > loose it?
>
> Because may be potential performance decrease?
> If QT containers are so great why I can't find any benchmarks?
> OK, there are some on QT lists, but these benchmarks are very poor.

Once more, I trust the guys at Trolltech that they wouldn't ship
poorly performing classes. At least not for Qt4 which had long time to
evolve from earlier versions.



On 10/29/06, Mateusz Loskot <mateusz at loskot.net> wrote:
> Martin Dobias wrote:
> > Qt containers also have java-like iterators which are simpler to use.
> > Besides this, they have generally the same functionality.
>
> Martin,
>
> Even if Trolls are warning you these iterators are slower than any other
> way to access container elements, are you going to use them?
> Just because of difference between (*it) and it.next() ?

I mention java-style operators as an alternativePersonally, I'm not
much in favour of them, but some people might like them more. Another
alternative is the "foreach" keyword. With STL you don't have such
alternatives, do you?

> Honestly, Java-like iterators are not so easy.
> What about the side effect in it.next(), is this still clear for you?
> This operation results in 2:
> - move iterator to next element
> - return current element

Yes it's clear to me.

> Now, Java iterator dereferencing does 2 things together and I strongly
> believe that C++ users may have problems with understanding it well.
> For example C++ coders may try to do something like this:
>
> int res = 0;
> QListIterator<int> i(list);
> while (i.hasNext())
> {
>      res = i.next() / (2 * i.next()) ...
> }

It's all about understanding that java-style iterators work as if they
were always between the values. So if someone doesn't understand well
the principle, he doesn't have to use it.



> Next, construction of Java-like iterators is error prone.
> Consider this:
>
> QList<QString> list;
>
> ...
>
> // 100 lines of code later
> QListIterator<int> i(list);
>
>
> Where with STL, you *can not* do this bug because well-designed
> container API. Container iterator is closely tight with container type,
> and this type is not std::list but std::list<T>.
> This obvious rule in C++ is broken with QT Java-like iterators.

Are you sure with it? I've made a simple example file:

#include <QString>
#include <QList>

int main()
{
  QList<QString> list;
  list.append("x");
  QListIterator<int> i(list);
  return i.hasNext();
}


When trying to compile it, gcc gives me errors:

x.cpp: In function `int main(int, char**)':
x.cpp:11: error: no matching function for call to
`QListIterator<int>::QListIterator(QList<QString>&)'
/usr/include/qt4/QtCore/qlist.h:637: note: candidates are:
QListIterator<int>::QListIterator(const QListIterator<int>&)
/usr/include/qt4/QtCore/qlist.h:637: note:
QListIterator<T>::QListIterator(const QList<T>&) [with T = int]

So I would say they care about the types in iterators. Or did you mean
something different?


Hopefully I've answered all your questions, it's your turn ;-)

bye,
Martin