google / google/xls

"reduce" builtin

Open
#331 1 comment 1 reaction 0 assignees View on GitHub
dslx enhancement
Dominant language
C++
Stars
1.9k
Forks
283
Avg merge
2d 10h
Merged PRs (30d)
135

Description

Similar to how we have 'map' builtin, it would be neat to have a 'reduce' builtin. We would pass in an array and a binary reduction operator, and 'reduce' would - you guessed it - reduce the array to a single value using an efficient tree struture internally, e.g.
reduce(s32[4]:[1, 1, 1, 1], my_add_func) --> s32:4

I believe the ir optimizer already transfroms associative ops into trees (e.g. if we add s32 types in a loop, this gets turned into a tree after unrolling). reduce would still be useful because 1) the user can define their own (possibly complex) reduction function that ir optimizer wouldn't catch and 2) the user can supply a reduction function that is not strictly associative if they want. For point 2, I'm thinking about reduction of a floating point array. A for-loop doing fp adds over the array might not get quite the same answer as fp reduction on the array, but most users probably just care about efficiency in this case and would opt for reduction.

In the long term, the ability to pass statically determined functions as arguments to other functions would probably be useful.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.