On Wednesday 20 January 2016 22:50:43 Kevin Kofler wrote:
> Marc Mutz wrote:
> > In those cases where it does matter, you'd return by const-&. Or an
> > array_view. And no, that doesn't restrict your freedom to implement the
> > function in any meaningful way, because you can always keep a caching
> > mutable member to hold the result for the next call to the function
> > (memoisation or however it's called), without any loss except the space
> > required for the member.
>
> All these are horrible and error-prone hacks that have obvious lifetime
> issues. You are complaining about Qt containers because the detaching can
> invalidate iterators. Well, the lifetime issues you introduce with the
> above proposed solutions are much worse! And a caching mutable member also
> destroys thread-safety (in addition to the obvious lifetime issue that the
> next call surprisingly invalidates your existing reference).
One word: QModelIndex.
> > What about non-arrays? By the time we get around to all this, there will
> > be no containers other than array-compatible ones left, because nothing
> > else will provide the required speed.
>
> Sorry, but that is just utter nonsense. Replacing a hash table with an
> array will NOT make your code more efficient. Replacing a linked list with
> an array can also make your code slower if you do enough
> insertions/removals.
In 90s text books, yes. In reality, no. The factors are so large these days
that big-O complexity is only valid for really, really large containers. The
vast majority of containers never grow big enough to offset that factor.
find_if
even beats lower_bound on a vector, for a large range of sizes (and a cheap
comparator).
Even in the 90s, Effective STL and Alex Stepanov recommended to use vector
unless the profiler tells you otherwise. In the past 20 years, the gap has only
widened.
> In the end, your real issue is not with the containers, but with the
> slowness of the malloc you use. Which means we need faster allocations, not
> containers that minimize allocations at all costs, including worse
> asymptotic algorithmic complexity.
QLinkedList<int> ll = generateRandomLL();
ll.sort();
// no more memory allocs beyond this point
QElapsedTimer timer;
timer.start();
for (int i = 0; i < 1000; ++i)
for (int e : ll)
some cheap payload processing....
timer.elapsed();
Then do the same benchmark with a QVector<int>.
If you don't understand why this is slow _as hell_ I suggest you run it on a
cache profiler.
Or monitor
https://www.youtube.com/user/MeetingCPP/playlists
for
http://meetingcpp.com/index.php/vl15/items/10.html
to become available.
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
