"In the vast majority of cases, a sorted vector is much faster, due to locality-of-reference. A RB-tree is optimized for wildly mixing insertions, lookups, and removals. When you can batch updates and separate them from lookups, time-wise, then a sorted vector is usually preferrable."
This is the kind of thing we should add to the documentation, but can you elaborate? I mean, illustrate the meaning of "locality of reference," "wildly mixing insertions, lookups, and removals," and "batch updates and separate them from lookups, time-wise." martin ________________________________________ From: development-bounces+martin.smith=theqtcompany....@qt-project.org <development-bounces+martin.smith=theqtcompany....@qt-project.org> on behalf of Marc Mutz <marc.m...@kdab.com> Sent: Sunday, February 8, 2015 2:28 PM To: development@qt-project.org Cc: Thiago Macieira Subject: Re: [Development] Upgrading the sources to C++11 keywords (Q_NULLPTR, etc.) Hi, Sorry for being late, didn't see the thread before. On Thursday 08 January 2015 23:33:34 Thiago Macieira wrote: > I think it's time to institute a policy that we should fix our sources to > use the new C++11 keywords. I'd like to propose the following. I totally agree, with the following amendments: 1. override - before adding an overriding function to a class, add Q_DECL_OVERRIDE to all members in a separate commit, to avoid said warning. 2. noexcept/nothrow - the only difference between the two is that nothrow may expand to throw() on compilers that implement semantics close to noexcept for that, and not the C++98 standard behaviour. This is currently only the case for MSVC, even though I believe GCC has a switch to emulate MSVC here. The semantic difference currently, is: when you violate noexcept, you're getting C++11 behaviour (std::terminate is called) or the exception leaves the function. If you violate nothrow, you're enterin undefined bahaviour. So only use nothrow if functions _cannot possibly_ throw. If you want to say "I'm fine with errors in this function terminating the process", which you should be very carefully considering (it should be the exception), you must use noexcept instead. Obviously, if you need conditionally-noexcept, you must use noexcept_expr. Talking about warnings: there's -Wnoexcept, which warns when a conditionally-noexcept function turns noexecpt(false) because of a function that isn't marked noexcept and where the compiler can prove it doesn't throw. That's a bit of a mouthful, but this, too, should be added to the headersclean check. Talking about narrow contracts: A function has a narrow contract if it has preconditions (on it's arguments, or *this). If you have preciditions, you may, in debug mode, assert them as an aid to the user of your function. Assertions may be turned by the user (there's also a movement behind John Lakos, yes, _the_ John Lakos that essentially gave us the d-pointer, to make this standard functionality), into exception throwing (which I had personally good experience with during Kleopatra development). But if your users do this, they expect to receive those exceptions, and not terminate the program without a hint that an assertion was triggered). That's why functions with narrow contracts should not be noexcept. Aside: of course, you can often drop preconditions by tightening the interface of the function. E.g. instead of taking a naked pointer, you could take a non_null_ptr<T>, which would explode when constructed with a nullptr, thus making sure that every successfully constructed instance is actually representing a non-null pointer. Another technique is to use enums, because the standard says that you cannot load a value from an enum variable that does not correspond to one of the enumerated values. Doing otherwise constitutes undefined behaviour, and compilers are getting oh-so- good at exploiting UB that your only chance is to learn about and avoid them. 3. nullptr - On top of the warning, which I wasn't aware about, I find the code easier to read. It's a mouthful, but it's what everyone will be using five years from now, so we might as well start it now. I treat this as a whitespace error, meaning I correct it whenever I touch a line of code for unrelated changes. I would add the following, unrelated to C++11, but found all over the place in Qt, and it's next to impossible to root out: Algorithmic ineffciency. That's a large blob, but the most important instances of it are: a. Not marking types as movable or primitive. We might actually want to have a policy to mark complex types explicitly as complex, to allow easier fixing of missing declarations. The rule here should be that every new class or struct that may at some point be held in a container must have a q_declare_typeinfo. Rationale: it's impossible to add them after release, since changing the typeinfo changes the memory layout of QList, making the change BIC. b. Using QLists when they are not optimally efficient. For a QList to be optimally efficient, the type T must be movable (or primitive) and sizeof T == sizeof (void*) (yes, different on 32 and 64-bit platforms!). For a QList to be acceptable (actually, it's not, but it's at least not horribly inefficient), replace == sizeof(void*) with <= sizeof(void*). The rule should be that you need to accompany any use of QList that isn't already mandated by existing APIs (QList<QVariant>, say), by a static_assert that QList is optimally efficient. There are patches in the pipeline to make this easier than checking QTypeInfo yourself. Of course, when QList is not efficient, you should use a QVector instead. c. Using QMap. As Alex Stepanov put it: every use of a map should be discussed in a face-to-face meeting with your manager. Since we don't have that, I'd change this to: Everyone wishing to use a QMap should implement one before using it for the first time. Then you'd see what you inflict on the world. In the vast majority of cases, a sorted vector is much faster, due to locality-of-reference. A RB-tree is optimized for wildly mixing insertions, lookups, and removals. When you can batch updates and separate them from lookups, time-wise, then a sorted vector is usually preferrable. d. Algorithmic complexity. Avoid O(n²) like the plague. Anthing worse than that should get a big fat comment saying why it's necessary (like: this optimisation algorithm is equivalent to the knapsack problem, so I need to use this exponential algorithm, because a) we need the global optimum, not a local one, and b) the set is always less than four elements. I could go on and on with this. Like using a set for de-duplication, then converting to a list and sorting that (because, surprise, QSet is std::unordered_set), but there's really no substitute to understanding what you're doing and no set of rules, however large, will give you that. Using std algorithms would, though, as far as they go. I'm sorry, this has become so much longer than planned... Thanks for reading up to here. May your code be the better for it, Marc -- Marc Mutz <marc.m...@kdab.com> | Senior Software Engineer KDAB (Deutschland) GmbH & Co.KG, a KDAB Group Company www.kdab.com || Germany +49-30-521325470 || Sweden (HQ) +46-563-540090 KDAB - Qt Experts - Platform-Independent Software Solutions _______________________________________________ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development _______________________________________________ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
