Optimization of strcmp() fn.


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 6 of 6

Thread: Optimization of strcmp() fn.

  1. #1
    Maya Guest

    Optimization of strcmp() fn.


    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?

  2. #2
    ralph Guest

    Re: Optimization of strcmp() fn.


    "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 )




  3. #3
    Danny Kalev Guest

    Re: Optimization of strcmp() fn.



    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

  4. #4
    Yuri Guest

    Re: Optimization of strcmp() fn.


    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?



  5. #5
    David B Guest

    Re: Optimization of strcmp() fn.


    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?



  6. #6
    Steve F Guest

    Re: Optimization of strcmp() fn.



    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?



Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center