<table><tr><td style="">dfaure added a comment.
</td><a style="text-decoration: none; padding: 4px 8px; margin: 0 8px 8px; float: right; color: #464C5C; font-weight: bold; border-radius: 3px; background-color: #F7F7F9; background-image: linear-gradient(to bottom,#fff,#f1f0f1); display: inline-block; border: 1px solid rgba(71,87,120,.2);" href="https://phabricator.kde.org/D12659">View Revision</a></tr></table><br /><div><div><blockquote style="border-left: 3px solid #8C98B8;
          color: #6B748C;
          font-style: italic;
          margin: 4px 0 12px 0;
          padding: 8px 12px;
          background-color: #F8F9FC;">
<div style="font-style: normal;
          padding-bottom: 4px;">In <a href="https://phabricator.kde.org/D12659#257292" style="background-color: #e7e7e7;
          border-color: #e7e7e7;
          border-radius: 3px;
          padding: 0 4px;
          font-weight: bold;
          color: black;text-decoration: none;">D12659#257292</a>, <a href="https://phabricator.kde.org/p/bruns/" style="
              border-color: #f1f7ff;
              color: #19558d;
              background-color: #f1f7ff;
                border: 1px solid transparent;
                border-radius: 3px;
                font-weight: bold;
                padding: 0 4px;">@bruns</a> wrote:</div>
<div style="margin: 0;
          padding: 0;
          border: 0;
          color: rgb(107, 116, 140);"><blockquote style="border-left: 3px solid #8C98B8;
          color: #6B748C;
          font-style: italic;
          margin: 4px 0 12px 0;
          padding: 8px 12px;
          background-color: #F8F9FC;">
<div style="font-style: normal;
          padding-bottom: 4px;">In <a href="https://phabricator.kde.org/D12659#257098" style="background-color: #e7e7e7;
          border-color: #e7e7e7;
          border-radius: 3px;
          padding: 0 4px;
          font-weight: bold;
          color: black;text-decoration: none;">D12659#257098</a>, <a href="https://phabricator.kde.org/p/dfaure/" style="
              border-color: #f1f7ff;
              color: #19558d;
              background-color: #f1f7ff;
                border: 1px solid transparent;
                border-radius: 3px;
                font-weight: bold;
                padding: 0 4px;">@dfaure</a> wrote:</div>
<div style="margin: 0;
          padding: 0;
          border: 0;
          color: rgb(107, 116, 140);"><p>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?</p></div>
</blockquote>

<p>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.</p></div>
</blockquote>

<p>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.</p>

<blockquote style="border-left: 3px solid #a7b5bf; color: #464c5c; font-style: italic; margin: 4px 0 12px 0; padding: 4px 12px; background-color: #f8f9fc;"><blockquote style="border-left: 3px solid #a7b5bf; color: #464c5c; font-style: italic; margin: 4px 0 12px 0; padding: 4px 12px; background-color: #f8f9fc;"><p>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.</p></blockquote>

<p>Using one list is better than two lists (one heap allocation instead of two), one size check when inserting ...</p></blockquote>

<p>Sure, but I'm only comparing "Another" and "AnotherV2", which both use a single vector.</p>

<blockquote style="border-left: 3px solid #a7b5bf; color: #464c5c; font-style: italic; margin: 4px 0 12px 0; padding: 4px 12px; background-color: #f8f9fc;"><p>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).<br />
 I would suggest QVector<QPair<uint, QVariant>>. Each element, taking alignment into account, is 24 bytes.</p></blockquote>

<p>If anyone attempts this, please name the struct and its members, don't use QPair ;-)<br />
But no, that cannot possibly be faster. QVariant has lots of overhead itself.</p></div></div><br /><div><strong>REPOSITORY</strong><div><div>R241 KIO</div></div></div><br /><div><strong>REVISION DETAIL</strong><div><a href="https://phabricator.kde.org/D12659">https://phabricator.kde.org/D12659</a></div></div><br /><div><strong>To: </strong>jtamate, dfaure, Frameworks<br /><strong>Cc: </strong>bruns, michaelh<br /></div>