<html>
<body>
<div style="font-family: Verdana, Arial, Helvetica, Sans-Serif;">
<table bgcolor="#f9f3c9" width="100%" cellpadding="8" style="border: 1px #c9c399 solid;">
<tr>
<td>
This is an automatically generated e-mail. To reply, visit:
<a href="https://reviewboard.asterisk.org/r/1201/">https://reviewboard.asterisk.org/r/1201/</a>
</td>
</tr>
</table>
<br />
<table bgcolor="#fefadf" width="100%" cellspacing="0" cellpadding="8" style="background-image: url('https://reviewboard.asterisk.orgrb/images/review_request_box_top_bg.png'); background-position: left top; background-repeat: repeat-x; border: 1px black solid;">
<tr>
<td>
<div>Review request for Asterisk Developers.</div>
<div>By schmidts.</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;">the so called "move to front" MTF functionality is a well known and documented improvement for hashes to improve the speed and accesstime for each object in the hash.
The idea of MTF is very simple. If you have a match on the object you searched, just move this object to the first position in the bucket. This operation is just a pointer exchange which means its cheap but could improve the performance well.
MTF works best when the spread over the buckets isnt well or if there are more objects than buckets. It will not help if there are only very few objects.
</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;">i didnt have done any time measurement but i counted how many compares are done to find an object. the following test results shows that its only a very little bit slower if there are less objects (in my test only 10 sip peers). if there is a big amount of objects (20k peers) the difference is like 5 times faster.
i used sipp to generate calls against asterisk, only to start the internal_ao2_callback function.
a short description about these values:
callbacks is the amount how often internal_ao2_callback was called.
bucketruns is the complete amount of traversal steps over the buckets
avg runs is the amount how many traversal steps are used to find the right object
10 peers with MTF
callbacks: 18201 bucketruns: 48440 avg runs: 2.661392
callbacks: 30001 bucketruns: 101864 avg runs: 3.395354
10 peers without MTF
callbacks: 18201 bucketruns: 46847 avg runs: 2.573869
callbacks: 30001 bucketruns: 101869 avg runs: 3.395520
as i said above with less date like 10 sip peers the difference is atomic.
1000 peers with mtf
callbacks: 20001 bucketruns: 82307 avg runs: 4.115144
callbacks: 30001 bucketruns: 116090 avg runs: 3.869538
1000 Peers without mtf
callbacks: 20001 bucketruns: 121156 avg runs: 6.057497
callbacks: 30001 bucketruns: 182905 avg runs: 6.096630
for 1000 peers there is a difference of nearly 2 times faster after 30k function calls.
20000 peers with MTF
callbacks: 8501 bucketruns: 33046 avg runs: 3.887307
callbacks: 30001 bucketruns: 161646 avg runs: 5.388021
20000 peers without MTF
callbacks 8501 bucketruns: 126252 avg runs: 14.851429
callbacks: 30001 bucketruns: 749008 avg runs: 24.966101
for 20.000 peers the difference after 30k function calls is nearly 5 times faster.</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>trunk/main/astobj2.c <span style="color: grey">(316039)</span></li>
</ul>
<p><a href="https://reviewboard.asterisk.org/r/1201/diff/" style="margin-left: 3em;">View Diff</a></p>
</td>
</tr>
</table>
</div>
</body>
</html>