D12659: two new UDS structures

[Stefan Brüns]

bruns added a comment.


  In D12659#257294 <https://phabricator.kde.org/D12659#257294>, @dfaure wrote:
  
  > 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.
  
  
  Even when appending in sorted order, the correct position has to be checked, which is O(n), the appending itself is O(1), as no movement is involved. Appending unsorted is always O(1) (when capacity is sufficient).
  
  >>> 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.
  
  The comment was addressing the difference between this approach and the "FrankUDSEntry".
  
  >> 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.
  
  QVariant has hardly any overhead in this case - the struct here stores one uint and one QString (which is justs its d-ptr), while the QVariant uses one uint for the type info and one union for the data. For both the uint case and QString, the data is stored inline in the QVariant data union.
  
  Using QVariant has the benefit of avoiding a homegrown structure. It is not faster, but it is also not slower.

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/01618b82/attachment.html>