Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Proposal: new streaming operators for scatter and reduce_by_index #737

Open
athas opened this issue Apr 2, 2019 · 1 comment
Open

Proposal: new streaming operators for scatter and reduce_by_index #737

athas opened this issue Apr 2, 2019 · 1 comment

Comments

@athas
Copy link
Member

athas commented Apr 2, 2019

Inspired by the need for efficient rasterisation (and some long-ago complaints by Cosmin), I would like to add the following operators for efficiently updating multiple elements of some targets for each element in an input array. The interface is heavily inspired by @melsman's expand utility function:

val stream_scatter 'a 'b [k] [n] :
     *[k]a
  -> (b -> i32)
  -> (b -> i32 -> (i32, a))
  -> [n]b
  -> *[k]a

The imperative semantics of an expression stream_scatter dest f g arr is given by the following pseudocode:

for i < n:
  m = f(arr[i])
  for j < m:
    (l, x) = g(arr[i], j)
    dest[l] = x

I expect that a similar core language representation with reasonable fusion rules will be easy to design, and that a stream_reduce_by_index will be a straightforward extension of the same idea.

@athas
Copy link
Member Author

athas commented Apr 6, 2021

The core IR implementation of this has been added in #1197, but I still don't see a nice way of safely exposing this to the source language.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant