Оптимизация доступа к памяти в C

Question

Мне нужно написать быструю правую функцию обрезки на C. Моя первая попытка сделать это была:

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';
    }
}

Вторая попытка:

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

Вопрос в том, сделал ли яулучшить доступ к памяти здесь?Как я могу оптимизировать это еще больше?Как оптимизировать доступ к памяти в целом?

Upd: Правда ли, что сканирование памяти в возрастающем последовательном порядке происходит быстрее?

Answer 1

Я бы не стал беспокоиться о тестах в начале. Для функции должно требоваться, чтобы была передана допустимая строка, которая исключает тест !s, а !*s является избыточным (кроме того, если поместить !s тест во вторую, это означает, что вы сначала упадете на !*s). Кроме того, вы можете избежать сканирования в обоих направлениях (strlen сканирует в одну сторону, а цикл while - в другую), отслеживая последний непробельный символ:

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.
}

РЕДАКТИРОВАТЬ: Обратите внимание, что strlen может быть быстрее, чем сканирование пробелов (см. Комментарии).

Answer 2

Кажется, ваш код будет проходить через пробелы с правой стороны дважды, один раз во время strlen и один раз в вашем цикле. Как насчет этого:

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'; 
}

Одна мысль, однако, поскольку вы пометили это как C ++. Если вы используете std::string, вы также можете использовать length() вместо strlen, и это будет O (1). И тогда вы можете resize() строку.

Answer 3

функция isspace(), которую вы используете в первой попытке, проверяет гораздо больше случаев, чем просто пробел: она также проверяет наличие табуляции, возврата каретки, перевода строки, ... но ваша вторая попытка проверяет только пробел характер.

Теперь оптимизация вручную не может быть хорошей идеей: используйте инструмент профилирования и посмотрите, сколько времени потребуется для выполнения вашей функции. при компиляции используйте сборку релиза и включите оптимизацию , и вы обнаружите, что самая простая форма может быть настолько агрессивно оптимизирована компилятором, что даже не стоит думать об оптимизации вручную.

на самом низком уровне, ваши 2 функции идентичны (кроме вызова isspace()), и я не удивлюсь, если ваш компилятор сгенерирует один и тот же код для 2 попыток. боюсь, вы ничего не оптимизировали.

Некоторые хорошие компиляторы способны генерировать листинг, который представляет собой удобочитаемый вывод сборки для скомпилированного кода. этот файл листинга - это файл, который вы абсолютно хотите прочитать, чтобы увидеть, как компилятор понимает ваш код и какая разница существует между двумя версиями одного и того же кода.

Answer 4

здесь это может вызвать ошибку сегмента

if (!*s)

сначала вы должны проверить, если s равно 0, прежде чем разыменовывать его

, за исключением того, что в любом случае это выглядит довольно нормально.оптимизация позаботится об этом за вас, так что не волнуйтесь

Answer 5

Вы можете избежать вызова strlen, сохраняя некоторое состояние во время цикла по строке. Это избавит вас от необходимости сканировать его (в худшем случае) дважды. Должно работать следующее:

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;
}

Я сохранил, если просто, рассматривая пробел как пробел, вы можете использовать isspace, чтобы охватить больше случаев, таких как табуляции.

Answer 6

Короткая версия:

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

Версия с 1 петлей:

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