[Ready] Fast Concurrent Deque Through Explicit Timestamping

[EduardBlees]

Implementation of [2014] Dodds,Haas,Kirsch Fast Concurrent Data-Structures Through Explicit Timestamping Выполняли: Чирухин, Блеес (3304), Саклакова (3303)

[EduardBlees]

@eugenyk

[pr3sto]

cтресс тесты не собирались из-за того, что несколько раз пересобирал разными версиями gcc. пересобрал с нуля одной версией - все заработало

[eugenyk]

@EduardBlees - пока тесты не проходят для большей части архитектур

[pr3sto]

@eugenyk #6 не собирается ассемблерный код под архитектуру i386, это поправим.

#7 и #4 выдают ошибку Exception: Illegal. Причем ошибка не только в стресс, но и в юнит тестах. По ошибке абсолютно не понятно, чем она вызвана. Я могу только предположить: у нас ассемблерный код написан только для двух архитектур: ts_hardwaretimestamp.h. И тесты используют платформозависимый HardwareTimestamp класс. Можно тесты переписать на AtomicCounterTimestamp, который не зависит от платформы и компилятора.

[khizmax]

@eugenyk #6 не собирается ассемблерный код под архитектуру i386, это поправим.

FYI - здесь собран зоопарк реализаций rdtsc для разных архитектур: https://github.com/google/benchmark/blob/v1.1.0/src/cycleclock.h#L56

[eugenyk]

Можно тесты переписать на AtomicCounterTimestamp, который не зависит от платформы и компилятора

@pr3sto по-хорошему надо бы в зависимости от платформы определять тип счётчика и для нереализованных действително использовать кроссплатформенный, через traits его передать в контейнер. Тут Максим меня может поправить

[khizmax]

по-хорошему надо бы в зависимости от платформы определять тип счётчика и для нереализованных действително использовать кроссплатформенный, через traits его передать в контейнер. Да, передача через traits - хорошее решение, которое даст возможность использовать кастомные счетчики или сравнивать производительность при разных реализациях счетчиков

[eugenyk]

выдают ошибку Exception: Illegal

@pr3sto, это ошибка вызова некорректной инструкции, ниже прилагаю содержимое core dump, полученного после запуска модульного теста - в общем ваше предположение верно в части счётчика

Core was generated by `./unit-deque'.
Program terminated with signal SIGILL, Illegal instruction.
#0  0x000000000046eb16 in void (anonymous namespace)::TSDeque::test<cds::container::TSDeque<int, cds::container::HardwareTimestamp, cds::opt::item_counter<cds::atomicity::item_counter>::pack<cds::container::tsdeque::traits> > >(cds::container::TSDeque<int, cds::container::HardwareTimestamp, cds::opt::item_counter<cds::atomicity::item_counter>::pack<cds::container::tsdeque::traits> >&) [clone .isra.183] [clone .constprop.228] ()
(gdb) bt
#0  0x000000000046eb16 in void (anonymous namespace)::TSDeque::test<cds::container::TSDeque<int, cds::container::HardwareTimestamp, cds::opt::item_counter<cds::atomicity::item_counter>::pack<cds::container::tsdeque::traits> > >(cds::container::TSDeque<int, cds::container::HardwareTimestamp, cds::opt::item_counter<cds::atomicity::item_counter>::pack<cds::container::tsdeque::traits> >&) [clone .isra.183] [clone .constprop.228] ()
#1  0x000000000046fe09 in (anonymous namespace)::TSDeque_hardware_timestamping_Test::TestBody() ()
#2  0x000000000049a263 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) ()
#3  0x0000000000491a64 in testing::Test::Run() [clone .part.368] ()
#4  0x0000000000491d1d in testing::TestInfo::Run() [clone .part.369] ()
#5  0x0000000000491f05 in testing::TestCase::Run() [clone .part.370] ()
#6  0x00000000004943b1 in testing::internal::UnitTestImpl::RunAllTests() [clone .part.371] [clone .constprop.426] ()
#7  0x00000000004947c1 in testing::UnitTest::Run() ()
#8  0x000000000043e7e6 in main ()

[pr3sto]

@eugenyk по этой ссылке есть только инструкция rdtsc. у нас используются: rdtsc и rdtscp. поэтому для других архитектур и компиляторов не добавил реализацию (для i386 поправил). тесты платформозависимых версий теперь только для архитектур, для которых есть реализация: https://github.com/khizmax/libcds/blob/d5ece4c2c229badd6426204c50f1de421ead2e80/test/unit/deque/ts_deque.cpp#L80

[eugenyk]

@pr3sto, тест всё равно не проходит под i386

[pr3sto]

@eugenyk я не вижу другого выхода для нас, кроме как удалить поддержку i386. У нас нет возможности тестировать и отлаживать код для этой платформы, а работа вслепую, как видим, результатов не приносит. Тем более, что у нас написан платформонезависимый atomiccountertimestamp, который работает абсолютно также, да и от алгоритма взятия временных меток работа дека никак не зависит

[eugenyk]

@eugenyk я не вижу другого выхода для нас, кроме как удалить поддержку i386. У нас нет возможности тестировать и отлаживать код для этой платформы, а работа вслепую, как видим, результатов не приносит. Тем более, что у нас написан платформонезависимый atomiccountertimestamp, который работает абсолютно также, да и от алгоритма взятия временных меток работа дека никак не зависит

Если вы попросите доступ - у вас будет возможность отлаживать код и под этой архитектурой, это не проблема. В любом случае, поддерживаться должны все архитектуры, которые сейчас поддерживаются библиотекой - пусть и через платформонезависмый счётчик будет поддерживаться i386, должно собираться и работать

[pr3sto]

@eugenyk последняя попытка пофиксить HardwareTimestamp. Скорее всего дело не в архитектуре, а в том, что у процессора просто нет инструкции rdtscp (по заявлениям авторов статьи, она есть на всех современных x86 процессорах). Добавил проверку (как описано тут)