[
https://issues.apache.org/jira/browse/QPID-2897?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Ken Giusti updated QPID-2897:
-----------------------------
Attachment: TrieMapLookup.cpp
TrieMapLookup.h
Here's a very rough prototype for a tree-of-maps approach to topic routes.
The basic concept is to break a binding route up into tokens, and build an
ordered tree of nodes from each token. As binding routes are added, a node may
end up having more than one "child" token. In these cases, I store a reference
to the child node in a map index by the child's token.
There are special nodes + children for wildcard tokens (* and #).
Using a simple benchmark against a large set of synthetic routes, the proposed
lookup scales well:
Routing with 1 routes and sending 10000 messages:
QpidLinearLookup - Prep: 0 seconds, Lookups:0.03 seconds
msgs=30000 matches=0
TrieMapLookup - Prep: 0 seconds, Lookups:0.06 seconds
msgs=30000 matches=0
Routing with 10 routes and sending 10000 messages:
QpidLinearLookup - Prep: 0 seconds, Lookups:0.14 seconds
msgs=30000 matches=27000
TrieMapLookup - Prep: 0 seconds, Lookups:0.08 seconds
msgs=30000 matches=27000
Routing with 100 routes and sending 10000 messages:
QpidLinearLookup - Prep: 0 seconds, Lookups:1.07 seconds
msgs=30000 matches=29700
TrieMapLookup - Prep: 0 seconds, Lookups:0.09 seconds
msgs=30000 matches=29700
Routing with 1000 routes and sending 10000 messages:
QpidLinearLookup - Prep: 0.01 seconds, Lookups:10.57 seconds
msgs=30000 matches=29970
TrieMapLookup - Prep: 0.01 seconds, Lookups:0.1 seconds msgs=30000
matches=29970
Routing with 10000 routes and sending 10000 messages:
QpidLinearLookup - Prep: 0.02 seconds, Lookups:106.42 seconds
msgs=30000 matches=29997
TrieMapLookup - Prep: 0.11 seconds, Lookups:0.11 seconds
msgs=30000 matches=29997
> C++ broker: improve scale and speed of route matching algorithm for topic
> exchanges.
> ------------------------------------------------------------------------------------
>
> Key: QPID-2897
> URL: https://issues.apache.org/jira/browse/QPID-2897
> Project: Qpid
> Issue Type: Improvement
> Components: C++ Broker
> Affects Versions: 0.6
> Reporter: Ken Giusti
> Assignee: Ken Giusti
> Priority: Minor
> Attachments: TrieMapLookup.cpp, TrieMapLookup.h
>
>
> The current route match algorithm used by a topic exchange is merely a linear
> search across all bindings, resulting in O(n) performance (n=# of bindings).
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
Apache Qpid - AMQP Messaging Implementation
Project: http://qpid.apache.org
Use/Interact: mailto:[email protected]
