Simple Routing Table Performance
I'm looking at creating a routing system for use with an inter-thread communication (asynchronous method calling) framework that I am working on.
I have a function that is analogous to Windows's PostMessage. It dispatches method calls to the incoming queue of the appropriate instance. That instance may be a single thread doing the work of a specific instance, or it may be a thread that handles multiple instances. In the latter case, I need a way to quickly find which thread is responsible for a given instance.
The best thing that I can come up with at the moment is a per-thread structure that stores the thread ID for a given instance ID. But what is the fastest way to perform a search (this function would be called several times on average per method call, per thread)?
A binary tree initially came to mind, but I'm not sure. This is a fairly simple framework (number of instances will never exceed 255, instance IDs are generated sequentially until they wrap around), so the work required to maintain a balanced tree for each thread may not be worth it. Would it be better to simply have an array of 255 entries and index directly into it (would cost a couple KB in memory per thread)?
I don't think actual network routers use trees, do they?
What about some sort of structure where each successful search for an instance ID promotes that ID, making it faster to find it the next time?
Sorry about the questions, but this is probably the most performance critical aspect of what I'm doing. :o