Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / General Programming / (almost) unique id good old question with no answer ? Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
kiddygames

February 28, 2005, 02:41 AM

Hello,

I know it's something that has already been discussed a lot but I can't see any good way to do it.

Let suppose you have some maps like this :

  1. std::map<std::string,things*>
for exemple. Accessing the map data with string is slower than with unsigned int IDs for exemple, but it's so easy with strings.

Creating a unique (or "almost" unique)IDs from a string can be done easilly, but I'm looking for a way to do it at preprocessor time. So I'll be able to do things like that:

  1.  
  2. std::map<unsigned int,things*> testMap;
  3.  
  4. things* testAcces=testMap[TO_UID("firstThingName")];
  5.  
  6.  


It can also be usefull for fast comparison:

  1.  
  2.  
  3. if(testAcces->myUID==TO_UID("firstThingName"))
  4. {
  5.  // this is what I'm looking for
  6. }
  7.  
  8.  


Any good ideas ?

Stéphane

 
Danny Chapman

February 28, 2005, 04:14 AM

If all your strings are known at compile time (must be so for your TO_UID macro to work), why not just store them all in one place - e.g.

MyStrings.cpp

const char * const ratString = "Rat";
const char * const catString = "Cat";

etc, and declare these in MyStrings.hpp

Then when you come to use it just use/compare the char* pointers directly. But this seems to obvious - maybe I misunderstood what you want to do...

 
Victor Widell

February 28, 2005, 04:32 AM

I would skip the string ID and go for an automatically generated int. Simple and robust.

 
kiddygames

February 28, 2005, 04:40 AM

Well, it's a good answer of course, but I'm using a modular design with class defined in dll, instance factory and stuff like that.

The main bad point with using pointers is that using windows dll, they will be stored at different addresses in each dll and in main app, so compare the pointer is not so safe. I think there are ways to use the same pointers everywhere (put everything in a big struct you give to each module for exemple) but each time you add a string in the list, you have to rebuild all (even if you just add a string for a dll class).

I would like something more straightforward with no runtime overhead.


Stéphane

 
kiddygames

February 28, 2005, 04:42 AM



Victor Widell wrote: I would skip the string ID and go for an automatically generated int. Simple and robust.


simple, robust, but how to do it automatically at preprocessor time ? this is the question...

Stéphane

 
davepermen

February 28, 2005, 04:52 AM

const ID firstThingID = __COUNTER__;

not portable, but works on some compilers..

 
Rui Martins

February 28, 2005, 10:07 AM

If I'm not mistaken Map already uses a Hash to convert those strings/id's to a HashMap, so there shouldn't be any speed problem, unless your strings are huge.

If there is a problem, define a Hash function to convert your strings to IDs once, at program start, then use the IDs in the std::map.

 
Daniel Hein

February 28, 2005, 01:15 PM

#define TO_UID(x) (int)&x

shouldn't that work?

It will just return the pointer to the string from the constant string table, and cast it to an int...

 
MadHed

February 28, 2005, 06:18 PM

Why don't you just use enums? O_o

 
Reedbeta

February 28, 2005, 06:36 PM

I think Rui is right. Using ints instead of strings isn't likely to gain you that much speed, so it's probably not worth worrying about.

 
juhnu

February 28, 2005, 08:31 PM

yeah use just strings and if the performance is a _real_ issue then you can use handles in the manager. handle can be a pointer to a string inside the manager class, so you can use always the same function. if you just happen to use valid handle the string compare is skipped.

//registering the module
ManagerSingleton().Register(this_or_something, L"MyModule" );
.....

ManagerSingleton().Get(L"MyModule") //compares strings
//or if you want to have possibly faster access you can store the handle and use that

const wchar_t* handle = ManagerSingleton().GetID(L"MyModule");
ManagerSingleton().Get(handle); //compares just pointers




juhani

 
Brian Legge

February 28, 2005, 09:08 PM

It seems like there are two different pressures here:

