<html>
<body>
<div style="font-family: Verdana, Arial, Helvetica, Sans-Serif;">
<table bgcolor="#f9f3c9" width="100%" cellpadding="12" style="border: 1px #c9c399 solid; border-radius: 6px; -moz-border-radius: 6px; -webkit-border-radius: 6px;">
<tr>
<td>
This is an automatically generated e-mail. To reply, visit:
<a href="https://git.reviewboard.kde.org/r/118452/">https://git.reviewboard.kde.org/r/118452/</a>
</td>
</tr>
</table>
<br />
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: 10px;">
<p style="margin-top: 0;">On December 10th, 2014, 11:03 p.m. UTC, <b>Milian Wolff</b> wrote:</p>
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: 10px;">
<pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;"><p style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;">LGTM, some nitpicks. And of course we need the results of the benchmark in release mode.</p></pre>
</blockquote>
</blockquote>
<pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;"><p style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;">NOTE: I just pushed some fixes to udsentrybenchmark, which was pretty broken in itself. It contained lots of unrelated stuff in its hotpath. Now, the effects of your patch should stand out much better. And indeed, for me I get these results:</p>
<p style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;">before:</p>
<p style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;"><strong style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;"><em style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;">*</em></strong><strong style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;"> Start testing of UDSEntryBenchmark <strong style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;"><em style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;">*</em></strong></strong>
Config: Using QtTest library 5.3.2, Qt 5.3.2
PASS : UDSEntryBenchmark::initTestCase()
PASS : UDSEntryBenchmark::createSmallEntries()
RESULT : UDSEntryBenchmark::createSmallEntries():
340,701,155 instructions per iteration (total: 340,701,155, iterations: 1)
PASS : UDSEntryBenchmark::createLargeEntries()
RESULT : UDSEntryBenchmark::createLargeEntries():
151,036,236 instructions per iteration (total: 151,036,236, iterations: 1)
PASS : UDSEntryBenchmark::readFieldsFromSmallEntries()
RESULT : UDSEntryBenchmark::readFieldsFromSmallEntries():
109,056,035 instructions per iteration (total: 109,056,035, iterations: 1)
PASS : UDSEntryBenchmark::readFieldsFromLargeEntries()
RESULT : UDSEntryBenchmark::readFieldsFromLargeEntries():
173,396,471 instructions per iteration (total: 173,396,471, iterations: 1)
PASS : UDSEntryBenchmark::saveSmallEntries()
RESULT : UDSEntryBenchmark::saveSmallEntries():
482,945,427 instructions per iteration (total: 482,945,427, iterations: 1)
PASS : UDSEntryBenchmark::saveLargeEntries()
RESULT : UDSEntryBenchmark::saveLargeEntries():
242,482,043 instructions per iteration (total: 242,482,043, iterations: 1)
PASS : UDSEntryBenchmark::loadSmallEntries()
RESULT : UDSEntryBenchmark::loadSmallEntries():
976,623,140 instructions per iteration (total: 976,623,140, iterations: 1)
PASS : UDSEntryBenchmark::loadLargeEntries()
RESULT : UDSEntryBenchmark::loadLargeEntries():
563,162,165 instructions per iteration (total: 563,162,165, iterations: 1)
PASS : UDSEntryBenchmark::cleanupTestCase()
Totals: 10 passed, 0 failed, 0 skipped
<strong style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;"><em style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;">*</em></strong><strong style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;"> Finished testing of UDSEntryBenchmark <strong style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;"><em style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;">*</em></strong></strong></p>
<p style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;">after:</p>
<p style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;"><strong style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;"><em style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;">*</em></strong><strong style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;"> Start testing of UDSEntryBenchmark <strong style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;"><em style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;">*</em></strong></strong>
Config: Using QtTest library 5.3.2, Qt 5.3.2
PASS : UDSEntryBenchmark::initTestCase()
PASS : UDSEntryBenchmark::createSmallEntries()
RESULT : UDSEntryBenchmark::createSmallEntries():
210,401,123 instructions per iteration (total: 210,401,123, iterations: 1)
PASS : UDSEntryBenchmark::createLargeEntries()
RESULT : UDSEntryBenchmark::createLargeEntries():
124,268,824 instructions per iteration (total: 124,268,824, iterations: 1)
PASS : UDSEntryBenchmark::readFieldsFromSmallEntries()
RESULT : UDSEntryBenchmark::readFieldsFromSmallEntries():
121,256,029 instructions per iteration (total: 121,256,029, iterations: 1)
PASS : UDSEntryBenchmark::readFieldsFromLargeEntries()
RESULT : UDSEntryBenchmark::readFieldsFromLargeEntries():
235,066,440 instructions per iteration (total: 235,066,440, iterations: 1)
PASS : UDSEntryBenchmark::saveSmallEntries()
RESULT : UDSEntryBenchmark::saveSmallEntries():
463,545,365 instructions per iteration (total: 463,545,365, iterations: 1)
PASS : UDSEntryBenchmark::saveLargeEntries()
RESULT : UDSEntryBenchmark::saveLargeEntries():
234,572,009 instructions per iteration (total: 234,572,009, iterations: 1)
PASS : UDSEntryBenchmark::loadSmallEntries()
RESULT : UDSEntryBenchmark::loadSmallEntries():
831,722,102 instructions per iteration (total: 831,722,102, iterations: 1)
PASS : UDSEntryBenchmark::loadLargeEntries()
RESULT : UDSEntryBenchmark::loadLargeEntries():
446,182,994 instructions per iteration (total: 446,182,994, iterations: 1)
PASS : UDSEntryBenchmark::cleanupTestCase()
Totals: 10 passed, 0 failed, 0 skipped
<strong style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;"><em style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;">*</em></strong><strong style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;"> Finished testing of UDSEntryBenchmark <strong style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;"><em style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;">*</em></strong></strong></p></pre>
<br />
<p>- Milian</p>
<br />
<p>On December 9th, 2014, 10:44 p.m. UTC, Frank Reininghaus wrote:</p>
<table bgcolor="#fefadf" width="100%" cellspacing="0" cellpadding="12" style="border: 1px #888a85 solid; border-radius: 6px; -moz-border-radius: 6px; -webkit-border-radius: 6px;">
<tr>
<td>
<div>Review request for KDE Frameworks and David Faure.</div>
<div>By Frank Reininghaus.</div>
<p style="color: grey;"><i>Updated Dec. 9, 2014, 10:44 p.m.</i></p>
<div style="margin-top: 1.5em;">
<b style="color: #575012; font-size: 10pt;">Repository: </b>
kio
</div>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Description </h1>
<table width="100%" bgcolor="#ffffff" cellspacing="0" cellpadding="10" style="border: 1px solid #b8b5a0">
<tr>
<td>
<pre style="margin: 0; padding: 0; white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;"><p style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;">I am continuing to split up https://git.reviewboard.kde.org/r/113355/ , which attempts to make UDSEntry more efficient memory and CPU-wise, into independent parts. This is the third step after
https://git.reviewboard.kde.org/r/113591/ and https://git.reviewboard.kde.org/r/115739/ .</p>
<p style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;">The present patch modifies the internal data storage of UDSEntry. UDSEntry contains a mapping from unsigned int keys to "Field" values, where Field is a struct that contains a QString and a long long (some keys correspond to numeric values, like size, date, etc, whereas others, like user and group, correspond to a QString).</p>
<p style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;">Currently, UDSEntry stores all data in a QHash<uint, Field> internally. This ensures that everything can be accessed in O(1) time, but is not very efficient memory-wise because a separate memory allocation is done for each hash node.</p>
<p style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;">I propose to change this and store both the uint keys and the Field values in a QVector each. This means that accessing a value becomes a O(n) operation, since the entire QVector of keys may need to be scanned in order to find a value, but because the number n of values in a UDSEntry is usually quite small and can currently not exceed a number ~100, this should not matter in practice.</p>
<p style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;">Some parts of https://git.reviewboard.kde.org/r/113355/ are still missing:</p>
<p style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;">(a) The QVectors which store the keys (which are usually the same for all items in a directory) are not shared yet. Changing this would reduce the memory usage further, but I decided to keep this change separate in order to keep the current patch small and easy to understand. Moreover, this makes it easier to benchmark other similar approaches (e.g., replace QVector by std::vector, or store keys and values together in a std::vector<std::pair<uint,Field>>).</p>
<p style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;">(b) No space is reserved in the vectors when key/value pairs are inserted one by one. Implementing this would make UDSEntry faster on the slave side (since repeated re-allocations would not be necessary any more), but this can be done in a later patch. Moreover, it might not be needed any more if UDSEntry is not used directly any more on the slave side, as suggested on the frameworks mailing list by Aaron (good idea BTW!). </p></pre>
</td>
</tr>
</table>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Testing </h1>
<table width="100%" bgcolor="#ffffff" cellspacing="0" cellpadding="10" style="border: 1px solid #b8b5a0">
<tr>
<td>
<pre style="margin: 0; padding: 0; white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;"><p style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;">Unit tests still pass.</p>
<p style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;">The memory usage of listjobtest with a directory with 100,000 files is reduced from 71344 K to 35392 K according to KSysGuard. I see similar savings when opening the directory in Dolphin.</p>
<p style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;">I still haven't set up a Qt5/KF5 build in release mode (shame on me!), so I cannot present any benchmark results.</p></pre>
</td>
</tr>
</table>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Diffs</b> </h1>
<ul style="margin-left: 3em; padding-left: 0;">
<li>autotests/udsentry_benchmark.cpp <span style="color: grey">(b5fa8d6)</span></li>
<li>src/core/udsentry.h <span style="color: grey">(98a7035)</span></li>
<li>src/core/udsentry.cpp <span style="color: grey">(b806e0e)</span></li>
<li>src/ioslaves/file/file.cpp <span style="color: grey">(1a2a767)</span></li>
<li>tests/udsentrybenchmark.cpp <span style="color: grey">(d9a118c)</span></li>
</ul>
<p><a href="https://git.reviewboard.kde.org/r/118452/diff/" style="margin-left: 3em;">View Diff</a></p>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">File Attachments </h1>
<li><a href="https://git.reviewboard.kde.org/media/uploaded/files/2014/12/09/038e443c-78eb-443b-b33a-b451b28d10ea__UDSEntry-benchmarks.png">Benchmark results</a></li>
</ul>
</td>
</tr>
</table>
</div>
</body>
</html>