I've written my own aligned allocator type based on TBB's scalable_aligned_malloc and scalable_aligned_free. Unfortunately, Eigen's std::vector specialization is only triggered when you use Eigen's own aligned_allocator, so I can't easily use my allocator for std::vectors of aligned Eigen types. I've been trying to think of a good way to allow users to supplement their own aligned allocators. What if Eigen's std::vector were specialized for all allocator types matching a specific type trait instead of one specific type? Then I could make my allocator compatible by making it match the type trait (probably by adding a typedef to its definition or deriving it from a specific class or something). I would think this would be fairly easy to do with boost::enable_if and boost::is_base_of, but I know adding Boost as a dependency isn't a desirable option. Ideas?

Allowing to use custom allocators would be very good, but we really don't need enable_if or anything fancy for that. I would just suggest that we rely a little on the preprocessor here: here are two ways we could proceed:

1) we let our StdVector header use a macro EIGEN_ALIGNED_ALLOCATOR that defaults to Eigen::aligned_allocator and can be overridden.

or

2) we let StdVector provide a macro that allows easily generating a partial specialization for a given allocator, passed as macro argument.

I think it would be better to just make it work via the syntax c++ users are already familiar with...namely:

Code: Select all

#define EIGEN_USE_NEW_STDVECTOR
#include <Eigen/StdVector>

typedef Eigen::Matrix<float, 3, 1> Vector3;
std::vector< Vector3, MyAllocator<Vector3> > foo;

It's much more intuitive and less unwieldy than something like a macro where you have to be conscious of things like compilation order.

Well, it looks like a macro may be the only option after all. I got it working using a combination of enable_if and is_base_of, but using enable_if with class templates requires adding an additional template parameter to the primary template which is std::vector in this case, so that isn't an option. sigh...

Should I add a ticket for creating the macro? It's such a simple change that if I find time after this weekend I can probably do it, but I don't know if I still have svn access or not since it's been so long.

Don't bother about the issue tracker.

If you want to be able to push directly to the mercurial repo, just create an account on bitbucket.org and tell me your username;

The beauty of mercurial is that you can work just as well without an account, since it's a DVCS. People commit locally, export that as a patch, send that to the mailing list, we import and push that, and they get credited just as if they had pushed themselves.

I added the macro and it's working well for me. I also took a stab at adding std::deque support since I've been needing that for awhile now. I basically copied and modified the std::vector implementation, but I haven't been able to get it to compile under MSVC (haven't tried GCC). MSVC still complains that the type won't be aligned due to std::deque::resize() even though I can plainly see in the compiler output that it's instantiating the partial specialization. I'm probably just missing something simple, but I can't make it work. As soon as I get the confirmation email for the mailing list, I'll send a patch with everything and maybe someone brighter than me can get std::deque working

OK cool. About the confirmation email, check your spam filter. It should be immediate; otherwise tell me and i'll manually sign you in.

If the preprocessor symbol EIGEN_DONT_VECTORIZE is defined, does it mean I can use my own allocator and non-specialized std::vector?

I use TTB's cache aligned allocator to avoid false sharing. Does Eigne's allocator align along cache lines. If so, I could it instead of TBB's allocator.

Almost. If EIGEN_DONT_VECTORIZE is defined, Eigen won't use any explicit vectorization so you won't get any alignment-related crash from Eigen. But Eigen will still assert() that certain arrays are aligned so you don't suddenly get a crash when you enable vectorization. So if you really want to make it safe to use any allocator, what you need is EIGEN_DONT_ALIGN_STATICALLY (only in the development branch) which will actually still allow vectorization of object allocated on the heap by Eigen itself; or you can use EIGEN_DONT_ALIGN (available in both branches) if you don't mind losing all vectorization.

Eigen's own aligned allocator only aligns to 16 bytes boundaries. Which is smaller than the size of a cache line (64 bytes, right?)

Yes, cache boundaries are 64/128 bytes. Does it mean that I can use TBB's allocator instead of Eigen't allocator with any STL container except std::vector?

