<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><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?<br />
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 ;)</p>
<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>
<p>Are those benchmarks run in Release (or RelWithDebInfo) mode, rather than Debug (which is a big no no for benchmarks)? Qt should be compiled with optimizations enabled too.</p>
<p>PS: for all alternatives where the API is the same, we could use a template function (templated on the type of UDSEntry implementation) to perform the tests; this would ensure that all tests are actually testing the same thing ;-)</p></div></div><br /><div><strong>INLINE COMMENTS</strong><div><div style="margin: 6px 0 12px 0;"><div style="border: 1px solid #C7CCD9; border-radius: 3px;"><div style="padding: 0; background: #F7F7F7; border-color: #e3e4e8; border-style: solid; border-width: 0 0 1px 0; margin: 0;"><div style="color: #74777d; background: #eff2f4; padding: 6px 8px; overflow: hidden;"><a style="float: right; text-decoration: none;" href="https://phabricator.kde.org/D12659#inline-64717">View Inline</a><span style="color: #4b4d51; font-weight: bold;">udsentry_benchmark.cpp:464</span></div>
<div style="font: 11px/15px "Menlo", "Consolas", "Monaco", monospace; white-space: pre-wrap; clear: both; padding: 4px 0; margin: 0;"><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="p">{</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span style="color: #304a96">inline</span> <span class="n">Field</span><span class="p">()</span> <span style="color: #aa2211">:</span> <span class="n">m_index</span><span class="p">(</span><span style="color: #aa2211">-</span><span style="color: #601200">1</span><span class="p">)</span> <span class="p">{}</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span style="color: #304a96">inline</span> <span class="n">Field</span><span class="p">(</span><span style="color: #aa4000">const</span> <span class="n">uint</span> <span class="n">index</span><span class="p">,</span> <span style="color: #aa4000">const</span> <span class="n">QString</span> <span style="color: #aa2211">&</span><span class="n">value</span><span class="p">)</span> <span style="color: #aa2211">:</span> <span class="n">m_str</span><span class="p">(</span><span class="n">value</span><span class="p">),</span> <span class="n">m_long</span><span class="p">(</span><span style="color: #601200">0</span><span class="p">),</span> <span class="n">m_index</span><span class="p">(</span><span class="n">index</span><span class="p">)</span> <span class="p">{}</span>
</div></div></div>
<div style="margin: 8px 0; padding: 0 12px;"><p style="padding: 0; margin: 8px;">m_long should be initialized too (in-place initialized in the member declaration would help not forgetting that)</p></div></div><br /><div style="border: 1px solid #C7CCD9; border-radius: 3px;"><div style="padding: 0; background: #F7F7F7; border-color: #e3e4e8; border-style: solid; border-width: 0 0 1px 0; margin: 0;"><div style="color: #74777d; background: #eff2f4; padding: 6px 8px; overflow: hidden;"><a style="float: right; text-decoration: none;" href="https://phabricator.kde.org/D12659#inline-64715">View Inline</a><span style="color: #4b4d51; font-weight: bold;">udsentry_benchmark.cpp:468</span></div>
<div style="font: 11px/15px "Menlo", "Consolas", "Monaco", monospace; white-space: pre-wrap; clear: both; padding: 4px 0; margin: 0;"><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span style="color: #74777d">// This operator is essential to gain some speed, because the default == is slow</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span style="color: #304a96">inline</span> <span style="color: #aa4000">bool</span> <span style="color: #aa4000">operator</span> <span style="color: #aa2211">==</span> <span class="p">(</span><span style="color: #aa4000">const</span> <span class="n">Field</span> <span style="color: #aa2211">&</span><span class="n">other</span><span class="p">)</span> <span class="p">{</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span style="color: #aa4000">return</span> <span class="n">m_index</span> <span style="color: #aa2211">==</span> <span class="n">other</span><span class="p">.</span><span class="n">m_index</span><span class="p">;</span>
</div></div></div>
<div style="margin: 8px 0; padding: 0 12px;"><p style="padding: 0; margin: 8px;">const</p></div></div><br /><div style="border: 1px solid #C7CCD9; border-radius: 3px;"><div style="padding: 0; background: #F7F7F7; border-color: #e3e4e8; border-style: solid; border-width: 0 0 1px 0; margin: 0;"><div style="color: #74777d; background: #eff2f4; padding: 6px 8px; overflow: hidden;"><a style="float: right; text-decoration: none;" href="https://phabricator.kde.org/D12659#inline-64723">View Inline</a><span style="color: #4b4d51; font-weight: bold;">udsentry_benchmark.cpp:487</span></div>
<div style="font: 11px/15px "Menlo", "Consolas", "Monaco", monospace; white-space: pre-wrap; clear: both; padding: 4px 0; margin: 0;"><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="p">{</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span style="color: #aa2211">*</span><span class="n">index</span> <span style="color: #aa2211">=</span> <span class="n">Field</span><span class="p">(</span><span class="n">field</span><span class="p">,</span> <span class="n">value</span><span class="p">);</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span style="color: #aa4000">return</span><span class="p">;</span>
</div></div></div>
<div style="margin: 8px 0; padding: 0 12px;"><p style="padding: 0; margin: 8px;">wouldn't it be faster to assign to index->m_str here?</p>
<div class="remarkup-code-block" style="margin: 12px 0;" data-code-lang="text" data-sigil="remarkup-code-block"><pre class="remarkup-code" style="font: 11px/15px "Menlo", "Consolas", "Monaco", monospace; padding: 12px; margin: 0; background: rgba(71, 87, 120, 0.08);">index->m_str = value;</pre></div></div></div><br /><div style="border: 1px solid #C7CCD9; border-radius: 3px;"><div style="padding: 0; background: #F7F7F7; border-color: #e3e4e8; border-style: solid; border-width: 0 0 1px 0; margin: 0;"><div style="color: #74777d; background: #eff2f4; padding: 6px 8px; overflow: hidden;"><a style="float: right; text-decoration: none;" href="https://phabricator.kde.org/D12659#inline-64716">View Inline</a><span style="color: #4b4d51; font-weight: bold;">udsentry_benchmark.cpp:491</span></div>
<div style="font: 11px/15px "Menlo", "Consolas", "Monaco", monospace; white-space: pre-wrap; clear: both; padding: 4px 0; margin: 0;"><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="p">}</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="n">storage</span><span class="p">.</span><span class="n">append</span><span class="p">(</span><span class="n">Field</span><span class="p">(</span><span class="n">field</span><span class="p">,</span> <span class="n">value</span><span class="p">));</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="p">}</span>
</div></div></div>
<div style="margin: 8px 0; padding: 0 12px;"><p style="padding: 0; margin: 8px;">std::vector with emplace_back would be interesting here, performance-wise.</p>
<p style="padding: 0; margin: 8px;">If you keep using QVector, though, then Q_DECLARE_MOVABLE(Field) would help, especially when reserving too small.</p></div></div><br /><div style="border: 1px solid #C7CCD9; border-radius: 3px;"><div style="padding: 0; background: #F7F7F7; border-color: #e3e4e8; border-style: solid; border-width: 0 0 1px 0; margin: 0;"><div style="color: #74777d; background: #eff2f4; padding: 6px 8px; overflow: hidden;"><a style="float: right; text-decoration: none;" href="https://phabricator.kde.org/D12659#inline-64722">View Inline</a><span style="color: #4b4d51; font-weight: bold;">udsentry_benchmark.cpp:498</span></div>
<div style="font: 11px/15px "Menlo", "Consolas", "Monaco", monospace; white-space: pre-wrap; clear: both; padding: 4px 0; margin: 0;"><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="p">{</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span style="color: #aa2211">*</span><span class="n">index</span> <span style="color: #aa2211">=</span> <span class="n">Field</span><span class="p">(</span><span class="n">field</span><span class="p">,</span> <span class="n">value</span><span class="p">);</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span style="color: #aa4000">return</span><span class="p">;</span>
</div></div></div>
<div style="margin: 8px 0; padding: 0 12px;"><p style="padding: 0; margin: 8px;">wouldn't it be faster to assign to index->m_long here?</p>
<div class="remarkup-code-block" style="margin: 12px 0;" data-code-lang="text" data-sigil="remarkup-code-block"><pre class="remarkup-code" style="font: 11px/15px "Menlo", "Consolas", "Monaco", monospace; padding: 12px; margin: 0; background: rgba(71, 87, 120, 0.08);">index->m_long = value;</pre></div></div></div><br /><div style="border: 1px solid #C7CCD9; border-radius: 3px;"><div style="padding: 0; background: #F7F7F7; border-color: #e3e4e8; border-style: solid; border-width: 0 0 1px 0; margin: 0;"><div style="color: #74777d; background: #eff2f4; padding: 6px 8px; overflow: hidden;"><a style="float: right; text-decoration: none;" href="https://phabricator.kde.org/D12659#inline-64726">View Inline</a><span style="color: #4b4d51; font-weight: bold;">udsentry_benchmark.cpp:510</span></div>
<div style="font: 11px/15px "Menlo", "Consolas", "Monaco", monospace; white-space: pre-wrap; clear: both; padding: 4px 0; margin: 0;"><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="p">{</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span style="color: #aa4000">for</span> <span class="p">(</span><span style="color: #aa4000">auto</span> <span class="n">index</span> <span style="color: #aa2211">=</span> <span class="n">storage</span><span class="p">.</span><span class="n">constBegin</span><span class="p">(),</span> <span class="n">end</span> <span style="color: #aa2211">=</span> <span class="n">storage</span><span class="p">.</span><span class="n">constEnd</span><span class="p">();</span> <span class="n">index</span> <span style="color: #aa2211">!=</span> <span class="n">end</span><span class="p">;</span> <span style="color: #aa2211">++</span><span class="n">index</span><span class="p">)</span> <span class="p">{</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span style="color: #aa4000">if</span> <span class="p">(</span><span class="n">index</span><span style="color: #aa2211">-></span><span class="n">m_index</span> <span style="color: #aa2211">==</span> <span class="n">field</span><span class="p">)</span>
</div></div></div>
<div style="margin: 8px 0; padding: 0 12px;"><p style="padding: 0; margin: 8px;">alternative: std::find_if.</p></div></div><br /><div style="border: 1px solid #C7CCD9; border-radius: 3px;"><div style="padding: 0; background: #F7F7F7; border-color: #e3e4e8; border-style: solid; border-width: 0 0 1px 0; margin: 0;"><div style="color: #74777d; background: #eff2f4; padding: 6px 8px; overflow: hidden;"><a style="float: right; text-decoration: none;" href="https://phabricator.kde.org/D12659#inline-64718">View Inline</a><span style="color: #4b4d51; font-weight: bold;">udsentry_benchmark.cpp:560</span></div>
<div style="font: 11px/15px "Menlo", "Consolas", "Monaco", monospace; white-space: pre-wrap; clear: both; padding: 4px 0; margin: 0;"><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="n">entry</span><span class="p">.</span><span class="n">stringValue</span><span class="p">(</span><span class="n">KIO</span><span style="color: #aa2211">::</span><span class="n">UDSEntry</span><span style="color: #aa2211">::</span><span class="n">UDS_GROUP</span><span class="p">)</span> <span style="color: #aa2211">==</span> <span class="n">entry2</span><span class="p">.</span><span class="n">stringValue</span><span class="p">(</span><span class="n">KIO</span><span style="color: #aa2211">::</span><span class="n">UDSEntry</span><span style="color: #aa2211">::</span><span class="n">UDS_GROUP</span><span class="p">);</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="n">QCOMPARE</span><span class="p">(</span><span class="n">equal</span><span class="p">,</span> <span style="color: #304a96">true</span><span class="p">);</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="p">}</span>
</div></div></div>
<div style="margin: 8px 0; padding: 0 12px;"><p style="padding: 0; margin: 8px;">QVERIFY(equal)</p></div></div><br /><div style="border: 1px solid #C7CCD9; border-radius: 3px;"><div style="padding: 0; background: #F7F7F7; border-color: #e3e4e8; border-style: solid; border-width: 0 0 1px 0; margin: 0;"><div style="color: #74777d; background: #eff2f4; padding: 6px 8px; overflow: hidden;"><a style="float: right; text-decoration: none;" href="https://phabricator.kde.org/D12659#inline-64724">View Inline</a><span style="color: #4b4d51; font-weight: bold;">udsentry_benchmark.cpp:593</span></div>
<div style="font: 11px/15px "Menlo", "Consolas", "Monaco", monospace; white-space: pre-wrap; clear: both; padding: 4px 0; margin: 0;"><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span style="color: #74777d">// This operator is essential to gain some speed, because the default == is slow</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span style="color: #304a96">inline</span> <span style="color: #aa4000">bool</span> <span style="color: #aa4000">operator</span> <span style="color: #aa2211">==</span> <span class="p">(</span><span style="color: #aa4000">const</span> <span class="n">Field</span> <span style="color: #aa2211">&</span><span class="n">other</span><span class="p">)</span> <span class="p">{</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span style="color: #aa4000">return</span> <span class="n">m_index</span> <span style="color: #aa2211">==</span> <span class="n">other</span><span class="p">.</span><span class="n">m_index</span><span class="p">;</span>
</div></div></div>
<div style="margin: 8px 0; padding: 0 12px;"><p style="padding: 0; margin: 8px;">const</p></div></div><br /><div style="border: 1px solid #C7CCD9; border-radius: 3px;"><div style="padding: 0; background: #F7F7F7; border-color: #e3e4e8; border-style: solid; border-width: 0 0 1px 0; margin: 0;"><div style="color: #74777d; background: #eff2f4; padding: 6px 8px; overflow: hidden;"><a style="float: right; text-decoration: none;" href="https://phabricator.kde.org/D12659#inline-64719">View Inline</a><span style="color: #4b4d51; font-weight: bold;">udsentry_benchmark.cpp:619</span></div>
<div style="font: 11px/15px "Menlo", "Consolas", "Monaco", monospace; white-space: pre-wrap; clear: both; padding: 4px 0; margin: 0;"><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="p">}</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="n">storage</span><span class="p">.</span><span class="n">append</span><span class="p">(</span><span class="n">Field</span><span class="p">(</span><span class="n">field</span><span class="p">,</span> <span class="n">value</span><span class="p">));</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="p">}</span>
</div></div></div>
<div style="margin: 8px 0; padding: 0 12px;"><p style="padding: 0; margin: 8px;">This relies on insert being called in ascending "field" order, for lower_bound to work.<br />
But that is not necessarily the case in kioslaves, so you'd have to insert at "index" here, instead of appending.</p></div></div><br /><div style="border: 1px solid #C7CCD9; border-radius: 3px;"><div style="padding: 0; background: #F7F7F7; border-color: #e3e4e8; border-style: solid; border-width: 0 0 1px 0; margin: 0;"><div style="color: #74777d; background: #eff2f4; padding: 6px 8px; overflow: hidden;"><a style="float: right; text-decoration: none;" href="https://phabricator.kde.org/D12659#inline-64720">View Inline</a><span style="color: #4b4d51; font-weight: bold;">udsentry_benchmark.cpp:634</span></div>
<div style="font: 11px/15px "Menlo", "Consolas", "Monaco", monospace; white-space: pre-wrap; clear: both; padding: 4px 0; margin: 0;"><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="p">}</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="n">QString</span> <span class="n">stringValue</span><span class="p">(</span><span class="n">uint</span> <span class="n">field</span><span class="p">)</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="p">{</span>
</div></div></div>
<div style="margin: 8px 0; padding: 0 12px;"><p style="padding: 0; margin: 8px;">const</p></div></div><br /><div style="border: 1px solid #C7CCD9; border-radius: 3px;"><div style="padding: 0; background: #F7F7F7; border-color: #e3e4e8; border-style: solid; border-width: 0 0 1px 0; margin: 0;"><div style="color: #74777d; background: #eff2f4; padding: 6px 8px; overflow: hidden;"><a style="float: right; text-decoration: none;" href="https://phabricator.kde.org/D12659#inline-64721">View Inline</a><span style="color: #4b4d51; font-weight: bold;">udsentry_benchmark.cpp:642</span></div>
<div style="font: 11px/15px "Menlo", "Consolas", "Monaco", monospace; white-space: pre-wrap; clear: both; padding: 4px 0; margin: 0;"><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="p">}</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span style="color: #aa4000">long</span> <span style="color: #aa4000">long</span> <span class="n">numberValue</span><span class="p">(</span><span class="n">uint</span> <span class="n">field</span><span class="p">,</span> <span style="color: #aa4000">long</span> <span style="color: #aa4000">long</span> <span class="n">defaultValue</span> <span style="color: #aa2211">=</span> <span style="color: #aa2211">-</span><span style="color: #601200">1</span><span class="p">)</span>
</div><div style="padding: 0 8px; margin: 0 4px; background: rgba(151, 234, 151, .6);"> <span class="p">{</span>
</div></div></div>
<div style="margin: 8px 0; padding: 0 12px;"><p style="padding: 0; margin: 8px;">const</p></div></div></div></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>michaelh, bruns<br /></div>