[asterisk-dev] fast-ast2 ready to merge to trunk, is that OK?

[Steve Murphy]

OK, I've been working on this for, what, a year now or so.

And today, I plan to merge it to trunk.

Unless violent objections, or serious flaws in my thinking are
expressed, that is.

I have blogged on the fast-ast project earlier, you may wish to review
that
material. It's changed only slightly. (see
hattp://www.asterisk.org/node/112)
(Stupid blog; my nice little graph disappeared!)   !$!@$!@$@$!!!!

I made sure I could do an 'ael reload' without problems, which required
some detailed attention to the merge_contexts_and_delete() and the
__ast_context_create functions, so they are looking for the right thing
in the right places, in the right way.

I also insured the right things happen if you add extensions on the fly
after
the initial 'load_module' of ael or extensions.conf. I also insured that
the new stuff is properly destroyed and freed in the right places.

It all appears to work. So, I'd like to check it in, please.

What's the advantages?

1. Flat response times in searching for a matching context, exten, and
priority in the dialplan, which were previously subject to exponential
slowdowns due to linked list searches. I have made graphs from 1 to 1000
elements in each category. This means that in a dialplan with 1000
contexts, and the context we are executing in, has 1000 extensions, and
in that context, we are executing apps after the 1000th priority, we
will see a speedup over the old code of roughly 23x. For bigger
dialplans, the speedup will be greater.  For dialplans with
over 10,000 extensions, the speedup could be maybe 100x; I haven't
measured it yet.

How did I do it?

Contexts and priorities are now stored in hash tables. I build a special
'trie' or tree that represents all the extensions. Using a 'scoreboard'
approach, it mimics the algorithm to find extensions, but instead, the
time it takes is more a function of the length of the patterns, than how
many there are. Thus, even finding an extension match is now pretty much
constant-time. (See the match_char code in main/pbx.c in
team/murf/fast-ast2) --Unfortunately, this cannot apply to realtime. No
way to know when the trie should be changed.

There are bound hiccups here and there over fine points, I'll try to
iron those out as they come up.

Any disadvantages?

Well, just two, AFAICT. 

1. In the case of a small dialplan, there's a 4% to 5% performance loss
over the current method in trunk. I THINK it's because the string
hashing for context names is taking up some cpu cycles.  To make you-all
feel better about this hit, allow me to point out that late last week, I
improved performance of the pbx priority processing engine by over 30%
So, all in all, you are still 25% ahead in ultra-small dialplan mode.
Not many are going to be hurt by this, I think. We
are still 5% (overall) ahead of where we were over a year ago.

2. The hash tables and Trie take up some added space; not huge, but
extra, nonetheless. Part of this is because I left the old linked lists
in place to reduce the impact of the code on the Asterisk code base. Old
stuff like the CLI 'dialplan show', will work as it has all along. In
the future, we can weed out any code that depends on the linked lists,
and get rid of the linked lists. But not today.

If you have objections, respond quickly. I guess, I can do no damage
that a 'revert' couldn't fix...

murf
(aka codefreeze)


-- 
Steve Murphy
Software Developer
Digium
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/x-pkcs7-signature
Size: 3227 bytes
Desc: not available
Url : http://lists.digium.com/pipermail/asterisk-dev/attachments/20071105/08dc583e/attachment-0001.bin