On 2019-06-06 08:24, Joerg Bornemann wrote:
On 6/5/19 5:49 PM, Mutz, Marc via Development wrote:
As a library implementer, you are simply not _allowed_ the freedom to
use a convenient tool over the most efficient one. That is, to put it
mildly, a disservice to users and a disgrace to the profession of
programmers. 8KiB just to look up a pointer in a map of {string, int}?
That's 1/4th of the icache size of many processors!
[...]
While I agree with this in general... every time we use a sorted vector
as a dictionary replacement we're scattering implementation details all
over the place, creating code that's much harder to read and easier to
make mistakes in (*).
Maybe it's time for a general purpose dictionary class based on a
sorted
vector?
FTR: More of the same:
https://codereview.qt-project.org/c/qt/qtbase/+/264128 and
https://codereview.qt-project.org/c/qt/qtbase/+/264129
I very strongly object to the notion that a find_if or lower_bound is
harder to read. More code does _not_ equate to less readable, as Qt over
and over has shown. There are different patterns involved than in using
Qt containers, sure, and by all means, if find_if frightens you, then
use a raw for loop, but this stuff is not rocket science. And depending
on how you define 'mistakes', it's just as easy to make a mistake by
forgetting qAsConst() on a Qt container than it is to, say, combine
iterators from different containers.
As for QSortedVector/QFlatMap. There's a reason there's none in the std,
yet, and it has to do with when to sort. In one of the patches above, we
don't need to sort at all, because there're only ever O(10) elements in
there. Sorting, as performed by a QFlatMap would be overkill there. In
another, we don't even store the key, as it's equal to the position of
the element in the array. Sorting the key would be nonsense. Oftem, you
populate the data structure once and then only perform lookups. In that
case, a QFlatMap would waste time sorting while you don't need it. So,
yes, by all means, let's have a QFlatMap, but it would just be another
over-complicated container that people misuse. Let's, as a community,
learn how to use a raw vector (or array) first, then introduce
convenience.
Don't pick a container by it's API. Pick it by how you use it. No-one
would use a RB tree for O(10) items if he had to implement it himself.
You wouldn't even implement one for O(1M) elements if insertions in the
middle are very infrequent. You are CS engineers. What would Knuth say
if he caught you using a RB tree with a static maximum of 10 entries?
There's a reason for this. It's horribly slow, and only used because in
very limited circumstances, evenry other container is _even_ slower.
It's a very, very, complex beast. Just because the compiler writes it
for you at nothing more than a mention of QMap<T,V>, doesn't mean it's
less complex. And that complexity doesn't go away just because you wrap
it in a nice API: the compiler has a hard time with it, and so does the
CPU, as evidenced by the O(KiB) savings involved in each replacement of
a QMap with a vector. Let's also not forget the memory overhead: a
QMap<int, int> uses at least 24 bytes of of storage per element. Plus
allocation overhead. Some platforms (Windows? At some point at least?)
didn't hand out heap in less than 64 bytes. That's 64 bytes of memory
for 8 bytes of payload. A vector uses exactly 8. So a map uses anywhere
between 3x and 8x more memory.
Just ask yourself: if you didn't have QMap/std::map or the hashed
versions, what data structure would you use? If the answer _actually_ is
"a RB tree (because I really need to insert and remove and lookup
roughly the same number of times", then fine, go use QMap. If it
_actually_ is "a hash table", then consider QHash/unorderd_map. Or maybe
an Open Addressing hash table would be better? BTW: with vector, you can
even implement a Heap (std::make/push/pop_heap).
There's no replacement for thinking here. There's no data structure that
will work best in all cases.
Thanks,
Marc
_______________________________________________
Development mailing list
Development@qt-project.org
https://lists.qt-project.org/listinfo/development
