Is parallel programming hard, and, if so, what can you do about it? • Hacker News Board

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

#101

Post by ascar » Wed, Jun 14, 2023, 3:29 PM UTC

vivegi wrote: post #94

ascar wrote: post #84

I see a lot of confusion between parallel programming [1] and concurrent programming [2] in the comments here. The former and what this book is about deals with the problem of parallelizaing a single sequential program. There usually is strong interaction or dependencies between elements and progress needs synchronization. E.g. timestep iterations in real-time simulations that need synchronization with data communica…

The book covers it in Appendix A.6 (p 424) in the v2023.06.11a PDF file. > A.6 What is the Difference Between “Concurrent” and “Parallel”? > From a classic computing perspective, “concurrent” and “parallel” are clearly synonyms. However, this has not stopped many people from drawing distinctions between the two, and it turns out that these distinctions can be understood from a couple of different perspectives. > The…

Well, funnily enough this does read in contrast to the definitions used in Wikipedia, which are the ones I am also familiar with (I also do teach a class called "Parallel Programming" to graduates).

I do think the differentation make sense from a perspective of problem classes, as also evident from the comments here. Running independent problems in parallel to better utilize hardware ressources is very different from running problems in parallel in timesteps that have strong dependencies in regards to progress of the overall computation. And that's not a problem of the scheduler, but a much more general concept.

It doesn't sound to me like the author has the whole web service parallelism/concurrency in mind that is very apparent in the comments here.

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

#102

Post by mrkeen » Wed, Jun 14, 2023, 3:31 PM UTC

cmrdporcupine wrote: post #40

Concurrent state management is hard, and I remain disappointed that software transactional memory -- and pushing a DB-style approach to non-DB workloads generally -- hasn't caught on. I think most "application" type programs would benefit from being able to manage state in terms of higher level transactional operations and let their runtime take care of serializing and avoiding deadlock and race conditions. Developer…

It's a good day when I get to use STM.

While the primary benefit is in thinking "these things should happen together or not at all" rather than thinking about locks, there's another feature I always forget about, which is retrying.

Retrying let's you 'nope' out of a transaction, and try again as soon as something changes without busy-waiting.

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

#103

Post by anchovy_ » Wed, Jun 14, 2023, 3:37 PM UTC

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…

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

Sure, this might be the case from a theoretical point of view (as per definition) but this completely disregards the hidden constants that come to light when actually implementing an algorithm. There's a reason why for instance a state-of-the-art matrix multiplication algorithm [0] can be completely useless in practice: The input data will never become large enough in order to amortize the introduced overhead.

[0] https://arxiv.org/abs/2210.10173

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

#104

Post by mrkeen » Wed, Jun 14, 2023, 3:40 PM UTC

twoodfin wrote: post #53

cmrdporcupine wrote: post #40

Concurrent state management is hard, and I remain disappointed that software transactional memory -- and pushing a DB-style approach to non-DB workloads generally -- hasn't caught on. I think most "application" type programs would benefit from being able to manage state in terms of higher level transactional operations and let their runtime take care of serializing and avoiding deadlock and race conditions. Developer…

You might be interested in Joe Duffy’s retrospective on Microsoft’s failed experiment to integrate STM into .NET: https://joeduffyblog.com/2010/01/03/a-brief-retrospective-on...

You really only need one paragraph from that:

> What do we do with atomic blocks that do not simply consist of pure memory reads and writes? (In other words, the majority of blocks of code written today.)

If you could just get programmers to stop mutating, you could get STM (which incidentally would give you back the ability to mutate)

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

#105

Post by Paradigma11 » Wed, Jun 14, 2023, 3:43 PM UTC

davidgrenier wrote: post #20

