Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Is parallel programming hard, and, if so, what can you do about it?

mirrors.edge.kernel.org

Post reply on HN
Print view View original

71–80 of 199 posts

Re: Is parallel programming hard, and, if so, what can you do about it?

#71

Post by Retric »

bob1029 wrote: post #59
remontoire wrote: post #27

Watching geohot code a general matrix multiply algorithm from 0.9 GFLOPS and optimising it to 100 glops by only tinkering with cache locality, it makes me wonder how much effort should be put into single threaded performance before ever thinking about multi threading

Fintech has mostly determined that 1 thread can get the job done. See LMAX disruptor and related ideas. What problems exist that generate events or commands faster than 500 million per second? This is potentially the upper bar for 1 thread if you are clever enough. Latency is the real thing you want to get away from. Adding more than one CPU into the mix screws up the hottest possible path by ~2 orders of magnitude.…

> What problems exist that generate events or commands faster than 500 million per second?

AAA games, Google search, Weather simulation, etc? I mean it depends on what level of granularity you’re talking about, but many problems have a great deal going on under the hood and need to be multi threaded.

Re: Is parallel programming hard, and, if so, what can you do about it?

#72

Post by uguuo_o »

On scientific computing (computational fluid dynamics, computational electromagnetics, etc.), parallel programing is a must. Most of the algorithms are not embarrassingly parallel, and need a significant amount of communication between threads during runtime. We mostly use one of the many MPI [0] libraries available for desktop and high-performance computing machines. Using these programming paradigms is difficult but tend to result in fantastic scalability for all types of engineering problems.

[0] https://en.m.wikipedia.org/wiki/Message_Passing_Interface

Re: Is parallel programming hard, and, if so, what can you do about it?

#73

Post by ModernMech »

IshKebab wrote: post #65
remontoire wrote: post #27

Watching geohot code a general matrix multiply algorithm from 0.9 GFLOPS and optimising it to 100 glops by only tinkering with cache locality, it makes me wonder how much effort should be put into single threaded performance before ever thinking about multi threading

It's quite rare for problems to be dominated by hot loops in the same way that matrix multiplication is. Think about something like speeding up a compiler or a web server or a spreadsheet. There's no 50-line function that you can spend a few hours optimising and speed up the whole thing. That's part of the reason why Python programs (except maths heavy stuff like ML) tend to be so slow despite everyone saying "just w…

This advice dates back to when Python was primarily used by scientists to drive simulations. I remember hearing this advice in the early 2000s as a physics student using vpython to drive N-body simulations. They told us to do the physics in C, but everything else in Python due to the simulation math taking too long in raw Python. We couldn’t make the visualization run at a reasonable frame rate without those optimizations.

These days Python is being used for everything, even things without hot loops as you note. Yet the advice persists.

Re: Is parallel programming hard, and, if so, what can you do about it?

#74

Post by ascar »

remontoire wrote: post #27

Watching geohot code a general matrix multiply algorithm from 0.9 GFLOPS and optimising it to 100 glops by only tinkering with cache locality, it makes me wonder how much effort should be put into single threaded performance before ever thinking about multi threading

Cache locality is certainly an important aspect and especially when it comes to matrix multiplication even just changing the loop order (and thus access pattern) has a huge performance impact. However, an O(n^3) algorithm will always loose out to an O(n^2*log(n)) algorithm, when the input gets big enough. And the difference between these two might be as simple as sorting your input data first.

I teach parallel programming to graduates and the first exercise we give them is a sequential optimization for exactly that reason. Think about if your algorithm is efficient before thinking about all the challenges that come with parallelization.

Re: Is parallel programming hard, and, if so, what can you do about it?

#75

Post by taeric »

Retric wrote: post #71
bob1029 wrote: post #59

Earlier quoted context omitted.

Fintech has mostly determined that 1 thread can get the job done. See LMAX disruptor and related ideas. What problems exist that generate events or commands faster than 500 million per second? This is potentially the upper bar for 1 thread if you are clever enough. Latency is the real thing you want to get away from. Adding more than one CPU into the mix screws up the hottest possible path by ~2 orders of magnitude.…

