Summary:ASTERISK-17801: Adding the Move to Front Hash functionality
Reporter:Stefan Schmidt (schmidts)Labels:
Date Opened:2011-05-05 02:04:33Date Closed:2011-05-05 02:09:22
Versions:1.8.4 Frequency of
Description: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.


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.
Comments:By: Digium Subversion (svnbot) 2011-05-05 02:09:22

Repository: asterisk
Revision: 316962

U   trunk/main/astobj2.c

r316962 | schmidts | 2011-05-05 02:09:21 -0500 (Thu, 05 May 2011) | 10 lines

Adding the Move to Front Hash functionality

Moving a found object to the front of its bucket to reduce the necessary traversal steps to find an object. This change improves the search time on large system with many data or in link lists.

(closes issue ASTERISK-17801)
Reported by: schmidts

Review: https://reviewboard.asterisk.org/r/1201/