Monthly Archives: June 2005

Code Timing functions

When it comes to timing your code, there are a lot of options, and depending on what you need to do, not all of them make sense. There are timing functions which utilize callbacks and other ways to periodically call a designated function at a regular interval–I’m not going to discuss those types of timers.

Instead, I’ll focus on the kinds of timing you can do to assess code performance.

To illustrate the differences between these methods, let’s have a simple C++ program:

[code lang=”cpp”]
#include
#include

using namespace std;

int main(int argc, char** argv)
{
//begin timing

//test code
const int nLimit = 10000000;
double sum = 0;

for (int i=0;i {
double rt = sqrt(static_cast(i));
sum+=rt;
}

//end timing

cout << “sum: “<

cout << elapsed << ” second(s) total”< cout << avg << ” second(s) average iteration”<

return 0;
}[/code]

I deliberately chose something simple and fast. Here’s why: if you’re timing something that always takes an hour–a second doesn’t matter, and the first option will work perfectly fine. On the other hand, if you need to time something small that will potentially be repeated dozens, hundreds, thousands, or millions of times, every microsecond can matter.

time_t and CTime

time() is the good old C standby. It’s simple, it’s easy, it’s historic, and it’ll break after 19:14:07, January 18, 2038, UTC.

To remedy this, Microsoft has the _time64() function, which uses the type __time64_t. It improves the lifespan, but not the precision.

Our code is now:
[code lang=”cpp”]
#include
#include
#include

using namespace std;

int main(int argc, char** argv)
{
//begin timing
time_t start = time(NULL);

//test code
const int nLimit = 10000000;
double sum = 0;

for (int i=0;i {
double rt = sqrt(static_cast(i));
sum+=rt;
}

//end timing
time_t end = time(NULL);
cout << “sum: “< long elapsed = static_cast(end – start);
double avg = (double)elapsed / nLimit;
cout << elapsed << ” second(s) total”< cout << avg << ” second(s) average iteration”<

return 0;
}[/code]

Output:
sum: 2.10819e+013
16 second(s) total
0 second(s) average iteration

MFC’s CTime is just a wrapper for time_t (VC++6.0) or __time64_t (VC++7), so nothing new here.

time_t is good when you don’t need very precise measurements, when you’re just interested in the date and/or time, as in wall-clock time, or when it’s your only option.

For timing code, this is not a great option.

GetTickCount

Windows contains a function called GetTickCount which returns the number of milliseconds since the machine was turned on. This gives us 1,000 times better accuracy then time().

[code lang=”cpp”]
#include
#include
#include

using namespace std;

int main(int argc, char** argv)
{
//begin timing
DWORD start = GetTickCount();

//test code
const int nLimit = 10000000;
double sum = 0;

for (int i=0;i {
double rt = sqrt(static_cast(i));
sum+=rt;
}

//end timing
DWORD end = GetTickCount();
cout << “sum: “< double elapsed = (end – start) / 1000.0;//ms –> s
double avg = ((double)elapsed)/ nLimit;
cout << elapsed << ” second(s) total”< cout << avg << ” second(s) average iteration”<

return 0;
}[/code]

Output:
sum: 2.10818e+010
0.172 second(s) total
1.72e-008 second(s) average iteration

As seen above, this value is returned in a DWORD, which is 32-bits wide. 232 milliseconds comes out to about 49 days, at which time the counter rolls over to 0. If you’re timing very short intervals, this probably won’t be a problem. The MSDN documentation has a code example to detect timer wrap-around.

GetTickCount provides much more precision than time_t, but with processor speeds at multiple gigahertz, a lot can happen in a millisecond. Enter…

QueryPerformanceCounter and QueryPerformanceFrequency

This set of functions is also available in the Win32 API and they are much more accurate than time_t and GetTickCount.

Their usage is often paired. QueryPerformanceCounter returns the current count on the timer, and QueryPerformanceFrequency returns how many counts per second there are. The documentation makes clear that timer frequency is not the same as processor clock frequency. This timer is hardware-based, however, and if your computer doesn’t have a timing device, then calling QueryPerformanceCounter returns the same thing as GetTickCount above, and QueryPerformanceFrequency returns 1000 (1000 ms = 1 s).

The code reads:

[code lang=”cpp”]
#include
#include
#include

using namespace std;

int main(int argc, char** argv)
{
//begin timing
LARGE_INTEGER start;
::QueryPerformanceCounter(&start);

//test code
const int nLimit = 10000000;
double sum = 0;

for (int i=0;i {
double rt = sqrt(static_cast(i));
sum+=rt;
}

//end timing
LARGE_INTEGER end;
LARGE_INTEGER countsPerSecond;
::QueryPerformanceCounter(&end);
::QueryPerformanceFrequency(&countsPerSecond);

double elapsed = (double)(end.QuadPart – start.QuadPart) / countsPerSecond.QuadPart;
double avg = elapsed / nLimit;
cout << “sum: “< cout << elapsed << ” second(s) total”< cout << avg << ” second(s) average iteration”<

return 0;
}[/code]

Output:
sum: 2.10818e+010
0.165298 second(s) total
1.65298e-008 second(s) average iteration

You can easily see the much improved precision.

OK, well these are all well and good if you have Windows, but what if you don’t have Windows, or the time isn’t as important as the number of cycles required to compute something?

Here’s…

GetMachineCycleCount

…a function to read the current CPU clock cycle. Note that there aren’t any API or standard library functions to do this so we need to use assembly. Note also that this wasn’t possible until the Pentium came along, so don’t run this code on a pre-Pentium computer. 🙂

[code lang=”cpp”]
#include
#include

using namespace std;

inline __int64 GetMachineCycleCount()
{
__int64 cycles; //64-bit int

_asm rdtsc; // won’t work on 486 or below – only pentium or above
_asm lea ebx,cycles; //ebx = &cycles
_asm mov [ebx],eax; //get low-order dword
_asm mov [ebx+4],edx; //get hi-order dword

return cycles;
}

int main(int argc, char** argv)
{
//begin timing

__int64 start = GetMachineCycleCount();

//test code
const int nLimit = 10000000;
double sum = 0;

for (int i=0;i {
double rt = sqrt(static_cast(i));
sum+=rt;
}

//end timing
__int64 end = GetMachineCycleCount();

cout << “sum: “< __int64 elapsed = end – start;
double avg = (double)elapsed / nLimit;
cout << elapsed << ” cycles total”< cout << avg << ” cycles average iteration”<

return 0;
}[/code]

Output:
sum: 2.10818e+010
263631085 cycles total
26.3631 cycles average iteration

What are some situations where this is useful? If you want to make a piece of code absolutely the fastest on any piece of hardware, regardless of clock-time, this can give you a truer reflection of the effectiveness of your algorithm. If you don’t have a high-performance timer API (and you don’t want to write one), then this is a quick-and-dirty, but effective, solution.

So what about discovering the speed of your processor? Well, there’s no machine instruction to do this. Basically, you have to combine the cycle count with the performance timers and run through a lot of loops to calculate an average.

I hope this has helped some people wade through the various options of timing performance-critical code.

25 Years

Well, today marks my 25th year of personal reign upon this earth….

I’m still young ‘un. I’m still in grad school, but I’ve got a good job, a wonderful wife, and things are going pretty well with everything else.

One of my favorite presents is a lego set. When I was a kid I played with legos constantly. Whenever I’m done with school and have time I plan to get back into it with legos and model building.

This week also celebrated my dad’s retirement from the U.S. Navy. He has had a long, illustrious and incredibly interesting career spanning the last three decades. I’m intensely proud of him and all his accomplishments. He had to fly into DC to take care of some paperwork, so we got to spend some time with him. I took him to the “other” air and space museum.

Visual Studio 2005 TS Beta 2

I finally received my Visual Studio 2005 Team System Beta 2 in the mail!

It took about 3 weeks to get here. I’m very excited. I plan on converting BRayTracer to use VS 2005.

It’s on track to take about 90 minutes to install. Installation of the compact framework failed, so I’m repairing that component. According to the log, it failed because another installation was in progress.

Features I’m looking forward to?

  • Refactoring – many free IDEs have them, it’s about time VS did too.
  • Improved IntelliSense – I know, IntelliSense is a crutch, but it’s a nice crutch to have–better than memorizing the API for Windows, .Net, MFC, and whatever sub-systems you’re working with.
  • The class designer – the old Add Method/Add Field was too slow and unwieldy to use.

There are a lot of other nice things that are in there. Check out the full list here.

Something I’d like to see that I don’t think is in there: change the type of a variable. I can foresee difficulties in this, but it would be a valuable feature.

[code lang=”cpp”]
float X;
[/code]

could be changed to

[code lang=”cpp”]
Coordinate X;
[/code]

and everywhere that variable is used, all the functions it gets passed to could be changed. As I said, there could be difficulties in this, but it would be powerful functionality.

Cars and the Idiots who Own Them – Part II

Well, I took it in this morning for a full checkup. I should preface this with by saying that for the last month, and especially the last week or so, I’ve been feeling strongly that I needed to take the car in for a serious look. Things just felt different–and not better.

I left it this morning at 8, and at 11 they had a diagnosis–made worse by the fact that my Honda Care extended warranty had run out a few months ago. Basically, new CV joints, new engine mounts, oil change (I just tacked that on), and something else that was fairly expensive.

The mechanic told me that otherwise the car is in great shape. The good news is that this kind of work won’t need to be done for a while.

I should be leaving to pick it up in about 45 minutes or so…

Cars and the Idiots who Own Them

Yes, I’m talking about me.

This morning, we had a big day planned: food shopping, checking out an international market, and having some guests this evening. We decided to go to the international market first1. We had heard they had really cheap produce and were not disappointed. We picked up quite a bit of greens and herbs and were on our way. We put them in the cooler to survive the trip to the next store, I put the keys in the ignition, and…

Nada.

The key turned all the way around the ignition, without turning on the car, and it wouldn’t come out! We tried for 15 minutes with the awful thing, every gimmick we’d ever heard of for stuck keys. Then we called our insurance company and they sent a tow truck–Estimated Time of Arrival: 2 hours.

Off and on for an hour I tried jiggling and juggling and haggling and huggling. Finally, after an hour, I took off the steering column’s plastic wrapper and looked at the ignition itself–it seemed a part was loose…just need to push it in…suddenly, it turned and locked and came out and went in and ignited! I canceled the tow truck, and drove straight to the dealership.

The thing is, I was going to take it in next Saturday for a full checkup no matter what anyway. Now I have an appointment for Monday morning to do that and fix the ignition. Skip work or rent a car? It’s hard to make up work when I have night classes. I might have to rent a car if mine needs serious work anyway.

Computers I can handle (usually!), but cars are another thing entirely. We ended up going to CostCo near where we live, instead of the much cheaper (and farther) Sam’s Club, but we made it home in one piece–and now we have yet another “theft deterrent.” 😉


1 – Grand Mart International Food, 6255 Little River Turnpike, Alexandria, VA.

Code Security and Typed Assembly Language

Over the summer I’m taking a class called Programming Languages and Security. This is the first time I’ve delved into security at this level before. It’s a seminar style, which means lots of paper reading, and I am going to give two presentations.

My first presentation was this past Thursday. I spoke about typed assembly language and security automata. It was absolutely fascinating, ignoring the formality of proofs, and all the mathematical notations.

The two papers I discussed were:

The TALx86 begins by describing many shortcomings of the Java Virtual Machine Language (bytecode), including such things as:

  • Semantic errors in the bytecode that could have been discovered if a formal model had been used in its design.
  • Difficulty in compiling languages other than Java into bytecode. For example, it’s literally impossible to correctly compile Scheme into bytecode. OK, Scheme is a pretty esoteric language, but…
  • Difficulty even in extending the Java language because of the bytecode limitations
  • Interpretation is slow, and even though JIT is often used these days, that’s not built-in to the VM

My immediate thought on reading this was, “Hey! .Net addresses each and every single one of these points!”

  • The CLR defines a minimal subset of functionality that must be supported by every .Net language–allowing over 40 languages to be compiled to MSIL
  • As a bonus, MSIL is typed (as is Java bytecode)
  • Just-In-Time compilation was designed in from the beginning and generally has superior performance to Java (in my experience)

It also seems that many of the experimental features present in such early research, such as TALx86, has ended up in .Net and compilers these days. Type safety is being pushed lower and lower. Security policies are being implemented into frameworks, operating systems and compilers, and there are other tools that analyze your code for adherence to security best practices.

On platforms such as .Net, type safety is more important because you can have modules written in VB.Net interacting with objects written in C++ or Python, for example. Those languages don’t know about each other’s types, but at the MSIL level you can ensure safety.

If you’d like, a copy of the presentation is available.

Attributes and Complexity

Attributes can be seen just as a way of gaining some benefits of multiple-inheritance without the awful complexity that comes with that feature. Most languages have wisely done away with MI, and replaced with interfaces, and now attributes.

For example, let’s look at this code fragment in C#:

[Category(“Test Class”)]
public class MyClass
{
//implementation of MyClass
}

This assigns an instance of a CategoryAttribute to MyClass. The same thing could be accomplished in C++, using a base class:

public class MyClass : public CategoryAttribute
{
MyClass() : CategoryAttribute(“Test Class”) { }
//implementation of MyClass
};

However, the disadvantage of the C++ approach is:

  • How do you get the attributes for an arbitrary object? You can try dynamic_cast<categoryattribute *>(arbitraryObject) and check to see if the result is not NULL.
  • If you want many attributes, you are doing multiple-inheritance in a big way, which is a Bad Thing. You will probably get collisions eventually.
  • The whole idea of using attributes per se is kind of lost when using inheritance. By definition, it violates the inheritance principle of “is a” (MyClass is a Category? ummm… no). Classes “have” attributes (MyClass has a Category? yes)

Managing Complexity – Part 2

Last time, I covered some generalities and anecdotes about minimizing complexity in my life. Today, I have a few more thoughts about complexity as it relates to software.

Software engineering has continually evolved since the inception of computer programming languages. One way of looking at that evolution is to see it in terms of improvements on complexity management. (This is a bit simplistic, since computers have simultaneously become much more complex.)

The first computers were simple by today’s standards, but the programming methodology was very complex: dials, levers, buttons, or physically connecting wires. Then machine language was developed binary code could be entered on a card, later memory, and interpreted.

These early languages required a perfect familiarity with the machine. If the machine changed, the code changed.

Over the years, the advances in languages have largely been a process of hiding the machine’s underlying complexity. ALGOL came around and hid the machine code and provided the foundation for FORTRAN and C. C built further by providing both structured programming tools and an abstraction of the machine’s language–one foot in each world.

Terminals began to have graphics capabilities and SmallTalk was developed to further hide the complexities of both growing code modules and user interface elements. Java hid the complexities of lower-level code like C and C++, and even took away the concept of a physical machine and substituted its own virtual machine, theoretically consistent across all physical platforms. C# has done much the same for Window–hiding the complexity of thousands of APIs in a hierarchical, intuitive framework of managed code.

Modern processors are beasts of infinite complexity and power compared to the early hulking iron giants, but the languages which we use hide nearly all of the complexity that our forebearers had to deal with on a daily basis.

Now it looks I’ve been really writing about abstraction. It’s extremely strongly related, but I don’t think it’s exactly the same thing. Abstraction is thinking at a higher level; minimizing complexity is thinking less.

Modern languages both abstract away lower level concerns and provide tools to minimize the complexity of things at the highest level.

There is increasingly a proliferation of visual tools, begun with GUI editors, but now including visual code designers.
Aspect-oriented programming and attributes are allowing complexity to be further minimized.

In the future, tools such as these, and increased use of COTS will become vital to accomplishing anything. Software complexity will only increase, but hopefully the trend of tools that minimize complexity will also continue.

Perhaps somebody (not me!) should investiage the theory of a total complexity quotient–a measure of the complexity of a system and the complexity of the tools to develop and manage that system. With this number we could measure if complexity overall is increasing or decreasing, and what/when is the crossover point.

Managing Complexity

Software engineers know that one of the keys to achieving development goals is effective complexity management. The single best way of managing complexity is to remove it from the system completely.

As a simple example, in an earlier version of my BRayTracer project (I really need to come up with a better name!), scene objects were edited by double-clicking on them in the tree view, which opened up a dialog window that displayed the properties of the scene object. The user could make changes and then click OK or Cancel.

This data flow introduced complexity by requiring:

  • An additional window to manage
  • Moving data between the main window and the dialog
  • Making a copy of the scene object
  • Allowing the user to cancel or undo previous actions

The functionality of being able to cancel changes necessitated most of that complexity.

While this example wasn’t overly complex, I still felt there was a better, simpler way. You can probably see a number of possible solutions:

  1. Implement a general undo system (more complexity)
  2. Don’t allow users to cancel changes–they’re committed! (possible, but wise?)
  3. Eliminate the dialog by having a child window on the main form (does not allow cancelling, but removes the additional dialog)
  4. Rethink how objects are edited from the ground up (expensive)

I went with option 3. Obviously, there’s a tradeoff here. I sacrificed some functionality for the sake of simplifying the interface and the code. In fact, in usability testing, many users wanted a way to cancel or undo changes. Someday, I’ll have to go back and add a way of doing it. This illustrates the principle that sometimes complexity is unavoidable for certain features (Undo support, for example, is nearly always very complex to implement effectively) and that often what is really going on is shifting the burden of complexity somewhere else.

Minimization of complexity is also tightly coupled to the principle of optimality (ah…but optimality of what?).


The tendency of developers (at least I assume it’s a tendency–I am, of course, generalizing from my own experience and those people I’ve observed) to minimize complexity is something that can carry over to our normal lives. I notice this myself in a number of ways, most of which probably aggravate Leticia to no end 🙂

  • When driving, I almost aways get in the “optimum” lane as soon as possible, that is, the lane from which I’ll have to make the fewest changes. Changing lanes adds to complexity. Having to worry about changing lanes when it becomes crucial adds too much complexity. While there are exceptions for painfully slow people, I change lanes only about 6 times on my 35 mile commute (4 roads and 4 highways).
  • When I cook, everything is optimized for minimal disruption. All ingredients and equipment are pregathered and then prepared in a way which minimizes work, time, and coordination.
  • When I watch movies at home, I try to optimize the experience by first queing up the movie, setting up the environment, volume, and then making popcorn. That way, once the popcorn is done we can begin watching immediately, while it’s hot. I almost can’t watch a movie without popcorn.