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

[Steve Murphy]

OK, I just committed the beast (see below). I did some last minute
code review, cleanup and some work to improve the cid matching code.

I fully expect all heck to break loose, stuff to 'hit the fan', riots,
armed uprisings, burning in effigy, etc. 

Reproducing all the nuances of the pattern matching algorithms
is/was/could be a bit tricky, so I expect there to a complaint or two or
ten...

SO, if you are testing trunk, and suddenly are having dialplan matching
problems, please report the bug ASAP and I'll do my best to resolve it
ASAHP. (As Soon As Humanly Possible). I'll probably need your
extensions.* file(s), and a description of what went wrong in your
bugs.digium.com report.

Also, might be interesting for you all who have gigantic dialplans, to
test this out and see if you get any performance enhancement! Can you
now handle twice the call volume? Ten times? No diff? Tell me!

murf
aka codefreeze



On Mon, 2007-11-05 at 10:41 -0700, Steve Murphy wrote:
> 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/20071109/9245fae5/attachment.bin