Optimization of strcmp() fn.

[Maya]

There is a block of code (a parser) that looked like
this (simplified):
Where text is a pointer to a null terminated string,
which may or may not
be a tag name.
if ( strcmp( text, "<BR>" ) == 0 )
{
... code ...
}
else if ( strcmp( text, "<P>" ) == 0 )
{
...code...
}
else if ( strcmp( text, "<BOLD>" ) == 0 )
{
...code..

Etc.
It was a huge block of if/else cases. The code
structure and function was something we were
very happy with, so we didn't want to change the code
inside the if cases. When we profiled it, however, the
strcmp functions were consuming most of the program's execution time.

So my question is:
What could you do to make this more efficient without
having to rewrite the
code inside the if cases?

[ralph]

"Maya" <maya_l2003@yahoo.com> wrote:
>
>There is a block of code (a parser) that looked like
>this (simplified):
>Where text is a pointer to a null terminated string,
>which may or may not
>be a tag name.
>if ( strcmp( text, "<BR>" ) == 0 )
>{
>... code ...
>}
>else if ( strcmp( text, "<P>" ) == 0 )
>{
>...code...
>}
>else if ( strcmp( text, "<BOLD>" ) == 0 )
>{
>...code..
>
>Etc.
>It was a huge block of if/else cases. The code
>structure and function was something we were
>very happy with, so we didn't want to change the code
>inside the if cases. When we profiled it, however, the
>strcmp functions were consuming most of the program's execution time.
>
>So my question is:
>What could you do to make this more efficient without
>having to rewrite the
>code inside the if cases?

You didn't mention your compiler.
If it is VC++ and an x86 platform, you can use the intrinsic version - the
compiler will create the function inline and save you the cost of a function
call.

Place the following line at the top of your source file...
#pragma intrinsic( strcmp )
The replacement will be inforce until the end of the file or until you..
#pragma function( strcmp )

[Danny Kalev]

Maya wrote:
>
> There is a block of code (a parser) that looked like
> this (simplified):
> Where text is a pointer to a null terminated string,
> which may or may not
> be a tag name.
> if ( strcmp( text, "<BR>" ) == 0 )
> {
> .. code ...
> }
> else if ( strcmp( text, "<P>" ) == 0 )
> {
> ..code...
> }
> else if ( strcmp( text, "<BOLD>" ) == 0 )
> {
> ..code..
>
> Etc.
> It was a huge block of if/else cases. The code
> structure and function was something we were
> very happy with, so we didn't want to change the code
> inside the if cases. When we profiled it, however, the
> strcmp functions were consuming most of the program's execution time.
>
> So my question is:
> What could you do to make this more efficient without
> having to rewrite the
> code inside the if cases?

to be honest? rewrite the strcmp function and apply certain ad hoc
optimizations. For example, if all your tags begin with < then perhaps
it would be a good idea to start the comparison at the second character.
This will save you 20%-25% percent of the computation time. Use the
specialized strcmp function instead of the standard one. There are
probably other optimizations you can apply such as casting each 4 bytes
of both strings into an int and comparing the int values and thus
short-circuiting the comparison process, e.g.

int mystrcmp(const char *p, const char *q)
{
register int first = *(int*)p;
register int second = *(int*)q;
if (p==q)
{
//..continue the comparison
}
return a_non_zero_value
}

Danny

[Yuri]

inline bool is_equal(const char* first, const char* second)
{
while (*first && *first == *second)
{ ++first; ++second; }
return !*second && !*first;
}


"Maya" <maya_l2003@yahoo.com> wrote:
>
>There is a block of code (a parser) that looked like
>this (simplified):
>Where text is a pointer to a null terminated string,
>which may or may not
>be a tag name.
>if ( strcmp( text, "<BR>" ) == 0 )
>{
>... code ...
>}
>else if ( strcmp( text, "<P>" ) == 0 )
>{
>...code...
>}
>else if ( strcmp( text, "<BOLD>" ) == 0 )
>{
>...code..
>
>Etc.
>It was a huge block of if/else cases. The code
>structure and function was something we were
>very happy with, so we didn't want to change the code
>inside the if cases. When we profiled it, however, the
>strcmp functions were consuming most of the program's execution time.
>
>So my question is:
>What could you do to make this more efficient without
>having to rewrite the
>code inside the if cases?

[David B]

Try hashing each of the strings.


"Maya" <maya_l2003@yahoo.com> wrote:
>
>There is a block of code (a parser) that looked like
>this (simplified):
>Where text is a pointer to a null terminated string,
>which may or may not
>be a tag name.
>if ( strcmp( text, "<BR>" ) == 0 )
>{
>... code ...
>}
>else if ( strcmp( text, "<P>" ) == 0 )
>{
>...code...
>}
>else if ( strcmp( text, "<BOLD>" ) == 0 )
>{
>...code..
>
>Etc.
>It was a huge block of if/else cases. The code
>structure and function was something we were
>very happy with, so we didn't want to change the code
>inside the if cases. When we profiled it, however, the
>strcmp functions were consuming most of the program's execution time.
>
>So my question is:
>What could you do to make this more efficient without
>having to rewrite the
>code inside the if cases?

[Steve F]

You can associate an int ID to each of your tags then put them into a map
of string(tag) to int(ID) (the more balanced the map the better your performance).
Then you do a find on the map with text. If the result is valid you get the
int ID and you can use it in a case statement that can replace your if's
verbatum. This still does string comparisons but rather than max of N comparisons
per text items you get max Log N base 2 comparisons per text item. If there
are a lot of tags(N) or text items it can be a significant savings.

Steve

"Maya" <maya_l2003@yahoo.com> wrote:
>
>There is a block of code (a parser) that looked like
>this (simplified):
>Where text is a pointer to a null terminated string,
>which may or may not
>be a tag name.
>if ( strcmp( text, "<BR>" ) == 0 )
>{
>... code ...
>}
>else if ( strcmp( text, "<P>" ) == 0 )
>{
>...code...
>}
>else if ( strcmp( text, "<BOLD>" ) == 0 )
>{
>...code..
>
>Etc.
>It was a huge block of if/else cases. The code
>structure and function was something we were
>very happy with, so we didn't want to change the code
>inside the if cases. When we profiled it, however, the
>strcmp functions were consuming most of the program's execution time.
>
>So my question is:
>What could you do to make this more efficient without
>having to rewrite the
>code inside the if cases?