All My Brain Where stuff from my brain lands

August 6, 2008

3 Optimizations for speeding Visual C++ compiled code.

Filed under: Programming — Tags: , , , , — Dennis @ 7:55 am

For fun, I participated in a programming contest. Instead of describing the process this time, I thought I’d include a function. Can you guess what it does? I’m changing some of the variable names so it isn’t obvious.

unsigned short result [dim][dim];
void foo(const string& info1, const string& info2, string& ret_val) {
 for (int x=0;x=0;--x) {
  sum += carry;
  carry = sum / 10;
  ret_val.insert( ret_val.begin(), (char)(sum % 10 + '0') );

Anyhow, now that that fun is over, I was reading comments on a C++ forum and someone mentioned a few tips to optimizing C++ code with Visual C++. I thought I’d do a quick comparison between these and see how much of a difference it made since I was interested in program execution time and already had timing code built into my program.

  1. Release build

    I was already doing this, but I thought I’d include it for the sake of being complete.

    Debug build running time: 0.09 seconds
    Release Build running time: .02 seconds

    Obviously, this is a big one.

  2. Optimizations

    Optimizations are usually the biggest difference between release and debug builds. By default, my compiler was adding /O2 to build for maximum speed. I decided I’d enable every other optimization possible

    Release build optimizations settings

    Release build optimizations settings

    Anyway, the funny thing was, it ran faster by leaving the settings as they were. Obviously, you’ll need to test these and know what they do before simply enabling them. One thing that did seem to make a difference though, was to link against the Multi-threaded library instead of the Multi-threaded DLL. (/MT instead of /MD)

  3. Disable secure stl

    I found references to adding /D_SECURE_SCL=0 to the compiler command line. I assume if you heavily use iterators with STL, this might make more of a difference. For my little program, it didn’t seem to do much at all. I’m not completely sure it was even working. I’m assuming for now though, that it will do something, but that my program isn’t a good test case.

June 2, 2008

The Difference Between Dijkstra’s Algorithm and A*

Filed under: Programming — Tags: , , , — Dennis @ 7:10 am

Over the last couple weeks, I’ve had an interest in brushing up my C++ skills. Friday, I came across a programming challenge that looked somewhat interesting and I thought I’d give it a shot.

The object was to find the lowest cost route between 10 cities encoded in a map of integers. Each integer represented the cost to get from that any adjacent location to that spot. This is a classic case of a graph navigation algorithm. Unfortunately, I didn’t have time to test my submission before I had to hand mine in. The deadline was Saturday so I did what I could and turned a solution in before I had to leave Saturday evening.

I ended up with the 3rd best solution for the lowest route and the 2nd best solution for time. I’m not going to discuss Dijkstra’s Algorithm here. You can view the Wikipedia definition or look it up elsewhere if you’re interested in implementing it. I’m simply going to discuss the difference between Dijkstra and A* and show what I could have done with more time to get a top score in the competition.

In Dijkstra’s algorithm you search all the verticies in the graph to determine the lowest cost route between each point. A* is a modification of Dijkstra’s algorithm that uses a heuristic to determine which vertices to search. The heuristic is the estimated cost (or distance) from the node you’re searching to the target node. The lower the heuristic, the more likely you’ll search that node’s edges next instead of some node that is further away. This leads you from the source to the target in a much faster manner. A* allows you to trade off the most accurate result for CPU time.

My route cost was quite a bit higher because I chose a heuristic that was too high. After testing a bit further, I found I could come up with a 2nd place route cost by simply lowering the heuristic a bit. This causes more nodes to be searched, and the algorithm run time to climb, but the result is more accurate. Doing away with the heuristic altogether yields a route cost of 2801, which is the same route cost that the 1st place entry received. The execution time goes up to 36 seconds in that case however. The more accurate Euclidian heuristic (linear distance) yields 2819 and costs 10 seconds.

My 2nd issue was implementation details. I think the algorithm is actually coded correctly but I used data structures that needed constructed and destroyed many times during the algorithm search. I planned on coding the algorithm correctly 1st and then optimizing it but didn’t have time to do the latter. The 1st optimization I’d make is to store node pointers instead of nodes and then only construct a node once during the algorithm’s search cycle. I don’t know if this would have yielded the fastest program or not. Either way, it’ll save a lot of cpu cycles.

Anyway, I accomplished my goal of re-familiarizing myself with lots of STL structures, some iostream details and a few C++ quirks that I hadn’t used or remembered for a while. Perhaps I’ll do better with Challenge 13.

Powered by WordPress

%d bloggers like this: