Open sissow2 opened 1 year ago
Thanks a lot! Yes had issues with Eigen before which made me suspect for some time that this was the case. I somehow thought that I fixed this in the past but it is clearly still there. Thanks for the nice words and for finding a small repro case!
So I did a bit of digging on this.
First, the current state. It looks like you've definitely thought about this before, since in rbts::node
you wrap T
in a std::aligned_storage_t
. This does correctly change the alignof(node)
to the appropriate value. Unfortunately, it looks like this mechanism is defeated because the buffer itself is initialized by a placement-new expression on an unaligned block of memory returned by MemoryPolicy::HeapPolicy::allocate
. I think this is a loophole that erases the alignment requirements posed by the aligned_storage_t
and therefore node
.
I can see a couple solutions here:
rbts::node
, add some machinery around leaf_t::buffer
that over-sizes the buffer (based on alignment requirements), and adjust rbts::node::leaf()
to apply an offset from the beginning of this buffer to ensure alignment.If you want I can take a pass at either of these options, or something else that you have in mind. Or I can leave it be; I have a workaround I can use at the call site (turning off alignment optimizations for eigen types I store in immer
containers).
Hi @sissow2!
Your assesment seems very much on point. Thanks a lot for looking into this. Either of the two approaches sounds good. Maybe the latter could be better as to keep the data-structure code simpler, but happy to take the other route if you feel like it's actually not much effort.
I don't have much time to look into this over the next few days, so if you wanna start the work it would be he greatly appreciated.
Also: can you reproduce this issue with some of the other data-structures?
Re other data structures: I updated the repro case to check all the data structures, as well as different alignments: https://github.com/arximboldi/immer/compare/master...sissow2:immer:sissow2-alignment-flex-vector-bug. Here's what I found:
vector
and flex_vector
. Notably, vector<box<T>>
was fine :thinking: The natural alignment of the compiler in nix-shell
is 16 bytes. Since this is the case, it makes sense at the 32-byte case has more failures. What's surprising to me is that there are failures at all for the 16-byte case. Digging even deeper, it looks like the RBTS-based structures will use an optimized free list for their heap, while HAMTS structures do not do this optimization and will use debug_size_heap<cpp_heap>
(which is 16-byte aligned). The 8 bytes of misalignment is therefore unique to the free list, which makes sense because free list nodes start with a pointer.
Re the allocator solution: Writing an allocator that is guaranteed to return aligned pointers seems to be quite the exercise, but fortunately c++17 added overloads to operator new
(see 3) that accept a desired alignment as input. Working backwards from this, the API would change to HeapPolicy::[de]allocate(size_t size, std::align_val_t alignment)
. This unfortunately would bump the c++ version from 14 to 17. Some potential workarounds:
#define
magic to only enforce alignment in cpp_heap
if C++17 is usedcpp_heap
with a custom alignment-aware implementation to work with C++14 as well. I'd need to do a bit of research on the state-of-the-art here though.I do no think we need the C++17 alignment API since we use our own allocator API?
Memory allocated with new
is alligned by default to alignof(std::max_align_t)
. It is us (me :sweat_smile:) that broke the alignment with the metadata that heaps like debug_size_heap
and free_list_heap
. I think changing the HeapPolicy
API and fixing those heaps adaptors should be enough.
Hey, it just hit me I forgot to communicate back here- I found a workaround that I can use in my own codebase, so I de-prioritized this as I needed to move on. I don't know when I'll have time to get back to this, so I just wanted to let you know not to wait on me!
Again, sorry for leaving this in limbo for so long.
No worries, I wasn't waiting for you. Thanks for checking in!
Essentially, flex_vector can (always?) allocates objects at addresses that do not align with the type's alignment requirements. I uncovered this while using Eigen with
immer
, which causes some nasty segfaults when there are alignment violations on vectorized types.I added a repro case here: https://github.com/sissow2/immer/commit/9d295b829c37dbabdb96b4f703ba56492734e76c . The sanity check with
std::vector
passes always, while theimmer::flex_vector
variant always fails :This might be related to https://github.com/arximboldi/immer/issues/228, but the reporter's repro case is for a non-vectorized type so I'm not sure it's the same issue.
I might be able to create a PR with a fix, but wondering if you have any ideas before I dive into it.
Also: I'm really liking this library! This and
lager
have been making my life so much easier. Also thanks for providing anix-shell
environment, it made creating this repro case a breeze.