Help with optimization?

[Mike Lawrence]

Hi folks,

Well, after my repeated posts to the list over the past days, I suspect I've used up my social credit, but in the off chance that anyone gets a kick out of optimization problems, I really could use a hand with this model: https://gist.github.com/mike-lawrence/5860316

As is, it runs too slowly to be useful (and this is actually just a simplest-case version of the model; I'd like to add fixed effects on each of the LBA parameters eventually). I've read through the optimization sections of the manual, but I don't see where I'm doing anything obviously (to my beginner's eye) non-optimal. Any help would be greatly appreciated.

Mike

--
Mike Lawrence
Graduate Student
Department of Psychology & Neuroscience
Dalhousie University

~ Certainty is (possibly) folly ~

[Mike Lawrence]

Ah! One big speedup can be achieved by not re-using variables inside the model block. I was initialized a variable, setting its value, then later re-setting its value to something else. On a hunch I tried initializing two variables and setting the value to each once, and this runs far faster.

--
Mike Lawrence
Graduate Student
Department of Psychology & Neuroscience
Dalhousie University

~ Certainty is (possibly) folly ~

[Ben Goodrich]

On Wednesday, June 26, 2013 10:00:36 PM UTC-4, Mike Lawrence wrote:

Ah! One big speedup can be achieved by not re-using variables inside the model block. I was initialized a variable, setting its value, then later re-setting its value to something else. On a hunch I tried initializing two variables and setting the value to each once, and this runs far faster.

I would be surprised if something like that made any difference. In your R code, you have

set.seed(1)

but that doesn't actually affect Stan. To be replicable, you need to pass a seed to the seed argument of stan().

My guess is that your model is such that if you get good starting values, it adapts and runs decently. And if you get bad starting values, then it doesn't.

Ben

[Marcus Brubaker]

Here are a couple tips to speed things up:

- Compute 1-accuracy[i] and reuse it instead of recomputing it 3 times

- As above, for many of the computations in that loop they are the same for each subject.  Precompute them for each subject in an array and then reference them in the loop.

- If L is large, instead of incrementing lp__ each time, create a vector[2*L] lpterms and set it's entry in the loop.  Then at the end of the loop write: lp__ <- lp__ + sum(lpterms);

The last one is probably your best bet for a quick win.

Cheers,

Marcus

--
You received this message because you are subscribed to the Google Groups "stan users mailing list" group.
To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Jiqiang Guo]

On Wed, Jun 26, 2013 at 10:16 PM, Ben Goodrich <goodri...@gmail.com> wrote:

On Wednesday, June 26, 2013 10:00:36 PM UTC-4, Mike Lawrence wrote:

Ah! One big speedup can be achieved by not re-using variables inside the model block. I was initialized a variable, setting its value, then later re-setting its value to something else. On a hunch I tried initializing two variables and setting the value to each once, and this runs far faster.

I would be surprised if something like that made any difference. In your R code, you have

set.seed(1)

but that doesn't actually affect Stan. To be replicable, you need to pass a seed to the seed argument of stan().

 

Actually, I think it is fine to set R's seed to make it replicable since the random seed for Stan's RNG is randomly generated in R if not set manually.

--

Jqiang 

 

My guess is that your model is such that if you get good starting values, it adapts and runs decently. And if you get bad starting values, then it doesn't.

Ben

[Bob Carpenter]

On 6/26/13 10:16 PM, Ben Goodrich wrote:
> On Wednesday, June 26, 2013 10:00:36 PM UTC-4, Mike Lawrence wrote:
>
> Ah! One big speedup can be achieved by not re-using variables inside the model block. I was initialized a variable,
> setting its value, then later re-setting its value to something else. On a hunch I tried initializing two variables
> and setting the value to each once, and this runs far faster.
>
>
> I would be surprised if something like that made any difference.

I think that depends on how bad the original program was :-)

For instance, this is slow:

vector[K] temp;
for (...) {
temp <- some calc for b;
... use temp ...
temp <- some calc for c;
... use temp ...
}

