[asterisk-dev] [Code Review] Adding the Move to Front Hash functionality

[Marquis]

-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviewboard.asterisk.org/r/1201/#review3467
-----------------------------------------------------------

Ship it!


Looks like a very worthwhile change for large systems!

- Marquis


On 2011-05-03 06:31:28, schmidts wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviewboard.asterisk.org/r/1201/
> -----------------------------------------------------------
> 
> (Updated 2011-05-03 06:31:28)
> 
> 
> Review request for Asterisk Developers.
> 
> 
> Summary
> -------
> 
> 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.
> 
> 
> Diffs
> -----
> 
>   trunk/main/astobj2.c 316039 
> 
> Diff: https://reviewboard.asterisk.org/r/1201/diff
> 
> 
> Testing
> -------
> 
> 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.
> 
> 
> Thanks,
> 
> schmidts
> 
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.digium.com/pipermail/asterisk-dev/attachments/20110504/c7b31912/attachment.htm>