[Development] Views

[Philippe]

I second your use of sorted vectors, especially for small ones.

However, a key to master code complexity is to be able to easily recognize abstractions.
This reduces cognitive load when dealing with code. Generally Qt shines here.

A potential QDictionnary would speak to a reader more directly than
'std::vector + std::lower_bound' etc.
simply because QDictionnary would be more of an abstraction.

Philippe

On Thu, 06 Jun 2019 09:05:31 +0200
"Mutz, Marc via Development" <development at qt-project.org> wrote:

> 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 at qt-project.org
> https://lists.qt-project.org/listinfo/development