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/11 12:35:00 UTC
[jira] [Resolved] (DISPATCH-1682) Optimize the parse tree match
algorithm to avoid O(N) lookup
[ https://issues.apache.org/jira/browse/DISPATCH-1682?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Ken Giusti resolved DISPATCH-1682.
----------------------------------
Fix Version/s: (was: Backlog)
1.13.0
Resolution: Fixed
> 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
> Priority: Major
> Fix For: 1.13.0
>
>
> 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