Re: [Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO

[Marc Mutz]

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:1
size	array	vector with pointers	vector with iterators	qvector with pointers	qvector with iterators	deque	list	qlist	set	qset->qlist	multiset
10	0.07	0.07	0.07	0.11	0.12	0.18	0.51	0.14	0.38	0.71	0.42
100	0.03	0.04	0.03	0.05	0.05	0.08	0.26	0.07	0.24	0.39	0.24
1000	0.05	0.04	0.06	0.06	0.06	0.11	0.26	0.07	0.29	0.34	0.31
10000	0.10	0.10	0.11	0.10	0.11	0.14	0.30	0.12	0.35	0.37	0.38
100000	0.10	0.10	0.11	0.11	0.11	0.13	0.42	0.12	0.49	0.37	0.52
1000000	0.10	0.10	0.10	0.11	0.11	0.13	0.59	0.27	0.84	0.82	0.93
excess elements:2
size	array	vector with pointers	vector with iterators	qvector with pointers	qvector with iterators	deque	list	qlist	set	qset->qlist	multiset
10	0.32	0.14	0.16	0.20	0.21	0.31	1.04	0.31	0.51	0.90	0.92
100	0.06	0.07	0.07	0.10	0.10	0.16	0.56	0.14	0.31	0.49	0.58
1000	0.18	0.18	0.18	0.20	0.20	0.29	0.59	0.24	0.49	0.45	0.71
10000	0.23	0.22	0.24	0.24	0.24	0.30	0.68	0.26	0.63	0.43	0.85
100000	0.22	0.22	0.22	0.23	0.23	0.29	1.08	0.26	0.86	0.43	1.37
1000000	0.22	0.21	0.23	0.22	0.22	0.28	1.26	0.59	1.57	0.93	2.03
excess elements:5
size	array	vector with pointers	vector with iterators	qvector with pointers	qvector with iterators	deque	list	qlist	set	qset->qlist	multiset
10	0.70	0.31	0.32	0.47	0.46	0.69	2.51	0.70	0.79	1.40	2.65
100	0.19	0.20	0.21	0.27	0.26	0.44	1.72	0.39	0.72	0.73	2.10
1000	0.59	0.59	0.61	0.65	0.64	0.84	1.67	0.74	1.07	0.62	2.15
10000	0.62	0.61	0.63	0.64	0.64	0.79	1.91	0.72	1.41	0.57	2.58
100000	0.57	0.58	0.61	0.60	0.60	0.75	4.36	0.72	2.13	0.70	4.98
1000000	0.57	0.59	0.59	0.60	0.59	0.73	3.84	1.64	3.87	1.13	6.27
excess elements:10
size	array	vector with pointers	vector with iterators	qvector with pointers	qvector with iterators	deque	list	qlist	set	qset->qlist	multiset
10	0.57	0.56	0.62	0.85	0.86	1.35	5.25	1.35	1.26	3.52	5.85
100	0.48	0.48	0.67	0.63	0.63	1.29	3.93	0.92	1.66	1.11	5.03
1000	1.25	1.26	1.28	1.34	1.41	1.71	3.80	1.54	2.01	0.91	5.28
10000	1.22	1.22	1.27	1.28	1.27	1.57	4.91	1.43	2.74	0.80	6.68
100000	1.15	1.30	1.20	1.19	1.23	1.48	10.33	1.48	4.10	1.19	12.14
1000000	1.16	1.16	1.20	1.20	1.19	1.46	9.12	3.48	8.25	1.77	14.79
excess elements:20
size	array	vector with pointers	vector with iterators	qvector with pointers	qvector with iterators	deque	list	qlist	set	qset->qlist	multiset
10	1.27	1.24	1.32	1.82	1.82	2.95	11.37	2.90	2.41	4.00	13.50
100	2.01	2.02	2.08	2.33	2.29	3.49	8.76	2.95	3.45	1.89	11.49
1000	2.57	2.57	2.66	2.74	2.75	3.43	8.82	3.19	3.86	1.45	12.25
10000	2.40	2.55	2.67	2.51	2.50	3.10	13.95	3.04	5.40	1.31	18.18
100000	2.49	2.32	2.44	2.57	2.42	2.99	24.50	3.08	8.49	2.22	30.31
1000000	2.33	2.35	2.44	2.41	2.56	2.93	19.67	7.28	15.49	3.00	34.36
excess elements:50
size	array	vector with pointers	vector with iterators	qvector with pointers	qvector with iterators	deque	list	qlist	set	qset->qlist	multiset
10	3.56	3.50	3.51	4.85	4.85	7.31	32.09	7.83	6.60	8.54	41.65
100	6.61	6.62	6.69	7.38	7.31	9.73	24.60	8.83	8.82	4.43	33.47
1000	6.59	6.60	6.78	6.93	6.94	8.64	25.68	8.04	9.39	2.96	37.02
10000	6.07	6.07	6.31	6.48	6.51	8.20	55.03	7.27	13.43	2.82	63.57
100000	6.23	6.08	6.31	6.42	6.43	8.00	73.25	8.18	20.72	5.94	94.72
1000000	5.85	5.99	6.24	6.00	6.15	7.41	56.95	20.35	38.70	7.04	106.47
excess elements:100
size	array	vector with pointers	vector with iterators	qvector with pointers	qvector with iterators	deque	list	qlist	set	qset->qlist	multiset
10	8.41	8.36	7.71	10.60	10.58	17.48	70.82	16.37	17.78	16.20	92.57
100	14.06	14.04	14.35	15.36	15.34	20.06	56.32	18.52	17.84	8.43	80.50
1000	12.78	12.80	13.21	13.45	13.44	16.90	62.47	15.66	18.65	5.53	91.59
10000	12.20	12.19	12.62	12.74	12.73	15.81	137.60	14.70	26.42	5.55	162.82
100000	12.10	12.09	12.55	12.45	12.46	15.29	166.16	16.09	39.96	11.18	225.32
1000000	11.75	11.74	12.20	12.05	12.06	14.57	129.52	43.66	78.06	14.62	250.44

_______________________________________________
Development mailing list
Development@qt-project.org
http://lists.qt-project.org/mailman/listinfo/development