[HN Gopher] Provably Space-Efficient Parallel Functional Program...
       ___________________________________________________________________
        
       Provably Space-Efficient Parallel Functional Programming
        
       Author : matt_d
       Score  : 36 points
       Date   : 2022-01-13 19:29 UTC (3 hours ago)
        
 (HTM) web link (blog.sigplan.org)
 (TXT) w3m dump (blog.sigplan.org)
        
       | nynx wrote:
       | Jeez, scrolling on that website is messed up
        
         | jaquer_1 wrote:
         | in what way?
        
         | mgraczyk wrote:
         | For me scrolling works fine on mobile but is broken on Chrome
         | desktop (page snaps around in ways I don't expect). Just
         | disable javascript on blog.sigplan.org, the page works fine
         | without it.
        
       | [deleted]
        
       | aristus wrote:
       | This sounds a bit like software transactional memory (STM), in
       | the sense of giving threads the illusion of total freedom while
       | keeping them separate in reality. In STM data races are solved by
       | unwinding the _victim_ thread, essentially allowing threads to
       | ask for forgiveness instead of permission.
       | 
       | 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.
        
       | abeppu wrote:
       | This seems cool, but this blog article doesn't really delve into
       | what the "provably" part is -- I can see how the structure
       | they're describing of having processors handle GC for a
       | collection of heaps which are structurally linked might make GC
       | more efficient, but they don't really talk about what is proved
       | or how.
       | 
       | 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?
        
         | Jtsummers wrote:
         | Near the top there's a link to a paper which seems to go into
         | more technical detail: https://dl.acm.org/doi/10.1145/3434299
         | 
         | 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.
        
       ___________________________________________________________________
       (page generated 2022-01-13 23:00 UTC)