Skip to content

Array to prod

Aaron Councilman requested to merge array-to-prod into main

Array to prod optimization for constant sized arrays.

  • To identify arrays that can be converted, we start from constant sized constant arrays and identify all users (including users of users) and all the arrays used by those users and ensure that all of those nodes can be converted.
    • Constructing these sets uses a custom union-find structure since I didn't find a good crate for it
  • Converts multi-dimensional arrays into nested products as it makes the transformations easier, SROA can then eliminate these products entirely.
  • The optimization can handle partial selections of a function and also has an optional argument for setting a maximum size of array (i.e. total number of elements) that it will convert.
  • To allow optional arguments/variable number of arguments in the scheduler, some small tweaks to the scheduler.

We should make sure to test this once forkify is fixed to handle the sorting loop, but if we manually unroll that loop this optimization is able to convert the median entirely into a tower of selects.

Merge request reports