Thread: Simple Routing Table Performance

  1. #1
    Registered /usr
    Join Date
    Aug 2001
    Newport, South Wales, UK

    Question 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.

  2. #2
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    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.


  3. #3
    Registered /usr
    Join Date
    Aug 2001
    Newport, South Wales, UK
    To be honest, I'm not really sure that I'm using the right terminology!

    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.


Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Hash Table with Simple record in files
    By infantheartlyje in forum C Programming
    Replies: 77
    Last Post: 10-13-2011, 03:15 AM
  2. hash table's performance
    By Verdagon in forum C++ Programming
    Replies: 10
    Last Post: 12-08-2010, 02:30 PM
  3. DHCP & routing table
    By Cactus_Hugger in forum Tech Board
    Replies: 6
    Last Post: 09-04-2009, 11:39 AM
  4. How i can modify routing table and coding on MAC layer?
    By comsci42 in forum Networking/Device Communication
    Replies: 0
    Last Post: 04-09-2006, 06:47 PM
  5. Errors in a simple hash table class.
    By TheSquid in forum C++ Programming
    Replies: 4
    Last Post: 02-23-2005, 04:49 AM