>>Single Point of Failure >>

Map

Ξ January 28th, 2012 | → 0 Comments |
∇ Programming | ∇ C++, Map, Picture |

Going Concurrent

Ξ December 23rd, 2011 | → 0 Comments |
∇ Programming | ∇ Brain, C++, Concurrency, Number, OpenMP |

I had to implement a progress bar for a GUI application, and in order to keep the application “live” my focus during last couple of weeks shifted to multi-threaded concurrent programming. The solution was simple and it basically implied implementing a background thread to update the progress bar while filling a data structure by reading a file. It was simple enough to be implemented in a couple of days, but it became clear that some of the topics related to concurrent programing just weren’t as consolidated I would like.

Since the I’ve been skimming over some interesting articles on the subject. Also began to read “Concurrent Programming in Java, 2nd Edition” by Doug Lea and “The Art of Concurrency” by Clay Breshears .

The following is my attempt to solve the brain-number problem (addressed initially by Ari Sundaram).

#include <cmath>
#include <iostream>
#include <limits>
#include <cassert>

#include "omp.h"

/* ***
 * Count the digits in the number
 * ***/
int count_digits(int number)
{
	return log10(static_cast<double>(number)) + 1;
}

/* ***
 * Calculate the brain-value of the number
 *
 * The brain-value is the sum of each digit in number to the power of the
 * number of digits.
 * BV(d1d2d3...dn) = d1^n + d2^n + d2^n + ...  + dn^n,
 *                                              where dn is the nth digit
 * ***/
int
brain_value(int number)
{
	int sum = 0;
	int digits = count_digits(number);

	while(number > 0)
	{
		sum += ::pow(number % 10, digits);
		number = number / 10;
	}

	return sum;
}

/* ***
 * Checks if number is a brain-number
 *
 * A number is a brain-number when it's brain-value equals the number itself
 * ***/
bool
is_brain_number(int number)
{
	return brain_value(number) == number;
}

/* ***
 * Prints the brain-numbers in the lower/upper range
 *                                 (Serial Version)
 * ***/
void
print_brain_numbers_in_range(int lower, int upper)
{
	assert(lower >= 0);
	assert(lower <= upper);

	for(int i = lower; i <=upper; i++)
		if(is_brain_number(i))
			std::cout << i << std::endl;
}

/* ***
 * Prints the brain-numbers in the lower/upper range
 *                                 (Parallel Version, using OpenMP)
 * ***/
void
print_brain_numbers_in_range_parallel(int lower, int upper)
{
	assert(lower >= 0);
	assert(lower <= upper);

	#pragma omp parallel
	{
		#pragma omp for
		for(int i = lower; i <=upper; i++)
			if(is_brain_number(i))
				#pragma omp critical
				{
					// Critical section ensures correct output
					std::cout << i << std::endl;
				}
	}
}

/* ***
 * Helper function to test the
 * ***/
template<typename Printer>
void execute_print_brain_numbers(Printer& printer, int lower, int upper) {

	std::cout << "The brain numbers between "
	          << lower << " and " << upper << " are:" << std::endl;
	double start = omp_get_wtime();
	printer(lower, upper);
	double end = omp_get_wtime();
	std::cout << "Listed in " << (end - start) << " seconds" << std::endl;
}

int main(void)
{
	execute_print_brain_numbers(
		print_brain_numbers_in_range,
			0,
			std::numeric_limits<int>::max() / 100);

	execute_print_brain_numbers(
		print_brain_numbers_in_range_parallel,
			0,
			std::numeric_limits<int>::max() / 100);

	return 0;
}

Once virtual, always virtual…

Ξ October 23rd, 2011 | → 0 Comments |
∇ Programming | ∇ C++, Programming, Rule, Virtual |

What will be the output of the code below?

#include <iostream>
#include <memory>

using namespace std;

