slow categorical_rng implementation

[torsti]

Summary:

The categorical_rng function is very slow for large N-simplexes, due to an unneccessary double loop.

Description:

The implementation of the categorical_rng function includes a double loop which, unless I am mistaken, just calculates the cumulative sum of theta:

for (int i = 0; i < theta.rows(); i++) {
    for (int j = i; j < theta.rows(); j++)
        index(j) += theta(i, 0);
}

Replacing that with a single loop, or say a call to cumulative_sum will speed up the function tremendously for large N.

Additionally replacing the iteration over the cumulative sum of theta with a binary search might also provide a small additional speed up.

Additional Information:

Just as an annectode: in a simulation model written in Stan, but using only transformed data and generated quantities, the program spent over 90% time (or ratherperf samples) in categorical_rng. Replacing the implementation with a custom version without the double loop (but no binary search) cut down the runtime where the N-simplex was of order 10000, from hours to a few minutes only.

Current Version:

v2.14.0

[bob-carpenter]

Thanks much for testing and reporting this. This should be easy to fix. This would be a great project for someone wanting to get their feet wet with our dev process.

[torsti]

I thought so. I'm trying to get the hang of the dev process over at #504. Maybe I was a bit rash sending the pull request before waiting for a comment on the issue first, though...