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

141–150 of 199 posts

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

#141

Post by crabbone »

vore wrote: post #110
crabbone wrote: post #106

Earlier quoted context omitted.

I don't know who invented this nonsense distinction. First time I was introduced to this idea of "concurrent programming" being a separate thing when Go was released. So, I associate this nonsense with Go, but it could have happened earlier, I simply never heard about it before then. Anyways. The way I see it used today, it's applied to language runtimes incapable or severely crippled when it comes to parallel / conc…

How is this nonsense or anything to do with "language runtimes with disabilities"? An OS running on a single core processor cannot be parallel but it may be concurrent: it can never physically do two things at the same time, but it might be able to logically interleave different tasks. Parallelism is a physical thing, concurrency is a logical thing.

You have just repeated the nonsense I was talking about.

The claim you repeat is meaningless. A program is either parallel / concurrent or not. The situation you describe (when there's a single processor core) isn't parallel or concurrent. In some sense, it emulates concurrent / parallel execution because it imitates the unpredictable ordering of code execution, which sure has its uses... but the whole point of dealing with this unpredictable ordering is that we actually want parallelism / concurrency. The emulation on its own is worthless.

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

#142

Post by crabbone »

sublinear wrote: post #137
crabbone wrote: post #106

Earlier quoted context omitted.

I don't know who invented this nonsense distinction. First time I was introduced to this idea of "concurrent programming" being a separate thing when Go was released. So, I associate this nonsense with Go, but it could have happened earlier, I simply never heard about it before then. Anyways. The way I see it used today, it's applied to language runtimes incapable or severely crippled when it comes to parallel / conc…

> In such environments programmers are offered a mechanism that has many downsides of parallel / concurrent programming (eg. unpredictable order of execution) without the benefits of parallel / concurrent programming (ie. nothing actually happens at the same time, or only sleep is possible at the same time etc.) From the developer's perspective it's a massive upside to not have to manage low-level details and just de…

What does this have to do with low or whatever other level?

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

#143

Post by imtringued »

The biggest problem with parallel programming are the fixed communications costs. Threads are expensive to launch and stop. This then leads to thread pooling which is not a bad idea but then you have to make sure that nothing blocks the thread pool. Java is going to fix this problem with virtual threads.

Even if threads are cheap, you still have to decide when to parallelize something. If the section is short enough, splitting up the work will make your program slower because you have to wait for the new thread to be scheduled and then for the launching thread to be scheduled.

These are just the problems to get you started. They are not big barriers but they are big enough to make it not be the default.

The next problem is dynamic runtime behaviour. A parallel program can exhibit far more weird behaviours due to the nature of interleaved execution. This means that you will want a strong ownership model for your data and so far only Rust does it competently. Instanced locks are difficult to get right. Static locks are almost trivial but only if you can guarantee that your critical section never calls code that invokes the same lock. Recursive locks are a bad idea but not using them means you need to have two sets of methods. One is the public synchronized method that library users call and the other is the private unsynchronized method that actually does most of the work. It's very ugly to work with locks.

The other problem is that a lot of problems are genuinely difficult to parallelize. It is better to parallelize hierarchically where each hierarchy is still single threaded. This way you can maintain the illusion of mostly single threaded code. The alternative often requires a bespoke architecture. There are hardly any generalized solutions. You need to be an expert at parallel programming.

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

#144

Post by crabbone »

phkahler wrote: post #114
crabbone wrote: post #106

Earlier quoted context omitted.

I don't know who invented this nonsense distinction. First time I was introduced to this idea of "concurrent programming" being a separate thing when Go was released. So, I associate this nonsense with Go, but it could have happened earlier, I simply never heard about it before then. Anyways. The way I see it used today, it's applied to language runtimes incapable or severely crippled when it comes to parallel / conc…

>> don't know who invented this nonsense distinction ... It not nonsense. In C or C++ lots of code can be made parallel using OpenMP and inserting some #pragma statements above for loops. This does not work for things like running a UI in one thread and some other work in another thread, perhaps displaying results as they are found. These are quite different types of parallelism.

What does this have to do with anything?

I mean, great... you discovered a somewhat useful library: OpenMP... so what? How does this factoid affect the validity of the definition of code parallelism?

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

#145

Post by vore »

crabbone wrote: post #141
vore wrote: post #110

Earlier quoted context omitted.

How is this nonsense or anything to do with "language runtimes with disabilities"? An OS running on a single core processor cannot be parallel but it may be concurrent: it can never physically do two things at the same time, but it might be able to logically interleave different tasks. Parallelism is a physical thing, concurrency is a logical thing.

You have just repeated the nonsense I was talking about. The claim you repeat is meaningless. A program is either parallel / concurrent or not. The situation you describe (when there's a single processor core) isn't parallel or concurrent. In some sense, it emulates concurrent / parallel execution because it imitates the unpredictable ordering of code execution, which sure has its uses... but the whole point of deali…

No it's not? How do you characterize running two programs on a single core without calling it concurrent but not parallel? There is a clear distinction between logical multitasking and physical multitasking that I think is useful to taxonomize.

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

#146

Post by vore »

crabbone wrote: post #140
vore wrote: post #121

Earlier quoted context omitted.

Uhh, I think it is pretty commonly accepted that a statically-typed language has typechecking facilities before runtime and a dynamically-typed language doesn't. Maybe there is a spectrum and things somewhere in the middle gradual typing but the general idea is quite clear.

1. That's not part of the language, it's part of an implementation. I.e. it means that the same language can be both statically-typed and not (according to your "definition"). Which is literally nonsense (in the sense true = false). 2. If something is commonly accepted doesn't make it anymore true. In the context of programming, a lot of commonly accepted beliefs are nonsense, this one isn't an exception. It's not ab…

What are you talking about? Languages are pretty explicitly designed to be statically- or dynamically-typed: e.g. take Python which relies a lot on having a dynamic typing discipline. Yes, you have Mypy and pytype, but those are pretty much different dialects.

Also, what reputable sources are you even talking about? That is also such an unwarranted personal attack you've attached as well.

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

#147

Post by crabbone »

titzer wrote: post #136
Nathanba wrote: post #127

Earlier quoted context omitted.

how are the problems different? In all cases you want the maximum performance. The only decision here is how you schedule your tasks. Ideally entirely in parallel and you only schedule them to wait if you can't find a way to make them 100% parallel

Parallelism and concurrency are different models. It is not a needless distinction. With just concurrency, you can have a system, e.g. an event processing system, where each event happens, is processed to completion, and then the next event is processed. Events can be of different types and can have different handlers. Events can be arrive (or be delivered) in different orders. The context-switching points are known…

This is word salad. Sorry.

What are you modeling?

The way you use "concurrency" it's indistinguishable from code without any signs of parallelism. From your "definition", concurrency is just any code. Such definitions are called "trivial" if you don't want to offend the author, and "worthless" if you are honest.

Your attempt at defining "parallelism" is even worse... You start by calling it undefined, and then proceed throwing poorly connected verbs and nouns...

Let me make it simple:

Parallel or concurrent code is code that doesn't require time interval between instructions (this is in contrast to Von Neumann model, where it's necessary to have a non-zero time span between instructions).

Here. That's it. No "but hardware", no "there are no well-defined" etc.

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

#148

Post by imtringued »

taeric wrote: post #126
ascar wrote: post #79

Earlier quoted context omitted.

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…

Thinking of graphics, though, i would assume most of that is in the GPU side. Simulations do make sense, but I see games like Factorio still focused on single thread first. And then look for natural parallel segments. That is all to say that millions of events still feels like a lot. I am not shocked to know it can and does happen.

There are no good solutions for something like factorio. There are solutions that work but they aren't worth the trouble. My personal recommendation is that you split the world into independent chunks. A big interconnected factorio map is a nightmare scenario because there is hardly anywhere where you can neatly split things up. Just one conveyor belt and you lose. Aka parallelize disconnected subgraphs.

So the game would have to be programmed so that conveyor belts and train tracks can be placed at region boundaries and that there is a hidden buffer to teleport things between regions. Now you need an algorithm to divide your graph to both minimize the imbalance between the number of nodes in the subgraph but also to minimize the edges between subgraphs.

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

#149

Post by nwallin »

ascar wrote: post #74
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 progra…

> [re:matrix multiplication] However, an O(n^3) algorithm will always loose out to an O(n^2*log(n)) algorithm, when the input gets big enough.

You have to be very careful about what 'big enough' means. In practice, Strassen multiplication is not faster than the naive algorithm until you get to the point where you're multiplying matrices with hundreds of rows/columns. Additionally, naive matrix multiplication is well suited to GPUs, while Strassen multiplication on the GPU requires temporary buffers and multiple jobs and sequencing and whatnot.

As a general rule, matrix multiplication with complexity better than the naive algorithm should probably not be used. Do naive matrix multiplication on the CPU. If you need it to be faster, do naive matrix multiplication on the GPU. If you need it to be faster, the numerical stability of your problem has probably already come a gutser and will get worse if you switch to Strassen or any of the other asymptotically faster algorithms.

And the algorithms faster than Strassen? Forget about it. After Strassen multiplication was invented, about a dozen or so other algorithms came along, slowly reducing that O(n^2.8) to about O(n^2.37188) or so. (most recently in 2022; this is still an area of active research) The problem is that for any of these algorithms to be faster than Strassen, you need matrices that are larger than what you can keep in memory. There is no big enough input that will fit in the RAM of a modern computer. One estimate I've heard is that if you convert every atom in the observable universe into one bit of RAM, and you use that RAM to multiply two 10^38 by 10^38 matrices to get a third 10^38 by 10^38 matrix, you're still better off using the O(n^2.8) Strassen multiplication instead of the state of the art O(n^2.37188) algorithm. The constant slowdown in the other algorithms really are that bad.

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

#150

Post by stoniejohnson »

crabbone wrote: post #141
vore wrote: post #110

Earlier quoted context omitted.

How is this nonsense or anything to do with "language runtimes with disabilities"? An OS running on a single core processor cannot be parallel but it may be concurrent: it can never physically do two things at the same time, but it might be able to logically interleave different tasks. Parallelism is a physical thing, concurrency is a logical thing.

You have just repeated the nonsense I was talking about. The claim you repeat is meaningless. A program is either parallel / concurrent or not. The situation you describe (when there's a single processor core) isn't parallel or concurrent. In some sense, it emulates concurrent / parallel execution because it imitates the unpredictable ordering of code execution, which sure has its uses... but the whole point of deali…

bruh your OS scheduler wants a word with you
Post reply on HN