You are viewing a plain text version of this content. The canonical link for it is here.

Posted to dev@qpid.apache.org by "Ken Giusti (Jira)" <ji...@apache.org> on 2020/06/01 19:56:00 UTC

[jira] [Created] (DISPATCH-1682) Optimize the parse tree match algorithm to avoid O(N) lookup

Ken Giusti created DISPATCH-1682:
------------------------------------

             Summary: Optimize the parse tree match algorithm to avoid O(N) lookup
                 Key: DISPATCH-1682
                 URL: https://issues.apache.org/jira/browse/DISPATCH-1682
             Project: Qpid Dispatch
          Issue Type: Bug
          Components: Routing Engine
    Affects Versions: 1.12.0
            Reporter: Ken Giusti
            Assignee: Ken Giusti
             Fix For: Backlog


The parse tree pattern match algorithm is optimized to search using a key that is made up of a sequence of tokens.

If all keys inserted into the parse tree are only single tokens then the lookup degrades into a linear list search. 

The treatment for every address is looked up in the parse tree.  If the address is not found the default treatment is used.  Lookups that miss end up performing O(N) searches.

The match algorithm should be re-designed to avoid O(N) searches for single token patterns.



--
This message was sent by Atlassian Jira
(v8.3.4#803005)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@qpid.apache.org
For additional commands, e-mail: dev-help@qpid.apache.org