Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Monday 20. July 2015 14:53:04 Knoll Lars wrote: Yes, I think pretty much everybody agrees that QList does not work as advertised. In the ideal case it’s performance is about as good as a QVector, in most other cases (with a few exceptions) it’s a lot worse. So Marc is completely right that we should be using QVector by default in any new code and in our implementations (as long as we don’t need QList compatibility with existing API). Thanks for clarifying. I would just like to have another clarification: How about new API that should return or take lists as parametter? Should we use QVector, or should we keep using QList for consistency. (As for example in https://codereview.qt-project.org/112105/ ) ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Monday 20 July 2015 16:53:04 Knoll Lars wrote: Most likely, we should change QList in Qt 6 to simply share it’s implementation with QVector and make them both compatible, but we unfortunately can’t do this right now. I'd rename it QArrayList and have it always operate in new'ed-up-items mode. That container is not available from the STL (though vectorunique_ptr comes close), so I'm ok with keeping it. But then it must _always_ new up items, even bools, otherwise you again can't rely on reference stability. If you want a vector, use a vector. Don't call a vector a list. Yes, that's going to be massively SiC, but by Qt 6, we can hopefully rely on template aliases to mitigate that problem (so a backwards-compatibility QList could be an alias for vector for types for which it basically is now (modulo padding), and QArrayList otherwise). My .02€ -- Marc Mutz marc.m...@kdab.com | Senior Software Engineer KDAB (Deutschland) GmbH Co.KG, a KDAB Group Company Tel: +49-30-521325470 KDAB - The Qt Experts ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
Let’s at least fix the docs. It won’t keep people from choosing QList because the type is so pervasive in Qt’s API, but at least we’re then giving better advice. https://codereview.qt-project.org/#/c/121674/ martin From: development-bounces+martin.smith=theqtcompany@qt-project.org development-bounces+martin.smith=theqtcompany@qt-project.org on behalf of Knoll Lars lars.kn...@theqtcompany.com Sent: Monday, July 20, 2015 4:53 PM To: Giuseppe D'Angelo; development@qt-project.org Subject: Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO On 13/07/15 10:34, Giuseppe D'Angelo giuseppe.dang...@kdab.com wrote: Il 12/07/2015 23:19, Alejandro Exojo ha scritto: El Sunday 12 July 2015, Thiago Macieira escribió: On Sunday 12 July 2015 16:16:07 Smith Martin wrote: I can see by your explanation that QVector is almost always more efficient than QList. But sometimes the difference doesn't matter. If it doesn't, then why not choose QVector? I've carefully read the thread, and I think the issue Martin or others might have is: * Documentation and the common know how about Qt containers tells that QList is a reasonable middle ground choice (sometimes is like a vector, sometimes like a linked list/vector hybrid). Is what the docs say, what the Qt Quarterly article says (which is old, but Olivier gave a recent explanation on containers on 2012's devdays), what is being used in the API as return type, etc. Nitpicking: it's never like a linked list. It's either an array of T or an array of T*. Access is always O(1) (with potentially a big factor hidden due to the indirection), insertion in the middle always O(N) (with potentially a smaller factor than QVector, esp. for big Ts, due to the indirection), etc. Then, yes, QList is the recommended generic sequential container, and the one used all around in Qt APIs. And that's the problem which started this discussion. Yes, I think pretty much everybody agrees that QList does not work as advertised. In the ideal case it’s performance is about as good as a QVector, in most other cases (with a few exceptions) it’s a lot worse. So Marc is completely right that we should be using QVector by default in any new code and in our implementations (as long as we don’t need QList compatibility with existing API). Most likely, we should change QList in Qt 6 to simply share it’s implementation with QVector and make them both compatible, but we unfortunately can’t do this right now. * Marc has been criticizing what the docs says, but even being a significant contributor to Qt, did not propose to change that. And I actually disagree with that, given that QVector is faster than QList in the majority of the cases (and std::vector could be even faster and/or expand to less code). Having false statements in the docs is not good. I would like to see them changed. Yes, we can’t complain about people using Qt wrongly (and even our own developers and contributors), if our docs are wrong. Let’s fix them to say that you should use QVector if possible and not QList. * According to Martin's explanations, he did send a patch for qdoc that replaced a wrong choice of container, but the change did not have any apparent effect. Which has been pointed out to be irrelevant to the purposes of this discussion (I have no idea of qdoc internals, has anyone profiled it? Maybe 99% of the time is spent on I/O or parsing C++ files and QVector over QList gives an advantage in nanoseconds for that particular use case?). But the totality of the other points in the first message stay, and noone has so far challenged them... * We are having a large thread with a heated discussion, and Marc said things like and the resulting code will be highly fragile and/or extremely inefficient. People might felt a bit offended by that. Is something being said about their work, after all. Please do not make this an ad-hominem. It's an argument about the code. When you spot an unwarranted usage of a QList in some code, what it is about? Pick: A) Premature pessimization (you could've used QVector instead, but you picked QList because it's the default container -- it's documented that way!) B) You want amortized fast prepend C) Your type is bad and you want to rely on validity of references when the container gets modified (There's no I want to call a function taking a QList because that's totally justified). Experience tells that you're in A) 99% of the time (extremely inefficient). B) or C) count for highly fragile, because you may break the code (or make it way more inefficient) by refactoring it. We've had cases of that. IIRC, this was a case of C) (refactoring from QList to QVector): https://codereview.qt-project.org/#/c/10878/9/src/corelib/kernel/qcoreapp lication.cpp To summarize: I not sure whether you (plural) think that no container should be advised as the preferred one, or if it should
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Monday 20 July 2015 22:01:01 Marc Mutz wrote: I'd rename it QArrayList and have it always operate in new'ed-up-items mode. That container is not available from the STL (though vectorunique_ptr comes close), so I'm ok with keeping it. But then it must _always_ new up items, even bools, otherwise you again can't rely on reference stability. Agreed, but we may need a better name. Array list is kind of a redundant. We could bring back a Qt3 name like QPtrList, though QPointerList might confuse with a list of QPointer. Anyway, name bikeshedding for the future... If you want a vector, use a vector. Don't call a vector a list. Yes, that's going to be massively SiC, but by Qt 6, we can hopefully rely on template aliases to mitigate that problem (so a backwards-compatibility QList could be an alias for vector for types for which it basically is now (modulo padding), and QArrayList otherwise). Yup, makes sense too. Note that template aliases have a weird and slightly unexpected side-effect: a specialisation of one does not imply specialisation of the other. And that, of course, is not properly implemented in compilers of today. We'd need to properly investigate things like QVectorQString and QListQString and how to deal with their special methods. -- Thiago Macieira - thiago.macieira (AT) intel.com Software Architect - Intel Open Source Technology Center ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Fri, Jul 17, 2015 at 12:07 PM, André Somers an...@familiesomers.nl wrote: Marc Mutz schreef op 17-7-2015 om 12:21: What might also be a consideration when making a container like this, is that I find the key is often (not always of course) already part of the value data structure. For instance, if I store employee records and key them by id, that id is also in the record itself. It would be nice to have a fast and friendly key-based container that could handle that without duplicating the data... You can have that with C++11 std::*set, and a custom transparent comparator, but of course, they are not cache-friendly. But it's testament to the value of having the ability to _have_ a custom comparator. QFashHash consequently has that ability, but its a map, not a set, so it won't fit your use-case. I guess this [1] would work, but that is C++14, not 11. Otherwise, I don't quite see how to retreive my Employee record again if I just have the id... André [1] http://en.cppreference.com/w/cpp/container/set/find variants 3 and 4 You can use std::find_if for that on any container. Works for C++11 and even before that. C++11 gives the benefit of using a lambda in the std::find_if UnaryPredicate. ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
Mark Gaiser schreef op 17-7-2015 om 13:44: You can use std::find_if for that on any container. Works for C++11 and even before that. C++11 gives the benefit of using a lambda in the std::find_if UnaryPredicate. Sure, but wouldn't that revert you back to a linear search? That sounds like getting the worst of both worlds: using a complicated red/black tree data structure and then iterating over it lineary to find an item that I could have found using the structure itself in logarithmic time... Or am I overlooking some very clever specialization in the find_if algorithm then? André ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Fri, Jul 17, 2015 at 2:13 PM, André Somers an...@familiesomers.nl wrote: Mark Gaiser schreef op 17-7-2015 om 13:44: You can use std::find_if for that on any container. Works for C++11 and even before that. C++11 gives the benefit of using a lambda in the std::find_if UnaryPredicate. Sure, but wouldn't that revert you back to a linear search? That sounds like getting the worst of both worlds: using a complicated red/black tree data structure and then iterating over it lineary to find an item that I could have found using the structure itself in logarithmic time... Or am I overlooking some very clever specialization in the find_if algorithm then? André Yes, that would give you linear search indeed. Guess you have to use that C++14 function then :) ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Thursday 16 July 2015 23:09:55 Gunnar Roth wrote: So I deduce from this test that for a container with up to 100 elements , std::vector is the best choice , if you want fastest lookup, but Vector should be avoided. For larger container QHash should be used for best lookup performance. It is not surprising that big-O _eventually_ wins. The point is that that eventually != always. Few collections in Qt will have more than 100 elements, and then, not all the time. Binary search is not very cache-friendly, because it exhibits a semi-random memory access pattern that the hardware has trouble predicting. If you want to see what I and others mean when we say that the node-based containers are slow, iterate over the containers. Search in large collections is what hash tables and rb-trees are optimized for, and of course they eventually win, with ever larger collections. But most collections are also iterated over, and then you better not have a node-based container in front of you if you do. Related: there's a similar benchmark to yours, container_benchmark.cpp by Stroustrup and Stepanov, which performs duplicates removal using different containers. It hasn't been updated since 2003, but it's easy to add new tests. I already posted a link in this thread, but google will find it, too. I've attached my local version, which includes some Qt containers. Thanks, Marc -- Marc Mutz marc.m...@kdab.com | Senior Software Engineer KDAB (Deutschland) GmbH Co.KG, a KDAB Group Company Tel: +49-30-521325470 KDAB - The Qt Experts /* Standard Container Benchmark Version 0.9, May 23, 2003 The primary purpose of this benchmark is to show how different standard containers are in terms of performance. We have observed that programmers often use sets, multisets, deques in the situations where sorted vectors are the optimal solutions. Similarly, programmers often choose lists simply because they do a few insertions and deletions without knowing that vectors are more efficient at that for small containers. Frequently, of course, performance does not matter, but it is important that programmers are aware of the consequences of their choices. We are not saying that only vectors should be used, there are cases when one really needs a more complicated data structure, but one needs to understand the price for additional functionality. The secondary purpose of the benchmark is to encourage compiler and library vendors to keep improving performance. For example, it is not acceptable that some compilers give you a sizable penalty for using vector iterators instead of pointer. It is also quite clear that performance of other standard containers could be improved. The benchmark is doing the same task 7 times using different data structures: array, vector (using a pointer as iterator), vector (using the defailt cector iterator), list, deque, set and multiset. The task is to remove duplicates from a sequence of doubles. This is a simple test, but it illustrates the performance of containers. It is clear that the benchmark needs to be eventually extended to slists and even to hash-sets and hash-maps, but we decided that at present it should work only with the standard containers. As the standard grows, so can the benchmark. The additional benefit of not including hash based containers is that now all the test have identical asymptotic complexity and, even more importantly, do almost the same number of comparisons. The difference is only in data structure overhead and cache behavior. The number of times that a given test is run inversly proportional to NlogN where N is the size of the sequence. This allows one to see how containers of different size behave. The instructive values used for the benchmark are: 10, 100, 1000, 1, 10, 100. The time taken for a run of the benchmark depends on the machine used, the compiler used, the compiler and optimizer settings used, as well as the standard library. Please note that the time taken could be several minutes - and much more if you use a slow debug mode. The output is a table where columns are separated by tabs and rows by newlines. This is barely ok for a human reader, but ideal for feeding into a program, such as a spreadsheet for display or analysis. If you want to add your own test of a container, add the name of your container to the header string, write a test function like the existing ones, e.g. vector_test, and add a call of run for your test in run_tests. Alex Stepanov stepa...@adobe.com Bjarne Stroustrup b...@cs.tamu.edu */ #include stddef.h // some older implementations lack cstddef #include time.h #include math.h #include stdlib.h #include vector #include QVector #include algorithm #include list #include QList #include QLinkedList #include deque #include set #include iostream #include iomanip typedef double element_t; using namespace std; vectordouble
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Thursday 16 July 2015 23:09:55 Gunnar Roth wrote: About QFastHash: that is WIP. It's the very rudimentary beginnings of an open- addressing hash container (a hash container using consecutive memory, not nodes). What was the idea behind it? Is so much slower than any other that I can just see why anyone should want to have this? What is the advantage? The idea is to implement https://en.wikipedia.org/wiki/Open_addressing with linear probing, which theoretically should be more cache friendly than a node- based container (less memory overhead, cache-friendly probing). But I separated key and values into different containers, so even at optimum, you get two cache hits instead of one with QHash. As Ossi pointed out in the review, that's probably a pessimisation unless you have a very loaded container. Likewise, OptionalT, required to mark entries as empty or occupied, isn't optimized at all. all but doubling the space required for most keys because of the pairing with a bool. As I said, it's WIP. -- Marc Mutz marc.m...@kdab.com | Senior Software Engineer KDAB (Deutschland) GmbH Co.KG, a KDAB Group Company Tel: +49-30-521325470 KDAB - The Qt Experts ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
Marc Mutz schreef op 17-7-2015 om 11:09: On Thursday 16 July 2015 23:09:55 Gunnar Roth wrote: About QFastHash: that is WIP. It's the very rudimentary beginnings of an open- addressing hash container (a hash container using consecutive memory, not nodes). What was the idea behind it? Is so much slower than any other that I can just see why anyone should want to have this? What is the advantage? The idea is to implement https://en.wikipedia.org/wiki/Open_addressing with linear probing, which theoretically should be more cache friendly than a node- based container (less memory overhead, cache-friendly probing). But I separated key and values into different containers, so even at optimum, you get two cache hits instead of one with QHash. As Ossi pointed out in the review, that's probably a pessimisation unless you have a very loaded container. Likewise, OptionalT, required to mark entries as empty or occupied, isn't optimized at all. all but doubling the space required for most keys because of the pairing with a bool. As I said, it's WIP. What might also be a consideration when making a container like this, is that I find the key is often (not always of course) already part of the value data structure. For instance, if I store employee records and key them by id, that id is also in the record itself. It would be nice to have a fast and friendly key-based container that could handle that without duplicating the data... André ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Friday 17 July 2015 11:02:08 André Somers wrote: Marc Mutz schreef op 17-7-2015 om 11:09: On Thursday 16 July 2015 23:09:55 Gunnar Roth wrote: About QFastHash: that is WIP. It's the very rudimentary beginnings of an open- addressing hash container (a hash container using consecutive memory, not nodes). What was the idea behind it? Is so much slower than any other that I can just see why anyone should want to have this? What is the advantage? The idea is to implement https://en.wikipedia.org/wiki/Open_addressing with linear probing, which theoretically should be more cache friendly than a node- based container (less memory overhead, cache-friendly probing). But I separated key and values into different containers, so even at optimum, you get two cache hits instead of one with QHash. As Ossi pointed out in the review, that's probably a pessimisation unless you have a very loaded container. Likewise, OptionalT, required to mark entries as empty or occupied, isn't optimized at all. all but doubling the space required for most keys because of the pairing with a bool. As I said, it's WIP. What might also be a consideration when making a container like this, is that I find the key is often (not always of course) already part of the value data structure. For instance, if I store employee records and key them by id, that id is also in the record itself. It would be nice to have a fast and friendly key-based container that could handle that without duplicating the data... You can have that with C++11 std::*set, and a custom transparent comparator, but of course, they are not cache-friendly. But it's testament to the value of having the ability to _have_ a custom comparator. QFashHash consequently has that ability, but its a map, not a set, so it won't fit your use-case. -- Marc Mutz marc.m...@kdab.com | Senior Software Engineer KDAB (Deutschland) GmbH Co.KG, a KDAB Group Company Tel: +49-30-521325470 KDAB - The Qt Experts ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On 17 July 2015 at 11:02, André Somers an...@familiesomers.nl wrote: But I separated key and values into different containers, so even at optimum, you get two cache hits instead of one with QHash. As Ossi pointed out in the review, that's probably a pessimisation unless you have a very loaded container. Likewise, OptionalT, required to mark entries as empty or occupied, isn't optimized at all. all but doubling the space required for most keys because of the pairing with a bool. As I said, it's WIP. What might also be a consideration when making a container like this, is that I find the key is often (not always of course) already part of the value data structure. For instance, if I store employee records and key them by id, that id is also in the record itself. It would be nice to have a fast and friendly key-based container that could handle that without duplicating the data... Woah, a big +1 to that! ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Friday 17 July 2015 11:18:06 Marc Mutz wrote: On Friday 17 July 2015 11:00:49 Marc Mutz wrote: [...] I've attached my local version, which includes some Qt containers. [...] That version was some bitrot. Here's the one that works. It also varies the number of duplicates to be removed. The exact operation performed is sort | uniq This kind of benchmark, together with a nice visualisation, and more use- cases, is what I'd wish we had for our users. Here are the results of running it on a Core-i7 Sandy Bridge pinned at 2.4GHz, formatted as HTML. Excesss dups of 1 means no duplicates, 100 means 99% dups. It is instructive to look at the memory consumption, because the size printed is the size of the *reduced* container, so the largest container size is 100 million elements, 1% of which are unique, 99% dups. That's 800M in vector, qlist, qvector, deque, but _a lot_ more in std::list (2400M + allocator overhead, on my machine 3.8G of resident memory), set, and multiset (3200M + allocator overhead, on my machine 5.2G). Conseqently, don't run this without at least 6G of RAM or reduce the max. working set size. As you can see, the only algorithm that can hold up with std::vector+std::sort+std::uniue is QSet+QList+std::osrt, but only at very high number of duplicates (starts here for some medium sizes and 90% dups), and even at its best, it's only 3x faster than std::vector, while it can be an order of magnitude slower. I find it particularly interesting that at 100'000 elements and 99% dups, it's almost as slow as std::vector, and at 1'000'000 elements, slower again. -- Marc Mutz marc.m...@kdab.com | Senior Software Engineer KDAB (Deutschland) GmbH Co.KG, a KDAB Group Company Tel: +49-30-521325470 KDAB - The Qt Experts Title: Container Benchmark excess elements:1sizearrayvector with pointersvector with iteratorsqvector with pointersqvector with iteratorsdequelistqlistsetqset->qlistmultiset 100.070.070.070.110.120.180.510.140.380.710.42 1000.030.040.030.050.050.080.260.070.240.390.24 1.050.040.060.060.060.110.260.070.290.340.31 10.100.100.110.100.110.140.300.120.350.370.38 100.100.100.110.110.110.130.420.120.490.370.52 1000.100.100.100.110.110.130.590.270.840.820.93 excess elements:2sizearrayvector with pointersvector with iteratorsqvector with pointersqvector with iteratorsdequelistqlistsetqset->qlistmultiset 100.320.140.160.200.210.311.040.310.510.900.92 1000.060.070.070.100.100.160.560.140.310.490.58 1.180.180.180.200.200.290.590.240.490.450.71 10.230.220.240.240.240.300.680.260.630.430.85 100.220.220.220.230.230.291.080.260.860.431.37 1000.220.210.230.220.220.281.260.591.570.932.03 excess elements:5sizearrayvector with pointersvector with iteratorsqvector with pointersqvector with iteratorsdequelistqlistsetqset->qlistmultiset 100.700.310.320.470.460.692.510.700.791.402.65 1000.190.200.210.270.260.441.720.390.720.732.10 1.590.590.610.650.640.841.670.741.070.622.15 10.620.610.630.640.640.791.910.721.410.572.58 100.570.580.610.600.600.754.360.722.130.704.98 1000.570.590.590.600.590.733.841.643.871.136.27 excess elements:10sizearrayvector with pointersvector with iteratorsqvector with pointersqvector with iteratorsdequelistqlistsetqset->qlistmultiset 100.570.560.620.850.861.355.251.351.263.525.85 1000.480.480.670.630.631.293.930.921.661.115.03 10001.251.261.281.341.411.713.801.542.010.915.28 11.221.221.271.281.271.574.911.432.740.806.68 101.151.301.201.191.231.4810.331.484.101.1912.14 1001.161.161.201.201.191.469.123.488.251.7714.79 excess elements:20sizearrayvector with pointersvector with iteratorsqvector with pointersqvector with iteratorsdequelistqlistsetqset->qlistmultiset 101.271.241.321.821.822.9511.372.902.414.0013.50 1002.012.022.082.332.293.498.762.953.451.8911.49 10002.572.572.662.742.753.438.823.193.861.4512.25 12.402.552.672.512.503.1013.953.045.401.3118.18 102.492.322.442.572.422.9924.503.088.492.2230.31 1002.332.352.442.412.562.9319.677.2815.493.0034.36 excess elements:50sizearrayvector with pointersvector with iteratorsqvector with pointersqvector with iteratorsdequelistqlistsetqset->qlistmultiset 103.563.503.514.854.857.3132.097.836.608.5441.65 1006.616.626.697.387.319.7324.608.838.824.4333.47 10006.596.606.786.936.948.6425.688.049.392.9637.02 16.076.076.316.486.518.2055.037.2713.432.8263.57 106.236.086.316.426.438.0073.258.1820.725.9494.72 1005.855.996.246.006.157.4156.9520.3538.707.04106.47 excess elements:100sizearrayvector with pointersvector with iteratorsqvector with pointersqvector with iteratorsdequelistqlistsetqset->qlistmultiset 108.418.367.7110.6010.5817.4870.8216.3717.7816.2092.57 10014.0614.0414.3515.3615.3420.0656.3218.5217.848.4380.50 100012.7812.8013.2113.4513.4416.9062.4715.6618.655.5391.59 112.2012.1912.6212.7412.7315.81137.6014.7026.425.55162.82 1012.1012.0912.5512.4512.4615.29166.1616.0939.9611.18225.32
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Friday 17 July 2015 12:07:22 André Somers wrote: Marc Mutz schreef op 17-7-2015 om 12:21: What might also be a consideration when making a container like this, is that I find the key is often (not always of course) already part of the value data structure. For instance, if I store employee records and key them by id, that id is also in the record itself. It would be nice to have a fast and friendly key-based container that could handle that without duplicating the data... You can have that with C++11 std::*set, and a custom transparent comparator, but of course, they are not cache-friendly. But it's testament to the value of having the ability to _have_ a custom comparator. QFashHash consequently has that ability, but its a map, not a set, so it won't fit your use-case. I guess this [1] would work, but that is C++14, not 11. Otherwise, I don't quite see how to retreive my Employee record again if I just have the id... André [1] http://en.cppreference.com/w/cpp/container/set/find variants 3 and 4 Yes, I meant those. Sorry, I thought they were C++11. -- Marc Mutz marc.m...@kdab.com | Senior Software Engineer KDAB (Deutschland) GmbH Co.KG, a KDAB Group Company Tel: +49-30-521325470 KDAB - The Qt Experts ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
Marc Mutz schreef op 17-7-2015 om 12:21: What might also be a consideration when making a container like this, is that I find the key is often (not always of course) already part of the value data structure. For instance, if I store employee records and key them by id, that id is also in the record itself. It would be nice to have a fast and friendly key-based container that could handle that without duplicating the data... You can have that with C++11 std::*set, and a custom transparent comparator, but of course, they are not cache-friendly. But it's testament to the value of having the ability to _have_ a custom comparator. QFashHash consequently has that ability, but its a map, not a set, so it won't fit your use-case. I guess this [1] would work, but that is C++14, not 11. Otherwise, I don't quite see how to retreive my Employee record again if I just have the id... André [1] http://en.cppreference.com/w/cpp/container/set/find variants 3 and 4 ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
Hi Marc. That's because your benchmark runs entirely in L1. If you want to test containers of 10, 100, 1000 and 1 elements each, then make - one run over 1×N containers of 1 elements each, - one run over 10×N containers of 1000 elements each, - one run over 100×N containers of 100 elements each, - one run over 1000×N containers of 10 elements each. Ok as this is a valid point you made, i changed my code ( https://github.com/gunrot/qtcontainerbench https://github.com/gunrot/qtcontainerbench ) to do this, i create N=min(1,1/testcout) containers for the tests. I iterate over the N container looking up 1 in all N containers then 2 and so on. You need to use a working set size large enough to not hit L1 all the time, because it's just not the usual case that a lookup table is completely in L1. But you can start with a small working set. As you increase the working set size, you should see how each individual test (at constant number of elements) increases in runtime. And you will see that the contiguous containers don't loose as much as the node-based. Actually in my test node based container win with increasing number of elements against vector. These are the results, i sorted by speed, fastest is first. The time is what it takes to iterate over N container looking up an int32 values, while doing this for every value between 1 and testcount. 5 elements ( 2000 containers) stdvector_lowerbound -- 5 „, WalltimeMilliseconds,0.5859375 QVector_lowerbound -- 5 „, WalltimeMilliseconds,0.8359375 QMap_constFind -- 5 „, WalltimeMilliseconds“,1.15625 stdmap_find -- 5 „,WalltimeMilliseconds,1.328125 QHash_constFind -- 5 „,WalltimeMilliseconds,1.59375 stdunordered_find -- 5 „, WalltimeMilliseconds“,2,128 qfasthash_find -- 5 „, WalltimeMilliseconds,3.75 boostunordered_find -- 5 „,WalltimeMilliseconds,2.65625 This test has a clear winner std::vector, being more than double as fast as nee base container. QVector is quite a bit slower but still faster than any other. 20 elements (500 containers) stdvector_lowerbound -- 20 „, WalltimeMilliseconds,1.0625 QMap_constFind -- 20 „,WalltimeMilliseconds“,1.140625 QVector_lowerbound -- 20 „,WalltimeMilliseconds“,1.453125 stdunordered_find -- 20 „, WalltimeMilliseconds,1.71875 stdmap_find -- 20 „, WalltimeMilliseconds“,1.84375 boostunordered_find -- 20 „, WalltimeMilliseconds,1.875 QHash_constFind -- 20 „, WalltimeMilliseconds,2.0625 qfasthash_find -- 20 „,WalltimeMilliseconds,3.5625 Again std:vector is the winner here, but closely followed by QMap ( much more close than QVector was in the case before) , QVector lost track here already. 50 elements (200 containers) QMap_constFind -- 50 „,WalltimeMilliseconds“,1.359375 stdvector_lowerbound -- 50 „, WalltimeMilliseconds,1.375 QHash_constFind -- 50 „, WalltimeMilliseconds“,1.53125 QVector_lowerbound -- 50 „,WalltimeMilliseconds“,1.8125 stdmap_find -- 50 „, WalltimeMilliseconds“,2.25 stdunordered_find -- 50 „, WalltimeMilliseconds“,2.46875 qfasthash_find -- 50 „,WalltimeMilliseconds“,4.625 Here QMap is now the winner, but so closely followed by std::vector that i call it even. Vector falls even more behind in is now only 4th place. 100 elements (100 containers) stdvector_lowerbound -- 100 „, WalltimeMilliseconds,1.46875 QHash_constFind -- 100 „, WalltimeMilliseconds,1.625 QMap_constFind -- 100 „, WalltimeMilliseconds“,1.78125 stdunordered_find -- 100 „,WalltimeMilliseconds“,1.78125 boostunordered_find -- 100 „, WalltimeMilliseconds,1.875 QVector_lowerbound -- 100 „, WalltimeMilliseconds“,2.28125 stdmap_find -- 100 „, WalltimeMilliseconds“,2.65625 qfasthash_find -- 100 „, WalltimeMilliseconds“,4.9375 std::vector is comeback kid here. But QVector loses more and more ground. 1000 elements (10 containers) QHash_constFind -- 1000 „, WalltimeMilliseconds“,1.15625 stdunordered_find -- 1000 „, WalltimeMilliseconds“,1.625 boostunordered_find -- 1000 „, WalltimeMilliseconds,1.8125 stdvector_lowerbound -- 1000 „,WalltimeMilliseconds“,1.875 QMap_constFind -- 1000 „, WalltimeMilliseconds,2.5 QVector_lowerbound -- 1000 „, WalltimeMilliseconds“,3.3125 stdmap_find -- 1000 „, WalltimeMilliseconds,3.5 qfasthash_find -- 1000 „, WalltimeMilliseconds“,4.15625 std::vector also falls behind now being 60% slower than the winner QHash,Vector is even nearly 2 times slower than std::vector. 1 elements (1 container) QHash_constFind -- 1 „, WalltimeMilliseconds“,1.15625 boostunordered_find -- 1 „, WalltimeMilliseconds,1.578125 stdunordered_find -- 1 „, WalltimeMilliseconds“,1.609375 qfasthash_find -- 1 „,WalltimeMilliseconds,2.03125 stdvector_lowerbound -- 1 ,WalltimeMilliseconds,3.4375 QMap_constFind -- 1 „, WalltimeMilliseconds“,3.9375 stdmap_find -- 1
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
Le jeudi 16 juillet 2015 à 23:09 +0200, Gunnar Roth a écrit : The vector classes are now very bad in this case. QHash is considerable better than any other. So I deduce from this test that for a container with up to 100 elements , std::vector is the best choice , if you want fastest lookup, but Vector should be avoided. For larger container QHash should be used for best lookup performance. Unless your vector content changes often, you should use a sorted vector and a dichotomic search for that use case. Also note that hash are usually subject to hash collision issues, which may be a security concern in certain context : i wouldn’t recommend such a container for general purpose. Regards, Julien Blanc ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Friday 17 July 2015 00:02:52 Gunnar Roth wrote: Well my tests show that vector is only good with up to 100 elements, at least from 1000 and above it is a lot worse than QHash. What security concern do you mean when hash collide for a hash based container. That's probably when you fall off the cliff of the cache size. With 1000 elements, the full data set does not fit in the L1d cache, so QHash is faster because it produces fewer cache misses (fewer pages to be touched) given its O(1)+collision search. Anyway, basic algorithm class: a hashing table has O(1) search but it comes with a cost. -- Thiago Macieira - thiago.macieira (AT) intel.com Software Architect - Intel Open Source Technology Center ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Thursday 16 July 2015 23:09:55 Gunnar Roth wrote: QHash is slower than std::unordered because std::hashdouble is inline and qHash(double) is out-of-line. May I ask why? Is this valid for all qHash()? Commit c0791ac76ec7cfdc3945efa67a6f72ee3623413c Add qHash() overloads for floating-point types Implemented out-of-line to avoid potential FP-comparison warnings, as well as to be able to use the file-static hash() functions, which gets inlined unlike qHashBits(), which cannot be. It was a tradeoff between a faster inlining into your code and a faster hashing algorithm. -- Thiago Macieira - thiago.macieira (AT) intel.com Software Architect - Intel Open Source Technology Center ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
Hi Julian Am 16.07.2015 um 23:43 schrieb Julien Blanc julien.bl...@nmc-company.com: Le jeudi 16 juillet 2015 à 23:09 +0200, Gunnar Roth a écrit : The vector classes are now very bad in this case. QHash is considerable better than any other. So I deduce from this test that for a container with up to 100 elements , std::vector is the best choice , if you want fastest lookup, but Vector should be avoided. For larger container QHash should be used for best lookup performance. Unless your vector content changes often, you should use a sorted vector and a dichotomic search for that use case. Also note that hash are usually subject to hash collision issues, which may be a security concern in certain context : i wouldn’t recommend such a container for general purpose. I assume dichotomic search is the same as binary search. Well my tests show that vector is only good with up to 100 elements, at least from 1000 and above it is a lot worse than QHash. What security concern do you mean when hash collide for a hash based container. Have you some links about this topic? A google search for: hash container security gave no results in this direction. Regards, Gunnar ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
Hi Thiago Am 12.07.2015 um 19:42 schrieb Thiago Macieira thiago.macie...@intel.com: On Sunday 12 July 2015 16:57:39 Gunnar Roth wrote: QMap_insert -- 1 ,WalltimeMilliseconds,0.625,80,128 Please run with -perf -minimumvalue 100. The CPU cycles counter is much more accurate and more representative. There is no -perf option, i think you maybe meant the -tickcount option. So this is the result. QMap_insert -- 1 ,CPUTicks,3407433,3407433,1 QHash_insert -- 1 ,CPUTicks,1767885,1767885,1 stdmap_insert-- 1 ,CPUTicks,3060120,3060120,1 stdvector_pb_sort-- 1 ,CPUTicks,1146499.5,2292999,2 stdunordered_insert -- 1 ,CPUTicks,2521209,2521209,1 qfasthash_insert -- 1 ,CPUTicks,1977711,1977711,1 boostunordered_inser -- 1 ,CPUTicks,2301750,2301750,1 QMap_find-- 1 ,CPUTicks,1781553,1781553,1 QMap_constFind -- 1 ,CPUTicks,1172022,1172022,1 QHash_find -- 1 ,CPUTicks,231001.5,1848012,8 QHash_constFind -- 1 ,CPUTicks,141855.75,1134846,8 QVector_lowerbound -- 1 ,CPUTicks,1196103,1196103,1 stdvector_lowerbound -- 1 ,CPUTicks,1159581,1159581,1 stdmap_find -- 1 ,CPUTicks,1531323,1531323,1 stdunordered_find-- 1 ,CPUTicks,258110.25,1032441,4 qfasthash_find -- 1 ,CPUTicks,332802,1331208,4 boostunordered_find -- 1 ,CPUTicks,334885.5,2679084,8 Hmm now the insertion cost for vector is a lot less and even the fastest. Any clue why? But QHash_constFind still the best and about 8 times faster than QVector. You can also try -perfcounter l1d-cache-loads or l1d-cache-load-misses (you want to remove the -minimumvalue option) to see if there's more L1 cache miss ratio. Ah i googled and this are option only available on linux, but as i wrote i am doing these benchmarks on OS X. I have no linux installation but in a VM and not at home. Regards, Gunnar ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Monday 13 July 2015 08:26:09 Gunnar Roth wrote: Hi Thiago Am 12.07.2015 um 19:42 schrieb Thiago Macieira thiago.macie...@intel.com: On Sunday 12 July 2015 16:57:39 Gunnar Roth wrote: QMap_insert -- 1 ,WalltimeMilliseconds,0.625,80,128 Please run with -perf -minimumvalue 100. The CPU cycles counter is much more accurate and more representative. There is no -perf option, i think you maybe meant the -tickcount option. So No, I meant the -perf option. The one I added for Qt 5.1... You can also try -perfcounter l1d-cache-loads or l1d-cache-load-misses (you want to remove the -minimumvalue option) to see if there's more L1 cache miss ratio. Ah i googled and this are option only available on linux, but as i wrote i am doing these benchmarks on OS X. I have no linux installation but in a VM and not at home. Right, because that's the OS that provides a nice interface for accessing the hardware performance counters. -- Thiago Macieira - thiago.macieira (AT) intel.com Software Architect - Intel Open Source Technology Center ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
Il 12/07/2015 23:19, Alejandro Exojo ha scritto: El Sunday 12 July 2015, Thiago Macieira escribió: On Sunday 12 July 2015 16:16:07 Smith Martin wrote: I can see by your explanation that QVector is almost always more efficient than QList. But sometimes the difference doesn't matter. If it doesn't, then why not choose QVector? I've carefully read the thread, and I think the issue Martin or others might have is: * Documentation and the common know how about Qt containers tells that QList is a reasonable middle ground choice (sometimes is like a vector, sometimes like a linked list/vector hybrid). Is what the docs say, what the Qt Quarterly article says (which is old, but Olivier gave a recent explanation on containers on 2012's devdays), what is being used in the API as return type, etc. Nitpicking: it's never like a linked list. It's either an array of T or an array of T*. Access is always O(1) (with potentially a big factor hidden due to the indirection), insertion in the middle always O(N) (with potentially a smaller factor than QVector, esp. for big Ts, due to the indirection), etc. Then, yes, QList is the recommended generic sequential container, and the one used all around in Qt APIs. And that's the problem which started this discussion. * Marc has been criticizing what the docs says, but even being a significant contributor to Qt, did not propose to change that. And I actually disagree with that, given that QVector is faster than QList in the majority of the cases (and std::vector could be even faster and/or expand to less code). Having false statements in the docs is not good. I would like to see them changed. * According to Martin's explanations, he did send a patch for qdoc that replaced a wrong choice of container, but the change did not have any apparent effect. Which has been pointed out to be irrelevant to the purposes of this discussion (I have no idea of qdoc internals, has anyone profiled it? Maybe 99% of the time is spent on I/O or parsing C++ files and QVector over QList gives an advantage in nanoseconds for that particular use case?). But the totality of the other points in the first message stay, and noone has so far challenged them... * We are having a large thread with a heated discussion, and Marc said things like and the resulting code will be highly fragile and/or extremely inefficient. People might felt a bit offended by that. Is something being said about their work, after all. Please do not make this an ad-hominem. It's an argument about the code. When you spot an unwarranted usage of a QList in some code, what it is about? Pick: A) Premature pessimization (you could've used QVector instead, but you picked QList because it's the default container -- it's documented that way!) B) You want amortized fast prepend C) Your type is bad and you want to rely on validity of references when the container gets modified (There's no I want to call a function taking a QList because that's totally justified). Experience tells that you're in A) 99% of the time (extremely inefficient). B) or C) count for highly fragile, because you may break the code (or make it way more inefficient) by refactoring it. We've had cases of that. IIRC, this was a case of C) (refactoring from QList to QVector): https://codereview.qt-project.org/#/c/10878/9/src/corelib/kernel/qcoreapplication.cpp To summarize: I not sure whether you (plural) think that no container should be advised as the preferred one, or if it should be QVector, though. IMHO it should be advised to be QVector. We have an excessive usage of QList in Qt APIs which makes people think QList is a good default, and this thread is all about why it's not a good default. -- Giuseppe D'Angelo | giuseppe.dang...@kdab.com | Software Engineer KDAB (UK) Ltd., a KDAB Group company | Tel: UK +44-1625-809908 KDAB - The Qt Experts smime.p7s Description: Firma crittografica S/MIME ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
El Sunday 12 July 2015, Thiago Macieira escribió: On Sunday 12 July 2015 16:16:07 Smith Martin wrote: I can see by your explanation that QVector is almost always more efficient than QList. But sometimes the difference doesn't matter. If it doesn't, then why not choose QVector? I've carefully read the thread, and I think the issue Martin or others might have is: * Documentation and the common know how about Qt containers tells that QList is a reasonable middle ground choice (sometimes is like a vector, sometimes like a linked list/vector hybrid). Is what the docs say, what the Qt Quarterly article says (which is old, but Olivier gave a recent explanation on containers on 2012's devdays), what is being used in the API as return type, etc. * Marc has been criticizing what the docs says, but even being a significant contributor to Qt, did not propose to change that. * According to Martin's explanations, he did send a patch for qdoc that replaced a wrong choice of container, but the change did not have any apparent effect. * We are having a large thread with a heated discussion, and Marc said things like and the resulting code will be highly fragile and/or extremely inefficient. People might felt a bit offended by that. Is something being said about their work, after all. To summarize: I not sure whether you (plural) think that no container should be advised as the preferred one, or if it should be QVector, though. I think that you, and others who have voiced their opinions agree with Marc on vectors being better that what first intuition will tell you (use of a list if you have changes in the middle or the beginning is not as right as it might seem due to caches). That's something that Stroustrup explained very well, e.g.: https://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Keynote-Bjarne- Stroustrup-Cpp11-Style (from minute 45 more or less) In that talk, he shows that std::vector is better than std::list for _all_ N, and is an exercise where insertions and deletions happen in the middle. He does explain that what dominates is the search for the insertion/removal point. That should be quite different with QList. But Stroustrup _does_ insertion and removals in the middle. Marc's benchmarks only do appends, and the says: I also didn’t test insertions in the middle, since they’re rather rare. That said, there are of course lots of other tests one could run (e.g. sorting), and I invite you, dear reader, to implement some of them in the test harness and contribute them back. Well, I certainly don't understand why that's irrelevant. And I think we would not be having this conversation if it were that clear. I *do* really find this discussion interesting, but what I really, *really* want is to have the best documentation possible, and if we can't agree on which container should be preferred as a first choice, let's remove that and move on. -- Alex (a.k.a. suy) | GPG ID 0x0B8B0BC2 http://barnacity.net/ | http://disperso.net ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
Sune Vuorela schreef op 12-7-2015 om 20:37: On 2015-07-12, Andre Somers an...@familiesomers.nl wrote: become easier to make the transition in user code? Then, if Qt itself changes its API in Qt 6 to use QVector instead of QList, the users' code will just work :-) In Qt6, QList can be fixed. The issue is what to do until then. Fixed how? To become QVector? In that case, just use QVector instead. I could imagine a QVector like container that can reserve some space at both ends in order to allow for fast prepending (or use the end of the reserved range for that, perhaps). But other than that, what quality from QList would you like to keep over QVector? André ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Sunday, July 12, 2015 04:58:01 PM Marc Mutz wrote: On Sunday 12 July 2015 15:05:51 Gunnar Roth wrote: Hi Marc, Better provide a benchmark into which users can easily plug their own types and that plots relative performance of various containers at various sizes. Then they can use that on their platform, on their type, with their access patterns to determine which container to choose. I tried to write a container benchmark for testing qt , std and boost containers. I did that already a while ago, but had not collected enough energy to post about it until now . ;-) This is not including QList because the benchmark is made to test how fast i can lookup something in a container. It can be found at https://github.com/gunrot/qtcontainerbench https://github.com/gunrot/qtcontainerbench I got irritating results from it , concerning all the praise i read on the qt mailings list for Vector instead of map or hash. That's because your benchmark runs entirely in L1. If you want to test containers of 10, 100, 1000 and 1 elements each, then make - one run over 1×N containers of 1 elements each, - one run over 10×N containers of 1000 elements each, - one run over 100×N containers of 100 elements each, - one run over 1000×N containers of 10 elements each. You need to use a working set size large enough to not hit L1 all the time, because it's just not the usual case that a lookup table is completely in L1. But you can start with a small working set. As you increase the working set size, you should see how each individual test (at constant number of elements) increases in runtime. And you will see that the contiguous containers don't loose as much as the node-based. snip In addition to that, you should additionally benchmark the setup cost for the containers. I have often seen code that was slow, not because finding items in it was slow, but rather because the lists where temporary and thus the setup cost never amortized. Then, the cost of malloc free is significant, often orders of magnitude more expensive than actually finding the elements. There, QVarLengthArray (if possible) or at least QVector/std::vector _really_ shines. Bye -- Milian Wolff | milian.wo...@kdab.com | Software Engineer KDAB (Deutschland) GmbHCo KG, a KDAB Group company Tel: +49-30-521325470 KDAB - The Qt Experts smime.p7s Description: S/MIME cryptographic signature ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On 12 Jul 2015, at 16:58, Marc Mutz marc.m...@kdab.com wrote: That's because your benchmark runs entirely in L1. If you want to test containers of 10, 100, 1000 and 1 elements each, then make - one run over 1×N containers of 1 elements each, - one run over 10×N containers of 1000 elements each, - one run over 100×N containers of 100 elements each, - one run over 1000×N containers of 10 elements each. This is getting defensive, and quite frankly, a bit boring. The fact that half of the emails are from one author defending his absolute view with increasingly complex arguments suggests action points be taken and the debate be closed. Clearly Marc should write a /book/ about which tricks should be applied when writing high performance code. It’s non-trivial, and it really is no container’s role to be the sole solution to everything. There’s also no such book out there but clearly many “undocumented tricks” and pitfalls. We can’t add tables, and complex explanations, or dynamic forms where you input your sizes and types, to Qt docs to “help” people choose the right container. Complex docs == bad docs. Writing high performance code requires a touch of genius, and only needs to be applied to choice of algorithms at the highest level and only the most important loops at the lowest level. The performance of QList isn’t the prime focus of people writing normal code. Paint engine insides, for example, we make an effort not to allocate memory at all from begin to end. That sort of rules out most container classes out there. Suggested actions points: 1. Update Qt docs to indicate that careful planning, perhaps a pointer to Marc’s blog, this thread, and QVector docs, could be useful when writing performance critical code. I’m certain QList will be just a tiny chapter in Marc’s upcoming book but link to that chapter. 2. Analyze (again) when is the time to make Qt’s containers simple wrappers over those of stl and/or boost. Performance differences over equivalent classes with different APIs should be limited to the API differences themselves. Nothing else makes sense. 3. Marc, consider writing that book. It’s not a general book on Qt, because Qt is about writing code simple quick and easy with acceptable performance, not how to squeeze every cycle out of every part of your code. Andreas ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
+1 martin From: development-bounces+martin.smith=theqtcompany@qt-project.org development-bounces+martin.smith=theqtcompany@qt-project.org on behalf of Andreas Aardal Hanssen andr...@hanssen.name Sent: Sunday, July 12, 2015 4:29 PM To: development@qt-project.org Subject: Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO On 12 Jul 2015, at 16:58, Marc Mutz marc.m...@kdab.com wrote: That's because your benchmark runs entirely in L1. If you want to test containers of 10, 100, 1000 and 1 elements each, then make - one run over 1×N containers of 1 elements each, - one run over 10×N containers of 1000 elements each, - one run over 100×N containers of 100 elements each, - one run over 1000×N containers of 10 elements each. This is getting defensive, and quite frankly, a bit boring. The fact that half of the emails are from one author defending his absolute view with increasingly complex arguments suggests action points be taken and the debate be closed. Clearly Marc should write a /book/ about which tricks should be applied when writing high performance code. It’s non-trivial, and it really is no container’s role to be the sole solution to everything. There’s also no such book out there but clearly many “undocumented tricks” and pitfalls. We can’t add tables, and complex explanations, or dynamic forms where you input your sizes and types, to Qt docs to “help” people choose the right container. Complex docs == bad docs. Writing high performance code requires a touch of genius, and only needs to be applied to choice of algorithms at the highest level and only the most important loops at the lowest level. The performance of QList isn’t the prime focus of people writing normal code. Paint engine insides, for example, we make an effort not to allocate memory at all from begin to end. That sort of rules out most container classes out there. Suggested actions points: 1. Update Qt docs to indicate that careful planning, perhaps a pointer to Marc’s blog, this thread, and QVector docs, could be useful when writing performance critical code. I’m certain QList will be just a tiny chapter in Marc’s upcoming book but link to that chapter. 2. Analyze (again) when is the time to make Qt’s containers simple wrappers over those of stl and/or boost. Performance differences over equivalent classes with different APIs should be limited to the API differences themselves. Nothing else makes sense. 3. Marc, consider writing that book. It’s not a general book on Qt, because Qt is about writing code simple quick and easy with acceptable performance, not how to squeeze every cycle out of every part of your code. Andreas ___ 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
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Sunday 12 July 2015 16:16:07 Smith Martin wrote: I can see by your explanation that QVector is almost always more efficient than QList. But sometimes the difference doesn't matter. If it doesn't, then why not choose QVector? -- Thiago Macieira - thiago.macieira (AT) intel.com Software Architect - Intel Open Source Technology Center ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Sunday 12 July 2015 16:29:58 Andreas Aardal Hanssen wrote: 2. Analyze (again) when is the time to make Qt’s containers simple wrappers over those of stl and/or boost. Performance differences over equivalent classes with different APIs should be limited to the API differences themselves. Nothing else makes sense. Only if we drop the implicit sharing. It can't be done with acceptable performance otherwise. -- Thiago Macieira - thiago.macieira (AT) intel.com Software Architect - Intel Open Source Technology Center ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On 12-7-2015 19:56, Smith Martin wrote: If it doesn't, then why not choose QVector? My intent in getting the information from Marc is to change the documentation of QList to say that. But QList is easy to use. How is it easier to use than QVector? I will grand you two: QList is two characters less to type than QVector, so QList has the definite advantage there. Other than that, now that the API is basicaly synchronized, I don't see much benefit in QList over QVector. And 2) that Qt's own API often returns a QList and not a QVector... Perhaps QList needs to implicitly convert to a QVector so it become easier to make the transition in user code? Then, if Qt itself changes its API in Qt 6 to use QVector instead of QList, the users' code will just work :-) André ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
Hi, On 12/07/2015 18:56, Smith Martin wrote: If it doesn't, then why not choose QVector? My intent in getting the information from Marc is to change the documentation of QList to say that. But QList is easy to use. Given the API is almost identical, so is QVector. Also having been shown that QVector performs better than QList, both in the general case and the majority of cases, both in terms of performance and memory efficiency, what other information do you require specifically? With respect to your argument about changing the high level algorithm having more effect than a QList to QVector switch, that is no surprise. Altering algorithms at that level often has a more profound effect. Changing QList to QVector after such a change will yield a small benefit but expecting it to be comparable is unreasonable. For a fun visualisation of the access speeds of the various cache levels take a look at this little animation http://www.overbyte.com.au/misc/Lesson3/CacheFun.html As Andreas pointed out, if you can avoid any memory allocations at all in performance critical sections that is good, but having the memory you work on being located in contiguous regions is as good as it is possible to get with today's hierarchy of cache architecture. There's a nice illusatration of how changing the high-level algorithm _and_ ensuring that your data is located in contiguous yields good results and importantly, _why_ it gets good results. Although it's written in the context of the PS3 it's also relevant to other architectures too. It's available at: https://www.google.co.uk/url?sa=trct=jq=esrc=ssource=webcd=1cad=rjauact=8ved=0CCEQFjAAahUKEwiwpJWxmtbGAhVlgdsKHYR_Ciwurl=http%3A%2F%2Fharmful.cat-v.org%2Fsoftware%2FOO_programming%2F_pdf%2FPitfalls_of_Object_Oriented_Programming_GCAP_09.pdfei=vq-iVbDNIeWC7gaE_6ngAgusg=AFQjCNEZ1HUlVbU83BDYfyJw5mfdOob8iwsig2=mT486mHb0Va1eYz7smn6-w QList is one of the culprits that leads to death by 1000 paper cuts. That is, when your app doesn't run as fast as it should but there is no one single big hitter in the profiling data as the problem is diffused across the entire application. Cheers, Sean -- Dr Sean Harmer | sean.har...@kdab.com | Managing Director UK Klarälvdalens Datakonsult AB, a KDAB Group company Tel. Sweden (HQ) +46-563-540090, USA +1-866-777-KDAB(5322) KDAB - Qt Experts - Platform-independent software solutions ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
I expect you to view those videos and to read those articles and then I expect you to apologise for this mail of yours. Well qdoc was taking about 15 minutes to run on Qt5, so I followed Andreas' advice and changed the high-level algorithm. Now it runs in about 2 minutes. I suspect that swapping a QList for a QVector, where the QList is completely built all at once with usually only 2 or 3 elements and then traversed and destroyed all in the same function, won't reduce that 2 minutes by much. And we only run qdoc to rebuild the documentation. I think this software engineering profession attracts obsessive-compulsive type thinkers (AKA perfectionists), because building a software system from a proper functional requirements list (written or mental) makes achieving perfection possible. Passing all the requirements tests is perfection by definition. But the obsessive-compulsive type thinker (I am one myself) can become a bit of a pain sometimes. striving to better, oft we mar what's well -- Kink Lear I like QList. 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, July 12, 2015 6:18 PM To: development@qt-project.org Subject: Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO On Sunday 12 July 2015 16:29:58 Andreas Aardal Hanssen wrote: On 12 Jul 2015, at 16:58, Marc Mutz marc.m...@kdab.com wrote: That's because your benchmark runs entirely in L1. If you want to test containers of 10, 100, 1000 and 1 elements each, then make - one run over 1×N containers of 1 elements each, - one run over 10×N containers of 1000 elements each, - one run over 100×N containers of 100 elements each, - one run over 1000×N containers of 10 elements each. This is getting defensive, and quite frankly, a bit boring. The fact that half of the emails are from one author defending his absolute view with increasingly complex arguments suggests action points be taken and the debate be closed. ROTFL. You made my day. Martin asks increasingly narrowly.focused questions, and you make that into me being defensive. Yeah, right. Obviously, I beg to differ. It's not *my* view. It's just not *your* view: - Scott Meyers: https://www.youtube.com/watch?v=WDIkqP4JbkE - Chandler Carruth: https://www.youtube.com/watch?v=fHNmRkzxHWs - Herb Sutter: https://www.youtube.com/watch?v=L7zSU9HI-6I - Alex Stepanov Bjarne Stroustup: http://www.stepanovpapers.com/container_benchmark.cpp - Ulrich Drepper: http://www.akkadia.org/drepper/cpumemory.pdf Clearly, all of the above (and Thiago, and Peppe, and Milian) are all wrong and I am part of a big conspiracy. Clearly Marc should write a /book/ about which tricks should be applied when writing high performance code. Those books have already been written. You should read them! - Herb Sutter: Exception C++, More Exceptional C++, C++ Coding Standards - Scott Meyers: Effective C++, More Effective C++, Effective STL, Effective Modern C++ - ... I expect you to view those videos and to read those articles and then I expect you to apologise for this mail of yours. Thanks, Marc -- Marc Mutz marc.m...@kdab.com | Senior Software Engineer KDAB (Deutschland) GmbH Co.KG, a KDAB Group Company Tel: +49-30-521325470 KDAB - The Qt Experts ___ 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
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
Marc, I think you misunderstand the nature of the discussion. I don't think anyone disputes your analysis of the relative efficiencies of the various collections. I think you are dismissing the simple elegance of QList for getting a Qt application up and running quickly. Or, as in my use case, making a change quickly to correct a bug. I can see by your explanation that QVector is almost always more efficient than QList. But sometimes the difference doesn't matter. 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, July 12, 2015 7:14 PM To: development@qt-project.org Subject: Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO On Sunday 12 July 2015 17:34:25 Smith Martin wrote: I like QList. This level of discussion, combined with a complete unwillingness to look anything up that was linked to in this thread is why I don't try patch the Qt docs. And I'm sorry for not having stuck to my initial resolve not to talk about _why_ QList is bad. All the information is out there, and I won't convince anyone who's TL;DR; Hereby reinstated. -- Marc Mutz marc.m...@kdab.com | Senior Software Engineer KDAB (Deutschland) GmbH Co.KG, a KDAB Group Company Tel: +49-30-521325470 KDAB - The Qt Experts ___ 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
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On 2015-07-12, Andre Somers an...@familiesomers.nl wrote: become easier to make the transition in user code? Then, if Qt itself changes its API in Qt 6 to use QVector instead of QList, the users' code will just work :-) In Qt6, QList can be fixed. The issue is what to do until then. /Sune ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
Hi Milian, hi Marc Am 12.07.2015 um 16:06 schrieb Milian Wolff milian.wo...@kdab.com: On Sunday, July 12, 2015 04:58:01 PM Marc Mutz wrote: On Sunday 12 July 2015 15:05:51 Gunnar Roth wrote: Hi Marc, Better provide a benchmark into which users can easily plug their own types and that plots relative performance of various containers at various sizes. Then they can use that on their platform, on their type, with their access patterns to determine which container to choose. I tried to write a container benchmark for testing qt , std and boost containers. I did that already a while ago, but had not collected enough energy to post about it until now . ;-) This is not including QList because the benchmark is made to test how fast i can lookup something in a container. It can be found at https://github.com/gunrot/qtcontainerbench https://github.com/gunrot/qtcontainerbench I got irritating results from it , concerning all the praise i read on the qt mailings list for Vector instead of map or hash. That's because your benchmark runs entirely in L1. If you want to test containers of 10, 100, 1000 and 1 elements each, then make - one run over 1×N containers of 1 elements each, - one run over 10×N containers of 1000 elements each, - one run over 100×N containers of 100 elements each, - one run over 1000×N containers of 10 elements each. You need to use a working set size large enough to not hit L1 all the time, because it's just not the usual case that a lookup table is completely in L1. But you can start with a small working set. As you increase the working set size, you should see how each individual test (at constant number of elements) increases in runtime. And you will see that the contiguous containers don't loose as much as the node-based. Ok i understand your concern about the influence of the L1 cache,the size of my L1 cache is 64 kb, but shouldn’t continuoscontainer like vector benefit even more from that than non contagious like map or hash? the test of 1 container of 1 items i can easily produce. I added a std::vector push_back and sort testcase. The result is: QMap_insert -- 1 ,WalltimeMilliseconds,0.625,80,128 QHash_insert -- 1 ,WalltimeMilliseconds,0.099609375,51,512 stdmap_insert-- 1 ,WalltimeMilliseconds,0.4921875,63,128 stdvector_pb_sort-- 1 ,WalltimeMilliseconds,2.4375,78,32 stdunordered_insert -- 1 ,WalltimeMilliseconds,0.2109375,54,256 qfasthash_insert -- 1 ,WalltimeMilliseconds,0.14453125,74,512 boostunordered_inser -- 1 ,WalltimeMilliseconds,0.140625,72,512 QMap_find-- 1 ,WalltimeMilliseconds,0.65625,84,128 QMap_constFind -- 1 ,WalltimeMilliseconds,0.5546875,71,128 QHash_find -- 1 ,WalltimeMilliseconds,0.0830078125,85,1024 QHash_constFind -- 1 ,WalltimeMilliseconds,0.05859375,60,1024 QVector_lowerbound -- 1 ,WalltimeMilliseconds,0.5078125,65,128 stdvector_lowerbound -- 1 ,WalltimeMilliseconds,0.484375,62,128 stdmap_find -- 1 ,WalltimeMilliseconds,0.5546875,71,128 stdunordered_find-- 1 ,WalltimeMilliseconds,0.111328125,57,512 qfasthash_find -- 1 ,WalltimeMilliseconds,0.162109375,83,512 boostunordered_find -- 1 ,WalltimeMilliseconds,0.103515625,53,512 so here inserting 1 elements QHash is the fastest and std::vector the slowest. Its by a factor of 25 slower for looking up items QHash constFind is the fastest , being faster by at least a factor of 2, against std:vector is wins by a factor of 5. snip In addition to that, you should additionally benchmark the setup cost for the containers. I have often seen code that was slow, not because finding items in it was slow, but rather because the lists where temporary and thus the setup cost never amortized. Then, the cost of malloc free is significant, often orders of magnitude more expensive than actually finding the elements. There, QVarLengthArray (if possible) or at least QVector/std::vector _really_ shines. Hmm std::vector at least does not shine here Best regards, Gunnar Roth ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Sunday 12 July 2015 17:34:25 Smith Martin wrote: I like QList. This level of discussion, combined with a complete unwillingness to look anything up that was linked to in this thread is why I don't try patch the Qt docs. And I'm sorry for not having stuck to my initial resolve not to talk about _why_ QList is bad. All the information is out there, and I won't convince anyone who's TL;DR; Hereby reinstated. -- Marc Mutz marc.m...@kdab.com | Senior Software Engineer KDAB (Deutschland) GmbH Co.KG, a KDAB Group Company Tel: +49-30-521325470 KDAB - The Qt Experts ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
On Sunday 12 July 2015 16:57:39 Gunnar Roth wrote: QMap_insert -- 1 ,WalltimeMilliseconds,0.625,80,128 Please run with -perf -minimumvalue 100. The CPU cycles counter is much more accurate and more representative. You can also try -perfcounter l1d-cache-loads or l1d-cache-load-misses (you want to remove the -minimumvalue option) to see if there's more L1 cache miss ratio. -- Thiago Macieira - thiago.macieira (AT) intel.com Software Architect - Intel Open Source Technology Center ___ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO
If it doesn't, then why not choose QVector? My intent in getting the information from Marc is to change the documentation of QList to say that. But QList is easy to use. martin From: development-bounces+martin.smith=theqtcompany@qt-project.org development-bounces+martin.smith=theqtcompany@qt-project.org on behalf of Thiago Macieira thiago.macie...@intel.com Sent: Sunday, July 12, 2015 7:45 PM To: development@qt-project.org Subject: Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO On Sunday 12 July 2015 16:16:07 Smith Martin wrote: I can see by your explanation that QVector is almost always more efficient than QList. But sometimes the difference doesn't matter. If it doesn't, then why not choose QVector? -- Thiago Macieira - thiago.macieira (AT) intel.com Software Architect - Intel Open Source Technology Center ___ 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
