Fast 64 bit comparison

Question

Hi

I'm working on a GUI framework, where I want all the elements to be identified by ascii strings of up to 8 characters (or 7 would be ok).

Every time an event is triggered (some are just clicks, but some are continuous), the framework would callback to the client code with the id and its value.

I could use actual strings and strcmp(), but I want this to be really fast (for mobile devices), so I was thinking to use char constants (e.g. int id = 'BTN1';) so you'd be doing a single int comparison to test for the id. However, 4 chars isn't readable enough.

I tried an experiment, something like- long int id = L'abcdefg';

... but it looks as if char constants can only hold 4 characters, and the only thing making a long int char constant gives you is the ability for your 4 characters to be twice as wide, not have twice the amount of characters. Am I missing something here?

I want to make it easy for the person writing the client code. The gui is stored in xml, so the id's are loaded in from strings, but there would be constants written in the client code to compare these against.

So, the long and the short of it is, I'm looking for a cross-platform way to do quick 7-8 character comparison, any ideas?

Answer 1

Easy to get pre-rolled Components

binary search tree for the win -- you get a red-black tree from most STL implementations of set and map, so you might want to consider that.

Intrusive versions of the STL containers perform MUCH better when you move the container nodes around a lot (in the general case) -- however they have quite a few caveats.

Specific Opinion -- First Alternative

If I was you I'd stick to a 64-bit integer type and bundle it in a intrusive container and use the library provided by boost. However if you are new to this sort of thing then use stl::map it is conceptually simpler to grasp, and it has less chances of leaking resources since there is more literature and guides out there for these types of containers and the best practises.

Alternative 2

The problem you are trying to solve I believe: is to have a global naming scheme which maps to handles. You can create a mapping of names to handles so that you can use the names to retrieve handles:

// WidgetHandle is a polymorphic base class (i.e., it has a virtual method),
// and foo::Luv implement WidgetHandle's interface (public inheritance)
foo::WidgetHandle * LuvComponent = 
          Factory.CreateComponent<foo::Luv>( "meLuvYouLongTime");
....

.... // in different function
foo::WidgetHandle * LuvComponent = 
          Factory.RetrieveComponent<foo::Luv>("meLuvYouLongTime");

Alternative 2 is a common idiom for IPC, you create an IPC type say a pipe in one process and you can ask the kernel for to retrieve the other end of the pipe by name.

Answer 2

The concept of string interning can be useful for this problem, turning string compares into pointer compares.

Answer 3

One possibility is to define your IDs as a union of a 64-bit integer and an 8-character string:

union ID {
  Int64 id;      // Assuming Int64 is an appropriate typedef somewhere
  char name[8];
};

Now you can do things like:

ID id;
strncpy(id.name, "Button1", 8);
if (anotherId.id == id.id) ...

Answer 4

I see a distinction between easily read identifiers in your code, and the representation being passed around.

Could you use an enumerated type (or a large header file of constants) to represent the identifier? The names of the enumerated types could then be as long and meaningful as you wish, and still fit in (I am guessing) a couple of bytes.

Answer 5

In C++0x, you'll be able to use user-defined string literals, so you could add something like 7chars..id or "7chars.."id:

template <char...> constexpr unsigned long long operator ""id();
constexpr unsigned long long operator ""id(const char *, size_t);

Although I'm not sure you can use constexpr for the second one.

Answer 6

Are you sure this is not premature optimisation? Have you profiled another GUI framework that is slow purely from string comparisons? Why are you so sure string comparisons will be too slow? Surely you're not doing that many string compares. Also, consider strcmp should have a near optimal implementation, possibly written in assembly tailored for the CPU you're compiling for.

Anyway, other frameworks just use named integers, for example:

static const int MY_BUTTON_ID = 1;

You could consider that instead, avoiding the string issue completely. Alternatively, you could simply write a helper function to convert a const char[9] in to a 64-bit integer. This should accept a null-terminated string "like so" up to 8 characters (assuming you intend to throw away the null character). Then your program is passing around 64-bit integers, but the programmer is dealing with strings.

Edit: here's a quick function that turns a string in to a number:

__int64 makeid(const char* str)
{
    __int64 ret = 0;
    strncpy((char*)&ret, str, sizeof(__int64));
    return ret;
}