[Bug libstdc++/65122] New: std::vector doesn't honor element alignment

[Bug libstdc++/65122] New: std::vector doesn't honor element alignment

[jacob.benoit.1 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65122

            Bug ID: 65122
           Summary: std::vector doesn't honor element alignment
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jacob.benoit.1 at gmail dot com

Created attachment 34807
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=34807&action=edit
testcase

Even in C++11 mode, even with the C++11 alignas keyword, element alignment
isn't honored by std::vector.

$ g++ vectoralign.cpp -o a --std=c++11 && ./a
ctor 0x2422010
ctor 0x2422050

Tested with a freshly built GCC 4.9.2 on Ubuntu x86-64.

Attaching testcase.

Note: this is morphing bug 53900.

[Bug libstdc++/65122] std::vector doesn't honor element alignment

[jacob.benoit.1 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65122

--- Comment #1 from Benoit Jacob <jacob.benoit.1 at gmail dot com> ---
Homologous libc++ bug report: http://llvm.org/bugs/show_bug.cgi?id=22634

[Bug libstdc++/65122] std::vector doesn't honor element alignment

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65122

--- Comment #2 from Marc Glisse <glisse at gcc dot gnu.org> ---
IMHO the only sensible solution is in this direction:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3396.htm

I hope Clark is still working on this...

[Bug libstdc++/65122] std::vector doesn't honor element alignment

[jacob.benoit.1 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65122

--- Comment #3 from Benoit Jacob <jacob.benoit.1 at gmail dot com> ---
I'd be interested in an explanation of why the default STL allocator can't just
honor the alignment of the value_type ? (The document linked in comment 2
seemed to assume that that goes without saying?)

[Bug libstdc++/65122] std::vector doesn't honor element alignment

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65122

--- Comment #4 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Benoit Jacob from comment #3)
> I'd be interested in an explanation of why the default STL allocator can't
> just honor the alignment of the value_type ?

[allocator.members] "It is implementation-defined whether over-aligned types
are supported" so we don't really have to. "the storage is obtained by calling
::operator new(std::size_t)" so we can't use posix_memalign (providing a
separate allocator that does could be a good idea though). We could, when the
type is over-aligned, do the usual trick of requesting too much memory so we
have enough margin to find a suitably aligned region inside, and write a marker
before so we remember where the real allocation started. That might be what was
tried in PR55727 (I didn't check), the maintainers might be ok with this if
someone posts a patch.

But calling new T would still be broken. It seems better in the long term to
add the aligned versions of operator new and make both new and std::allocator
use those (in the standard). Note that there would be ABI issues switching from
the trick in the previous paragraph to this.

[Bug libstdc++/65122] std::vector doesn't honor element alignment

[jacob.benoit.1 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65122

--- Comment #5 from Benoit Jacob <jacob.benoit.1 at gmail dot com> ---
So while the standard says that over-aligned types dont have to be supported,
it also says in 3.11/9 in
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf that:

> If a request for a specific extended alignment in a specific context is not supported by an implementation,
> the program is ill-formed. Additionally, a request for runtime allocation of dynamic storage for which the
> requested alignment cannot be honored shall be treated as an allocation failure

In my naive understanding, that sounds like if over-aligned allocation is not
supported then it must be an allocation failure (i.e. not fail silently to
honor alignment).

That's relevant because failing all over-allocated allocations is probably not
something that a compiler could do in the real world (that would break a lot of
existing software) and so this 3.11/9 clause might then be de-facto forcing
compilers to support over-allocated allocation.

What do you think? How else would you interprete 3.11/9?

[Bug libstdc++/65122] std::vector doesn't honor element alignment

[jacob.benoit.1 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65122

--- Comment #6 from Benoit Jacob <jacob.benoit.1 at gmail dot com> ---
(In reply to Marc Glisse from comment #4)
> "the storage is obtained by
> calling ::operator new(std::size_t)" so we can't use posix_memalign

Ouch. That's very unfortunate. I see. I would still be interested in how you
understand 3.11/9 and how to reconcile it with that without breaking a lot of
software.

[Bug libstdc++/65122] std::vector doesn't honor element alignment

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65122

--- Comment #7 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Benoit Jacob from comment #6)
> I would still be interested in how you understand 3.11/9

I consider it a defect in the standard, so it needs fixing, not
understanding...

[Bug libstdc++/65122] std::vector doesn't honor element alignment

[jacob.benoit.1 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65122

--- Comment #8 from Benoit Jacob <jacob.benoit.1 at gmail dot com> ---
If there is a defect in the standard, isn't it in the part that forces the
compiler to not use the useful type information that it has, that is, the
above-quoted "the storage is obtained by calling ::operator new(std::size_t)" ?

[Bug libstdc++/65122] std::vector doesn't honor element alignment

[jacob.benoit.1 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65122

--- Comment #9 from Benoit Jacob <jacob.benoit.1 at gmail dot com> ---
s/compiler/standard library

[Bug libstdc++/65122] std::vector doesn't honor element alignment

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65122

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Benoit Jacob from comment #6)
> (In reply to Marc Glisse from comment #4)
> > "the storage is obtained by
> > calling ::operator new(std::size_t)" so we can't use posix_memalign
> 
> Ouch. That's very unfortunate. I see. I would still be interested in how you
> understand 3.11/9 and how to reconcile it with that without breaking a lot
> of software.

But ::operator new(std::size_t) could always return memory aligned for the
most over-aligned type?  Thus our default new implementation could use
posix_memalign (..., MIN (size, BIGGEST_ALIGNMENT), size)?

If the user provides its own ::new then he is on its own, of course (and
doing that and using posix_memalign in it would be a workaround for this
issue?!).

[Bug libstdc++/65122] std::vector doesn't honor element alignment

[jacob.benoit.1 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65122

--- Comment #11 from Benoit Jacob <jacob.benoit.1 at gmail dot com> ---
(In reply to Richard Biener from comment #10)
> But ::operator new(std::size_t) could always return memory aligned for the
> most over-aligned type?  Thus our default new implementation could use
> posix_memalign (..., MIN (size, BIGGEST_ALIGNMENT), size)?

The problem is there are lots of use cases for really high alignment: AVX
brings uses of 32-byte alignment, and cache lines are typically >= 64 byte
aligned. So alignas has to support at least 64 or 128 byte alignment to support
cache friendly code, and even without that, it would have to support at least
32 byte alignment for AVX vectorized code.

Making all allocations that large would lead to substantial allocator slop. For
example, jemalloc has a quantum of 8 or 16 byte depending on whether the arch
is 32 or 64 bit, so increasing it to 32, 64 or 128 byte would be a big
difference.

> 
> If the user provides its own ::new then he is on its own, of course

I agree that's how I would like things to be. Unfortunately, the spec quote in
comment 4, "the storage is obtained by calling ::operator new(std::size_t)",
goes in the opposite direction, by requiring allocators to use the type-blind
::new , thereby losing useful type information such as the type's alignment.
That's why I think that this is the spec's weak spot that might be questioned.
but you're the expert, not me :)

> (and
> doing that and using posix_memalign in it would be a workaround for this
> issue?!).

That could be a good compromise for many applications, that either don't care
about minimizing memory usage, or don't do many tiny allocations.
Unfortunately, my context here is a library (Eigen), so we can't make this
decision for all our users.

[Bug libstdc++/65122] std::vector doesn't honor element alignment

[jacob.benoit.1 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65122

--- Comment #13 from Benoit Jacob <jacob.benoit.1 at gmail dot com> ---
(In reply to Richard Biener from comment #12)
> (In reply to Benoit Jacob from comment #11)
> > (In reply to Richard Biener from comment #10)
> > > But ::operator new(std::size_t) could always return memory aligned for the
> > > most over-aligned type?  Thus our default new implementation could use
> > > posix_memalign (..., MIN (size, BIGGEST_ALIGNMENT), size)?
> > 
> > The problem is there are lots of use cases for really high alignment: AVX
> > brings uses of 32-byte alignment, and cache lines are typically >= 64 byte
> > aligned. So alignas has to support at least 64 or 128 byte alignment to
> > support cache friendly code, and even without that, it would have to support
> > at least 32 byte alignment for AVX vectorized code.
> > 
> > Making all allocations that large would lead to substantial allocator slop.
> > For example, jemalloc has a quantum of 8 or 16 byte depending on whether the
> > arch is 32 or 64 bit, so increasing it to 32, 64 or 128 byte would be a big
> > difference.
> 
> Though does it really matter in practice?  Tiny allocations would not suffer
> because of the MIN (align, size), so the worst-case is max-align + 1
> allocations.  Btw, you could as well try MIN (align, size & -size),
> thus assume that the allocation size is N * alignof ().

Oh, I was missing the MIN (size, BIGGEST_ALIGNMENT) part of your proposal. So
you're right, that nicely takes care of tiny allocations. Correct also on MIN
(align, size & -size)   (though I have to trust your bit wizardry here) so that
neatly exploits the low bits of the size parameter to infer the alignof ---
sounds very good to me!

[Bug libstdc++/65122] std::vector doesn't honor element alignment

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65122

--- Comment #14 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Benoit Jacob from comment #13)
> (In reply to Richard Biener from comment #12)
> > (In reply to Benoit Jacob from comment #11)
> > > (In reply to Richard Biener from comment #10)
> > > > But ::operator new(std::size_t) could always return memory aligned for the
> > > > most over-aligned type?  Thus our default new implementation could use
> > > > posix_memalign (..., MIN (size, BIGGEST_ALIGNMENT), size)?
> > > 
> > > The problem is there are lots of use cases for really high alignment: AVX
> > > brings uses of 32-byte alignment, and cache lines are typically >= 64 byte
> > > aligned. So alignas has to support at least 64 or 128 byte alignment to
> > > support cache friendly code, and even without that, it would have to support
> > > at least 32 byte alignment for AVX vectorized code.
> > > 
> > > Making all allocations that large would lead to substantial allocator slop.
> > > For example, jemalloc has a quantum of 8 or 16 byte depending on whether the
> > > arch is 32 or 64 bit, so increasing it to 32, 64 or 128 byte would be a big
> > > difference.
> > 
> > Though does it really matter in practice?  Tiny allocations would not suffer
> > because of the MIN (align, size), so the worst-case is max-align + 1
> > allocations.  Btw, you could as well try MIN (align, size & -size),
> > thus assume that the allocation size is N * alignof ().
> 
> Oh, I was missing the MIN (size, BIGGEST_ALIGNMENT) part of your proposal.
> So you're right, that nicely takes care of tiny allocations. Correct also on
> MIN (align, size & -size)   (though I have to trust your bit wizardry here)
> so that neatly exploits the low bits of the size parameter to infer the
> alignof --- sounds very good to me!

That trick of course requires you to not "optimize" your allocations manually
to omit tail padding in aggregates (or manually compute allocation sizes).
Or use

struct { avx512vector x; char c; } __attribute__((packed,aligned(64)));

which has alignment 64 and size 65... (of course arrays of such objects
are ill-defined)

[Bug libstdc++/65122] std::vector doesn't honor element alignment

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65122

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
Oh, and I wonder if there is an aligned realloc (though C++ doesn't define
sth like realloc and thus std::vector can't optimize the copy when
reallocating?!).  But for a C program using posix_memalign or any other such
facility means realloc is out of the question as well.