What if I switch to dynamic size matrices? As I understand, the benefit of fixed size matrices diminishes as matrix size get's larger and allocation/delocation performed less frequently. Internally dynamic size matrices use Eigen's 16 byte aligned allocator, which can lead to false sharing. The ideal scenario for me would be to use std::vector, have vectorization enabled and have all structures cache aligned. Is there a way to make the dynamic size matrices to use TBB's allocator? That would solve my problem nicely.

EDIT:

Since Eigen's matrices are allocated into a continuous memory block, the impact of false sharing lessens as the matrix size increases. With large matrices cache alignment is no issue and one can use dynamic size matrices and keep vectorization for extra performance.

Things are somewhat more complicated with small size matrices. My project uses large size vectors of matrices. As the container size is fairly large, the vector itself is not severally affected by false sharing. But if its elements are dynamic size matrices, then each element can be affected by false sharing, because the elements allocate their date in free store. Switching to fixed size matrices should fix the problem, because all matrices would be allocated into a continuous memory block. This way I can use Eigne's specialization std::vector don't bother with cache alignment. Did I get it right?

renorm wrote:Yes, cache boundaries are 64/128 bytes. Does it mean that I can use TBB's allocator instead of Eigen't allocator with any STL container except std::vector?

Unfortunately most STL containers suffer from the same problem as std::vector, namely that the optional parameter of resize() is a value_type passed by value. This is being fixed in the upcoming c++0x.

Fortunately, Ken's recent patch allows to use Eigen's STL container specializations with other allocators than just Eigen's own allocator. And yes, if your TBB allocator allocates to 64 byte boundaries, then in particular it allocates to 16 byte boundaries so it can be used.

What if I switch to dynamic size matrices?

Then there is no problem at all, since their own constructor takes care of allocating the array of coeffs at runtime on the help, so it takes care of alignment.

By the way do make sure you read this:

http://eigen.tuxfamily.org/dox-devel/To ... iners.html

As I understand, the benefit of fixed size matrices diminishes as matrix size get's larger

True.

and allocation/delocation performed less frequently. Internally dynamic size matrices use Eigen's 16 byte aligned allocator, which can lead to false sharing. The ideal scenario for me would be to use std::vector, have vectorization enabled and have all structures cache aligned. Is there a way to make the dynamic size matrices to use TBB's allocator? That would solve my problem nicely.

That's a reasonable feature request. If you made a patch doing that, we'd probably take it. It's not hard at all. The only file you need to read is Core/util/Memory.h. All the currently-16-byte-aligned allocs go through ei_aligned_malloc so you just have to add a path there. There is also ei_aligned_stack_alloc but it is either doing alloca() which returns page-aligned ptrs (typically 4k) or calls ei_aligned_malloc so you don't need to worry about it.

EDIT:

Since Eigen's matrices are allocated into a continuous memory block, the impact of false sharing lessens as the matrix size increases. With large matrices cache alignment is no issue and one can use dynamic size matrices and keep vectorization for extra performance.

Things are somewhat more complicated with small size matrices. My project uses large size vectors of matrices. As the container size is fairly large, the vector itself is not severally affected by false sharing. But if its elements are dynamic size matrices, then each element can be affected by false sharing, because the elements allocate their date in free store. Switching to fixed size matrices should fix the problem, because all matrices would be allocated into a continuous memory block. This way I can use Eigne's specialization std::vector don't bother with cache alignment. Did I get it right?

Yes, that sounds right
Just keep in mind that Eigen only aligns fixed-size matrices when they are multiple of 16 bytes. So if you have a 5x5 float matrix it won't be aligned by default. You can make it aligned by setting a bigger, multiple-of-16-bytes max-size-at-compile-time, but even so, Eigen will have little opportunity for vectorization. Vectorization only is efficient if your matrix is either large enough, or multiple-of-16-bytes.

I am curious, why passing by value discards alignment?

bjacob wrote:Unfortunately most STL containers suffer from the same problem as std::vector, namely that the optional parameter of resize() is a value_type passed by value. This is being fixed in the upcoming c++0x.

Even more unfortunate. On Visual Studio 10 (VC10), it is not yet fixed even though quite a bunch of C++0x features are already supported out of the box.

- Hauke

renorm wrote:I am curious, why passing by value discards alignment?

Because passing by value means push onto the stack, which isn't 16-byte aligned...