Tag Archives: programming

Creating an Object-Oriented Framework from an existing API

One of my personal goals this year is to go through Petzold’s book on Programming Windows. During that 1500+ page journey I’m creating a framework class library for my personal use while developing Windows applications. This way I can simultaneously learn the intricacies of Win32 while at the same time developing a framework library that is different than MFC or .Net. Why would I want to do that? Well… MFC isn’t exactly lightweight and it has some performance issues. But aside from that, it’s just fun!

When embarking on something ambitious like this, however, you immediately comes across issues you need to solve, such as how to map an essentially flat API like Win32 into an object-oriented hierarchy of reusable classes. Win32 was, after all, designed before object oriented programming became popular.

There are some patterns that you can use to recognize opportunities for classes and inheritance.

1) Some parameters show up a lot, often as the first argument to a function. All of the GDI functions, for example, take a handle to a device context. This pattern is much like the implicit this parameter in OO programming. A device context is a good candidate for being wrapped into a class, with the GDI functions as members. Most window manipulation functions take as an argument a handle in the form of HWND. Window is another candidate for a class. There are other examples, but these two are good starting places for creating the class hierarchy.

2) There are many variables that are often typecast to other types. Think GDI handles such as HPEN, HBRUSH, and HBITMAP. GDI functions such as SelectObject return a generic HGDIOBJECT which is usually cast to the appropriate HPEN or what-have-you. Fundamentally, these are all the same basic data type–just interpreted differently. This situation is a good candidate for inheritance and polymorphism.

You can also look at other framework libraries for ideas, but this idea is not as attractive, because the point is to develop something original through the learning process, and if those frameworks provided exactly what you wanted, why bother creating a new one anyway? On the other hand, much can be learned by examining proven techniques.

Another big issue you need to deal with in developing a framework library is messaging, but I’ll deal with that in a later post.

ArgumentNullException and ArgumentException

Does it strike anyone else as ironic that ArgumentException and ArgumentNullException have mismatched argument ordering? The parameter name is first for the null version, but second for the other one. Uggh… this makes it awkward to remember if you use both. ArgumentOutOfRangeException follows the example of ArgumentNullException.

I can see no obvious reason for the discrepancy. In all three cases, the constructors are exactly the same. In fact, MSDN explicitly says that the behavior is the same.

Why Developer Certification Doesn’t Make Sense

Much as been said about the pros and cons of requiring software engineers to be certified, just like the medical, law, and engineering fields.

I personally do not believe this should happen. First of all, those other, certified, fields have existed for thousands of years. Computer Science is not even a century old. The field is incredibly immature. Sure, we have fancier tools, and we can do some amazing things, but we’re still in infancy!

Look at the best software makers you can think of. I won’t name names. Think of the highest quality applications you have ever used. Now think of all the problems and bugs and limitations of that software. If that’s the best we can do, what meaning does certification have?

All the other certified fields have well-established standards that have withstood the tests of time. Computer Science hasn’t had the time. We can’t even agree on the best way to make software!

So go ahead and enforce certification now, but it’s not going to mean anything.

Infinite Enjoyment with Finite Resources

Have you ever thought about the miracle of music? OK, some might object to the world miracle, but I’m talking about music, something where transcendental terminology is appropriate.

On a piano you have 88 keys. Instruments can go higher (violin) or lower (organ), but with the same repeated 12-note octave everything in western music is created.

Thing about that. 12 notes, repeated over and over, at higher and lower frequencies. It’s such a small working set! How many melodies can you create in one octave?

More importantly, how many beautiful melodies can you create? Thousands of composers over thousands of years have proven that there is no limit to the originality possible with these limited tools. Of course, there are accompanying tools: instruments, rhythm, and personal style. But always with the same 12 notes.

And an infinity of beauty is possible because of it. Granted, our notions of what art is beautiful change over time, but who denies the beauty of War and Peace, Les Misérables, The Last Supper, Intermezzo from Cavelleria Rusticana, Jesu, Joy of Man’s Desiring, Pachelbel’s Canon in D, or anything by Rembrandt? Beauty grows, never shrinks.

