speeding up ps_point

[Bob Carpenter]

Some comments on

src/stan/mcmc/hmc/hamiltonians/ps_point.hpp

now that we know it's a bottleneck.

0. Are the public member variables manipulated directly? Otherwise
I don't see how you could get a ps_point with nonzero values.

If everything's public like this, you can use struct.

1. In the constructor, do we really need a zero-init?

ps_point(int n, int m): q(n), r(m), p(Eigen::VectorXd::Zero(n)),
V(0), g(Eigen::VectorXd::Zero(n))

This will result in an element-by-element copy from the expression
template constructed with Zero(n). If you just start p and g out
with their size-based constructor, it should be much. (You may need
to specify rows and columns to avoid ambiguity in the constructor
signatures.) You can always zero these things out later when you
need to.

2. This copy_base function could probably be replaced with a copy
constructor, and then new instances created rather than existing
ones copied.

void copy_base(ps_point& z) {
q = z.q;
r = z.r;
p = z.p;
V = z.V;
g = z.g;
}

I'd rather see things like ps_point be immutable. (Or if we
must make them mutable, then share them in a pool!)

If that won't work, then you could speed this up if in fact
the copy constructor is super-slow compared to resizing and
copying data.

Also, it'd be nice to have the z reference be const here. This
won't work given that the fields are not constant. You could
provide const accessos.



3. For these gets:

virtual void get_param_names(std::vector<std::string>& model_names,
std::vector<std::string>& names) {
for(size_t i = 0; i < q.size(); ++i)
names.push_back(model_names.at(i));
for(size_t i = 0; i < q.size(); ++i)
names.push_back(std::string("p_") + model_names.at(i));
for(size_t i = 0; i < q.size(); ++i)
names.push_back(std::string("g_") + model_names.at(i));
}

virtual void get_params(std::vector<double>& values) {
for(size_t i = 0; i < q.size(); ++i)
values.push_back(q.at(i));
for(size_t i = 0; i < q.size(); ++i)
values.push_back(p(i));
for(size_t i = 0; i < q.size(); ++i)
values.push_back(g(i));
}

a. Do they really need to be virtual? The only reason for this would
be if you were going to use them when their class isn't known statically.
Can we get around that somehow, like with the curiously recursive template
pattern? If they're virtual, do you want virtual destructors, too?

b. You can use assign() with iterators rather than push_back(),
and it should be faster:

http://www.cplusplus.com/reference/vector/vector/assign/

Both Eigen::Matrix and std::vector guarantee contiguous memory.

c. They can both be const, as in:

virtual void get_params(std::vector<double>& values) const;

- Bob

P.S. For future reference:

For std::vector, thex .at(i) method checks bounds, whereas operator[] doesn't.
You shouldn't need to check given that you're looping on size.

I take it the fact that they all use q.size() is intended? It's
more idiomatic to use the variable you're walking through and should
also be easier for a compiler to optimize.

[Michael Betancourt]

Make sure to look at the version in feature/fast_constructor which already addresses some of these issues (unfortunately without much of an effect on performance).

> 0. Are the public member variables manipulated directly? Otherwise
> I don't see how you could get a ps_point with nonzero values.
>
> If everything's public like this, you can use struct.

Yes, they are very much manipulated directly.

> 1. In the constructor, do we really need a zero-init?
>
> ps_point(int n, int m): q(n), r(m), p(Eigen::VectorXd::Zero(n)),
> V(0), g(Eigen::VectorXd::Zero(n))
>
> This will result in an element-by-element copy from the expression
> template constructed with Zero(n). If you just start p and g out
> with their size-based constructor, it should be much. (You may need
> to specify rows and columns to avoid ambiguity in the constructor
> signatures.) You can always zero these things out later when you
> need to.

See the new version which does just this.

> 2. This copy_base function could probably be replaced with a copy
> constructor, and then new instances created rather than existing
> ones copied.
>
> void copy_base(ps_point& z) {
> q = z.q;
> r = z.r;
> p = z.p;
> V = z.V;
> g = z.g;
> }
>
> I'd rather see things like ps_point be immutable. (Or if we
> must make them mutable, then share them in a pool!)
>
> If that won't work, then you could speed this up if in fact
> the copy constructor is super-slow compared to resizing and
> copying data.
>
> Also, it'd be nice to have the z reference be const here. This
> won't work given that the fields are not constant. You could

> provide const accesses.

Yes, I can make this a copy constructor that explicitly takes in a base class.

The methods are used only rarely so I didn't bother pushing any templates to speed them up.

> P.S. For future reference:
>
> For std::vector, thex .at(i) method checks bounds, whereas operator[] doesn't.
> You shouldn't need to check given that you're looping on size.
>
> I take it the fact that they all use q.size() is intended? It's
> more idiomatic to use the variable you're walking through and should
> also be easier for a compiler to optimize.