> What problems exist that generate events or commands faster than 500 million per second? AAA games, Google search, Weather simulation, etc? I mean it depends on what level of granularity you’re talking about, but many problems have a great deal going on under the hood and need to be multi threaded.

I am curious on that. 500 million events per second sounds high. Even for games. That many calculations? Sure. I take "events" to mean user generated, though. And that sounds high.

Same for searches. Difficulty there is size of search space, not searches coming in. Right?

Re: Is parallel programming hard, and, if so, what can you do about it?

#76

Post by jbergens »

johnnyanmac wrote: post #63
klabb3 wrote: post #5

I’m way-above-average interested in concurrent programming but this 600+ page brick will probably remain on my reading list until I am stranded on a deserted island. Did anyone here read the whole thing? Can one make a reasonable summary or is this more of a lexicon of different techniques?

the PDF I opened was almost 1000 pages. And yes, from what I'm viewing in the Table of Contents, this is more of a comprehensive textbook covering almost every corner of the topic. I don't think it's meant to be read linearly (ha), nor is it expected to be binged in a few large sittings. Definitely meant for professionals or very motivated students more than a general hobbyist.

If one thousand of us read one page each we can be done in 15 minutes!

Then we just have to sync our knowledge.

Re: Is parallel programming hard, and, if so, what can you do about it?

#77

Post by Wildgoose »

stevage wrote: post #41
cj wrote: post #23

This reminds me when I was going through the YC accelerator in 2012. We were building a web-based email client, and PG didn’t like the idea. He pulled our team aside during one of the batch-wide Tues night dinners and suggested we pivot to building something that could take single threaded programs and quickly/easily make them multi-threaded. No one on our team knew anything about threading (none of us had even gradu…

That's such a random suggestion. To switch from building a user application to building a tool for devs...that is in no way related to what you were working on?

It sounds to me that pg had realised there wasn't a future in their web-based email, but thought they had good programming chops and would be able to produce something useful.

Re: Is parallel programming hard, and, if so, what can you do about it?

#78

Post by PheonixPharts »

cpach wrote: post #50
PheonixPharts wrote: post #30

Earlier quoted context omitted.

There are multiple replies like this one, but it's a bit shocking to see that on Hacker News people don't know the difference between concurrent programming and parallel programming. Concurrency means that you can have multiple tasks running in the same time period, Parallelism means you have multiple tasks running at the same time . The most obvious demonstration of this is that you can (and many languages do) have…

Correct me if I’m wrong, but isn’t concurrency enough for “most” use-cases? When does one really need true parallelism?

Concurrency is typically a great solution of IO bound tasks, which is why it figures so prominently in modern day webdev. It's also essential for any UIs in which case you don't want a single threaded process to be blocking user interaction just because it's running a task that takes time to complete.

Parallelism is used to solve CPU bound problems. Obvious examples are things like efficient matrix multiplication. However this is what make Parallel programming so hard. There's a lot of nuance working effectively with multiple cores/threads that makes even "embarrassingly parallel" problems sometimes fail to see benefits from naive parallel programming (for example if your parallel solution requires something as little as more frequent visits to l2 cache instead of l1 you can see performance degradation).

So parallelism and concurrency ultimately solve two very different domains of problems.

Re: Is parallel programming hard, and, if so, what can you do about it?

#79

Post by ascar »

taeric wrote: post #75
Retric wrote: post #71

Earlier quoted context omitted.

> What problems exist that generate events or commands faster than 500 million per second? AAA games, Google search, Weather simulation, etc? I mean it depends on what level of granularity you’re talking about, but many problems have a great deal going on under the hood and need to be multi threaded.

I am curious on that. 500 million events per second sounds high. Even for games. That many calculations? Sure. I take "events" to mean user generated, though. And that sounds high. Same for searches. Difficulty there is size of search space, not searches coming in. Right?

Google search isn't a good example. AAA games are a great example when you think about graphics. However, most of that is trivially parallelizable, thus "all you need to do" is assign vertices/pixels to different threads (in quotation marks as that's of course not trivial by itself, but a different kind of engineering problem).

However, once you get into simulations you have billions (or multiple orders of magnitude more) elements interacting with each other. When you simulate a wave every element depends on it's neighbors and the finer the granularity the more accurate your simulation (in theory at least).

Post reply on HN