[Development] The future of QtAlgorithms

[João Abecasis]

Hello everyone,

[ The topic at hand was discussed on IRC this morning. Thiago agreed on
the general idea/concept. We also agreed on bringing the discussion to
the list. ]

Qt has historically offered some common algorithms, arguably a very
limited but still useful subset of what is available in the C++ Standard
Library. One of the reasons for this was to allow their use inside the
Qt libraries, which need to compile when QT_NO_STL is defined and the
standard library isn't available.

I'm talking about QtAlgorithms.

While the intention is good and people do appreciate the warm and fuzzy
feeling brought by the camel-casing and the q* prefix (honest!), the
current situation hurts Qt and our users more than it helps. Let me
explain.

[Note: this may get long and winded. Feel free to skim and skip to the
proposal at the bottom]


1) Performance

The algorithm implementations are generally sound and good, and the
big-Ohs should match what is commonly available in standard libraries.
The real performance, however, suffers and is falling behind. Even more
so as standard library implementors have been exploiting new language
features and compiler hooks to get the best performance they can out of
(mostly) generic implementations.

[See also: http://codereview.qt-project.org/#change,13866 and the bugs
mentioned there]


2) Fragmentation

Ignoring or fixing issue 1) is not the end of the story. Whatever we do,
         algorithms in QtAlgorithms and the ones in the standard library
         are islands and the more QtAlgorithms is used, the more they
         diverge. The issue are subtle technical differences:

    - qSort, by default, relies on:
        - qLess for comparisons (which defaults to operator<)
        - qSwap for swapping values

    - std::sort, by default, relies on
        - operator<
        - std::iter_swap / std::swap / ADL-swap (it's complicated ;-)

Users have to decide which side of the fence they stand on, or duplicate
effort to maintain and support both routes.

Inside Qt, however, we have little choice:

     - we litter our code with #ifdef QT_NO_STL to be able to use the
       better std counterparts;
     - or, we stick to the crippled qCamelCase versions.

We have so far stuck with the latter option.

In effect, by supporting an alternative, instead of helping use cases
that don't have access to a proper standard library, we adversely effect
Qt and all its users.


3) Maintenance effort

Realistically speaking, we have limited resources and need to prioritize
which work gets done. I don't think it's fun to play catch up with the
standard library, particularly so when it is right there for most to see
and use and it is pretty damn good when it is there!

In practice, QtAlgorithms has seen little maintenance or improvements,
despite known performance issues in the implementation.


4) Long-term plan

What is the long-term plan for QtAlgorithms?

According to the documentation, it has no intention to replace or
compete with the standard library:

    [quoting from a recent qalgorithm.qdoc]

    “ These functions have taken their inspiration from similar
    functions available in the STL \c <algorithm> header. Most of them
    have a direct STL equivalent; for example, qCopyBackward() is the
    same as STL's copy_backward() algorithm.

    If STL is available on all your target platforms, you can use the
    STL algorithms instead of their Qt counterparts. One reason why you
    might want to use the STL algorithms is that STL provides dozens and
    dozens of algorithms, whereas Qt only provides the most important
    ones, making no attempt to duplicate functionality that is already
    provided by the C++ standard. ”

Albeit slowly, the standard library is evolving. TR1 came out in 2003,
C++11 is fresh out and the Standard Committee has expressed intent to
put out revisions of the standard in shorter cycles. (There was also a
TR2 being worked on, I don't know if that is still coming out on its
own.)

Personally, I don't think if fits Qt's or (its users) interests to
compete or undermine the language and standard library we build upon. So
the only long-term plan I see is to encourage and empower users to move
over to using what is in there.


=== THE PROPOSAL ===

(Thanks for reading/skimming/skipping this far ;-)

- Leave QtAlgorithms as is, mark everything (except qDeleteAll)
deprecated since 5.0

- Provide standard-compliant implementations of the algorithms in
QtAlgorithms (no 'q' prefixes, no camel casing -- sorry!) and
selectively import those into a known namespace when QT_NO_STL is
defined:

    namespace QtPrivateStd {
    #ifdef QT_NO_STL
        using namespace std;
    #else
        using namespace QtPrivateStlImpl::std;
    #endif
    }

Utilities in QtPrivateStlImpl would be based on what is already in
QtAlgorithms, changed to syntactically and semantically match the
standard library.

- Fix Qt's code to redirect through QtPrivateStd, and ensure everyone
gets the best possible features when using a proper standard library.


Thoughts? Comments?


João