stan-dev / stan-dev/stanc3

Two more loop shapes for vectorize_loops

Open
#1,705 1 comment 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

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

Description

Thanks for #1683, it picks up a lot. I ran it over posteriordb and the models it rewrites got a lot faster in CmdStan (dogs 2.2x, radon_pooled 3.7x over --O1 alone). Two shapes it doesn't touch yet show up all over the corpus, so I hand-vectorized a few models to see what they'd get. Timings below are CmdStan gradient evaluations, stock stanc at --O1, medians of five runs on the same machine.

Reading something the loop body just wrote

for (n in 1:N) {
  mu[n] = alpha[county_idx[n]];
  target += normal_lpdf(log_radon[n] | mu[n], sigma_y);
}

After the first line mu is in the do-not-read set, so the second line stays a loop even though it only reads the element that was just written. Eleven of the thirteen radon models look like this (two of them write twice before reading), and sigma[n] = exp(sigma[n]) is the same thing in one line. The rewrite is just

mu = alpha[county_idx];
target += normal_lpdf(log_radon | mu, sigma_y);
model data loop vectorized speedup
radon_partially_pooled_centered radon_mn, N = 919 20.1 us 5.9 us 3.4x
radon_partially_pooled_centered radon_all, N = 12777 273 us 76 us 3.6x

I think the rule is that reading x[n] after writing x[n] earlier in the same body is fine, because the vectorized statements run in the same order. #1681 kept a list of written names for this before it was closed.

Scalar and int temporaries in the body

for (t in (K + 1):T) {
  real mu = alpha;
  for (k in 1:K) mu = mu + beta[k] * y[t - k];
  y[t] ~ normal(mu, sigma);
}

for (n in 1:Npts) {
  int irat = rat[n];
  y[n] ~ normal(alpha[irat] + beta[irat] * (x[n] - xbar), sigma_y);
}

Any declaration in the body stops the pass. A real temporary could become a vector over the loop range, and an int pulled out of a data array could be substituted into its uses as a gather. By hand:

vector[T - K] mu = rep_vector(alpha, T - K);
for (k in 1:K) mu = mu + beta[k] * to_vector(y[(K + 1 - k):(T - k)]);
y[(K + 1):T] ~ normal(mu, sigma);

y ~ normal(to_vector(alpha[rat]) + to_vector(beta[rat]) .* (to_vector(x) - xbar), sigma_y);
model data loop vectorized speedup
arK T = 200, K = 5 7.8 us 2.5 us 3.1x
rats_model Npts = 150 4.5 us 2.0 us 2.3x

arK, rats_model and the mixture models with an array[K] real temp are the corpus cases. #1681 called this inline_temps. The rats one also needs to_vector around the array gathers since arrays don't do elementwise arithmetic; the pass already widens arithmetic so maybe that part is small.

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 locating the vectorize_loops pass and review the prior work referenced in #1683 and #1681, especially the written-name list and inline_temps idea. Trace how the pass handles loop-body reads, declarations, gathers, and arithmetic widening. Done means both described loop shapes are transformed correctly, including scalar and int temporaries, with regression coverage for the shown patterns.

Written by the indexing model from the issue text.

Assessment

Tech stack
ocaml
Domain
compilers, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.