Fast search of guid tables

We are increasingly using guids as keys for objects. Currently the guids are kept in sorted arrays in memory and lookup is done by binary search.

Since guids are widely used I guess the best organisation for fast lookup is thoroughly researched by now. I am looking for a pointer to a good description (on the web) of the best algoritms for this or advice from somebody who has firsthand experience with implementation of this.

My question is: Can we get significantly faster lookup on guids than binary sort for our use (se below)? In that case, what organisation/lookup algorithms would be faster?

Here are some details of our implementation:

It is programmed in C++ (We are not using a DB tool) .
The guid tables will typically be up to 1 million entries.
The guid tables will all be in memory.
The lookup speed is very critical and it is done many times in "inner loops".
The tables are not known at compiletime.
Some tables are fairly stable after first time load.
Some tables are dynamic (delete/insert). Most of the operations will however be add or insert.
The speed of the delete/insert/add administration is not as critical as the lookup speed.
We know in advance which tables are dynamic and which are stable.

-Rune
rj_dds_noAsked:
Who is Participating?
 
TommySzalapskiCommented:
I haven't used Boost myself, but GUIDs has very nicely using any normal hashing algorithm, so I would say it should work quite well. You could just run some tests and see what you get out of it, but either method should approximate O(1), so they both would be feasible for your application.
0
 
TommySzalapskiCommented:
Binary search is O(lg(n)). Hash tables approximate O(1). You really need some kind of indexing/hash table.
Have you ever used a hash table? Are you using standard C++ or Visual C++?
0
 
rj_dds_noAuthor Commented:
We use Visual C++, but try avoid too much MS-extensions. Hashing can be implemented in many ways. For a hashing advice to be useful, it would have to point to specific hashing techniques that have proven useful for lookup in guid tables.
0
Cloud Class® Course: Certified Penetration Testing

This CPTE Certified Penetration Testing Engineer course covers everything you need to know about becoming a Certified Penetration Testing Engineer. Career Path: Professional roles include Ethical Hackers, Security Consultants, System Administrators, and Chief Security Officers.

 
TommySzalapskiCommented:
You could implement your own hash table I guess, but the Dictionary class is in there already so I would use that. It's been used for GUIDs before (and out performs other hash tables too). Se here for an example which was made using GUIDs.
http://www.phase9studios.com/post/2008/01/08/DictionaryVSHashTable.aspx
0
 
rj_dds_noAuthor Commented:
Thanks! We will look into the Dictonay class and see if it is an option for us and how fast it performs. I'll come back on it when we have checked it out.
0
 
rj_dds_noAuthor Commented:
We use Boost. I discorvered that boost now have uuid with support for boost::hash

Any experience with lookup performance in uuid maps using boost anyone?
0
 
rj_dds_noAuthor Commented:
We are not using managed code in C++ and using the Dictonary class will require access through COM which we belive is not optimal for such high performance needs.

We were looking for more specific experience with a solution like Boost. But after researching more on the guid/uuid I see that it should be well suited for hashing and I agree that any sensible implementation of this should give very good guid lookup performance.
0
 
rj_dds_noAuthor Commented:
Had hoped for more specific experience and advice on the topic. But the general advice is correct and fair enough.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.