That's good to know.

[Bob Carpenter]

On 6/1/13 4:30 AM, Michael Betancourt wrote:
> Make sure to look at the version in feature/fast_constructor which already addresses some of these issues (unfortunately without much of an effect on performance).

Thanks --- didn't realize that was there.

>> 1. In the constructor, do we really need a zero-init?

...

> See the new version which does just this.

Not quite. You have this:

ps_point(int n, int m): q(n), r(m), p(n), V(0), g(n) {
p.setZero();
g.setZero();
};

That's still going to need to walk over all of p and g to do
the sets. I'm suggesting that you can get away without doing
the setZero() in the size-based constructor and then call setZero()
if you need to.

But then I don't see anywhere in the code where this getting called
like this anywhere other than the subclass constructors for size,
and then I don't see those getting called anywhere.

>> 3. For these gets:
>>
>> virtual void get_param_names(std::vector<std::string>& model_names,
>> std::vector<std::string>& names) {

...

>> virtual void get_params(std::vector<double>& values) {

...

>>
>> a. Do they really need to be virtual? The only reason for this would
>> be if you were going to use them when their class isn't known statically.
>> Can we get around that somehow, like with the curiously recursive template
>> pattern? If they're virtual, do you want virtual destructors, too?
>>
>> b. You can use assign() with iterators rather than push_back(),
>> and it should be faster:
>>
>> http://www.cplusplus.com/reference/vector/vector/assign/
>>
>> Both Eigen::Matrix and std::vector guarantee contiguous memory.
>>
>> c. They can both be const, as in:
>>
>> virtual void get_params(std::vector<double>& values) const;
>
> The methods are used only rarely so I didn't bother pushing any templates to speed them up.

OK --- then the time to do virtual calls won't matter.

Another concern is that having even a single virtual method
means you wind up allocating another pointer per object
for the vtable.

- Bob

[Michael Betancourt]

> That's still going to need to walk over all of p and g to do
> the sets. I'm suggesting that you can get away without doing
> the setZero() in the size-based constructor and then call setZero()
> if you need to.

I'm just anal about having reasonable initialization values, lest I assumed them somewhere in the algorithm.

> But then I don't see anywhere in the code where this getting called
> like this anywhere other than the subclass constructors for size,
> and then I don't see those getting called anywhere.

Right, it's mostly copy constructors.

>
> OK --- then the time to do virtual calls won't matter.
>
> Another concern is that having even a single virtual method
> means you wind up allocating another pointer per object
> for the vtable.

Oy, I really hope we're not getting that deep into optimization yet...

[Marcus Brubaker]

Agreed.  Have you had a chance to benchmark grad_log_prob() of one or two of the models in 1.3.0 vs develop?

Cheers,
Marcus

[Bob Carpenter]

On 6/1/13 2:38 PM, Michael Betancourt wrote:
>> That's still going to need to walk over all of p and g to do
>> the sets. I'm suggesting that you can get away without doing
>> the setZero() in the size-based constructor and then call setZero()
>> if you need to.
>
> I'm just anal about having reasonable initialization values, lest I assumed them somewhere in the algorithm.

That's why I like having immutable objects. You guarantee
they're always in a reasonable state.

Setting a default of zero isn't the solution, though.
If you're going to make a mutable class like this, you're
already pushing the burden to do the right thing to the client code.

I'd rather NOT have reasonable "guesses", because they can mask
bigger issues.

Since these constructors don't seem to be called anywhere, they're
just cluttering up the code.

>> But then I don't see anywhere in the code where this getting called
>> like this anywhere other than the subclass constructors for size,
>> and then I don't see those getting called anywhere.
>
> Right, it's mostly copy constructors.

Copy constructors plus sets.

I'm not convinced yet you need this many objects flying
around. You may be able to reuse them more efficiently.

>> OK --- then the time to do virtual calls won't matter.
>>
>> Another concern is that having even a single virtual method
>> means you wind up allocating another pointer per object
>> for the vtable.
>
> Oy, I really hope we're not getting that deep into optimization yet...

It's probably not going to matter here because the class is
going to be relatively large compared to the vtable pointer.
For smaller classes like var, it absolutely matters.

- Bob

[Michael Betancourt]

With the changes in the current feature/fast_constructor branch the timing comparison is better but still not perfect.  We're down to about 25% slowdown, but that starts to disappear when the models become nontrivial (taking more than a few seconds to run) and the gradient computations start to dominate.  I'm guessing the turnover past x=1 is due to the faster agrad computations implemented since v.1.3.0.

We should probably start looking into culling acid test models to better reflect the more computationally complex models people are using.

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