CODEWITHSUNDEEP
c++optimizationmemorytrim
Sergei G
Sergei G

Reputation: 1570

Memory access optimization in C

I have to write fast right-trimming function in C. My first attempt to do it was: 

void TrimRight( char *s )
{
    char* pS;
    if (!*s)
        return;
    if (!s)
        return;
    for ( pS = s + strlen(s) - 1; isspace(*pS) && (pS >= s); pS--)
    {  
        pS[1] = '\0';
    }
}

Second attempt:

void TrimRight( char *s )
{   
    if (!*s)
        return;
    if (!s)
        return;
    char* pS = s + strlen(s) - 1;
    while ((*pS == ' ') && (pS > s))
    {
        (*pS--) = '\0';
    }
}

The question is: Did I improve memory accesses here? How can I optimize this even more? How to optimize memory access in general?

Upd: Is it true that scanning memory in increasing sequential order is faster?

Upvotes: 1

Views: 1223

Answers (6)

Marcelo Cantos
Marcelo Cantos

Reputation: 185932

I wouldn't bother with the tests at the beginning. It should be a requirement of the function that a valid string be passed, which obviates the !s test, and the !*s is redundant (Besides, placing the !s test second means you'll crash first on the !*s). Also, you can avoid scanning in both directions (the strlen scans one way, the while loop goes the other way) by keeping track of the last non-whitespace character:

char* TrimRight(char *s)
{
    // ws tracks the char after the last non-whitespace char.
    char* ws = s;
    while (*s)
        if (s++ != ' ') // or !isspace(s++)
            ws = s;
    *ws = '\0';
    return ws; // Knowing where the trimming occurred might come in handy.
}

EDIT: Note that strlen might be faster than scanning for spaces (see comments).

Upvotes: 7

Pubby
Pubby

Reputation: 53057

Short version:

void TrimRight( char *s )
{   
    if (!*s || !s)
        return;
    char* pS = s + strlen(s);
    while (*(--pS) == ' ')
      if (pS == s) break;
    *(++pS) = '\0';
}

1 loop version:

void TrimRight( char *s )
{   
    if (!*s || !s)
        return;
    char* x = s;
    while (*s != '\0') {
      if (*s++ != ' ')
        x = s;
    }
    *x = '\0';
}

Upvotes: 0

AndersK
AndersK

Reputation: 36092

this here could cause a seg fault

if (!*s)

you should first check first if s is 0 before dereferencing it

other than that it seems pretty ok, either way. optimization will take care of it for you so don't worry

Upvotes: 3

Vlad
Vlad

Reputation: 18633

It seems your code would go over the spaces on the right side twice, once during strlening and once in your loop. How about this:

void TrimRight(char*s){

    if (!s) return;

    char*trimHere;
    bool sp = false;
    while(*s){
        if (*s==' '){
            if (!sp){
                sp=true;
                trimHere=s;
            }
        }
        else
            sp=false;
        s++;
    }
    if (sp)
        *trimHere='\0'; 
}

One thought however, since you tagged this as C++. If you use std::string, you could also use length() instead of strlen, and it would be O(1). And you could then resize() the string.

Upvotes: 3

Sean
Sean

Reputation: 62492

You can avoid calling strlen by keeping some state while looping through the string. This will save you having to scan it (worse case) twice. The following should work:

void TrimRight(char *text)
{
    if(text==0) return;
    if(*text==0) return;

    char *lastWhitespace=0;

    char *next=text;

    // Scan the string once to find the last bit of whitespace
    while(*next)
    {
        if(*next==' ' && lastWhitespace==0) 
        {
            lastWhitespace=next;
        }
        else if(*next!=' ' && lastWhitespace!=0)
        {
            lastWhitespace=0;
        }

        next++;
    }

    if(lastWhitespace!=0) *lastWhitespace=0;
}

I've kept if simple by just treating a space as whitespace, you can use isspace to cover more cases, such as tabs.

Upvotes: 1

Adrien Plisson
Adrien Plisson

Reputation: 23303

the isspace() function you are using in the first attempt checks for far more cases than just a space character: it also checks for tabs, carriage return, line feed, ... but your second attempt only checks for a space character.

now, optimizing by hand may not be a good idea: use a profiling tool and see how long it takes to execute your function. when compiling, use a release build and turn on optimization, and you will find that the simplest form may be so aggressively optimized by the compiler that it is not even worth thinking about optimizing by hand.

at the lowest level, your 2 functions are identical (except the isspace()call), and i won't be surprised if your compiler generates the same code for the 2 attempts. so, i am afraid you did not optimize anything.

some good compilers are able to generate a listing, that is a human readable assembly output for the compiled code. this listing file is the file you absolutely want to read in order to see how the compiler understood your code and what difference exists between 2 versions of the same code.

Upvotes: 3

Related Questions