Crucially, this new scheme still allows for mutation of shared data structures as long as they were allocated before the thread's birth. You can enjoy parallel execution managed by the compiler, but maintain your ability to footcannon if you need to, and don't have anywhere near the bookkeeping overhead of STM.
> Disentanglement opens a new perspective on parallel memory management: rather than viewing memory as a global shared resource, we can instead organize memory as a distributed structure that mirrors (i.e., corresponds with) the structure of parallelism in the program.
Parallel, concurrent, and distributed systems are moving closer and closer to a relativistic model of the world. If we consider memory as roughly equivalent to space (N bits of memory take O(sqrt(N)) physical space http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html ) then this approach is essentially scheduling the work across spacetime (rather than just time); or, from a different perspective, the interactions defined within the program can be interpreted as a spatial layout of the problem/solution, which this compiler is utilising when deciding how to arrange the allocations.
See also https://en.wikipedia.org/wiki/Relativistic_programming
1) Relativity in the physical world arises if we consider some distributed model of computation
2) Physical laws, in particular speed of light, affecting algorithm complexity limits
- We assume there's a total order anyway. This lets us use Gallilean relativity, but is an incorrect model, which manifests as race conditions.
- We impose a total order, by introducing causality between every event (e.g. synchronisation, or data dependencies like counters, etc.). This lets us use Gallilean relativity and maintain correctness, but it is no longer concurrent/parallel.
- We only assume a partial order. This avoids race conditions, but allows races between independent results (which can therefore be calculated in parallel). This is inherently relativistic, since independent events can occur in a different order for different observers (in the case of this article, the observers are CPU cores).
See also https://en.wikipedia.org/wiki/Relativity_of_simultaneity
I guess, even from a practical perspective, how does this end up comparing with GC in something like the JVM with functional languages like scala?
Context around the link:
> In our POPL 2021 paper (which won a Distinguished Paper award), we proposed a specific heap scheduler and showed that it yields provable work and space bounds.
I haven't read it yet, but this is where their claims of being provably space-efficient seems to come from.
EDIT: A quick read later, section 6 is where they prove their claim. It's efficient when compared to equivalent sequential execution.
It looks like they're comparing against MLton, which is interesting since it performs whole-program optimisation. That makes their speedups even more impressive!
That is great, but runs into the next problem with concurrent programming - shared data - where, for performance, you absolutely have to share memory between heaps and pass ownership between heaps.
Erlang has specific escape hatches for that, I wonder how that would in a functional language.
It's helpful here to distinguish parallelism from concurrency. Disentanglement naturally emerges in data-race-free parallel programs, which have no concurrency. But certainly, you bring up a good point for programs that are highly concurrent in addition to being highly parallel. There's lots of work already on concurrent functional programming, for example CML (https://en.wikipedia.org/wiki/Concurrent_ML), and we think these ideas could be adapted to work with disentanglement really well.
Memory sharing in Pony uses a more advanced form of borrow checker which allows not just two "kinds" of shared memory (as with Rust's `mut` and not `mut`), but several: `val`, `ref`, `iso`, `trn`, `box`, `tag`. I think that for any solution to this problem that actually allows any shared memory to exist between threads, something in those lines must be required.
This idea would be hugely controversial in all places I've worked at, and is often the opposite direction of where many languages, runtimes etc are moving.
Maybe it's just innocent wording, but "research converging" on something that few in the industry believe in makes me think academia may be navel-gazing beyond healthy levels, even if the research itself is very interesting.
Did the industry believe in the value of linear or affine types? Sound static typing? Pure functional programming?
It's the typical arrogance of the practionier to rule out computer science research as irrelevant just because the application doesn't come in a nicely advertised package yet.
Of course, the scientific community can get lost on wrong paths or mix up fashion with established knowledge. I don't know enough about this particular topic to form an opinion here. But in general, when there has been a scientific consensus regarding programming languages it turned out to be relevant for the field.
To be fair, I don't either, depending on what's enough. I base this on what I've read, heard and experienced regarding GCs, query planning, and a lot of runtime "magic", that often end up being over generalized black boxes in many practical cases. In turn, this led to a Renaissance of simpler systems that are predictable, easy to reason about, and tweakable for the specific domain. Just my observations.
> But in general, when there has been a scientific consensus regarding programming languages it turned out to be relevant for the field.
I have a different view of academia than most people, so not expecting agreement here, but scientific consensus in a field like programming language theory should be rare, in fact I'd expect much more vigorous debate. This field is so young, incredibly complex and has common surface area with industry use cases and our mental models.
Quick question. What sort of parallelism are they discussing, Mimd or Simd?
Notably, can what they're discussing run on a GPU?
Difference here: https://en.wikipedia.org/wiki/Flynn%27s_taxonomy
What I find more interesting is things like Dyna-Soar as well as the parent project/paper. Futhark seems primarily very tensor-type computation specific (like APL+ extra features) and I'm interested in things that more naturally prone to code and data divergence and in trying to find ways to compensate for this.