stan-dev / stan-dev/stanc3

Peephole optimization for commonly paired functions

Open
#1,677 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

feature help wanted optimization performance
Dominant language
OCaml
Stars
160
Forks
59
Avg merge
21h 45m
Merged PRs (30d)
26

Description

See #1674 for an initial attempt. Thanks to @sims1253 for the suggestion

There are several functions that historically duplicated work and now can be done in a single call returning a tuple. These were primarily added in https://github.com/stan-dev/math/pull/2931:

  • qr: replaces calls to qr_Q/qr_R
  • qr_thin: replaces calls to qr_thin_Q/qr_thin_R
  • eigendecompose_sym: replaces calls to eigenvalues_sym/eigenvectors_sym
  • eigendecompose: replaces calls to eigenvalues/eigenvectors
  • complex_schur_decompose: replaces calls to complex_schur_decompose_t/complex_schur_decompose_u
  • svd: replaces calls to svd_U/svd_V
  • csr_extract : replaces calls to csr_extract_u/csr_extract_v/csr_extract_w

The proposal is to add a small optimization which detects cases where these are called one after the other and rewrite them to use the combined version.

It may also be useful to separately flag a warning for models where the older functions are both called on the same thing.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reading issue #1674 and the stanc3 optimization code that handles function-call patterns. Trace how paired calls to qr, qr_thin, eigendecompose, complex_schur_decompose, svd, or csr_extract are represented and transformed. Done means qualifying consecutive calls use the combined tuple-returning function, with coverage for the rewrite and possibly a separate warning for older paired calls.

Written by the indexing model from the issue text.

Assessment

Tech stack
ocaml
Domain
compilers, performance
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.