Simple Routing Table Performance

Hello,

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

I'm confused about your multiple uses of "instance".

Do you think you can give an example?

A binary tree seems sufficient for your needs, but a binary tree is not sufficient for network routers. They will probably use a variation of undirected graphs and sortable keys into such a graph or update such a graph with weighting.

Soma

To be honest, I'm not really sure that I'm using the right terminology! :o

Erm... it's a system where you write a "class", then create instances of that class at runtime.
Usually each class instance runs in its own thread, with one exception: there is an instance that is exclusively for handling user interfaces. You can create instances of UI-based classes but this single instance/thread will perform the processing for all of them (design decision to limit people doing silly things inside window procedures).

So, I have an initial non-UI instance (ID 2). It creates two UI-based instances (IDs 3 and 4) and expects to be able to talk to them. Both instances are handled by the UI instance (ID 1).

Naturally this is a simple example, you can imagine that many more instances are created/deleted over the lifetime of the application, but the instance with ID 2 still needs to be able to quickly communicate with IDs 3 and 4, by figuring out that it needs to send the method calls to ID 1.

Kapeesh?