namespace abyss {

class A {
public:
  virtual ~A() {}
  virtual void f() { cout << "A::f" << endl; } // base is virtual
};

class B: public A {
public:
  virtual ~B() {}
  void f() { cout << "B::f" << endl; } // this is also virtual
};

class C: public B {
public:
  virtual ~C() {}
  void f() { cout << "C::f" << endl; } // continues to be virtual
};

}

int main() {
  auto_ptr<abyss::A> base(new abyss::C);
  base->f();
   // method called using pointer to base gets dispatched to C::F

  return 0;
}

Take notice of the “once virtual always virtual” rule that states that once a method is qualified as virtual there is no way to turn off the dispatching mechanism provided by the language for virtual functions. Unlike Java, C++ does not have the notion of final (which interrupts the dispatching). This means that, even though neither B or C classes qualify f() as virtual, the call to base->f() shall be dispatched as if it was.

I like to follow the convention to place an explicit virtual qualifier to make clear the expected behaviour. It would be nice to have some kind of warning from the compiler, but no issue is raised (at least when using g++ 4.5.1).

abyss::round

Ξ October 9th, 2011 | → 0 Comments |
∇ Programming | ∇ C++, Round, Standard |

From time-to-time the question re-emerges “How to round floating values?”. (I know its stupid, but after this post, I’m sure the mental note will stick!)

Yes, there is a round function in C and C++ standards.
It was introduced in the C99 standard, and it is also available in the C++98 standard. The round function is defined amongst others mathematical related function in math.h (cmath for C++ purposes).

But, for purposes not worth mentioning, I was using a pre-round compiler and had to roll my own function. The standard defines that the round function shall return the nearest integer value in floating point format, rounding halfway cases away from zero. This means that negative values rounds up in absolute value (i.e. -1.7 rounds to -2.0, while -1.2 rounds to 1.0). Here is the result of my experiments (abyss is the namespace that stores my experiments, as in “It is by going down into the abyss that we recover the treasures of life.“).

#include <cassert>
#include <iostream>
#include <cmath>

typedef double(*round_function_t)(double);

namespace abyss {
double round(double x) {
  return (x > 0.0) ? std::floor(x + 0.5) : std::ceil(x - 0.5);
}
}

void testRoundedValue(double value, double expected,
                      round_function_t round_function) {

  double rounded = round_function(value);

  std::cout << value << " rounds to " << rounded
            << " obtains " << expected << std::endl;
  assert( rounded == expected );
}

int main(void) {
  round_function_t round_func = abyss::round;
                                // use std::round for standard round

  testRoundedValue(-1.70, -2.0, round_func);
  testRoundedValue(-1.51, -2.0, round_func);
  testRoundedValue(-1.50, -2.0, round_func);
  testRoundedValue(-1.49, -1.0, round_func);
  testRoundedValue(-1.20, -1.0, round_func);

  testRoundedValue(-0.50, -1.0, round_func);
  testRoundedValue(-0.49, -0.0, round_func);
  testRoundedValue( 0.00,  0.0, round_func);
  testRoundedValue( 0.49,  0.0, round_func);
  testRoundedValue( 0.50,  1.0, round_func);

  testRoundedValue( 1.20,  1.0, round_func);
  testRoundedValue( 1.49,  1.0, round_func);
  testRoundedValue( 1.50,  2.0, round_func);
  testRoundedValue( 1.51,  2.0, round_func);
  testRoundedValue( 1.70,  2.0, round_func);

  return 0;
}

Best Reading

Ξ April 8th, 2011 | → 0 Comments |
∇ Programming | ∇ C++, Design, Generic, Patterns, Programming |

Today I finished one of the best C++ books that I’ve ever read. “Modern C++ Design” by Andrei Alexandrescu is amazing. The techniques presented are ground breaking, and I must admit the joy of learning about the described techniques was immense. This is certainly a must-read book for all C++ afficionados, like myself.

Reading this book made me believe (I was sure of it from the start, even before starting) that there’s still much to learn about C++. This book is certainly not for the faint of heart. In order to keep up with the huge amount of new concepts, techniques and approach, I had to “build” a mind-map. Check it out to have just a glimpse of the books contents, as “seen” by me. 

