3 ms·

I looked through the slides but not the video and the slides ignore the hard problem: how do you schedule these requests? How do you know how many parallel requ

I looked through the slides but not the video and the slides ignore the hard problem: how do you schedule these requests? How do you know how many parallel requests you can issue without hammering the database or service? How do you batch queries so that you get acceptable latency and a query size that will not choke the database? The last question is probably easy for most use cases where you have independent requests coming in (typical web application) - in the context of a single request you can usually get away with batching as much as is possible. But the scheduling problem is very similar to the promises of "free parallelism because Church-Rosser" - actually taking advantage is an open problem. Even when you know how much time each job takes in advance, multiprocessor scheduling is NP-hard. Anyway, if someone watched the video and the question is addressed there, please let me know so I can watch it.

eru 9y ago
I think the idea is that with the Haxl approach the scheduling can be dealt with independently from your business logic. By the way, I don't see how Church-Rosser would give you any free parallelism---even in theory. You'd still have to heed Guy Steele's advice (see https://vimeo.com/6624203 https://vimeo.com/6624203).
- sedachv 9y ago
  > By the way, I don't see how Church-Rosser would give you any free parallelism---even in theory. Church-Rosser theorem means that all possible reduction sequences lead to the same normal form, so you can β reduce the subterms in parallel. If you look at Paul Hudak's and SPJ's publications from the late 1980s and early 1990s many of them are actually about trying to exploit this implicit parallelism: http://sunsite.informatik.rwth-aachen.de/dblp/db/indices/a-tree/j/Jones:Simon_L=_Peyton.html http://sunsite.informatik.rwth-aachen.de/dblp/db/indices/a-t... http://dblp.uni-trier.de/pers/hd/h/Hudak:Paul http://dblp.uni-trier.de/pers/hd/h/Hudak:Paul https://pdfs.semanticscholar.org/8912/5be7f9c222793c18b99d0644c16ff19d9f06.pdf https://pdfs.semanticscholar.org/8912/5be7f9c222793c18b99d06... This turns out to be a hard problem and fell out of fashion as a research topic. The big problem is managing overhead. There has been some recent work to try to incorporate automatic profiling feedback to adjust the parallelism granularity: http://dominic-mulligan.co.uk/wp-content/uploads/2015/05/S-REPLS_Calderon.pdf http://dominic-mulligan.co.uk/wp-content/uploads/2015/05/S-R...
  - eru 9y ago
    Yes, but you still need to have those parallel subterms in the first place! If you eg still use a linked list data structure as an input, you are never gonna be faster than O(n) no matter how clever your implicit parallelism is.
    - sedachv 9y ago
      > If you eg still use a linked list data structure as an input, you are never gonna be faster than O(n) no matter how clever your implicit parallelism is. I think you took away completely the wrong point from Steele's talk. The bottleneck is not in the data structures, it is in the control flow, which is just a trivial way of restating Amdahl's law. In fact Steele co-wrote an excellent expository paper with Daniel Hillis, while they were at Thinking Machines, showing how to do parallel processing on linked lists: http://cva.stanford.edu/classes/cs99s/papers/hillis-steele-data-parallel-algorithms.pdf http://cva.stanford.edu/classes/cs99s/papers/hillis-steele-d...
      - eru 9y ago
        I was in the audience and asked questions, and chatted with him afterwards.. Data flow dictates control flow (to a certain extent). The paper you linked to is very interesting: but even there they have to augment their 'linked list' with more links. And they assume one processor per list element and don't count the set-up time of having each processor find its list element. (There's some more complication to it. But I am glad between 1986 when the paper was written and 2009 when he gave the talk, he figured out how to explain some of these issues more simply.)

eru 9y ago

I think the idea is that with the Haxl approach the scheduling can be dealt with independently from your business logic. By the way, I don't see how Church-Rosser would give you any free parallelism---even in theory. You'd still have to heed Guy Steele's advice (see https://vimeo.com/6624203 https://vimeo.com/6624203).

sedachv 9y ago
> By the way, I don't see how Church-Rosser would give you any free parallelism---even in theory. Church-Rosser theorem means that all possible reduction sequences lead to the same normal form, so you can β reduce the subterms in parallel. If you look at Paul Hudak's and SPJ's publications from the late 1980s and early 1990s many of them are actually about trying to exploit this implicit parallelism: http://sunsite.informatik.rwth-aachen.de/dblp/db/indices/a-tree/j/Jones:Simon_L=_Peyton.html http://sunsite.informatik.rwth-aachen.de/dblp/db/indices/a-t... http://dblp.uni-trier.de/pers/hd/h/Hudak:Paul http://dblp.uni-trier.de/pers/hd/h/Hudak:Paul https://pdfs.semanticscholar.org/8912/5be7f9c222793c18b99d0644c16ff19d9f06.pdf https://pdfs.semanticscholar.org/8912/5be7f9c222793c18b99d06... This turns out to be a hard problem and fell out of fashion as a research topic. The big problem is managing overhead. There has been some recent work to try to incorporate automatic profiling feedback to adjust the parallelism granularity: http://dominic-mulligan.co.uk/wp-content/uploads/2015/05/S-REPLS_Calderon.pdf http://dominic-mulligan.co.uk/wp-content/uploads/2015/05/S-R...
- eru 9y ago
  Yes, but you still need to have those parallel subterms in the first place! If you eg still use a linked list data structure as an input, you are never gonna be faster than O(n) no matter how clever your implicit parallelism is.
  - sedachv 9y ago
    > If you eg still use a linked list data structure as an input, you are never gonna be faster than O(n) no matter how clever your implicit parallelism is. I think you took away completely the wrong point from Steele's talk. The bottleneck is not in the data structures, it is in the control flow, which is just a trivial way of restating Amdahl's law. In fact Steele co-wrote an excellent expository paper with Daniel Hillis, while they were at Thinking Machines, showing how to do parallel processing on linked lists: http://cva.stanford.edu/classes/cs99s/papers/hillis-steele-data-parallel-algorithms.pdf http://cva.stanford.edu/classes/cs99s/papers/hillis-steele-d...
    - eru 9y ago
      I was in the audience and asked questions, and chatted with him afterwards.. Data flow dictates control flow (to a certain extent). The paper you linked to is very interesting: but even there they have to augment their 'linked list' with more links. And they assume one processor per list element and don't count the set-up time of having each processor find its list element. (There's some more complication to it. But I am glad between 1986 when the paper was written and 2009 when he gave the talk, he figured out how to explain some of these issues more simply.)