为什么这个线性和二进制搜索的基准代码不起作用？

Question

我正在尝试将线性搜索和二分搜索作为作业的一部分进行基准测试。我已经编写了必要的搜索和随机函数。但是当我尝试对它们进行基准测试时，即使对于更大的数组大小，我也会得到 0 延迟。

代码：

#include<iostream>
#include <time.h>
#include <windows.h>
using namespace std;

double getTime()
{
    LARGE_INTEGER t, f;
    QueryPerformanceCounter(&t);
    QueryPerformanceFrequency(&f);
    return (double)t.QuadPart/(double)f.QuadPart;
}


int linearSearch(int arr[], int len,int target){
    int resultIndex = -1;
    for(int i = 0;i<len;i++){
        if(arr[i] == target){
           resultIndex = i;
           break;
        }
    }

    return resultIndex;
}

void badSort(int arr[],int len){
    for(int i = 0 ; i< len;i++){
        int indexToSwapWith = i;
        for(int j = i+1;j < len;j++){
            if(arr[j] < arr[indexToSwapWith] )
                indexToSwapWith = j;
        }
        if(indexToSwapWith != i){
            int t = arr[i];
            arr[i] = arr[indexToSwapWith];
            arr[indexToSwapWith] = t;
        }
    }
}

int binSearch(int arr[], int len,int target){
    int resultIndex = -1;

    int first = 0;
    int last = len;
    int mid = first;

    while(first <= last){
        mid = (first + last)/2;
        if(target < arr[mid])
            last = mid-1;
        else if(target > arr[mid])
            first = mid+1;
        else
            break;
    }

    if(arr[mid] == target)
        resultIndex = mid;

    return resultIndex;
}

void fillArrRandomly(int arr[],int len){
    srand(time(NULL));
    for(int i = 0 ; i < len ;i++){
        arr[i] = rand();
    }
}

void benchmarkRandomly(int len){

    float startTime = getTime();

    int arr[len];
    fillArrRandomly(arr,len);
    badSort(arr,len);

    /*
    for(auto i : arr)
        cout<<i<<"\n";
    */

    float endTime = getTime();
    float timeElapsed = endTime - startTime;
    cout<< "prep took " << timeElapsed<<endl;

    int target = rand();

    startTime = getTime();
    int result = linearSearch(arr,len,target);

    endTime = getTime();
    timeElapsed = endTime - startTime;
    cout<<"linear search result for "<<target<<":"<<result<<" after "<<startTime<<" to "<<endTime <<":"<<timeElapsed<<"\n";

    startTime = getTime();
    result = binSearch(arr,len,target);
    endTime =  getTime();
    timeElapsed = endTime - startTime;
    cout<<"binary search result for "<<target<<":"<<result<<" after "<<startTime<<" to "<<endTime <<":"<<timeElapsed<<"\n";
}

int main(){
    benchmarkRandomly(30000);
}

示例输出：

准备用了 0.9375

701950 到 701950:0

之后 29445:26987 的线性搜索结果

701950 到 701950:0

之后 29445:26987 的二进制搜索结果

我也尝试过使用 clock_t，但结果是一样的。我需要更大的数组大小还是我的基准测试方式有误？

在课程中，我必须自己实现大部分内容。这就是我不使用 stl 的原因。我不确定是否允许使用 stl::chrono，但我想首先确保问题不在其他地方。

编辑：如果不清楚，我不能在基准测试中包括排序和随机生成的时间。

Answer 1

一个问题是您在用随机值打包测试数组之前设置了 startTime = getTime()。如果随机数生成速度很慢，这可能会主导返回的结果。主要工作是对数组进行排序，与此相比，搜索时间将非常短。正如您所建议的那样，这可能太过间隔了。对于 30k 对象的二进制搜索，我们只讨论 12 或 13 次迭代，因此在现代机器上最多 20 / 1000000000 秒。这大约是零毫秒。

增加数组条目的数量不会有太大帮助，但您可以尝试增加数组大小，直到接近内存限制。但是现在你的问题是准备随机数生成和排序将永远花费。

我会建议：-

一个。检查大量项目:-

unsigned int total;
startTime = getTime();
for (i=0; i<10000000; i++)
    total += binSearch(arr, len, rand());
endTime = getTime();

乙。修改您的代码以计算您比较元素的次数并使用该信息而不是计时。

Answer 2

看起来您正在使用搜索结果（通过 cout * 在计时区域之外打印它，这很好）。而且数据+键是随机的，所以搜索不应该在编译时被优化掉。（禁用优化的基准测试毫无意义，因此您需要这样的技巧。）

你用调试器看过 timeElapsed 了吗？也许它是一个非常小的 float，在默认 cout 设置下打印为 0？

或者 float endTime - float startTime 实际上等于 0.0f 因为四舍五入到最接近的 float 使它们相等 .减去附近的两个大 floating-point 数字产生 "catastrophic cancellation".

记住 float only has 24 bits of significand, so regardless of the frequency you divide by, if the PerformanceCounter values differ in less than 1 part in 2^24, you'll get zero. (If that function returns raw counts from x86 rdtsc, then that will happen if your system's last reboot was more than 2^24 times longer ago than the time interval. x86 TSC starts at zero when the system boots, and (on CPUs in the last ~10 years) counts at a "reference frequency" that's (approximately) equal to your CPU's rated / "sticker" frequency, regardless of turbo or idle clock speeds. See Get CPU cycle count?)

double 可能会有所帮助，但最好在除法 之前在整数域中减去。此外，重写该部分将占用 QueryPerformanceFrequency 时间间隔！

正如@Jon 所建议的，将被测代码放入一个较长时间间隔内的重复循环通常更好，这样（代码）缓存和分支预测可以预热。

但是你会遇到确保重复调用没有被优化掉的问题，以及在循环内随机化搜索键的问题。（否则，聪明的编译器可能会将搜索提升到循环之外）。

volatile int result = binSearch(...); 之类的东西可以提供帮助，因为分配给（或初始化）volatile 是一个可见的 side-effect，无法优化掉。所以编译器需要在寄存器中实际实现每个搜索结果。

对于某些编译器，例如对于支持 GNU C 内联汇编的那些，您可以使用内联汇编来要求编译器在寄存器中生成一个值 而无需 增加任何存储它的开销。 AFAIK 这对于 MSVC 内联 asm 是不可能的。

为什么这个线性和二进制搜索的基准代码不起作用？

Why is this benchmark code for linear and binary search not working?

c++

benchmarking

binary-search

linear-search