Cool Link Stash, February 2013

Graphics

Simon Yeoung posted a nice article on his blog on his implementation of voxel cone tracing.

NVIDIA posted a great article on their site on why to use pre-multiplied alpha called Alpha Blending: To Pre or Not To Pre. A longer, more in-depth treatise of the same subject was posted in 2006 by Tom Forsyth, a worthwhile read.

Steve McAuley has a short post on his blog that builds on a previous post he did on making the often used wrapped diffuse model energy-conserving. In this new post, he extends the formula to a generic wrapped diffuse model where an arbitrary power is used to soften the look a bit. His post is called Extension to Energy-Conserving Wrapped Diffuse.

Here's a nice blog post comparing NVIDIA's FX Composer to Unity when it comes to quick shader prototyping.

C++

Google released a C++ library called cpp-btree, which provides an STL-style implementation of B-tree data structures.

Another one of Herb Sutter's talks at C++ and Beyond 2012 got released on Channel 9. atomic Weapons: The C++ Memory Model and Modern Hardware is a two-part talk on the new C++11 memory model. This is a must-watch if you're doing any work on lock free algorithms. Great, in-depth talk.

Other

Decoda is a free and open source IDE for Lua with an integrated debugger. You can check out the source code on the Decoda GitHub repository.

After having done code reviews of the various open sourced id Software code bases, Fabien Sanglard is back with a review of the code of Duke Nukem 3D.

C++11 Wrap Pattern

Herb Sutter gave a great talk at the C++ and Beyond 2012 conference on concurrency in C++11.

The talk had an interesting interlude on how to wrap all functions performed on an existing type T in order to inject any desired behavior, and that's what this post is all about.
The pattern basically looks like this:

template <typename T>
class wrap
{
public:
	wrap(T wrapped = T{}) : m_wrapped{wrapped}
	{}
	
	// operator() takes any code that accepts a wrapped T
	// will usually be a lambda
	template <typename F>
	auto operator()(F func) -> decltype(func(m_wrapped))
	{
		// do any pre-function call wrapper work 
		auto result = func(m_wrapped);
		// do any post-function call wrapper work 
		return result;
	}
	
private:
	T m_wrapped;
	// ... other state required by wrapper
};

This wrap class template can now be used by instantiating it and calling operator() on it with an anonymous lambda function that accepts the wrapped type as single argument.

wrap<X> wrapper;
wrapper([](X& x)
{
	x.call_something(foo, bar);
	x.do_something_else();
	std::cout << x.print() << std::endl;
});

A concrete example of using this pattern is a monitor wrapper class, which is similar to the synchronized keyword in Java.
A monitor wraps every function call (or a group of function calls) on an existing class in a mutex lock to make the class thread-safe.

template <typename T>
class monitor
{
public:
	monitor(T wrapped = T{}) : m_wrapped{wrapped}
	{}
	
	template <typename F>
	auto operator()(F func) -> decltype(func(m_wrapped))
	{
		std::lock_guard<mutex> lock{m_mutex};
		return func(m_wrapped);
	}

private:
	mutable T m_wrapped;
	mutable std::mutex m_mutex;
};

Note that m_wrapped is mutable, which is required so that func(m_wrapped) works if func takes the T as a non-const reference T&.

Mutable in C++11 means thread-safe, which means either bitwise const or internally synchronized. Our mutex lock guard guarantees that by the time the m_wrapped is used in func(m_wrapped) it will be internally sychronized, so making m_wrapped mutable is perfectly acceptable.

monitor<string> s = "start\n";
std::vector<std::future<void>> tasks;

// start a bunch of tasks
for (int i = 0; i < 5; ++i)
{
	tasks.push_back(async([&,i]
	{
		// single transaction, synchronized modification of s
		s([=](string& s)
		{
			s += "transaction " + to_string(i) + " of 5";
			s += '\n';
		});
		
		// do some more work
		
		// single transaction, synchronized read of s
		s([](string& s)
		{
			std::cout << s;
		});
	});
}

// join all tasks
for (auto& task : tasks)
	task.wait();

Note that T used in wrap or monitor could also be a reference, if you don't want to make a copy of T. This is useful for capturing stateful objects, such as std::cout.
So it is perfectly valid to do:

monitor<ostream&> sync_cout{std::cout};

sync_cout([=](ostream& cout)
{
	cout << "Writing stuff to cout..." << std::endl;
	cout << "in a synchronized way" << std::endl;
});

That's a wrap, folks! 🙂

C++11 Lambda Expression Overloading

I recently read about a neat trick regarding overloading of lambda expressions in C++ in a blog post by Dave Abrahams here. This technique was originally described by Mathias Gaunard. I want to do a short post about it here so I don't forget it.

In C++11, it is possible to overload lambda expressions by creating a helper function object class that inherits from the function objects the compiler generates for the lambda expressions and then pulling in the lambda expressions' operator() via using declarations.

Simple Example

Here's a simple console application that demonstrates this for two lambda expressions:

#include <iostream>

template <class F1, class F2>
struct overload_set : F1, F2
{
	overload_set(F1 f1, F2f2)
		: F1(f1), F2(f2)
	{}

	using F1::operator();
	using F2::operator();
};

template <class F1, class F2>
overload_set<F1, F2> overload(F1 f1, F2 f2)
{
	return overload_set<F1, F2>(f1, f2);
}

int main(int argc, const char* argv[])
{
	auto f = overload
		(
			[]() { return 1; },
			[](int x) { return x + 1; }
		);

	int x = f();
	int y = f(2);

	std::cout << "x = " << x << ", y = " << y << std::endl;

	return 0;
}

The overload function in this example returns a function object called overload_set that inherits from the two function objects created by the compiler for the two lambda expressions passed to it. Note that you don't necessarily have to use lambda expressions. Any function object class that exposes an operator() can be used.

The two operator() are then pulled into the overload_set class via a using declaration. So client code now sees a function object class that provides two operator(), in this case, one that has no arguments and one that has an integer argument. When calling through the function object regular function overloading comes into play and the compiler chooses the correct function to call depending on the supplied arguments.

Variadic Template Implementation

Here's a more general implementation of the technique described above using variadic templates. If you're not yet familiar with C++11 variadic templates, the Wikipedia page on the subject is pretty good.

template <class... Fs> struct overload_set;

template <class F1, class... Fs>
struct overload_set<F1, Fs...> : F1, overload_set<Fs...>::type
{
	typedef overload_set type;

	overload_set(F1 head, Fs... tail)
		: F1(head), overload_set<Fs...>::type(tail...)
	{}

	using F1::operator();
	using overload_set<Fs...>::type::operator();
};

template <class F>
struct overload_set<F> : F
{
	typedef F type;
	using F::operator();
};

template <class... Fs>
typename overload_set<Fs...>::type overload(Fs... x)
{
	return overload_set<Fs...>(x...);
}

This is quite a neat trick, even though admittedly it probably won't be useful very often. It might come in handy for certain generic algorithms, for example to implement compile-time double dispatch.