A Puzzle…

Ξ November 6th, 2010 | → 0 Comments |
∇ Programming | ∇ C++, Exceptional, Programming, Puzzle |

The Exceptional C++ book series by Herb Sutter are amazing. The three books^* provide (sometimes not so easy but) very interesting puzzles related to the possible uses of modern C++ programming. Its perfect to the passionate programmer, and you can be sure to learn and enjoy the time spent reading these books.
Here is an excerpt from Item 4 of More Exceptional C++, which intends to find a mechanism to check, at compile time, that a given class D is derived from a base class B.

template<typename D, typename B>
class IsDerivedFrom
{
  class No { };
  class Yes { No no[2]; };

  static Yes Test( B* ); // declared, but not defined
  static No Test( … ); // declared, but not defined

public:
  enum{ Is = sizeof(Test(static_cast(0))) == sizeof(Yes) };
};

I have to admit that it took me a while to understand what the hell was going on in this piece of code. Can you see how this solved the issue? Very clever, right!?

* Exceptional C++, More Exceptional C++ and Exceptional C++ Style

Factory

Ξ March 28th, 2010 | → 0 Comments |
∇ Programming | ∇ Abstract, Architecture, C++, Design, Factory, Method, Pattern |

 

My goal was to read an XML file containing a list of class names, and then instanciate the classes according to that list by caling a simple function inside a for loop.
The Abstract Factory is a very interesting design pattern that provides an encapsulation mechanism to the creation of families of objects. Combining this with the Factory Method it is possible build a factory that, after ‘generator method’ being registered, enables a simple mapping between a string object and an object.

The example shows an abstract Product which implements a given interface. There are two concrete products that derive from the base definition: a BigProduct and a SmallProduct. Then we have the Factory<T> that will be the production line for objects of type T. In the example, with T = Product, we have Factory<Product> that allows to call registration and creation methods, respectivelly:

template <class P>
void Factory<P>::registerProduct(const std::string& key, const Generator& generator)

template <class P>
P* Factory<P>::newProduct(const std::string& key)

The trick is that during registration you must provide the Generator function (also known as Factory Method) that will be used as building method by the factory. In this implementation, the Generator
is defined by the Factory itself but it could be defined anywhere as long as it returns a pointer to an abstract product. The implemented generation is based on default construction:

template <class P> template <class DP> // where P is Product and DP any kind of Derived Product
P* Factory<P>::generate()
{
return new DP();
}

In practice, using the factory is quite simple…

int main (void)
{
typedef Factory<Product> GenericFactory; // Simplifying the factory type…

GenericFactory factory;

// Register products and ‘generation’ methods…
factory.registerProduct(”BigProduct”, GenericFactory::generate<BigProduct>);
factory.registerProduct(”SmallProduct”, GenericFactory::generate<SmallProduct>);

// Calling for product creation
// NOTE: The use of auto pointer ensures that newly allocated object
//       is automatically destroyed as the end of scope
std::auto_ptr<Product> bp(factory.newProduct(”BigProduct”));
std::auto_ptr<Product> sp(factory.newProduct(”SmallProduct”));

bp->doFeature();
sp->doFeature();

return 0;
}

There is one very interesting evolution of this design that I’ve done, to enable runtime class registration. I’ll post on that the next time.

---

Download the implementation: Product.hpp BigProduct.hpp SmallProduct.hpp Factory.hpp Main.cpp

Code Snipet of the Day

Ξ February 4th, 2010 | → 0 Comments |
∇ Programming | ∇ C++, code, snipet, toupper |

Tokens

Ξ January 31st, 2010 | → 0 Comments |
∇ Programming | ∇ Boost, C++, Experiments, Tokens |

Experiments with tokens and Boost

Tic Tac Toe, just for kicks

Ξ January 16th, 2010 | → 0 Comments |
∇ Programming | ∇ C++, Game, Tic Tac Toe |

Download here, compile and play.