Thread: timing accuracy?

  1. #1
    Registered User
    Join Date
    Jul 2003
    Posts
    6

    timing accuracy?

    This is my first post and any help would be appreciated. I'm writing a program that reads a file of integers of unknown length, then allows the user to choose 1 of 5 kinds of sorts. At the end. the time it took to sort the list will be displayed. The problem has been finding something to time it in ms. What I have below is the closest I've gotten but at times still shows 0 seconds, other times .06, or .11 (all my testing so far has been with a selection sort and bubble sort of 200 integers).

    Code:
    void SelectionSort(	vector <int>& listOfData, 
    		double& duration)
    {	
        int	temp;
        int	counter;
        int	index;
        int	minIndex;
        clock_t	start;	
        clock_t	finish;	
    
        start = clock();     //  grabs beginning count
    
        for (counter = 0; counter < listOfData.size(); counter++)
       {
            minIndex = counter;
    
            for (index = counter + 1; index < listOfData.size(); index++)
            {
                if (listOfData[index] < listOfData[minIndex])
                    minIndex = index;
            }
    
            temp = listOfData[counter];
            listOfData[counter] = listOfData[minIndex];
            listOfData[minIndex] = temp;
        }	
    	
        finish = clock();         // grabs ending count
        duration = double (finish - start) / CLOCKS_PER_SEC;
    }
    I hope I got the code tags right. If there's any other methods of timing anyone knows that are more consistent and accurate I would appreciate it. Thanks!

    Also on a somewhat unrelated topic. With vectors, is there an upper range limit of elements that a vector can hold? Is it necessary to do checks for out of bounds? And if so, how might I do that without knowing the number of elements I'll be adding? I'll appreciate any help. Thanks!
    Last edited by mfknitz; 07-15-2003 at 01:34 PM.

  2. #2
    Registered User
    Join Date
    Jul 2003
    Posts
    6
    Thanks, I'll give those a shot. Appreciate the info on vectors.

  3. #3
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    With your guess of the initial size, use the reserve(size_type n) member function (where n is the number of objects to hold). Then, continue to use push_back(). The vector will not reallocate its array until you've filled up the n spots available, and you call push_back() once more.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  4. #4
    Registered User
    Join Date
    Jul 2003
    Posts
    6
    What I've done so far is created a zero length vector and called push_back() as I read from the file. Is it better to create a vector of say 2000 (my estimate) up front, even though there could be significantly more or less elements than that? I guess creating the spaces up front would be more efficient, but wouldn't it waste memory if they aren't all used? Thanks

  5. #5
    Registered User
    Join Date
    Jun 2003
    Posts
    245
    Whats the default number of elements an vector holds if you don't use reserve() but immediately do push_back, before it allocates another block of memory?

  6. #6
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    It would be a waste of memory, but it all depends on which is more important: time efficiency, or memory efficiency.

    If time is an issue, allocate a lot, and use however much you need. If memory is an issue, allocate on demand only.

    There are also some strategies for allocating memory, such as the following: allocate memory based on an initial guess - once you run out, allocate twice as much memory, and repeat as necessary. This way, no more than half of the memory is wasted (assuming that at least one reallocation did occur).

    Here is some (untested) code which illustrates what I am talking about:
    Code:
    const int elements_to_add = 700;
    int elements added = 0;
    
    void foo()
    {
      vector<int> array;
      array.reserve(200);
    
      add_elements(array);
    
      while(elements_added < elements_to_add)
      {
        array.reserve(2 * array.capacity());
        add_elements(array);
      }
    }
    
    void add_elements(vector<int>& vec)
    {
      while(vec.size() < vec.capacity() && elements_added < elements_to_add)
      {
        vec.push_back(3);
        ++elements_added;
      }
    }
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  7. #7
    Registered User
    Join Date
    Jul 2003
    Posts
    6
    Elixia--
    As far as I can tell it's just an empty container with zero length and memory is allocated every time push_back() is called (not very efficient as I see now).

    Zach L.--
    That makes a lot of sense. I'm going try something like you showed and see how it works out. It looks like resize() would be helpful.

    This is my first try at dynamic allocation so I appreciate all your guys' help.

  8. #8
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Glad to be of help.

    Just some more info on resizing vectors. resize() and reserve() do very different (externally), yet very similar (internally) things (yes, I know that makes no sense... hang on a second). reserve() sets the capacity of the vector, but you don't want to access elements until its size (number of indexable elements) reaches that particular index. The size() returns the size (essentially, the number of indexable elements), while capacity() returns how many can 'fit' into the currently allocated space. Granted, you can write to that memory using the subscript operator, your vector will not know about it (at() would fail, and end() will point to the wrong location.

    For example:
    Code:
    vector<int> vec;
    vec.reserve(10);
    cout << vec.size(); // Print "0".
    cout << vec.capacity(); // Print "10"
    ...
    vec.push_back(10); // size() == 1, capacity() == 10
    Cheers
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  9. #9
    Hardware Engineer
    Join Date
    Sep 2001
    Posts
    1,398

    Thumbs down Windows Timing Wierdness

    I'll bet you're running Windows.

    With Windows, clock() does NOT get updated every millisecond. It has somethng to do with the interrupt clock rate. I don't recall what the interrupt rate is, but once every ~50ms might be right. So, clock() still returns milliseconds, but the resolution is about 50ms.

    There is a Windows function that works. I think it's GetClockTick().

  10. #10
    jasondoucette.com JasonD's Avatar
    Join Date
    Mar 2003
    Posts
    278

    Re: timing accuracy?

    Originally posted by mfknitz
    What I have below is the closest I've gotten but at times still shows 0 seconds, other times .06, or .11
    That's because you are using the default system timer that ticks approximately 18.2 times per second (about every 55 msec). In fact, it is the original 4.772720 MHz clock of the original IBM PC divided by 2^18. You should use the QueryPerformanceCounter function, instead, if you are programming under Windows.

  11. #11
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    About vector memory:
    The exact allocation strategy is implementation-defined, but the most common is this:
    initial size: 0
    first addition: allocate 1
    whenever not enough memory: allocate twice as much as there already is

    I know that SGItech STL and STLport use this. I'm quite sure the the MS and GNU STL use it too.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  12. #12
    Registered User
    Join Date
    Jul 2003
    Posts
    6
    Thanks everyone for your great replies. The GetTickCount() worked but still wasn't accurate enough for really small lists. The QueryPerformanceCounter works great though.

    I've allocated more memory initially in my vector now and it's working pretty well. I think it'll take me a little bit to learn all the ins and outs of dynamic memory but this is a pretty good start. Thanks

  13. #13
    jasondoucette.com JasonD's Avatar
    Join Date
    Mar 2003
    Posts
    278
    There's also a
    clock_t clock( void );
    function in <time.h>

    On my WinXP system, it has a resolution of 1/100th of a second, even though it returns values in milliseconds, as CLOCKS_PER_SEC on my machine is 1000.

    I guess this is something you could use if your system doesn't have a High-Resolution Timer.

  14. #14
    Registered User
    Join Date
    Jun 2003
    Posts
    245
    In a program I've written that talks to an external device on the serial port, the device requires millisecond accuracy to "wake up". I've implemented this as follows which works perfectly as the resulting serial trace on an oscilloscope was measured and found to be at exactly 1ms intervals.


    timeBeginPeriod (1); // request windows to be accurate to within 1ms instead of the normal 5ms. This function will return TIMERR_NOCANDO if the system does not support 1ms accuracy (works fine under 2000 and XP, which are my main OS's).

    timeGetTime(); // Returns the system time, in milliseconds. This is very efficient and low-overhead function. It returns a DWORD result, and so wraps around to 0 every 2^32 milliseconds, which is about 49.71 days.

    timeEndPeriod(1); // Call this function immediately after you are finished using timer services. Parameter is the value you used in timeBeginPeriod.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Performance Timing Function
    By rosicky2005 in forum C++ Programming
    Replies: 11
    Last Post: 05-31-2007, 03:09 PM
  2. My Timing System
    By jmd15 in forum Windows Programming
    Replies: 4
    Last Post: 01-01-2006, 11:43 PM
  3. mouse accuracy
    By joed in forum Windows Programming
    Replies: 3
    Last Post: 06-25-2005, 04:52 PM
  4. Games - timing
    By Magos in forum Game Programming
    Replies: 7
    Last Post: 03-06-2004, 11:32 AM
  5. Timing in Windows
    By steinberg in forum Windows Programming
    Replies: 3
    Last Post: 07-14-2002, 12:43 AM