   Test my Function to see which is fastest
  HelloI have made my own lower_bound() function that is really just a binary search which has been altered to find the closest value within a vector.I have my program that compares the functions running time to a linear_lower_bound() & the standard lower_bound() to see which has the fastest average time.But I get some issues, like sometimes the standard lower_bound() has the fastest avg then sometimes my one has the fastest avg, plus I dont even know what units my timing is in?Program exe  http://www.mediafire.com/?cziyy1dhzdq Can you run the program executable on your computer & tell me which is the fastest function? Or maybe you can tell which will be fastest by looking at the code below?My Problems:  - What units is my running time in(milliseconds, clock ticks?)? I use QueryPerformanceCounter() to calculate a functions running time.  - Which function is fastest?Program:/*   Example of my own LowerBound() function to retreive the closest object to the   key. In this case we search a list of UbCells to find the cell that whose y value   is closest to the key value parameter.*/#include <iostream>#include <windows.h>#include <algorithm>#include <cstdlib>#include <vector>#include <time.h>#include "PrecisionTimer.h"  // Allow me to test the time efficiency of each functionusing namespace std;// Objectstruct UbCell {   int x; int y; UbCell();};// FunctionsUbCell* LowerBoundA(vector <UbCell*> &v, int first, int last, int value);UbCell* myOwn(vector <UbCell*> &v, int value);UbCell* linear(vector <UbCell*> &v, int value);void average(vector <double> v);int main(){    srand(time(NULL));   vector <UbCell*> UbCellList(100000);    vector <int> test;    vector<int>::iterator low;    vector <double> binAvg, linAvg, mlbAvg, algAvg;    clock_t start, end;    double timet;   // Build UbCell objects    for (int i=0; i<100000; i++){   UbCellList.at(i) = new UbCell;   UbCellList.at(i)->x = 20;  UbCellList.at(i)->y = (i*20) + 20;   test.push_back( (i*20) + 20 );    }   // Test y values to find nearest UbCellint array[10] = {5, 10, 99999, 44, 59, 80, 377, 86683, 120, 119};  // Test each searching method & calculate the time it takes to carryout the function    for (int i=0; i<10; i++){ // Binary Search lower bound    CPrecisionTimer atimer;   atimer.Start();   UbCell* closestCell = myOwn(UbCellList, array);   timet = atimer.Stop();   cout << "Binary Lower_Bound = " << timet << " Milliseconds \n";   binAvg.push_back( timet );    // Linear Search lower bound   CPrecisionTimer btimer;   btimer.Start();   UbCell* Cell = linear(UbCellList, array);   timet = btimer.Stop();   cout << "Linear Lower_Bound = " << timet << " Milliseconds \n";   linAvg.push_back( timet );    // Lower bound algorithm that I made   CPrecisionTimer dtimer;   dtimer.Start();   UbCell* bbb = LowerBoundA(UbCellList, 0, UbCellList.size(), array);   timet = dtimer.Stop();   cout << "My Own Lower_Bound = " << timet << " Milliseconds \n";   mlbAvg.push_back( timet );    // lower_bound() from algorthim library   CPrecisionTimer ctimer;   ctimer.Start();   low = lower_bound(test.begin(), test.end(), array);   timet = ctimer.Stop();   cout << "Algori Lower_Bound = " << timet << " Milliseconds \n";   algAvg.push_back( timet ); cout << endl;    }   // Print out the avage running time for each search function    average(binAvg);    average(linAvg);    average(mlbAvg);    average(algAvg);   while (!UbCellList.empty())    {delete UbCellList.back(); UbCellList.pop_back();    }   system("PAUSE");    return 0;}// Implementation UbCell::UbCell(){   // Default Constructor x = rand() % 100;   y = rand() % 100;}UbCell* LowerBoundA(vector <UbCell*> &v, int first, int last, int value){   // Post: This algorithm doesn't return the correct UbCell so just ignore this function UbCell* it;   int count, step;    count = last - first; while ( count>0 )   { it = v.at( first ); step = count/2; first += step;  if (it->y <= value) {first++;count -= step+1;   } else count=step;   } return v.at(first);}UbCell* myOwn(vector <UbCell*> &v, int value){   // Pre:  Vector parameter must be an ordered from lowest to highest   // Post: Binary Search Lower Bound    // if value is less than the lowest value in vector   if ( value < v.at(0)->y )   {  return NULL;    } int first = 0;   int last  = v.size();   int mid;    int forwardValue; while (first <= last)   {  mid = (last + first) / 2;   // if mid = last vector index  if ( mid == v.size() - 1 )  {  forwardValue = INT_MAX;  }  else forwardValue = v.at(mid+1)->y;    if (value >= v.at(mid)->y  && value < forwardValue)   {  return v.at(mid);  }  else if (v.at(mid)->y > value)  {  last = mid - 1;  }  else if (v.at(mid)->y < value)  {  first = mid + 1;  }   }   }UbCell* linear(vector <UbCell*> &v, int value){   // Post: Linear Lower Bound if (value < v.at(0)->y)    {  return NULL;   }for (int i=0; i<v.size()-1; i++)   {  if (value >= v.at(i)->y  && value < v.at(i+1)->y )  { return v.at(i);  }   } return v.back();}void average(vector <double> v){    double total = 0;   for (int i=0; i<v.size(); i++)    {   total += v.at(i);    }    float avg = total / v.size();   cout << "Average = " << avg << endl;}Precision time header:#ifndef _PRECISIONTIMER_H_#define _PRECISIONTIMER_H_#include <windows.h>class CPrecisionTimer{  LARGE_INTEGER lFreq, lStart;public:  CPrecisionTimer()  {    QueryPerformanceFrequency(&lFreq);  }  inline void Start()  {    QueryPerformanceCounter(&lStart);  }    inline double Stop()  {    // Return duration in seconds...    LARGE_INTEGER lEnd;    QueryPerformanceCounter(&lEnd);    return (double((lEnd.QuadPart - lStart.QuadPart)) / lFreq.QuadPart);  }};#endif // _PRECISIONTIMER_H_
  According to this: http://msdn.microsoft.com/en-us/library/ms644904%28v=VS.85%29.aspx it returns the current performance-counter count. In fact, it doesn't matter what unit you use, as long as you use the same timer across the program.It is very inaccurate the measure just one carryout of a function. Instead, measure the time it takes to execute the function N times (with N being 100 or 100 000 000 etc.). Also, just let it run longer, don't run the main loop 10 times, but more like 100 or 1000. This will give you more consistent results. Add these values up to some variable (or array) and at the end of the program display this (or take the average or leave the total, doesn't matter).   ;  There was another thread about QPC here recently.  I believe QPC reads the cycle counter of your CPU(which is different for each CPU on a multi core machine, and veries when power saving throttles the CPU).  Either way QPC is considered unreliable.  Second assuming you are using windows it schedules threads at 12 ms second intervals  your test should be large enough that 12ms differences are just noise and doesn't effect your data.  Gettickcount return MS since system was booted its resolution is in the 16ms range.   ;  Your synthetic bechmark isn't very good.1) you need to run in release to get reasonable results on your timing.  The std:: functions are going to have a lot of debug code, and code that depends on the compiler inlining stuff.2) because you need to benchmark in release, you need to write an actual use case for your function to make sure it doesn't optimize anything out.  Right now, your benchmark risks the compiler optimizing out too much because you don't use the results of your functions. 3) you aren't doing enough work to make it count. The faster your function, the more times you have to call it to get accurate timings on the involved code.4) you aren't taking into account the cache.  The first calls to your functions will be slow, but if you call on cached data, they will run much faster. Do you want to time the uncached speed? or the cached speed? You're going to have to do some work with your data and memory usage to get the result you want.5) etc.Your best bet it to write some actual code that uses the function the way you'd actually want to use it.  Like looking up names given by the user from some file in a large phone book of names. and outputting the associated phone numbers into another text file.  Then grab AMD's Code Analyst or another external profiler tool, and benchmark your functions using the external tool.Quote:There was another thread about QPC here recently. I believe QPC reads the cycle counter of your CPU(which is different for each CPU on a multi core machine, and veries when power saving throttles the CPU). Either way QPC is considered unreliableIt might be, but it seems to work just fine for my home projects...   ;  QPC itself isn't to blame - it's the BIOS on certain boards that contains the bug. There's a software patch you can run to fix the problem if your specific hardware has the bug.The frequency is apparently not tied to the clock speed, and it shouldn't ever vary while the computer is turned on. But again, some hardware has a bug where power saving features cause it to do just that.I used to own a PC with the QPC bug, and software patched it. I've never seen the frequency bug occur, even when deliberately throttling the CPU speed while running tests.   ;  Thanks for the responses. I dont think I will use QueryPerformanceCounter to time my functions.But would anyone know just by looking at my code or some other way which is function is faster, My binary search Upper_bound function or the Algorithm library upper_bound() function?My Binary search upper_bound():UbCell* myOwn(vector <UbCell*> &v, int value){   // Pre:  Vector parameter must be an ordered from lowest to highest   // Post: Binary Search Lower Bound    // if value is less than the lowest value in vector   if ( value < v.at(0)->y )   {  return NULL;    } int first = 0;   int last  = v.size();   int mid;    int forwardValue; while (first <= last)   {  mid = (last + first) / 2;   // if mid = last vector index  if ( mid == v.size() - 1 )  {  forwardValue = INT_MAX;  }  else forwardValue = v.at(mid+1)->y;    if (value >= v.at(mid)->y  && value < forwardValue)   {  return v.at(mid);  }  else if (v.at(mid)->y > value)  {  last = mid - 1;  }  else if (v.at(mid)->y < value)  {  first = mid + 1;  }   }   }