Optimization of stack_alloc::alloc

[Marcus Brubaker]

I made some small changes to stack_alloc::alloc() which cut it's cost by ~37%.  Since it's a pretty central function I wanted to run the patch by people before I pushed it.  I've run make test-unit which comes up clean, but I wanted to be doubly sure.

On a related note it seems like (at least in my case) it's not (entirely) extra calls to to_var() that are the culprit.  In fact ~60% of the calls are coming from operators (* and +) being used in Eigen::internal::gebp_kernel which is called by Eigen::internal::general_matrix_matrix_product (from multiply(matrix_v,matrix_v)) and Eigen::internal::triangular_solve_matrix (from multi_normal_cholesky_log).

(For reference, this profiling is done with g++ -O3 using callgrind and the excellent Kcachegrind to visualize results.)

Cheers,
Marcus

[Bob Carpenter]

Awesome. I'll take a look. If all of our
unit tests are passing, we should be OK.

g++ -O3 is exactly what we're targeting. Thanks
for pointing out which tools you used.

I'll take a look and hopefully learn more about C++
optimization.

The other thing to look at is the way objects
get constructed in var and vari -- that's where
the stack allocation's getting called.

For to_var(), I was talking about arithmetic operators of mixed
types, as in Matrix<var> * Matrix<double> and even more so
Matrix<var> + Matrix<double>. The extra memory overhead hurts
as much as the time.

The solvers shouldn't need to_var() at all, as they work on a single
type. And we of course expect the solving to dominate (like
the log gamma and digamma functions implicated in some of
the gradients and to a lesser extent, log and exp itself).

For some operations, we know there's no effect on gradients,
like transpose. But for others like products or sums,
it'd be nice to compute the gradients directly. That's only
going to help for the solvers if we can push it through to
the operator*() for Eigen matrices used by the solvers.

In some cases (like inverse as you pointed out before),
we might be able to get some speedup by sending a Matrix<double>
to the solver and computing the effect on the gradients ourselves.

- Bob

[Bob Carpenter]

This all looks fine, and I can see the motivation for
the changes. Some I didn't know would make
that much of a difference, like declaring a variable
outside of the body of an if statement.

My only concern is how portable

__builtin_expect

is. Does it run on all compilers we're likely to encounter?
If not, could we IFDEF the likely(x) and unlikely(x)
macros for some flag indicating we're using GCC and
fall back to a simpler definition?

We are mainly targeting gcc, but we want to be able
to run on Windows, and that's been a compilation
struggle so far.

We've been trying to avoid macros, but this is exactly
the kind of place where they make sense.

All those calls to eight_byte_aligned_malloc might
be removed, too, but I figured they weren't too common
and are only going to occur in the context of an already
expensive malloc operation.

- Bob

[Marcus Brubaker]

On Tue, Mar 13, 2012 at 7:39 PM, Bob Carpenter <ca...@alias-i.com> wrote:

This all looks fine, and I can see the motivation for
the changes.  Some I didn't know would make
that much of a difference, like declaring a variable
outside of the body of an if statement.

I was a little surprised about that as well.  I figured the compiler would be smart enough to optimize it appropriately, but apparently not.  That said, a big part of improvement was simply avoiding multiple calls to .size().
 

My only concern is how portable

   __builtin_expect

is.  Does it run on all compilers we're likely to encounter?
If not, could we IFDEF the likely(x) and unlikely(x)
macros for some flag indicating we're using GCC and
fall back to a simpler definition?

We are mainly targeting gcc, but we want to be able
to run on Windows, and that's been a compilation
struggle so far.

We've been trying to avoid macros, but this is exactly
the kind of place where they make sense.

I double checked that it's available on both gcc and clang.  It can be easily ifdef'd out based on __GNUC__, although I'm not sure what happens with clang in that case.

 

All those calls to eight_byte_aligned_malloc might
be removed, too, but I figured they weren't too common
and are only going to occur in the context of an already
expensive malloc operation.

The typical use pattern for stack_alloc means that eight_byte_aligned_malloc will almost never be called compared to the rest of the code in there.  This is so much the case that eight_byte_aligned_malloc never really shows up on the profiles.

On a related note, I realized that there is a bug in the 8 byte alignment of stack_alloc::alloc().  Specifically, when the value of used_ is not a multiple of 8, the returned pointer will not be properly aligned even if malloc() is properly aligned.  I suspect that this rarely happens in practice, but it could in theory.

Cheers,
Marcus

[Ben Goodrich]

On Tuesday, March 13, 2012 7:55:02 PM UTC-4, Marcus Brubaker wrote:

I double checked that it's available on both gcc and clang.  It can be easily ifdef'd out based on __GNUC__, although I'm not sure what happens with clang in that case.

clang defines __GNUC__, see

goodrich@CYBERPOWERPC:/tmp$ clang -x c /dev/null -dM -E | grep GNUC
#define __GNUC_MINOR__ 2
#define __GNUC_PATCHLEVEL__ 1
#define __GNUC_STDC_INLINE__ 1
#define __GNUC__ 4

so the Linux kernel apparently does

#ifdef __GNUC__
#  define likely(x)   __builtin_expect((x), 1)
#  define unlikely(x) __builtin_expect((x), 0)
#else
#  define likely(x)   (x)
#  define unlikely(x) (x)
#endif

Ben

[Bob Carpenter]

I tried to apply the patch and ran into this
problem:

~/stan>git am stack_allocopt.patch
Patch format detection failed.

Could you (Marcus) apply it on your side?
The patch Ben sent me that worked looked like an
e-mail and then had a diff command inside; yours
didn't have the e-mail header or the file insert/delete
listing before the diff.

I'd like to provide an ifdef for non-g++ and
non-clang++ compilers. The current macros from
Marcus's patch are:

#define likely(x) (__builtin_expect(!!(x),1))
#define unlikely(x) (__builtin_expect(!!(x),0))

I get the double-negation in the expect 1 case
for likely(x), but shouldn't we be able to get
rid of it in the second case for unlikely(x)?

So what I'm thinking (perhaps without second "!!")
is:

#ifdef __GNUC__
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)

#else
# define likely(x) (x)
# define unlikely(x) (x)
#endif

Plus the rest of Marcus's patch, of course.

- Bob

[Marcus Brubaker]

So I've gone ahead and added in the ifdef, removed the double negation on both counts (I've seen both versions floating about) and pushed the change since no one seemed to have significant objections.  It should be in git now.  Of course if something comes up we can back it out.

Sorry, I had meant to send an email about this when I pushed the changes it but I forgot.  Mea culpa.

Cheers,
Marcus

[Ben Goodrich]

On Wednesday, March 14, 2012 5:12:18 PM UTC-4, Bob Carpenter wrote:

I tried to apply the patch and ran into this
problem:

   ~/stan>git am stack_allocopt.patch
   Patch format detection failed.

Could you (Marcus) apply it on your side?
The patch Ben sent me that worked looked like an
e-mail and then had a diff command inside; yours
didn't have the e-mail header or the file insert/delete
listing before the diff.

FYI: patches should be created with git format-patch, in which case they can be applied (assuming no conflicts) with git apply or git am.

But this is now moot in this case because Marcus did a git push.

Ben

[Marcus Brubaker]

I've been using git diff, which seemed to produce patches which applied for me.  (I used them to move some patches between different machines.)  However, after looking at the git format-patch and git am help pages, those seem like they'd be really helpful in being more selective with the patch creation.  Thanks for the tip!

Cheers,
Marcus