HN Books @HNBooksMonth

"Peopleware" http://www.amazon.com/Peopleware-Productive-Projects-Second-... , a lot of insights and ideas how to build great teams. Great to read for developers, team leads and managers.

"The art of multiprocessor programming", excellent book on parallel programming theory with code explanations: http://www.amazon.com/gp/product/0123705916?ie=UTF8&tag=nirs...

⬐ scrabble

Got about 20 pages left in the Peopleware third edition. Excellent book even if you aren't a manager.

⬐ dkersten

I read (not all of it, maybe 50% of it) "The art of multiprocessor programming" a couple of years ago and I agree, its an excellent book. I have a handful of books on the topic and I find this to be my favourite.

⬐ playing_colours

If you have the list of books to read on the topic I would be happy if you share it. My next book on the topic will be http://mitpress.mit.edu/books/programming-distributed-comput...

⬐ dkersten

The only ones I can think of off-hand are these two. The second one isn't really about parallel/concurrent/distributed programming per se, but rather about using Intels Threading Building Blocks - good book if that's what you want to do, but not very useful if not. The first book is interesting and covers a lot of ground (covering general techniques and algorithms as well as specific implementations with OpenMP, MPI and Java's facilities), but I liked Art of multiprocessor programming more, probably because it has a more beginner friendly teach everything from the very beginning approach.

http://www.amazon.com/Patterns-Parallel-Programming-Timothy-...

http://www.amazon.com/Intel-Threading-Building-Blocks-Parall...

There are rather basic (producer/consume queues) and as some have pointed out, are buggy. I'd highly suggest looking at Boost's threading library (for an example of an object oriented approach to threading, taking advantage of RAII -- much of it is now standard in C++11), Intel's Thread Building Blocks, Java's built in Concurrency Utilities (java.util.concurrent package), Doug Lea's Fork Join Framework. The a great book on the subject is Maurice Herlihy's The Art of Multiprocessor Programming:

http://www.amazon.com/The-Multiprocessor-Programming-Maurice...

The book is in Java, but C++11 has the required primitives (cross platform compare and set for integral types, a defined memory model) so you could follow allong in C++11.

There are much better ways to implement a concurrent queue than the ones shown. Using locks for every single queue/dequeue is a very good way to completely kill performance. A much better alternative is to use hand-over-hand locking, or use CAS for a lock-free implementation.

TAOMP ( http://www.amazon.com/The-Multiprocessor-Programming-Maurice... ) goes over this in great detail and is overall an excellent book.

⬐ atechie

Following is a great resource for Concurrent programming without locks and software transaction memory : http://www.cl.cam.ac.uk/research/srg/netos/lock-free/

Well, you could also perform CAS using AtomicReference -- the examples in Maurice Herlihy's The Art of Multiprocessor Programming [1] and Brian Goetz' Java Concurrency In Practice [2] do that. So you don't really need to use sun.misc.Unsafe in your own code (of course, you need CAS to implement AtomicReference in the first place).

You're also completely correct about placement new: I am working on a cleaned up version of this class, this was essentially a first pass to get myself more familiar with concurrency in c++0x. What complicates things a bit is that allocators are (much like all else in STL) meant to be used as class template arguments, which makes main separate compilation impossible -- hence the need of an adapter from an STL-style allocator to a pure virtual class. Separate compilation is why I also made a void* version of this initially.

I have a much cleaned up version in the work that will handle more than void . There's an implementation I call it ConcurrentLinkedQueueImpl that handles just void , that is compiled separately -- and there is generic version ConcurrentLinkedQueue that is specialized for void * (ends up just proxying the calls to ConcurrentLinkedQueueImpl), with the generic version (in turn) using ConcurrentLinkedQueue<void *> and placement new to hold any type.

Once again, the version posted there was a rough pass to get myself familiar with 0x concurrency constructs and hazard pointers -- the code is fairly messy.

[1] http://www.amazon.com/Art-Multiprocessor-Programming-Maurice... [2] Everyone should read this book cover to cover -- http://jcip.net/

I'm not quite sure what you mean, but synchronization without atomic operations is possible.

An example of mutual exclusion, without any atomic operations, taken from the book "The art of multiprocessor programming"[1] is (paraphrased) as follows:

Two threads, A and B, want to access some memory. Each thread has a flag.

When thread A wants to access the shared memory:

    Set flag A
    Wait for flag B to become unset
    Access memory
    Unset flag A

When thread B wants to access the shared memory:

    Set flag B
    While flag A is set {
        Unset flag B
        Wait for flag A to become unset
        Set flag B
    }
    Access memory
    Unset flag B

Obviously this isn't a general purpose solution, but rather an easy to understand example demonstrating that atomic operations are not required.

[1] http://www.amazon.com/Art-Multiprocessor-Programming-Maurice...

⬐ tedunangst

That only works with coherent in order memory operations. Once you add the appropriate memory barriers, it looks a lot more "atomic".

⬐ dkersten

I chose that example because its easy to understand, obviously in modern processors with out of order execution and whatnot, you would need something a lot more elaborate.

Once you add the appropriate memory barriers, it looks a lot more "atomic"

Well, they force in order memory access. That doesn't look terribly "atomic" to me, but I understand your point.

Maybe I'm naive, but I don't think the problem is what everyone always says - that parallel programming is super hard and most programmers cant effectively program for multicore systems. Instead I think the problem is one of education and training. How many programmers actually get decent training and education in multicore programming? I don't think its very many. Of all the programmers complaining how hard it is to write effective multicore programs, how many have actually read books and research papers on the subject? Again, I'd wager not many.

For example, In my four year computer science degree, a lot of time was spent on high level languages like Java, C, C++, Haskell, even prolog. A good bit of time was spent on low level details (two computer architecture modules, an "advanced" computer architecture module, an assembly programming module). Some time was spent on computability, complexity and parsing. Of course, we had a number of math modules too, including probability, statistics and linear algebra. A lot of time was spent on object oriented programming, data structures and algorithms. A little bit of time was spent on other topics like network programming, databases, operating systems (we did cover deadlock and some concurrent programming stuff in great detail here) and AI. The rest was split between single (optional!) modules on niche areas: digital signal processing, cryptography, compression, 3d graphics and so on.. including concurrent programming.

We spent so much time learning how to program sequentially, why would anyone even suggest that we should be able to program for multicore systems? Were we given years of training in parallel programming languages, algorithms, data structures and libraries? Nope. Instead the time was spent on sequential programming. Of course its going to be hard to program for multicore!

Heres a car analogy:

Its like spending years learning to drive tractors, expecting that you can then drive formula one cars.

Some problems simply don't make much sense to try and solve with parallel programming. Some problems do, but we're not properly educated to spot these effectively, to know what data structures are appropriate and what algorithms we should use, nevermind things like testing and debugging parallel software.

As an aside, if performance is what we're trying to achieve with multicore programming, then we need to be taught about efficient cache usage too! Misuse of the processor cache kills multicore performance and popular software development principles, like object-oriented programming actually works against the processor cache! Ugh.

There is plenty to help us effectively program for multicore. A short (and very incomplete) list:

    - monitor based concurrency (mutexes, semaphores, condition variables + threads); usually not the best option
    - Software Transactional Memory; replace manual synchronisation with transactional access to shared memory
    - Message passing; multiuple threads/tasks communicating through immutable messages (being immutable means that synchronization concerns are minimized)
    - Dataflow languages/libraries where data "flows" through computational nodes and many streams of data can flow through in parallel (each node can be processing at the same time)
    - Tools and libraries such as OpenMP, OpenCL and Intel Threading Building Blocks
    - Languages with a focus on parallel programming like Erlang and Clojure (I especially like Clojures view on *time*)
    - Languages with built-in immutable data structures help make synchronisation less painful. Same goes for atomic data structures.
    - Entity Systems[1] are actually surprisingly suited for multicore programming, IMHO

I would suggest everybody to pick up the book The Art of Multiprocessor Programming[2] and get an introduction to the basic concepts. After that it depends on what you want to do, but if you're a C++ programmer, I would suggest the intel threading building blocks book[3].

[1] http://t-machine.org/index.php/2007/09/03/entity-systems-are...

[2] http://www.amazon.com/Art-Multiprocessor-Programming-Maurice...

[3] http://www.amazon.com/Intel-Threading-Building-Blocks-Parall...

⬐ gtani

The Speak Multicore table is some PL archeology:

ABCPL, actorScript, ada, afnix, alef, alice, APL

Axum, C*, chapel, cilk, clojure, curry DAPPLE,

E, eiffel, emerald, erlang, fork, glenda

Go, id, janus, joCaml, Join Java, joule, joyce, labView

[[etc]]

⬐ dkersten

Quote from page 18 of the O'Reilly book on Intel Threading Building Blocks:

One of the truths in programming is this: the best serial algorithm is seldom the best parallel algorithm, and the best parallel algorithm is seldom the best serial algorithm.

Following on from what I said in my previous post, since we are being educated in serial algorithms, we cannot realistically expect to write decent parallel algorithms in a way similar to how we write serial algorithms.

If you are into wait-free and lock-free data structures, you owe it to yourself to get Herlihy and Shavit's "Art of Multiprocessor Programming."

http://www.amazon.com/Art-Multiprocessor-Programming-Maurice...

Not only does it provide a well-debugged, well-written collection of wait-free data structures; it teaches you to think about concurrency in a structured way. The mutual exclusion chapter doesn't teach you which pthread routines to use, but instead tells you how to implement mutual exclusion, and the trade-offs inherent in, e.g., spin locks vs. queueing locks. A significant bonus is Maurice Herlihy's distinctive prose voice: correct, concise, and funny in that order. It is the best computer book I've read recently, and the one I recommend to all colleagues who are trying to take their concurrency chops up to the next level.

(I took a course from Herlihy in '99, but am otherwise unaffiliated.)

⬐ nkurz

I just got this book as an interlibrary loan based on this recommendation, and so far I'm not finding it that helpful. This isn't because it's a bad book: to the contrary, just as you say it's very readable. But it's also very strongly a book about concurrency in Java.

My first thought was that this wouldn't matter --- an algorithm is an algorithm. But for the purposes I'm interested in (multiprocessor malloc replacements, fast userspace read-write locks, generally low-level Linux on x86) I'm finding the high-level theoretical view to be impractical.

It's not that that using Java for the examples is a problem, but that apart from the appendices there is very little discussion of what I find are the real performance issues: cache misses, memory bandwidth, and processor pipelines. All of which could be considered hardware specific implementation details, but all of which make the difference between a 'provably correct solution' and one that actually performs well in the real world.

Anyway, a fine book, but perhaps better titled "The Theory of Concurrency in Java". I'll keep reading it, and I'm sure I'll learn from it, but I'll also keep looking for something more nitty and gritty.

Since then, Real world haskell (freely available), Hutton's book, maybe another came out

http://book.realworldhaskell.org/

http://www.amazon.com/Programming-in-Haskell-ebook/dp/B001FS...

also: Herlihy , Shavit , Multiprocessor Programming

http://www.amazon.com/Art-Multiprocessor-Programming-Maurice...

OK, let me try to be more helpful. Here's good backgrounders

http://www.tbray.org/ongoing/What/Technology/Concurrency/

http://www.sauria.com/blog/2009/10/05/the-cambrian-period-of...

http://groups.google.com/group/clojure/browse_thread/thread/...

http://blogs.azulsystems.com/cliff/2008/09/jvm-language-su.h...

http://wiki.jvmlangsummit.com/pdf/36_Click_fastbcs.pdf

---------------------

also recommended: Herlihy/Shavit book, blogs by Sutter and Duffy,

http://www.amazon.com/Art-Multiprocessor-Programming-Maurice...

http://herbsutter.com/

http://www.bluebytesoftware.com/blog/Default.aspx