On 02/09/2015 09:54 AM, Smith Martin wrote: > > "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."
IMHO: A lot of this is information you find in a CS course or in a book. Not in the Qt documentation. That said, there is certainly room for more info on performance impact in the Qt documentation. The discussion a while ago about what calls removes the effect of reserve() was one example. Bo. > ________________________________________ > 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 > Bo Thorsen, Director, Viking Software. -- Viking Software Qt and C++ developers for hire http://www.vikingsoft.eu _______________________________________________ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development