时间戳

首页 > 解决方案 > 如何最好地增强我的程序以利用 strcmp 的时序优化？

c - 如何最好地增强我的程序以利用 strcmp 的时序优化？

问题描述

我目前正在做一个依赖 strcmp 时序优化的项目。例如，给定两个字符串 a1, a2 其中 a1=a2 和两个字符串 b1, b2 where b1=/=b2 我们知道 strcmp (a1,a2) 在理论上比 strcmp(b1,b2) 需要更长的时间来完成，因为 strcmp一旦它意识到第一个字符串中的一个字节不等于第二个字符串中的相应字节，这意味着当两个字符串相等时 strcmp 将花费最长的时间来完成，因为它需要遍历整个长度。我的项目目前正在使用各种字符串对 strcmp 的性能进行计时，它的成功取决于一次调用 strcmp 是否比另一次调用更快，即使正在比较的两个字符串中的一个字节是关闭的。

我创建了一个更简单的虚拟程序来隔离和测试性能（下面是虚拟程序），它比较了比较两个相等字符串的性能与两个不相等字符串的性能。参考代码，当 str3="aaaaaaaaaa"（或任何与 str1 有很大差异的随机文本）时，很明显，比较两个相等字符串（str1 和 str2）的第一段比比较两个不相等字符串的第二段慢得多（str2 和 str3）。但是，当如下所示切换 str3="hellohella" 时，结果非常相似，并且确定哪个段完成得更快/更慢变得不可预测。我也尝试过使用 clock() 来计时函数调用，但这比 rusage 更不准确。

有什么办法可以改变我的代码，使两个不相等的字符串的比较总是比两个相等的字符串的比较快（即使只有 1 个字节）？有没有比我尝试过的更准确的 C 计时器？感谢您的时间。

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;

}

标签： cstringoptimizationstrcmp

解决方案

您的方案需要考虑以下几点：

  • 一个合理的编译器会认识到你的 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);
}

我要做的下一件事是让字符串 WAAAAYYYYYY 更长，并增加你做的迭代次数。就目前而言，您可能会看到 getrusage() 的开销使 strcmp 时间相形见绌。

祝你好运。性能分析是一个非常酷的领域。

推荐阅读