cacheint, spinlock instances not necessarily 64-byte aligned

[nickhutchinson]

libcuckoo tags the definitions of the cacheint and spinlock classes with alignas(64)/__attribute__((aligned(64))), presumably to avoid false sharing. However it goes on to use these classes in containers like std::vector and lazy_array. AFAIK the std::vector from libstdc++ or MSVC will not respect the alignment of its containing elements, and lazy_array doesn't seem to either. The alignas here ensures that elements are spaced 64-bytes apart, but doesn't ensure they're aligned on 64-byte boundaries.

You may want to consider writing a custom allocator that has support for over-aligned allocations and using it for these containers. The aligned_allocator_adaptor from Boost gives an example.

[manugoyal]

Yes this is definitely an issue!

Now that the container is allocator-aware, I'm a bit reluctant to impose an aligned allocator on top of that, because if somebody does pass in an aligned-allocator, we'll be double-aligning each time. Also, I think this issue will be resolved in C++17, because new and delete will do over-aligned allocations properly.

Perhaps it's worth adding a warning to the documentation that the table makes use of over-aligned types so it's recommended to pass in an aligned allocator like the boost one.

[rayrapetyan]

I also observe a significant performance degradation (especially in simple tests) in a benchmark: https://github.com/rayrapetyan/shmaps/blob/master/src/bench/libcuckoo.cpp

spinlock with alignas(64):

---

Benchmark Time CPU Iterations

LibCuckooFixture/BM_LibCuckoo_Set_IntInt 5064304 ns 5044381 ns 134 LibCuckooFixture/BM_LibCuckoo_SetGet_IntInt 6234558 ns 6216647 ns 116 LibCuckooFixture/BM_LibCuckoo_Set_IntFooStats 5762053 ns 5751777 ns 112 LibCuckooFixture/BM_LibCuckoo_SetGet_IntFooStats 7411218 ns 7406090 ns 89 LibCuckooFixture/BM_LibCuckoo_Set_StringInt 22467459 ns 22423548 ns 31 LibCuckooFixture/BM_LibCuckoo_SetGet_StringInt 32538412 ns 32516091 ns 22 LibCuckooFixture/BM_LibCuckoo_Set_StringFooStatsExt 36773063 ns 36747684 ns 19 LibCuckooFixture/BM_LibCuckoo_SetGet_StringFooStatsExt 46580592 ns 46559933 ns 15

spinlock without alignas(64):

---

Benchmark Time CPU Iterations

LibCuckooFixture/BM_LibCuckoo_Set_IntInt 3566283 ns 3565072 ns 194 LibCuckooFixture/BM_LibCuckoo_SetGet_IntInt 5410120 ns 5278531 ns 147 LibCuckooFixture/BM_LibCuckoo_Set_IntFooStats 3915558 ns 3906744 ns 160 LibCuckooFixture/BM_LibCuckoo_SetGet_IntFooStats 5430732 ns 5429336 ns 131 LibCuckooFixture/BM_LibCuckoo_Set_StringInt 18859071 ns 18838237 ns 38 LibCuckooFixture/BM_LibCuckoo_SetGet_StringInt 27735135 ns 27696308 ns 26 LibCuckooFixture/BM_LibCuckoo_Set_StringFooStatsExt 34524203 ns 34514150 ns 20 LibCuckooFixture/BM_LibCuckoo_SetGet_StringFooStatsExt 47511294 ns 47508333 ns 15

[milianw]

This is still an issue, triggering UBSAN warnings as shown in #97. Note that I'm compiling with C++17, yet the issue is still there and not resolved.

The documentation of libcuckoo says:

 * @tparam Allocator type of allocator. We suggest using an aligned allocator,
 * because the table relies on types that are over-aligned to optimize
 * concurrent cache usage.

Yet even when I specify boost::alignment::aligned_allocator as allocator for libcuckoo, I still get misaligned address warnings from UBSAN:

    libcuckoo::cuckoohash_map<QString, InternedString, std::hash<QString>, std::equal_to<QString>, boost::alignment::aligned_allocator<std::pair<const QString, InternedString>, 64>> mStringMap;

/home/milian/projects/kdab/qitissue/KDAB/io/../../3rdParty/libcuckoo/libcuckoo/cuckoohash_map.hh:805:18: runtime error: member access within misaligned address 0x7f5343f9a6a0 for type 'struct spinlock', which requires 64 byte alignment
0x7f5343f9a6a0: note: pointer points here
 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00
              ^ 
    #0 0x7f5373045890 in libcuckoo::cuckoohash_map<QString, ImageIO::OnDiskStringCache::InternedString, std::hash<QString>, std::equal_to<QString>, boost::alignment::aligned_allocator<std::pair<QString const, ImageIO::OnDiskStringCache::InternedString>, 64ul>, 4ul>::spinlock::spinlock() /home/milian/projects/kdab/qitissue/KDAB/io/../../3rdParty/libcuckoo/libcuckoo/cuckoohash_map.hh:805
    #1 0x7f5373043ef2 in libcuckoo::cuckoohash_map<QString, ImageIO::OnDiskStringCache::InternedString, std::hash<QString>, std::equal_to<QString>, boost::alignment::aligned_allocator<std::pair<QString const, ImageIO::OnDiskStringCache::InternedString>, 64ul>, 4ul>::cuckoohash_map(unsigned long, std::hash<QString> const&, std::equal_to<QString> const&, boost::alignment::aligned_allocator<std::pair<QString const, ImageIO::OnDiskStringCache::InternedString>, 64ul> const&) /home/milian/projects/kdab/qitissue/KDAB/io/../../3rdParty/libcuckoo/libcuckoo/cuckoohash_map.hh:116

How is this supposed to work?

[milianw]

Hmm this is pretty odd - https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65122 claims this should work with GCC 7 onwards, and I'm already using 11.1, yet it still doesn't work.

[milianw]

OK, I think this isn't really related to libcuckoo, but rather an issue with the compilers or C++ as a language. This is enough to trigger the warnings:

#include <vector>

struct alignas(64) spinlock {
    int i = 0;
};

int main()
{
    std::vector<spinlock> locks;
    locks.emplace_back(spinlock());
    return 0;
}

Basically it looks like emplace_back does not work correctly. Resize on the other hand seems to work: https://godbolt.org/z/o4qGWravq