Divide & Conquer Algorithms


(Jon Hull) #1

I would like to see Swift gain something similar to Clojure’s Reducers Library. Basically this is somewhat similar to our Sequence, but for tree-based structures instead of sequential ones. It allows a series of algorithms that operate using a divide and conquer strategy, and it is easy to massively parallelize.

One interesting property is that, because you don’t have to work sequentially, you are able to take a series of calls that do the equivalent of map/filter/flatMap, and compose the functions to make a single call on each piece of data (thus you don’t have build or recurse over intermediate sequences). Everything can be done in a single pass (and that pass can be done in parallel). It can be a big win in terms of efficiency.

Here is a blog post where someone benchmarked ‘fold’ from the reducers library (306ms) vs sequence-based reduce (1450ms):
https://adambard.com/blog/clojure-reducers-for-mortals/

Here is another post explaining how the idea might work in Python:
https://adambard.com/blog/Reducers-explained-through-Python/

Finally here is a video one of the developers of Clojure talking about why this pattern is so great (just after the 19 min mark):
https://www.infoq.com/presentations/Clojure-Design-Patterns

Adding something like this to Swift would be a great boon by providing generic parallelizable algorithms…

Thanks,
Jon


(Xiaodi Wu) #2

I would like that feature too.

Wouldn't this require Swift to have settled its concurrency model (which in
turn would require settling ownership and borrowing)?

···

On Tue, Apr 18, 2017 at 03:03 Jonathan Hull via swift-evolution < swift-evolution@swift.org> wrote:

I would like to see Swift gain something similar to Clojure’s Reducers
Library. Basically this is somewhat similar to our Sequence, but for
tree-based structures instead of sequential ones. It allows a series of
algorithms that operate using a divide and conquer strategy, and it is easy
to massively parallelize.

One interesting property is that, because you don’t have to work
sequentially, you are able to take a series of calls that do the equivalent
of map/filter/flatMap, and compose the functions to make a single call on
each piece of data (thus you don’t have build or recurse over intermediate
sequences). Everything can be done in a single pass (and that pass can be
done in parallel). It can be a big win in terms of efficiency.

Here is a blog post where someone benchmarked ‘fold’ from the reducers
library (306ms) vs sequence-based reduce (1450ms):
https://adambard.com/blog/clojure-reducers-for-mortals/

Here is another post explaining how the idea might work in Python:
https://adambard.com/blog/Reducers-explained-through-Python/

Finally here is a video one of the developers of Clojure talking about why
this pattern is so great (just after the 19 min mark):
https://www.infoq.com/presentations/Clojure-Design-Patterns

Adding something like this to Swift would be a great boon by providing
generic parallelizable algorithms…

Thanks,
Jon
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution