Sorting data in parallel CPU vs GPU - In which we show more graphics
Posted on February 7, 2013 by Paul
The code for this post is on GitHub: https://github.com/sol-prog/Sort_data_parallel/tree/TBB in the TBB branch.
This is a sequel to my last article in which we’ve shown that you can, relatively easily, implement a parallel merge-sort algorithm using only functions from the standard library of a programming language, C++11 in this case. We’ve also compared our implementation with a state of the art sorting function from the CUDA 5.0 SDK thrust::stable_sort.
Following some concerns, raised by a commenter - snk_kid, I’ve made a new set of tests based on a state of the art CPU parallel sorting function from Intel’s TBB. His main these was that my previous comparison between CPU and GPU was misleading, because the use of raw threads in merge-sort is not efficient and, in general, I should refrain myself from writing about this subject unless I use task based parallelism or high level parallel libraries.
Sorting data in parallel CPU vs GPU
Posted on February 4, 2013 by Paul
The code for this post is on GitHub: https://github.com/sol-prog/Sort_data_parallel.
You can read the second part of this article.
For many programmers sorting data in parallel means implementing a state of the art algorithm in their preferred programming language. However, most programming languages have a good serial sorting function in their standard library. It appears to me, that the obvious thing to do is to first try to use what your language library provides. If this approach is not successful, you should try to find an existing library that is used, and consequently well debugged, by other programmers. Only as a last resort, you should implement a new sorting algorithm from scratch.
In the case of C++, we have a well tested sorting function in the STL, std::sort, unfortunately std::sort will use only a fraction of the processing power available in a modern multicore system.
Building Clang 9, LLVM 9, libc++ and lldb on Ubuntu 18.04
Posted on January 17, 2013 by Paul
Updated on 24 September 2019
Clang with libc++ represents today a viable alternative to GCC for C and C++ programmers. Even if you plan to ship your C++ application compiled with GCC, I think it is a good test to check your app for errors by building it with a different compiler and library.
In this short post, I’m going to show you how to build the latest Clang and libc++ on a Linux box. I’ve tested this procedure on Ubuntu 18.04, but it should work on Debian and WSL without a problem.
Building Lua 5.3 on macOS
Posted on January 12, 2013 by Paul
Updated 7 October 2017
If you want to build yourself the latest Lua on macOS there is a simple recipe for this:
- Start by downloading the Lua source code from http://www.lua.org/ftp/.
- Extract the archive (I did this in my Downloads folder).
- Open a Terminal and navigate to the Lua source code:
1 cd Downloads
2 cd lua-*C++11 sort benchmark
Posted on October 24, 2012 by Paul
The code for this post is on GitHub: https://github.com/sol-prog/Sort_benchmark.
A good sorting routine is a building block for many numerical algorithms and, because of this, most modern programming languages provide one or more sorting algorithms in their standard library. C++ is not an exception. What varies, from one C++ implementation to another, is the performance of the sorting algorithm.
C++11 lets you use three sorting functions std::qsort, std::sort and std::stable_sort. While std::qsort comes from the C roots of C++, std::sort and std::stable_sort are provided by C++’s Standard Template Library. The new C++11 standard requires that the complexity of std::sort to be \(O(n \cdot \log (n))\) in the worst case. Historically, in the C++98 standard std::sort was defined as \(O(n \cdot \log (n))\) on average, with a possible worst case scenario of \(O(n^2)\).
C++11 async tutorial
Posted on October 17, 2012 by Paul
For a few years now, we live in a multiprocessor world, starting from the phone in my pocket to the parallel quad-core beast I have on my table. Today, you could easily buy a six or twelve core machine that is several orders of magnitude more powerful than the super computers from a decade ago.
As programmers, we need to be able to use at full capacity the available computing power, you can’t buy a new computer and expect that your serial code will run faster. You need to write code that can run on multiple core machines or you will deliver a low quality product to your potential clients.
The new C++11 standard allows us to maximize the use of the available hardware directly from the language. Today, you could write portable multithreading code using only the standard library of the language.
C++11 timing code performance
Posted on October 14, 2012 by Paul
Prior to the release of the C++11 standard, there was no standard way in which one could accurately measure the execution time of a piece of code. The programmer was forced to use external libraries like Boost, or routines provided by each operating system.
The C++11 chrono header file provides three standard clocks that could be used for timing one’s code:
- system_clock - this is the real-time clock used by the system;
- high_resolution_clock - this is a clock with the shortest tick period possible on the current system;
- steady_clock - this is a monotonic clock that is guaranteed to never be adjusted.
Building Cling (the C++ interpreter) on Windows
Posted on September 2, 2012 by Paul
11 September 2012 update
The last revision of Cling, r45925, doesn’t need any modifications in order to compile on Cygwin, I’ve removed some outdated instructions about manually editing the libcling.exports file.
3 September 2012 update
After a discussion with the main developer of Cling I’ve removed a paragraph about adding some hard codded paths in the Clang sources, this was an unnecessary complication. I’ll keep updating this article if we’ll find any other simplifications.
In my last article I wrote about Cling, the C and C++ interpreter. If you want to have a taste of what Cling can do for you, read my earlier post or this one. In short, Cling is a C++ REPL that uses Clang and LLVM for just in time compilation and parsing of your code. Currently, Cling can be officially compiled only on Unix like operating systems (e.g. Linux or OSX). What if you can’t, for various reasons, use a Unix like OS ? Well, this post is for you, the Windows user!
In principle, you could use Visual Studio to compile Cling, however because of the incompatibilities between Clang and Visual Studio, the resulting interpreter will let you use only C code. At the time of this writing, a Visual Studio compiled Clang is not able to build C++ executables … A C only interpreter, while useful, is not so attractive, at least not for me.
Cling a C++11 interpreter
Posted on August 14, 2012 by Paul
A C++11 REPL may sound strange, after all C++ is generally seen as a compiled language. However, any programming language can be implemented as a compiler or as an interpreter and Cling happens to be an interactive C++ interpreter based on LLVM and Clang.
If you’ve ever programmed in a language that can be used in a Read-eval-print-loop or REPL you already know what productivity boost can be to be able to test an idea without waiting for your build system to compile your code. Even with tools like make you need sometimes to wait from a few seconds to a few minutes just to see the effects of some small change in a particular piece of code.
Roguelike game in C++ - Adding a rudimentary monster to the game
Posted on August 1, 2012 by Paul
The code for this post is on GitHub: https://github.com/sol-prog/roguelike.
Last time we’ve added a real map to the game, generated with a Perlin noise function. But where is the fun in a roguelike game without a monster ? In this post, we are going to add a rudimentary monster to our game, that will chase the main character. The player task will be to dodge the monster and stay alive …
Our monster will be dumb, all he knows is to chase the main character on the map. Because I’m more interested in testing an idea for a chasing algorithm, we are not going to create a separate class for the monster, we’ll refactor the code and add some AI to our monster in a future tutorial. For now we could use the Character class to initialize our monster:
1 int main() {
2
3 ...
4
5 // Initialize the main character. We are going to put this in the middle of
6 // the game map (for now)
7 Character main_char('@', game_map.height()/2, game_map.width()/2);
8
9 // Add a dummy monster to the game (we start with a hard coded monster position defined
10 // relatively to our main character position)
11 Character monster('M', main_char.row() + 7, main_char.col() + 22);
12
13 ...
14
15 // Start the game loop
16 game_loop(game_map, viewport, main_char, ch, monster);
17
18 return 0;
19 }Roguelike game in C++ - Map generation with Perlin noise
Posted on July 25, 2012 by Paul
The code for this post is on GitHub: https://github.com/sol-prog/roguelike.
In the last post of this series we’ve added a dummy map to the game on which the main character was able to move freely. Now it is time to add a real map to our roguelike game, in order to be able to add elements on the map we are going to use a Perlin noise function. If you are interested in how I’ve implemented the Perlin noise function in C++ you could read my Perlin noise in C++11 article.
I’ll include here, for completeness, the PerlinNoise class definition. The complete code is on the Github repository posted at the beginning of this article:
1 class PerlinNoise {
2 // The permutation vector
3 std::vector<int> p;
4 public:
5 // Initialize with the reference values for the permutation vector
6 PerlinNoise();
7 // Generate a new permutation vector based on the value of seed
8 PerlinNoise(unsigned int seed);
9 // Get a noise value, for 2D images z can have any value
10 double noise(double x, double y, double z);
11 private:
12 double fade(double t);
13 double lerp(double t, double a, double b);
14 double grad(int hash, double x, double y, double z);
15 };Perlin noise in C++11
Posted on July 18, 2012 by Paul
The code for this post is on GitHub: https://github.com/sol-prog/Perlin_Noise.
Ken Perlin’s noise function is the building block of many texture generation algorithms, you can use it to create realistically looking materials, clouds, mountains etc … The first version of this function was developed in 1988 and it is still used in various graphical libraries. In 2002 the author has published an improved version of his noise function.
I searched the Internet for a C++ implementation of the improved Perlin noise function, while obviously available in various libraries I didn’t found this implemented as a ready to use class. Also there seems to be a general confusion between what is a Perlin noise function, some websites confuse the Perlin noise function with FBM (Fractal Brownian Motion).
Roguelike game in C++ - Adding a map to the game
Posted on July 16, 2012 by Paul
The code for this post is on GitHub: https://github.com/sol-prog/roguelike.
The last post of this series has laid the ground for a small roguelike game - the main character @ was added on the screen and the user was able to change his position using the arrow keys. Now it is time to add more interactivity to our game by creating a test map on which the character is allowed to move freely.
We’ll start by refactoring a bit the code for the screen initialization part implemented last time, we could put all this code in a Screen class, we show here only the definition of the Screen class:
Roguelike game in C++ - Bootstrap
Posted on July 12, 2012 by Paul
The code for this post is on GitHub: https://github.com/sol-prog/roguelike.
I suppose you’ve skimmed through the Introduction to this series of blog posts about implementing a toy roguelike game in C++. That being said, let’s get started!
If you want to follow along with the development, you will need a C++ compiler and the ncurses library. I’m going to use the GNU C++ compiler (specifically g++-4.7.1) for testing and compiling my code. In principle any C++ compiler available on your system should work, just be sure that you can work with the last version of ncurses. For Mac users, installing Xcode and the Command line tools will also install ncurses. On Linux you could use your package manager for installing g++ and ncurses, the procedure is different from distribution to distribution, if you use a Debian derived distro, like Ubuntu, all you have to do is to write in a Terminal:
1 sudo apt-get install g++
2 sudo apt-get install libncurses5-devRoguelike game in C++ - Introduction
Posted on July 12, 2012 by Paul
The code for this post is on GitHub: https://github.com/sol-prog/roguelike.
A few days ago I read an article named How to Write a Roguelike in 15 Steps, this article wet my appetite to implement my own roguelike game in C++. Why am I losing my time with a text based game instead of say attempting to implement the next clone of Angry Birds for iOS? Well, first I think implementing a small game from scratch is fun and I could learn a lot during the development phase. I tried a few times before, to work on a fully blown graphical game (C++ and OpenGL) but it is easy to lose interest when you code a few hours for testing an idea and you notice that the initial concept was a bad one. It seems to me that I could be more productive if I use my time to develop the game concept instead of thinking at how to implement a complex graphical effect.
I plan to document the development of the game in a few blog posts.