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

[schmidts]

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

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/20110503/9478b02f/attachment-0001.htm>