This looks brutal, for a lot of people John Reppy's book Concurrent Programming in ML (as in SML not Machine Learning) is going to be much more accessible. Pick the CSP-style library in the programming language of your choice. Go with goroutines and channels Clojure with core.async F# with Hopac It would be a very interesting project to roll your own in C# using Microsoft Robotics Studio's CCR (Coordination and Concu…

https://github.com/Hopac/Hopac is such an impressive piece of software. Too bad it never really took off like it deserved but with more popular competition like rx or just tasks/async (which is enough for most stuff) pretty unavoidable.

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

#106

Post by crabbone » Wed, Jun 14, 2023, 3:51 PM UTC

ascar wrote: post #84

I see a lot of confusion between parallel programming [1] and concurrent programming [2] in the comments here. The former and what this book is about deals with the problem of parallelizaing a single sequential program. There usually is strong interaction or dependencies between elements and progress needs synchronization. E.g. timestep iterations in real-time simulations that need synchronization with data communica…

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 / concurrent execution. Eg. Python, JavaScript etc. 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.)

I feel like this distinction, while a nonsense idea at its core, became so popular due to the popularity of language runtimes with disabilities and their users needing to validate their worth by adding features to their languages their runtimes are inherently incapable of implementing.

Similar situation happened with ML-style types. Python, for example, works very poorly with this add-on, but the desire to match features of other languages led Python developers to add those types anyways. Similarly, TypeScript and a bunch of similar languages, especially in Web.

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

#107

Post by tambourine_man » Wed, Jun 14, 2023, 3:53 PM UTC

tomrod wrote: post #48

tambourine_man wrote: post #38

Earlier quoted context omitted.

Stranded on a deserted island is bit radical, but I recommend going to a place with no internet connection for a week or so. I though I had a long reading problem. Turns out, I have an internet problem.

I didn't realize I also was a tambourine_man -- you literally just described my recent realization. I'm moving this week and won't have internet for a few days. I look forward to the relative break.

If you still have access to cellular internet, it's no good, in my experience. There needs to be no internet.

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

#108

Post by Retric » Wed, Jun 14, 2023, 3:54 PM UTC

bob1029 wrote: post #83

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 would add a qualifier of "serializable" to those events or commands. This is the crux of why fintech goes this path. Every order affects subsequent orders and you must deal with everything in the exact sequence received. The cases you noted are great examples of things that do justify going across the PCIe bus or to another datacenter.

That’s half of it, the other half is each of those events is extremely simple so the amount of computation is viable with a single thread.

If individual threads were dramatically slower the architecture would get unpleasant by necessity. Consider the abomination that is out of order execution on a modern CPU.

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

#109

Post by cmrdporcupine » Wed, Jun 14, 2023, 3:55 PM UTC

cmrdporcupine wrote: post #64

twoodfin wrote: post #53

Earlier quoted context omitted.

You might be interested in Joe Duffy’s retrospective on Microsoft’s failed experiment to integrate STM into .NET: https://joeduffyblog.com/2010/01/03/a-brief-retrospective-on...

Thanks, skimmed a bit of the first half but will get into it more after my work day.

So, going through this a bit more on lunch break; I think the root of some of the disillusionment faced here -- and probably the lack of success in STM at this level generally -- is that they tried to do too much.

I don't necessarily want the whole memory model of the runtime or VM to offer transactions necessarily. What I think is a good idea is to offer an overall framework -- within which higher level applications can be written -- that brings transactional semantics with it. Basically a set of collections and data transformation and communications and process coordination libraries that work in harmony with an underlying MVCC storage layer -- rather than baking a transactional atomic keyword down to the syntactical level of the language or the memory model of the VM/runtime.

Put another way: I wouldn't necessarily give users the STM facilities. I would use lower level STM facilities to construct a higher level toolkit, and only expose that. Basically an RDBMS in-process -- without the SQL language boundary -- to be frank.

Yes, users could escape it easily, and start doing inconsistent things. But that's on them, same as any other framework.

Provide the pattern and tools in a nice coherent box and don't try to take over the whole world.

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

#110

Post by vore » Wed, Jun 14, 2023, 3:56 PM UTC

crabbone wrote: post #106

ascar wrote: post #84

I see a lot of confusion between parallel programming [1] and concurrent programming [2] in the comments here. The former and what this book is about deals with the problem of parallelizaing a single sequential program. There usually is strong interaction or dependencies between elements and progress needs synchronization. E.g. timestep iterations in real-time simulations that need synchronization with data communica…

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.