# Model with reduce\_sum takes too long

**URL:** <https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317>\
**Category:** Modeling\
**Created:** [August 8, 2020, 9:30am UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317 "2020-08-08T09:30:33Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![nerpa](https://avatars.discourse-cdn.com/v4/letter/n/85e7bf/32.png) [@nerpa](https://discourse.mc-stan.org/u/nerpa)\
**Post date:** [August 8, 2020, 9:30am UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/1 "2020-08-08T09:30:33Z")

</div>

Hello all. After implementing the within-chain parallelization with `reduce_sum` in cmdstanpy (with your help), I reached a dead end. My model is pretty complicated (attached) and I fit a lot of data, and even if I run it on many cores (now 25) it takes unreasonably long time to fit (it’s stuck in warmup for two days already). I tried different ways to parallelize and improve the process, but to no avail and I am out of options.  
Any suggestion how to improve it, to make it faster or anything will be highly appreciated.  
I am using cmdstanpy with cmdstan 2.24, centOS7, g++ 9.3.0.

Thank you!

[model\_parallel.txt](https://discourse.mc-stan.org/uploads/short-url/wFi3QBU57C1JCuo6cyb3KAzhhNc.txt) (18.7 KB)

---

<div class="post-metadata">

**Author:** ![nerpa](https://avatars.discourse-cdn.com/v4/letter/n/85e7bf/32.png) [@nerpa](https://discourse.mc-stan.org/u/nerpa)\
**Post date:** [August 8, 2020, 11:03am UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/2 "2020-08-08T11:03:39Z")

</div>

UPDATE - how big is my model? I have ~25k parameters and a bit more than 2 million observations.

---

<div class="post-metadata">

**Author:** ![wds15](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/wds15/32/908_2.png) [@wds15](https://discourse.mc-stan.org/u/wds15)\
**Post date:** [August 8, 2020, 3:30pm UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/3 "2020-08-08T15:30:26Z")

</div>

That’s huge! Did you measure your speed ups on smaller problem sizes first? Do you have a sense for how long this will take with a single core?

---

<div class="post-metadata">

**Author:** ![nerpa](https://avatars.discourse-cdn.com/v4/letter/n/85e7bf/32.png) [@nerpa](https://discourse.mc-stan.org/u/nerpa)\
**Post date:** [August 8, 2020, 3:42pm UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/4 "2020-08-08T15:42:56Z")

</div>

Yes it is :) I was building it during the last few months. I was running it on small `N` of 8-10 on a similar number of cores and it finished within 20 hours. `N=20` on 20 cores scaled up to 40 hours. And these are just small portions of my data. Single core processing of `N=15` took ~70 hours for the fastest chain (6 days for the last chain). So I think something can be done better with the parallelization, but I am really not sure what. Vectorizing the loops within `reduce_sum` didn’t give much speed gain.

---

<div class="post-metadata">

**Author:** ![wds15](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/wds15/32/908_2.png) [@wds15](https://discourse.mc-stan.org/u/wds15)\
**Post date:** [August 8, 2020, 4:13pm UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/5 "2020-08-08T16:13:54Z")

</div>

Usually vectorization is super important. If that does not help, then things are odd to me.

Anyway, you should try to

- slice parameters used per group; so if your model is a hierachical one, then slice all the parameters needed per group
- parameters in the shared arguments list is very expensive, since it’s copied for every call of the partial sum function (hence, slice the parameters as appropriate for your model).
- having data in the share arguments is cheap, because its handled by reference (no copy)

Other than that make sure the model runs efficient without reduce\_sum first, then go to reduce\_sum… I hope that is what happened in your case.

---

<div class="post-metadata">

**Author:** ![nerpa](https://avatars.discourse-cdn.com/v4/letter/n/85e7bf/32.png) [@nerpa](https://discourse.mc-stan.org/u/nerpa)\
**Post date:** [August 8, 2020, 4:25pm UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/6 "2020-08-08T16:25:14Z")

</div>

> [@wds15](#):
>
> slice parameters used per group; so if your model is a hierachical one, then slice all the parameters needed per group

You mean I should pass all the arrays I want to slice before I pass `grainsize` in the `partial_sum`?

---

<div class="post-metadata">

**Author:** ![nerpa](https://avatars.discourse-cdn.com/v4/letter/n/85e7bf/32.png) [@nerpa](https://discourse.mc-stan.org/u/nerpa)\
**Post date:** [August 8, 2020, 4:31pm UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/7 "2020-08-08T16:31:19Z")

</div>

> [@wds15](#):
>
> Other than that make sure the model runs efficient without reduce\_sum first, then go to reduce\_sum… I hope that is what happened in your case.

Based on the tests I run, the serial version would take more than a month for the full dataset. I am not sure what counts as efficient here, but this is what I;ve got after optimizing each part of my model separately. That’s where I started to implement multithreading.

---

<div class="post-metadata">

**Author:** ![nerpa](https://avatars.discourse-cdn.com/v4/letter/n/85e7bf/32.png) [@nerpa](https://discourse.mc-stan.org/u/nerpa)\
**Post date:** [August 8, 2020, 4:34pm UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/8 "2020-08-08T16:34:34Z")

</div>

> [@wds15](#):
>
> Usually vectorization is super important. If that does not help, then things are odd to me

I guess not always.

> [@Multithreading with pystan3](https://discourse.mc-stan.org/t/multithreading-with-pystan3/16946/14):
>
> Loops in Stan are C++ loops so sometimes vectorization doesn’t help.

---

<div class="post-metadata">

**Author:** ![wds15](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/wds15/32/908_2.png) [@wds15](https://discourse.mc-stan.org/u/wds15)\
**Post date:** [August 8, 2020, 5:54pm UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/9 "2020-08-08T17:54:53Z")

</div>

This version with a for loop:

```stan
for(i in 1:N) {
   y[i] ~ normal(mu[i], sigma);
}

```

is **massively** slower as opposed to

```stan
  y ~ normal(mu, sigma);

```

Now, building up a large `mu` vector using a for loop is ok, but definitely not calling out by element to the lpdfs.

---

<div class="post-metadata">

**Author:** ![nerpa](https://avatars.discourse-cdn.com/v4/letter/n/85e7bf/32.png) [@nerpa](https://discourse.mc-stan.org/u/nerpa)\
**Post date:** [August 8, 2020, 6:00pm UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/10 "2020-08-08T18:00:02Z")

</div>

I vectorized these loops where possible in the `partial_sum` function, but didn’t see significant speedup. This was odd to me, but I left it vectorized.

---

<div class="post-metadata">

**Author:** ![nerpa](https://avatars.discourse-cdn.com/v4/letter/n/85e7bf/32.png) [@nerpa](https://discourse.mc-stan.org/u/nerpa)\
**Post date:** [August 8, 2020, 6:16pm UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/11 "2020-08-08T18:16:41Z")

</div>

> [@wds15](#):
>
> slice parameters used per group; so if your model is a hierachical one, then slice all the parameters needed per group

you mean something like this?

```no-highlight
for (w in 1:W) {
    target += reduce_sum(partial_sum, parameters1[,w], parameters2[,w], grainsize, data1[,w], data2[,w])	
}

```

I wish this was possible, but it goes against `partial_sum` function signature.

---

<div class="post-metadata">

**Author:** ![wds15](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/wds15/32/908_2.png) [@wds15](https://discourse.mc-stan.org/u/wds15)\
**Post date:** [August 8, 2020, 6:22pm UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/12 "2020-08-08T18:22:54Z")

</div>

No. Never call many reduce sum like this if you can avoid it.

Can u annotate your model to see where the 25k params and all that data is? Somehow easier to read model would be nicer.

---

<div class="post-metadata">

**Author:** ![wds15](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/wds15/32/908_2.png) [@wds15](https://discourse.mc-stan.org/u/wds15)\
**Post date:** [August 8, 2020, 6:34pm UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/13 "2020-08-08T18:34:28Z")

</div>

Now I see that you do have a for loop calling multiple reduce sum…that’s not efficient. As a workaround you could try to nest reduce sum calls as a start, but it would be a lot better to have one single layer of reduce sum only.

---

<div class="post-metadata">

**Author:** ![nerpa](https://avatars.discourse-cdn.com/v4/letter/n/85e7bf/32.png) [@nerpa](https://discourse.mc-stan.org/u/nerpa)\
**Post date:** [August 8, 2020, 6:38pm UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/14 "2020-08-08T18:38:53Z")

</div>

Here is the annotated model. Hope it is clearer. The general design is that participants (`N`) perform 7 different tasks (each with a well defined computational model) during multiple weeks (`W`).

[model\_parallel.txt](https://discourse.mc-stan.org/uploads/short-url/9ljHz2kIN2spdJH96CYI1GuC3Ob.txt) (19.4 KB)

---

<div class="post-metadata">

**Author:** ![nerpa](https://avatars.discourse-cdn.com/v4/letter/n/85e7bf/32.png) [@nerpa](https://discourse.mc-stan.org/u/nerpa)\
**Post date:** [August 8, 2020, 6:40pm UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/15 "2020-08-08T18:40:32Z")

</div>

Yes, this was one of my latest tries that also was not successful. Initially I parallelized over `N` by using `reduce_sum_static` with `grainsize=1` - that is each participant will get a core. But it also was very slow.

---

<div class="post-metadata">

**Author:** ![nerpa](https://avatars.discourse-cdn.com/v4/letter/n/85e7bf/32.png) [@nerpa](https://discourse.mc-stan.org/u/nerpa)\
**Post date:** [August 8, 2020, 6:47pm UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/16 "2020-08-08T18:47:45Z")

</div>

> [@wds15](#):
>
> Now I see that you do have a for loop calling multiple reduce sum…that’s not efficient

Now I see that you meant the loop over `W` . This is unavoidable bc I am modeling a dynamical process. So there is no solution to it?

---

<div class="post-metadata">

**Author:** ![wds15](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/wds15/32/908_2.png) [@wds15](https://discourse.mc-stan.org/u/wds15)\
**Post date:** [August 9, 2020, 7:42am UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/17 "2020-08-09T07:42:55Z")

</div>

How big is N and W?

I would expect that each subject (out of N) is independent of all the others, right? It‘s just that per subject things are correlated over time, the weeks. Is that how your model works?

---

<div class="post-metadata">

**Author:** ![nerpa](https://avatars.discourse-cdn.com/v4/letter/n/85e7bf/32.png) [@nerpa](https://discourse.mc-stan.org/u/nerpa)\
**Post date:** [August 9, 2020, 10:01am UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/18 "2020-08-09T10:01:40Z")

</div>

yes, exactly. Except for dynamic variables (eg., `X`) that are shared across subjects. My `N` is ~100 and `W` is ~10. You wrote earlier to use a nested version of `reduce_sum` is an option. What did you mean by it?

---

<div class="post-metadata">

**Author:** ![wds15](https://yyz2.discourse-cdn.com/flex030/user_avatar/discourse.mc-stan.org/wds15/32/908_2.png) [@wds15](https://discourse.mc-stan.org/u/wds15)\
**Post date:** [August 9, 2020, 1:34pm UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/19 "2020-08-09T13:34:45Z")

</div>

Then you should really rewrite the model such that you form partial sums over subjects. So how about this plan:

- rewrite the model so that it is of the form  
`for( i in 1:N ) target += subject_log_lik(... subject i ...); `

- then you write a function forming partial sums over multiple patients

- finally you use use reduce\_sum

As a last step you can try to slice all those parameters _per subject_. So the first argument which gets sliced becomes an array of dimension a[N,…] and this contains for a given subject all your parameters needed which are specific to the subject to calculate his log-lik.

---

<div class="post-metadata">

**Author:** ![nerpa](https://avatars.discourse-cdn.com/v4/letter/n/85e7bf/32.png) [@nerpa](https://discourse.mc-stan.org/u/nerpa)\
**Post date:** [August 9, 2020, 2:53pm UTC](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317/20 "2020-08-09T14:53:20Z")

</div>

Sorry for being so slow… You mean I should put the loop over `W` inside this

`for( i in 1:N ) target += subject_log_lik(... subject i ...);` ?

If yes, I am not sure I can do that. Some of the parameters are subject-specific, but some parameters are shared across subjects and are updated dynamically with the progression of `W`.

[Next page](https://discourse.mc-stan.org/t/model-with-reduce-sum-takes-too-long/17317.md?page=2)