Printable View
Hi!
I'm currently playing around with different (self-made) implementations of data structures to hold a large amount of (custom) data like B*Trees and Hashtables.
The goal should be to find the most efficient solution, but I don't know how to compare them by their memory consumption and general performance.
As a compiler I'm using the MinGW port.
What whould you propose for those measurements?
Thank you in advance!
Easiest approach is to use your own version of new/delete to count the amount of memory being used. The simplest way to achieve that in itself is to wrap ALL of your code inside another class - that way, you can implement new & delete for that class, and then use the ::new and ::delete to actually implement the new&delete functionality. Bear in mind that you also need to do new[] and delete[].
As long as your work is purely CPU bound, you should be able to measure the CPU usage by using clock() .
--
Mats
Well, you can also measure performance by time spent.
Measure time1
Algorithm
Measure time2
Time spent = Measure time2 - Measure tim2.
Use gettimeofday() to measure time. Generally you can use both gettimeofday() and clock(), which measure different things to have a more accurate counting on performance.
The thing is that you have to come up with an algorithm. That is up to you. For example the algorithm might test how fast the elements are accessed. So you it can simple sum all elements (in that way you also see if the result is correct).
You can measure how fast you can write things to it. So you can iterate through its elements and right something to them.
You can measure how fast you can delete elements from it. So start deleting random elements in the algorithm.
So this way you will be able to calculate speed and memory usage (as mastp said) for some common things, like insertion, deletion, access etc etc
thank you for your fast answers!
Using time measurements is a good idea, I'll do that!
Can you give me a short example how to create my own new & delete to measure the used heap space, please?Quote:
Originally Posted by matsp
There is an example of implementing your own new/delete by calling global new/delete here:
http://cboard.cprogramming.com/showthread.php?t=110083
Inside your new function, just add up the size in new. If you need to account for deleted elements, then you'd have to add a bit of extra space when allocating with ::new, and store the size, then return the place beyond the size [to ensure that the alignment is still correct, you may want to put this in a union that also has a long long or a double - or even a 16-byte SSE type value - and return the position after this union]. That way, delete will know the size being returned to the free store (heap) - remember to then ::delete the base pointer where the size is stored, not the pointer returned back to the user from new (and thus passed to delete).
--
Mats
Note that clock() has different meanings on different platforms. I never tried the MS compiler, but it behaves differently even between GCC on native Linux and GCC on MinGW. I don't remember which is which, but one of them would measure the wall time, while the other would measure CPU time.
gettimeofday() is a lot more consistent.
Considering that gettimeofday is not available in Windows, I don't see how it can be MORE consistent.Quote:
Originally Posted by cyberfish
clock() on Linux gives CPU time, whilst on Windows, it is gives the wall-time value. But as long as the process is running 90+% cpu usage, it shouldn't make much difference.
--
Mats
I think MinGW now implements it.
Even if it doesn't, there is a widely used implementation of it using WinAPI, too -
http://www.halcode.com/archives/2008...-gettimeofday/
If you are in Windows use QueryPerformanceCounter() and QueryPerformanceFreq() for timing information.
That gives more detailed timing, but otherwise the same flaw as clock() - don't differentiate betwen CPU usage and waiting time.Quote:
Originally Posted by Bubba
--
Mats
Good information matsp. As well Salem pointed in another thread that there are issues with QPC and QPF as well. If I wasn't so lazy I'd post the link to it here. :D.
I guess there isn't a 100% correct way to get accurate timing under XP?
clock() is pretty good averagely - but it very much depends on what is being measured, and how. If the process being measured is not working the processor 100% of the time (or close to), then clock() isn't a great option. If you need really short intervals, it's also not that great, as it's only updated on clock-ticks (10ms or so). Performance Counter is better then (but not perfect - as pointed out in the other thread on the subject).Quote:
Originally Posted by Bubba
If you want to know how much time a particular process has used up, then GetProcessTimes is an option - that will not increment when other processes are being run, or when the system is idle. It will even show how much time is user-space and how much is kernel-space time. Again, no more precise than clock() or GetTickCount().
--
Mats
how about GetSystemTimeAsFileTime()?
Again, although it appears to be VERY PRECISE, it is actually just a different format around "GetTickCount()" - it is updated on each timer tick (10ms), but it returns a 100ns precise time. The reason for this is that it ALLOWS the system to give a precise time should it have an easy way to do so. By the way, clock() in my VS .Net uses GetSystemTimeAsFileTime() and a "starttime" variable that is set at the beginning of execution (before main()).Quote:
Originally Posted by cyberfish
--
Mats
Ah I see. Thanks for the information.
So I guess there is no way to get precise AND accurate wall time on Windows?
Out of curiosity, what is the accuracy (not precision) of gettimeofday() of typical Linux implementations?
Depends on the implementation, but most systems provide nanosecond accuracy using for example RDTSC - of course, that is still subjec to the problems described elsewhere which is that it CAN vary between CPU's. There are various things done in the system to keep them in sync, but there is still some chance that two or more processors run out of sync, thus leading to minor differences in timing.Quote:
Originally Posted by cyberfish
--
Mats
Does it mean the accuracy is about 1ns, but in 2 consecutive calls to gettimeofday(), the second one may return a time earlier than that returned by the first call?
the timer tick resolution on a win system can be increased by call to timeBegin(End)PeriodQuote:
Originally Posted by matsp
http://msdn.microsoft.com/en-us/libr...13(VS.85).aspx
high precision timing in XP on multicore is a big issue (google will give a ton of references). If there is one argument for windows vista regarding multimedia applications/simulations/games and so one than it is it's support for timing via cpu independent HPET chips.
And of course, on really modern processors, the TSC is constant and synchronized across cores and sockets, so there's not the same need to worry about it. But for older processors, the HPET is a good way to get it. But there's been problems with HPET on some models of chipsets too, unfortunately.Quote:
Originally Posted by pheres
--
Mats