Wednesday, July 23, 2008

C++ Looping Beauty

(TODO: categorize posts)

/* This is for any programming folks out there! For the record, I realize that very few people reading this will understand more than 2% of this. So I won't be offended if you stop reading right here. I promise. Sometimes I'll write about programming in non-programming lingo, but this is very lingo-infested. */

Every Tuesday at Chief Architect we developers have a development talk (consisting of c++ libraries or Chief program architecture or design patters) over lunch (consisting of Qdoba, Pizza Hut, or a local deli). Earlier this summer, one of our developers gave a talk on high-level coding practices in C++, and made a couple shocking statement in particular.

1) Don't write loops.
2) Don't write conditionals

Loops and conditionals, of course, are two fundamental control structues and the buildling blocks of all computer programs since the 1960s or so. So of course it's not really possible to avoid them, and the shocking claims are better rewritten as follows:

1) Favor standard algorithms over manual loops.
2) Use polymorphism instead of conditionals.

Rule #1-- in C++, this often means using the for_each standard algorithm with functors. Suppose you have a list of images that you want to generate thumbnails of. The manual method, and the first that comes to mind for most programmers, looks something ilke this:

// Method #1
for (int i=0; i < images.size(), ++i) {
Bitmap thumb = shrinkImage(images[i]);

This works fine, but has at least one major downside. Suppose your "images" container is a list, which is good because you can add and remove from lists in constant time. However, to access the i'th element of a list, you have to traverse through each element in the list from the beginning to element i--no big deal if you're at say element 5, big problem if you're at element 10,000. So--under the hood--the first time through the loop you just grab element 0; the second time, you step over #0 to get #1; the third time, you step over #0 and #1 to get #2; the hundredth time, you step over #0 and #1 and all the way to #98 to get #99. (This is the same whether you're in C++ or Java or C# or Lisp or Basic or whatever, whenever you're working with a linked list data type.) Now, in C++ you can use iterators to solve this really quick:

// Method #2
for (list::iterator i = images.begin(); i != images.end(); ++i) {
Bitmap thumb = copyAndShrink(*i);

This time, by dereferencing the iterator (*i) you can work with items of the list as you're walking through it, which is phemonenally faster than before. But this is still a manual loop, and Rule #1 is about avoiding manual loops, like so:

// Method #3
void generateThumbnail(Bitmap& image)
Bitmap thumb = copyAndShrink(image);
std::for_each(images.begin(), images.end(), generateThumbnail)

THIS is what the rule's all about. Put your looping code into its own function or function object--functor (see example below). Why? For one thing, in Method #2, you had to worry about what kind of iterator you're using, which in that case was a list iterator. When you're using for_each, you can change your "images" datatype from a list to a vector to a raw array to a deque, or any container with a .begin() and a .end() method, without having to change your loop a bit.

This guideline doesn't just apply to for_each (which means, do something to each item in a container). The C++ Standard Template Library has a whole slew of functions that can replace manual loops: find, find_if, remove, remove_if, reverse, etc etc. These functions are written by people whose entire job is to make the most efficient algorithm mathematicaly possible, for whatever kind of iterator you're working with (which means whatever kind of container you're working with). And this is why it's better to use a library function rather than a loop whenever possible.

Now if you've actually understood all this, and unless you've used the STL a lot, you're probably thinking that there's no way this can replace ALL loop cases--which is (for pratical purposes) true. But it works well for a heck of a lot more cases than I originally thought. For instance, suppose your thumbnail loop needs to make thumbnail objects and place them in another collection, say a list. That is, you want to do this:

// Manual loop (a C++ vector is a commonly used container, not a vector like in physics)
vector images = loadImages();
vector thumbnails;
for(vector::iterator i = images.begin(); i != images.end(); ++i) {
Bitmap thumb = copyAndShrink(*i);

In this case, you can't just write an ordinary to do what you want in the loop, because the function will know nothing about the vector "thumbnails." Soooo you can make a function object--functor--and pass it a reference to thumbnails in its constructor. Then you "call" this function object just like you would an ordinary function, with operator() like so.

// Super cool and effecient loop
class LoadThumbnails : std::unary_function // necessary to use in a STL loop for typedefs
LoadThumbnails(vector& thumbsList) : mThumbsList(thumbsList) {}
void operator()(Bitmap& bmp)
Bitmap thumb = copyAndShrink(bmp);
vector& mThumbsList;
vector images = loadImages();
vector thumbnails;
std::for_each(images.begin(), images.end(), LoadThumbnails(thumbnails));

I'll talk about Rule #2 later. But I'll leave with just a couple quick observations (this is so much fun). (I know, I'm a nerd.) First, in the manual loops I used ++i instead of i++, because the pre-increment is one processor cycle faster than post-increment. (Post-increment copies the stored value, increments the stored value, and returns the copied value. Pre-increment increments the stored value and returns the stored value.) Second, these collections of Bitmaps should really just store pointers to bitmaps, because bitmaps are large and you don't want to keep copying them around in memory (which STL containers will do). If you're in a garbage-collected language like Java or C# then you're always got pointers. In C++ you have to keep track of who owns the memory to know who's responsible for deleting it... OR you could use a fancy smart pointer (like a boost::shared_ptr) which manages the memory by keeping a reference count, and every time its destructor is hit, it decrements the reference count, and when the reference count hits zero, voila! Deallocate the memory.

Sunday, July 20, 2008


Had a great mini-vacation with my family in Kellogg, Idaho at Silver Mountain. (Random fact, the speed limit is 75 mph out there--I've never seen a speed limit greater than 70. I guess I need to get further inland more often.) We took lots of great pictures on my family's new camera, which is unfortunately by understandably with them and not with me, so maybe I'll make a facebook album from them next time I'm home. Which will occur, God willing, in four weeks, during the few days between when my job ends and the semester begins.


I'm not a big fan of Facebook Applications in general, but I put on these two a few weeks back and recommend them:

If you love music (so virtually everyone): "Currently Listening To." It shows the name, artist, and album cover of whatever CD you're currently listening to. This is one of the features I loved about Xanga back in the day.

If you love to read: "Currently Reading." Likewise, this just shows the book name, title, and cover of whatever you're reading. I love the simplicity of it. I don't have to sketch out all the books I've ever read, the books I own, the books I want to read, etc etc (there are more popular library applications out there for that), but this is just what I'm reading right now. It takes about 5 seconds. Both this and the listening to application work with a simple query, and this has picked up even the more obscure books I've tried.

I'm currently listening to Bebo Norman's greatest hits CD, which is amazing (he's got a duet with Rich Mullins, who died over 10 years ago), and reading the autobiography of Jonathan Goforth, a missionary to China after the turn of the century, who emphasized Revival by the work of the Holy Spirit through people who pray continually. Goforth--isn't that a wonderful name for a missionary??

Sunday, July 13, 2008

Majesty Come Down

I couldn't resist. I broke down and played my favorite two songs from Bebo Norman's Christmas CD, "From the Realms of Glory": Angels Interlude and Born to Die.

And the angels filled the sky /
All of heaven wondered why /
Why the King would choose to be /
Be a baby born to die

Tuesday, July 8, 2008

Living as Witnesses

“‘But you will receive power when the Holy Spirit comes on you; and you will be my witnesses in Jerusalem, and in all Judea and Samaria, and to the ends of the earth.’” Acts 1:8

“But in your hearts set apart Christ as Lord. Always be prepared to give an answer to everyone who asks you to give the reason for the hope that you have. But do this with gentleness and respect, keeping a clear conscience….” 1 Peter 3:15-16

“So do not be ashamed to testify about our Lord, or ashamed of me his prisoner.” 2 Timothy 1:8

“You are the light of the world. A city on a hill cannot be hidden. Neither do people light a lamp and put it under a bowl. Instead they put it on its stand, and it gives light to everyone in the house. In the same way, let your light shine before men, that they may see you good deeds and praise your Father in heaven.” Mathew 5:16

The Problem:

The problem is twofold. First, college Christians too often do not live in that shining light—walking in the Spirit, filled with joy and peace, serving others in humility. As a result, unbelievers have no good works to see and praise God about.

Second, college Christians too rarely share the gospel with other people. There are several reasons for this. (1) We don’t care. When our hearts should break for lost souls, headed for hell, we often respond in casual indifference—focusing on our own business rather than caring for others. This selfishness is clearly sin, and we must repent of it. (2) We are afraid of rejection, or that others will think of us as strange. By valuing the opinion of people over the opinion of God, and by valuing their opinion over their lost souls, we sin and need to repent. (3) We shy away because we don’t feel confident enough to explain and defend the gospel. We must take Scripture's command seriously to always be prepared. Even so, we can’t cite a lack of readiness as an excuse when the Spirit prompts us to share. We’re called to be “witnesses”—a witness is simply someone who shares what he has seen (witnessed) Christ do in his or her life. We must confess our excuses as sin and repent, depending on the Spirit to the give us words to say and on Spirit to turn hearts from darkness to light.

Many Christians have a different problem. They do share the gospel, but they become discouraged because few respond. They can even feel responsible for the condemnation of those around them. These Christians need to remember that only God can open their eyes—Jesus declared, “I shall lose none of all that he (the Father) has given me” (John 6:39)—and to continue to faithfully speak the good news as the Spirit leads.

Monday, July 7, 2008

On Earth as it is in Heaven

"This, then, is how you should pray:

'Our Father in heaven,
hallowed be your name,
your kingdom come,
your will be done
on earth as it is in heaven.
Give us today our daily break.
Forgive us our debts,
as we also have forgiven our debtors.
And lead us not into temptation,
but deliver us from the evil one.'"

Jesus Christ, Matthew 6:14-15


One thing God has spoken,
two things have I heard:
that you, O God, are strong,
and that you, O Lord, are loving.

David, Psalm 62:11-12


Jon Foreman wrote a breathtakingly beautiful song from these two verses in "Your Love is Strong," Track 5 in his Spring album. These verses are what's so amazing.

Tuesday, July 1, 2008

Line Style Editor

I'm just finishing up a project at Chief Architect, the small software company (also the name of their flagship product) where I'm working this summer. It's been a wonderful experience working here--the work day flies by, so I figure that's a good sign--and having a blast in design and programming. My recent project has been a line style editor:

What's a line style? If you draw a line in Microsoft Word, you can choose a set of line styles like dashed and dotted, but you can't customize them or anything. Chief Architect is a CAD (Computer Aided Design) tool tailored for home design, and a fundamental CAD tool is lines. Engineers and architects want a whole array of line styles (dash dot dash, dash dot dot, little-dash long-dash little-dash dot, dot dot dot dot little-dash dot, water line, power line, A/C, etc etc). My little editor here allows you to edit and create them from scratch. Anyways, I've had fun with it. Under the hood it's over 1000 lines of code. Didn't take long to get the basics working--it did take long to get all the intricate details and making it compatible throughout the system.

As I'm writing this, there's lighting flashing and thunder cracking all around me here in Post Falls ID. Sometime I'll have to take a picture the falls, which is literally across the street from Luke's and my place.