D12659: two new UDS structures

[Stefan Brüns]

bruns added a comment.


  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.
  
  > But even if both were equal performance-wise I'd favor linear search because sorted insertion is easy to get wrong - as this patch shows ;)
  > 
  > 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 ...
  
  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.
  
  QMap and QHash are clearly overkill here. The involved pointer chasing ruins any performance benefit from the asymtotically faster lookup.

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/942f5cff/attachment.html>