Now imagine if there were infinite numbers of keys–how would that change things? What if we doubled the resolution of the notion of half-step (F toF#, for example) to a quarter step?* 8th step? 16th step? I don’t think this will inspire more creativity (at least not creativity that produces beautiful works of art). Too many options will spoil the landscape–clutter it up so much that not only can we not understand music produced like this, but creating it becomes onerous–there are way too many possibilities. The mathematical framework of music forces us to contain our creativity within bounds of structure that “make sense” to our minds, that allow us to understand, dissect, and enjoy.

The modern notion that lack of constraints promotes creativity is a false one. No constraints means less thought and feeling has to be put into work.

I hand you a canvas and tell you to paint your best work ever. What will you do?

You might ask–“What is the subject of the painting?” I respond–“Anything.”

You can’t work like that. Of course, you might come up with a theme yourself, but now you’re constraining yourself along a certain path.

Another example: in the 20’s Hollywood had no movie-making constraints. There were no censors. Do you remember many movies from the 20’s? In the 30’s, constraints were imposed by the government, forcing Hollywood to clean up its act. How many movies are memorable from the 30’s onward? A lot, even to my young mind. I think a case could be made that dissapearing constraints now is creating the same dull period in Hollywood that existed back in the 20’s. Sure, you can make anything you want, but who is actually going to care deeply about it?

Software development thrives under these conditions. Software developed with no or few constraints quickly looks like garbage and is much less useful. Impose coding constraints, design constraints, interface constraints–all these RULES you have to obey–and your code will become artful. Look in all the books on the subject of turning average programming into craftsmen, artists, what-you-will–the books mostly teach you RULES to follow, lines to stay within.

Coloring outside the lines is fun every so often, but you rarely frame it and call it art.

* Of course, continuous instruments such as strings can do this, but it’s not standard musical technique.

2-D Arrays versus Structs

I had a situation the other day where I needed an array of two values and the thought occurred to me: which is better? A 2-D array or a 1-D array of structs. I decided to come up with a quick test to see.

Here are my results:

2-D Arrays : 55.9376 cycles/row
Structs : 31.9937 cycles/row

That’s the number of cycles, on average, to add up the numbers in a row. Cycles makes more sense to me than microseconds when we’re talking about this level of code.

It turns out that the struct version is about 74% faster, which confused me slightly. Isn’t the memory layout for both options the same and should thus have the same assembly code?

It turns out…no. Before proceeding, download the test code here. It’s not pretty, but it works. Some of the mess is designed to keep the compiler from optimizing out my test cases. I tested with Visual Studio 2005 beta 2 with default release mode compiler options.

So lets look at two things I discovered:

Here are the addresses of the first two rows (of two elements each) of the two array styles:

sum1: 0x00354860 0x00354868 0x00354878 0x00354880
sum2: 0x026F0020 0x026F0028 0x026F0030 0x026F0038

Take a look at sum2 (the array of structs); each element starts exactly at 8-byte intervals–what we would expect because memory is often aligned on 8-byte boundaries on x86.

But look at sum1; the elements in the first row are 8 bytes apart, but the next row starts 16 bytes later! That means 8 additional bytes are wasted between each row. This means that fewer rows will fit in the CPU’s L1 cache, causing more cache misses, slowing down the program. (Why did this layout occur? I don’t know the answer to that yet)

Second of all, let’s look at the assembly code. This is just for adding the two elements of a row together.

;array addition
mov eax, DWORD PTR _arr$[esp+4] ; 1st operand addr
mov eax, DWORD PTR [eax+ebp*4] ; 2nd operand addr
fld QWORD PTR [eax+8] ; 1st operand
fadd QWORD PTR [eax] ;add 2nd operand
faddp ST(1), ST(0) ;add result to answer

;struct addition
fld QWORD PTR [eax+8];put first operand in register
fadd QWORD PTR [eax-16] ; add other operand
faddp ST(1), ST(0) ;add result to answer

So…the array version has to do two mov’s to fixup the correct addresses.

It seems now that the struct version is slightly more efficient here–both in space and in speed. However, this is really a microcosm of a problem. This kind of thing probably wouldn’t matter unless you were doing a lot of it. Personally, I’d go with the struct more often than not because it would be much easier to update the code to use a 3rd field, for example.

List<> vs. ArrayList

I read Rico Mariani’s latest quiz, and decided to check out the results for myself in BRayTracer.

I already have some simple performance benchmark tests in my NUnit tests, so I ran some before and after. I changed only the ArrayList’s used in the scene object to hold shapes, materials, and lights.

Before:

25.197 opaque spheres/sec (time: 3.969 )

After:

31.841 opaque spheres/sec (time: 3.141 )

Pretty impressive savings with minimal work! Almost a full second! In an enormous scene, that will add up to a LOT of time saved. I still have to change the implementation for polygons and polygonal meshes–this will greatly speed up those operations, which are currently fairly slow. In fact, the way I have polygonal meshes written at the moment, they’re nearly impossible to render in a decent amount of time.

More exciting things coming to BRayTracer soon…

Curvy: Part 1

I’ve been wanting to learn COM lately, and not knowing where to start I began in some of the MFC books I have. Admittedly, MFC hides quite a bit of COM complexity, but I figured it would be a good place to get my feet wet without getting scared.

My first test program is called Curvy (Actually, Curvy2 since I restarted it with the doc/view architecture). It’s a curve drawing program. You can use the left mouse button to create points on a curve, the right mouse button closes the curve, and you can change the control points and move the curves.

The fun part was implementing copy & paste. It uses the OLE clipboard and puts both its native format and a bitmap on the clipboard.

The other fun part was implementing OLE Drag & Drop. This took me a few times to get quite right, but the results are spectacular. You can drag shapes within a window as well as to other windows. Holding down the ctrl key will copy the shape instead.

The project is in VS .Net 2005 format, but the code will compile under previous versions of VS.

Click here to download.

Next stop for this? Implement a full OLE server so other programs can host Curvy components inside them!

Checking if a Directory Exists

I recently had to write a utility that moved hundreds of thousands of files to a new location under a different directory organization. As part of it, I checked to see if the destination directory already existed and if not, created it. At one point I wondered if it would just be faster to try and create it, and if it fails, assume that it already exists (remember, I’m dealing with hundreds of thousands of files here–anything to speed it up is very welcome).

Determining if a directory exists isn’t entirely straightforward. If you use .Net, you can use Directory.Exists(), but that function must use the Win32 API at some point and there is no Win32 API that determines the existence of a directory, so what is it doing?

Ah, but there is an API to get the attributes of a given filename.

[code lang=”cpp”]
BOOL DirectoryExists(const char* dirName)
{
DWORD attribs = ::GetFileAttributesA(dirName);
if (attribs == INVALID_FILE_ATTRIBUTES) {
return false;
}
return (attribs & FILE_ATTRIBUTE_DIRECTORY);
}[/code]

Note that if the function call fails it doesn’t necessarily mean that the directory doesn’t exist–it could be that the device is inaccessible, you don’t have security permissions, or any number of other things. To know for sure what’s going on, you would need to call GetLastError().

So what if you’re creating directories? Why not try to create them no matter what? That’s fine, but is that faster than checking to see if it exists first? Let’s test it.

[code lang=”cpp”]
BOOL CreateDirectory(const char* dirName)
{
return ::CreateDirectoryA(dirName,NULL);
}

…

for (int i=0;i

CreateDirectory(dirName);

}
[/code]

Results (10,000,000 iterations):
265.227 second(s) total
2.65227e-005 second(s) average iteration

Now let’s try checking first:

[code lang=”cpp”]
for (int i=0;i BOOL bExists = DirectoryExists(dirName);
if (!bExists) {
CreateDirectory(dirName);
}
}
[/code]

Results (10 million iterations):
103.24 second(s) total
1.0324e-005 second(s) average iteration

Over 2 .5 times faster!

Now, my simple test is retrying a single folder over and over, and it never actually creates anything. In my case for the utility I mentioned above, I’m creating far fewer directories than the number of files I’m moving to them (though still in the thousands). In that case, it’s definitely worth my time to check to see if the folder exists before trying to create it.

To me, it appears that unless the number of folders you’re creating is of the same magnitude as the number of files, it definitely makes sense to check first.

This goes to show that you can’t believe anything related to performance until you measure it for your application.