Monthly Archives: January 2014

Maze

maze

This code generates 'perfect' mazes and solves them.

This code is just for fun. It generates a ‘perfect’ maze and solves it. The results are written out to a PNG file. For details, click here.

Fractals

Fractals

These are pictures of fractals generated by using Newton's method in the complex plane.

f(z) = z^5 - 5.0*z^4 - 55.0*z^3 + 245.0*z^2 + 654.0*z - 2520.0
f(z) = z^5 - 5.0*z^4 - 55.0*z^3 + 245.0*z^2 + 654.0*z - 2520.0
f(z) = z^5 - 5.0*z^4 - 55.0*z^3 + 245.0*z^2 + 654.0*z - 2520.0
f(z) = z^5 - 5.0*z^4 - 55.0*z^3 + 245.0*z^2 + 654.0*z - 2520.0
f(z) = sin(z)
f(z) = sin(z)
f(z) = sin(z)
f(z) = sin(z)

This software uses Newton’s method (the one from any first year calculus course) in the complex plane to generate fractals. This code makes use of many of the new C++11 language features, so a newer compiler will be required (I used GCC 4.8.1 running on Opensuse). This code is documented thoroughly with doxygen.

How it Works

A rectangular region is first chosen in the complex plane. Then, the fractal is computed row by row (a row is a line with all points on the line having a constant imaginary component – a horizontal line). Each point on the row is used as the initial guess for Newton’s method. Newton’s method will eventually converge on one of the zeros of the fractal generating function. The color of the associated pixel is chosen by which zero Newton’s method finds. The shading is derived from the number of iterations needed to reach the zero.

Source and Documentation

Here

Atomic Locking vs. Mutexes

atomic_v_mutex

Quotient of Times
Quotient of Times
Atomic Lock Times
Atomic Lock Times
Mutex Lock Times
Mutex Lock Times

The Question

Which is faster, a queue guarded by a std::mutex, or the same queue guarded by an atomic? This experiment attempts to at least partially answer that question. To do this, I constructed a queue that could be guarded by either a std::mutex or by my own atomic based lock. Then, I ran a fixed number of elements through the queue, with varying numbers of producer and consumer threads.

To be clear, this experiment was run several times (in single user mode). The number of elements that passed through the queue was the same for all runs. Each run had a fixed number of consumer threads and a fixed number of producer threads. Each run had a guard on the queue that was either a std::mutex or it was an atomic based lock. Each run was timed, and the results were recorded.

The Results

See especially the graphic titled “Mutex / Atomic”. Surprisingly, the atomic based lock out performed std::mutex in most cases. Only in those cases where there is much contention (that is, where there are many producer and consumer threads) did std::mutex do better. In these high contention cases, it is likely that those threads using an atomic lock are consuming quite a bit of time spinning, and you can see the resulting drop in performance (see the graph labeled “Atomic Serialization”). In those cases where there is low contention, it would appear that the atomic lock simply has less overhead than a std::mutex. Later, I’ll have to look at the C++11 standard, to see exactly what is required of a std::mutex. That might explain things.

The Source

Is available here.