| Summary: | ASTERISK-17801: Adding the Move to Front Hash functionality | ||
| Reporter: | Stefan Schmidt (schmidts) | Labels: | |
| Date Opened: | 2011-05-05 02:04:33 | Date Closed: | 2011-05-05 02:09:22 |
| Priority: | Minor | Regression? | No |
| Status: | Closed/Complete | Components: | General |
| Versions: | 1.8.4 | Frequency of Occurrence | |
| Related Issues: | |||
| Environment: | Attachments: | ||
| 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. ****** ADDITIONAL INFORMATION ****** 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/ ------------------------------------------------------------------------ http://svn.digium.com/view/asterisk?view=rev&revision=316962 | ||