Resources to learn and understand parallel programming. The hard way

There’s no way other than the hard way. (c)

Parallel programming is considered as not easy or even advanced topic by many programmers. It’s the starting point for even more advanced stuff like distributed computations, reliability, CAP theorem, consensus problems and much more. Besides, deep understanding of how CPU and operating system works can help you to write less buggy software and parallel programming can help you with that too.

In this post I will focus on books describing parallel programming using 1 computer and 1 CPU using classical approaches. Neither they contain SSE instructions guides nor you will find matterials on CUDA or OpenCL. Similary you will find no resourced about Hadoop and/or MapReduce technologies and nothing about technologies supporting parallel programming out of the box like Go or Erlang.

So I will go now through all the resources which I find more or less useful. I’m not going to stick to any technology in general – the point is to understand the topic from different perspectives. The materials I’m refering to in general should not be considered as entry-level –  they require fair amount of knowledge, but nevertheless, list goes sorted starting from “easier” things.


.NET String Dictionary vs string switch performance

I had a simple task to map a collection of objects with string property. Map function should replace one string property to another from set of 5-6 strings. Existing solution used Dictionary initialized with those hard-coded values. Once upon a time I tried to compare Dictionary with int keys to int switch and int switch was FAR better. It was chess engine so performance mattered.

Now it’s a web request with thousands of rows of reply, serialized to json, so performance matters again. I wrote simple program, which generated 10 million instances of my simple class with several properties and mapped this list with both methods. Before that I ensured that both methods were JIT’ed. You can find source code at Github.

Details below..


YaCE contester engine

This is not-a-success story about one of my projects, YaCE (Yet another Contester Engine). It’s a system, written in Ruby and Bash which can check ACM problems solution validity. It can be scaled on a number of nodes, accessible via network (VMs or real machines).

The main reason to create it was to rewrite existing system which we used to train for ACM contests. “ACM Contester” was not scalable enough and it didn’t have precise enough measurements of used memory and cpu time, which is crucial for testing our solutions.

I wanted to make it scalable and predictable. I wanted to write it in Ruby on Linux and for Linux.
YaCE has been started 2 years ago and last commit was made 11 months ago.


Developer competencies list with useful links (preparing to the interview)

Starting short training before competency test at my current work. You can find list of things you have to know. And comparison to those from Amazon. Below you can find advices what or where to read to be ready to interview or smth like this

Needed materials and topics can be found here:

Data Structures – array, linked list, stack, queue, dictionary, hash table, tree, binary search tree, hashtable, heap, AVL/RB tree, B-tree, skip list, segment tree

Useful links: Arrays article, Article about structures, used to implement dictionaries, Skip list implementation

Algorithms – sorting, searching, data structure traversal algorithms, algorithm complexity, O() notation, space/time complexity, greedy and dynamics algorithms, tree, graph algorithms, N-logN sorting

Useful links: Several O(N*logN) sorting implementations, quite good Wiki article about Binary search

Graph algorithms – dfs, bfs, loops (usual and Euler’s), Floyd-Warshall, Kruskal’s algorithm

Concurency – shared state and synchronization problems, sync primitives, basic parallel algorithms, sync primitives efficiency, data and task parallelism patterns, deadlocks, race conditions, thread scheduling details, GUI threading models