1) Rapid mapping from string to object.
2) Minimize memory use by using unique ints as identifiers instead of strings (ie don't have strings at all).

If you are trying to address the first issue, you have a few simple options. You can use a hash_map (not part of the standard, but most stl implementations have some form of one), or you can use create a little wrapper class (something like):

  1.  
  2. class Token
  3. {
  4.     // Hash the string on assignment
  5.     Token( const char* const );
  6.  
  7.     // Sort by hash, then string.
  8.     bool operator<( const Token& ) const
  9.  
  10.     uint32      m_hash;
  11.     std::string m_string;
  12. };
  13.  


which does hash comparisions as an 'early out' -- basically, order by hash, and if the hashes are the same, order by string. Assuming a decent hash function, you should be able to almost always avoid the string comparision.

I would also suggest stepping in to your map class implementation to see how it does comparisions. The last version I worked with did std::string less than tests to sort, which differs from the implementation Rui uses.

If you are more interested in the second issue, well, you need to have some sort of off line string database which contains unique IDs for all the strings in the game. This has the nice payoff of avoiding string overhead, but can complicate debugging.

 
kiddygames

March 01, 2005, 02:43 AM


Rui Martins wrote: If I'm not mistaken Map already uses a Hash to convert those strings/id's to a HashMap, so there shouldn't be any speed problem, unless your strings are huge. If there is a problem, define a Hash function to convert your strings to IDs once, at program start, then use the IDs in the std::map.


Well, I have seen a few monthes ago a paper with some kind of "short fixed size strings", and accessing objects in a map with those strings was really faster. In fact, if I remember well, the "trick" was just to use unsigned long ID = 'myclass', assuming unsigned long has a size of 8 bytes. I'm sorry that I just can't find this paper anymore...

At that time, I've done some testing and using integer was really faster than using string to access objects in maps. I suppose that when use :

  1.  
  2.  
  3. thing* some=theMap["the_Object_I_Want"];
  4.  
  5.  


there's an allocation (implicit std::string constructor from the const char*), and a destruction, and perhaps this is the main speed problem.

Stéphane

 
kiddygames

March 01, 2005, 03:12 AM

Daniel Hein wrote: #define TO_UID(x) (int)&x shouldn't that work? It will just return the pointer to the string from the constant string table, and cast it to an int...


Well, it's just the same problem as using pointers, the returned pointer will be different (unless you use some manager like the one proposed by juhnu) in each dll and in the main app, and you have to use a global map for all the string used in the whole code.

MadHed wrote: Why don't you just use enums? O_o


Ok, I'm perhaps a bit lazy, or it's because my main language is french so I didn't wanted to go into a in depth explanation... In fact I have no real speed problems at the moment, I use string as ID for my instance factory, or to search in maps, and I like it that way cause I think this is an "elegant" way to do.

So I'm just looking for a more efficient, but "elegant" way to do...

Reedbeta wrote: I think Rui is right. Using ints instead of strings isn't likely to gain you that much speed, so it's probably not worth worrying about.


I'm really not sure about it (see the answer to Rui).

juhnu wrote: yeah use just strings and if the performance is a _real_ issue then you can use handles in the manager


That's what I'm doing at the moment (using strings I mean) ;-)... But I'm curious and always try to find faster/better ways... Your manager can do the trick, and the "Token" class by Brian Legge also, but the id is computed at runtime, or at startup time if you use a map of used strings.

I was just looking for a trick to make a TO_UID macro, so that I was able to just replace all my code using :

  1.  
  2.  
  3. std::map<std::string,things*> testMap;
  4. things* testAcces=testMap["firstThingName"];
  5.  
  6.  


by code using :

  1.  
  2.  
  3. std::map<unsigned int,things*> testMap;
  4. things* testAcces=testMap[TO_UID("firstThingName")];
  5.  
  6.  


More efficient and as "elegant". But doing it with macro seems impossible.

Stéphane




 
Corre

March 01, 2005, 03:49 AM

Use a manager then, and have your TO_UID macro call the appropriate manager method.

 
_aphex_

March 01, 2005, 09:23 AM

Are you on about template metaprogramming?

 
kiddygames

March 01, 2005, 10:55 AM

_aphex_ wrote: Are you on about template metaprogramming?


err! not sure I understand you ? I've also looked for solutions using template metaprogramming but with no success. You can't do :

  1.  
  2.  
  3. template <const char *> class TO_UID
  4. {
  5.  // my code here
  6. };
  7.  
  8. TO_UID<"toto"> aTest; // compiler don't like it
  9.  
  10.  


Do you have a solution ?

Stéphane

 
Matt Newport

March 01, 2005, 01:42 PM

std::map isn't implemented as a hash table. It's a red-black tree in every STL implementation I know of. std::map is intended to be efficient for frequent insertions, deletions and lookups. Often you actually want a structure optimized for very frequent lookups with relatively infrequent insertions and deletions. std::map is pretty inefficient for that common case and espescially so if you use std::strings as the key. It may still be 'good enough' for many uses but it's certainly far from optimal.

 
kiddygames

March 10, 2005, 06:00 AM

well, I wanted to use a macro to avoid runtime evaluation, not just to use a macro...

Your solution just hide the use of a manager to the reader of the code, but doesn't change anything for the compiler...

Stéphane

 
robomurito

March 10, 2005, 10:01 AM

You can't really break up string constants to pass in portions as template arguments. So template metaprogramming is out.

The best thing you can do is something like this:

  1.  
  2. std::map<unsigned int, things*> stuff;
  3.  
  4. void foo() {
  5.    static unsigned int uid = compute_uid("foo");
  6.    things* x = stuff[uid];
  7.    // .. do more later
  8. }
  9.  


Because uid is static, you only get a performance hit the first time the code is executed. Once uid is computed, you never do the expensive hashing again.

In general, I would advise against doing hashing in your inner loops in general.

 
This thread contains 20 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.