Как лучше всего улучшить мою программу, чтобы воспользоваться преимуществами оптимизации времени strcmp? - PullRequest
Новая
       8

Как лучше всего улучшить мою программу, чтобы воспользоваться преимуществами оптимизации времени strcmp?

0 голосов
/ 07 июня 2018

В настоящее время я работаю над проектом, который опирается на временную оптимизацию strcmp.Например, учитывая две строки a1, a2, где a1 = a2, и две строки b1, b2, где b1 = / = b2, мы знаем, что выполнение strcmp (a1, a2) займет больше времени, чем strcmp (b1, b2) в теории, поскольку strcmpзавершается, как только понимает, что один байт в первой строке не равен соответствующему байту во второй, что подразумевает, что strcmp займет самое длинное время для завершения, когда две строки равны, поскольку он должен выполнять итерацию по всей длине.В настоящее время мой проект рассчитывает время выполнения strcmp с использованием различных строк, и его успех зависит от того, что один вызов strcmp быстрее другого, даже если один байт в двух сравниваемых строках выключен.

Я создалболее простая фиктивная программа для изоляции и тестирования производительности (фиктивная программа ниже), которая сравнивает производительность сравнения двух одинаковых строк с производительностью двух неравных строк.Ссылка на код, когда str3 = "aaaaaaaaaa" (или любой произвольный текст, который сильно отличается от str1), становится очень очевидным, что первый сегмент, сравнивающий две одинаковые строки (str1 и str2), намного медленнее, чем второй сегмент, который сравнивает две неравные строки(стр2 и стр3).Однако при переключении str3 = "hellohella", как показано ниже, результаты очень похожи, и определение того, какой сегмент завершается быстрее / медленнее, чем другой, становится непредсказуемым.Я также пытался использовать clock () для определения времени вызовов функций, но это даже более неточно, чем rusage.

Можно ли как-нибудь изменить свой код так, чтобы сравнение двух неравных строк ВСЕГДА было решительно быстрее, чем сравнение двух одинаковых строк (даже если только на 1 байт)?Есть ли таймеры С, которые более точны, чем те, которые я пробовал?Спасибо за ваше время. 

int main ()
{
    int iterations=10000;
    struct rusage usage;
    struct timeval start, end;

    char * str1="hellohello";
    char * str2="hellohello";
    char * str3="hellohella";
    double tempTotal=0;
    for (int i=0; i<iterations; i++){
            struct rusage usage;
            struct timeval start, end;


            getrusage(RUSAGE_SELF, &usage);
            start=usage.ru_stime;

            for (int j=0; j<100000; j++) strcmp(str1, str2);

            getrusage(RUSAGE_SELF, &usage);
            end=usage.ru_stime;
            double startTime=((double)start.tv_sec + (double)start.tv_usec)/10000;
            double endTime=((double)end.tv_sec+(double)end.tv_usec)/10000;
            tempTotal+=(endTime-startTime);
    }
    printf("Avg time taken: %f\n", tempTotal/iterations);

    printf("\n\n");
    double tempTotal2=0;
    for (int i=0; i<iterations; i++){

            struct rusage usage2;
            struct timeval start2, end2;

            getrusage(RUSAGE_SELF, &usage2);
            start2=usage2.ru_stime;

            for (int j=0; j<100000; j++) strcmp(str1, str3);

            getrusage(RUSAGE_SELF, &usage2);
            end2=usage2.ru_stime;

            double startTime2=((double)start2.tv_sec+(double)start2.tv_usec)/10000;
            double endTime2=((double)end2.tv_sec+(double)end2.tv_usec)/10000;
            tempTotal2+=endTime2-startTime2;
    }

    printf("Avg time taken: %f\n", tempTotal2/iterations);
    return 0;

}

1 Ответ

0 голосов
/ 07 июня 2018

В вашем сценарии необходимо учесть несколько моментов:

  • Разумный компилятор распознает, что ваш результат strcmp не используется, и может полностью исключить вызов
  • Разумныйкомпилятор распознает, что сравнение является инвариантным цикла (то есть оно не меняется с итерациями цикла) и «поднимет» вызов вне цикла и сделает это один раз, а затем полностью исключит цикл, потому что он ничего не делает

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

for (int j=0; j<100000; j++) {
  external_strcmp(str1, str3);
}

, затем вставил бы в другой файл: 

int external_strcmp(const char* str1, const char* str2) {
  return strcmp(str1, str2);
}

Следующее, что я хотел бы сделать, это сделать строки WAAAAYYYYY длиннее И увеличить количество итераций, которые выделать.В существующем состоянии вы, вероятно, видите, что издержки getrusage () сокращают время strcmp.

Удачи.Анализ производительности - это очень крутая область.

...