D12659: two new UDS structures

[David Faure]

dfaure added a comment.


  In D12659#257292 <https://phabricator.kde.org/D12659#257292>, @bruns wrote:
  
  > In D12659#257098 <https://phabricator.kde.org/D12659#257098>, @dfaure wrote:
  >
  > > Thanks for that investigation. Interesting that linear search is faster than binary search in the same data structure... maybe the compiler optimizes it better? Did you profile V2 to find out where the time is spent, or do you have a better explanation?
  >
  >
  > Binary search has a (small) overhead, you can hardly beat linear search when the number of entries is small. When you use binary search, you pay when inserting - find the right position, probably move other items. When you do inserts one item a time, you have O(n^2) behavior.
  
  
  I know that but that's not what the code was doing, he is appending in (hopefully) sorted order, so the difference was only at lookup time, where I can't see any overhead due to binary search.
  
  >> When you say "scales better", we're talking about the number of fields in the udsentry, not the number of items. But kioslaves don't fill in 1000 fields, so I have the feeling that scaling with the number of fields isn't a requirement.
  > 
  > Using one list is better than two lists (one heap allocation instead of two), one size check when inserting ...
  
  Sure, but I'm only comparing "Another" and "AnotherV2", which both use a single vector.
  
  > A good data structure here is one contigous vector storing both key and (small value or d-pointer). Inserting is O(1) when the space has been reserved, lookup is O(n). (For binary search, lookup is O(log n) - for 8 entries, this is == 3, linear search is 8/2 == 4, but no overhead).
  >  I would suggest QVector<QPair<uint, QVariant>>. Each element, taking alignment into account, is 24 bytes.
  
  If anyone attempts this, please name the struct and its members, don't use QPair ;-)
  But no, that cannot possibly be faster. QVariant has lots of overhead itself.

REPOSITORY
  R241 KIO

REVISION DETAIL
  https://phabricator.kde.org/D12659

To: jtamate, dfaure, #frameworks
Cc: bruns, michaelh
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/kde-frameworks-devel/attachments/20180502/8918676d/attachment.html>