but this is faster:

vector[K] b;
b <- some calc for b;
vector[K] c;
c <- some calc for c;
for (...) {
... use b ...
... use c ...
}

There shouldn't be a noticeable difference between:

vector[K] temp;
temp <- some calc for b;
... use b ...
temp <- some calc for c;
... use c ...

and

vector[K] b;
b <- some calc for b;
vector[K] c;
c <- some calc for c;
... use b ...
... use c ...

In general, you want to define things that are used multiple
times as high up as possible.

- Bob

[Bob Carpenter]

On 6/26/13 11:08 PM, Marcus Brubaker wrote:
> Here are a couple tips to speed things up:
>
> - Compute 1-accuracy[i] and reuse it instead of recomputing it 3 times
> - As above, for many of the computations in that loop they are the same for each subject. Precompute them for each
> subject in an array and then reference them in the loop.

exactly!

> - If L is large, instead of incrementing lp__ each time, create a vector[2*L] lpterms and set it's entry in the loop.
> Then at the end of the loop write: lp__ <- lp__ + sum(lpterms);

Marcus has suggested we change the way lp__ is incremented internally
so that this behavior will be built in without so much burden on
the user.

As before, I'd say get it working before worrying about
optimization.

- Bob

[Bob Carpenter]

Never rule out the possibility that it's not the speed
of the iterations that's too slow, but the parameterization
or the model itself. Alas, these are much more involved and
subtle problems to fix.

You are running at -O3, right? If not, doing that's your
biggest win.

- Bob

[Mike Lawrence]

Hm, I take that back; the "speedup" I observed was a consequence of failing to set the random seed in my benchmarking :Op Running both versions of the code with the same input data and random seed yield pretty much identical run times. Still, it's probably good practice for human-readability not to re-use variables as I did. Back to the optimization drawing board...

--
Mike Lawrence
Graduate Student
Department of Psychology & Neuroscience
Dalhousie University

~ Certainty is (possibly) folly ~

[Bob Carpenter]

For readability it's best to declare them near where they're used
and define them only once. That goes for class design, too,
where it's easiest to reason about the state of immutable objects.

- Bob

[Mike Lawrence]

Thanks everyone for your input. (FYI, my delayed response is due to the fact that I somehow turned off receiving mail from the list yesterday; fixed now)

Marcus: Thanks for the tip on pre-computing 1-accuracy into a transformed data variable; didn't notice much of an impact, but it certainly makes sense. Regarding your suggestion to pre-compute variables that are currently inside the main model loop beforehand for each subject, I actually don't think this can be done because each of those variables can eventually be traced back to be dependent on the rt variable over which that loop is intended to iterate. I will, however, take a look at whether I can rearrange the math to eliminate that dependency for at least some of the variables. Finally, and surprisingly, incrementing lp__ out of the loop actually causes a dramatic slowdown (x3) for some reason; not sure what's going on there!

Ben: you caught the set.seed(1) bit before I did, but I didn't receive your message until I figured it out. Thanks anyway!

Bob: -O3 is triggered in RStan by calling set_cppo(mode = "fast") before stan(), correct?

[Bob Carpenter]

On 6/28/13 12:47 PM, Mike Lawrence wrote:

> Bob: -O3 is triggered in RStan by calling set_cppo(mode = "fast") before stan(), correct?

Yes. You need to have R in the right state before
installing it the first time, but if you hadn't fiddled with
your compile options for R, it should be OK.

- Bob

[Marcus Brubaker]

On Fri, Jun 28, 2013 at 9:47 AM, Mike Lawrence <mike....@gmail.com> wrote: 

Finally, and surprisingly, incrementing lp__ out of the loop actually causes a dramatic slowdown (x3) for some reason; not sure what's going on there!

Can you post your code for which this is the case?  It should definitely not be.  It may not be a huge speedup, but it should definitely not be a slow-down.

 

Cheers,
Marcus

[Mike Lawrence]

hm, I've played a bit and can't seem to reproduce my observation; I suspect I was simply failing to set the random seed again while playing.