О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 10.03.10 17:09
Оценка: 330 (36) +1
#Имя: FAQ.cpp.lock-free
[пост получился достаточно длинный, поэтому сразу скажу о бонусе — это простой и эффективный алгоритм очереди на основе буфера фиксированного размера — нетерпеливые могут сразу перемещаться к концу поста ]

Последние дни на RSDN шла своего рода распределенная игра по написанию lock-free контейнеров. Вначале vf запостил lock-free стек для .Net:
http://www.rsdn.ru/forum/dotnet/3719883.aspx
Автор: vf
Дата: 27.02.10

Я указал, что в стеке содержится достаточно изощренная ошибка:
http://www.rsdn.ru/forum/dotnet/3721436.1.aspx
Автор: remark
Дата: 01.03.10


Потом Caracrist запостил lock-free очередь для С++:
http://www.rsdn.ru/forum/src/3725942.1.aspx
Автор: Caracrist
Дата: 05.03.10

Я указал на ряд ошибок:
http://www.rsdn.ru/forum/src/3726327.1.aspx
Автор: remark
Дата: 05.03.10


Потом дали ссылку на блог некого товарища из Яндекса с описанием lock-free стека для С++:
http://users.livejournal.com/_foreseer/34284.html
Я тоже указал на ошибку:
http://www.rsdn.ru/forum/dotnet/3721636.1.aspx
Автор: remark
Дата: 01.03.10


К чему я это? Что не надо писать lock-free контейнеры? Это смотрите сами, мне всё равно. Это пусть говорят другие, те которые сами не умеют писать lock-free алгоритмы В целом lock-free алгоритмы писать вполне реалистично, единственное надо немного сноровки, ревью коллег, и соответствующие инструменты.
Кстати, по поводу инструментов, тут я не могу не упомянуть в качестве рекламы свой Relacy Race Detector. Если последние 2 ошибки удалось найти при просмотре кода, то первую смог вскрыть только Relacy Race Detector (кстати, если кто следит за такими тулзами, то CHESS от Microsoft не смог её найти — ограничение планировщика потоков).

Я должен отметить, что Caracrist в итоге запостил корректный алгоритм очереди, ну по-крайней мере я не вижу ошибок:
http://www.rsdn.ru/forum/src/3727286.1.aspx
Автор: Caracrist
Дата: 07.03.10

Однако алгоритм получился достаточно сложный — 6 независимых переменных состояния, плюс достаточно не эффективный — 6 Interlocked инструкций на операцию. Для сравнения аналогичный алгоритм с применением спин-мьютекса будет исполнять по 1 Interlocked инструкций на операцию, и соотв. Будет в 6 раз быстрее в случае низкой конкуренции.

В чём сложность создания таких алгоритмов? В том, что последовательность атомарных операций сама по себе не является атомарной операций, это по-прежнему разрозненная последовательность (в отличие от алгоритмов, основанных на мьютексах). Наибольшую сложность представляют промежуточные состояния структуры данных, которые возникают в процессе выполнения последовательности. Каждое такое состояние должно быть полностью целостным. Целостным в том плане, что если придёт другой поток, то он должен посмотреть на структуру; определить, что это за состояние; понять, что ему делать дальше; и при этом не порушить планы первого потока. Даже хуже — прерываний потоков может быть несколько, т.е. первый поток перевёл структуру в какое промежуточное состояние; потом пришёл второй поток, и тоже выполнил часть операции; потом пришёл третий поток, выполнил ещё несколько незаконченных действий, и т.д. И после всего этого структура всё ещё должна оставаться в понятном консистентном состоянии.
В идеале поток целиком выполняет операцию за одну атомарную операцию, т.е. считывает состояние структуры, проверяет его, вычисляет новое состояние, и пытается атомарно перевести структуру из исходного состояния в новое с помощью CAS (InterlockedCompareExchange). Так работает известный алгоритм lock-free стека:
http://www.rsdn.ru/forum/dotnet/3721740.1.aspx
Автор: remark
Дата: 01.03.10

В таком алгоритме нет промежуточных (читай — потенциально проблематичных) состояний, структура либо не модифицирована вообще, либо операция полностью выполнена.
Однако это применимо только для простейших случаев, в более сложных случаях невозможно выполнить операцию за одну атомарную операцию — как в случае с очередью на основе фиксированного буфера, тут надо и записать данные и сместить позицию записи.

Кстати, к вопросу о сложных операциях с множеством промежуточных состояний, есть такая интересная презентация Cliff Click (сейчас он работает в Azul Systems, ранее в Sun – и там и там он был ключевой фигурой в разработке JVM) о реализации полностью lock-free хэш-мап (код доступен в сети):
http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf
Представьте себе хэш-мап, в котором несколько потоков одновременно добавляют один и тот же элемент, несколько пытаются его считать, несколько удалить, и плюс одновременно с этим происходит увеличение размера таблицы. Каково? Клиф подошёл к вопросу фундаментально — он нарисовал в явном виде стейт-машину для ячейки таблицы; для каждого состояния описал как его можно определить (в смысле понять, что ячейка сейчас находится именно в этом состоянии); для каждой пары (состояние, тип операции (чтение, добавление, удаление)) описал, что потоку делать дальше; и потом реализовал все переходы между состояниями с помощью атомарных CAS.
Это если поверхностно, в реальности там много деталей и есть некоторые негативные моменты, которые он сам же внёс дабы реализовать хэш полностью без блокировок. Например, элементы никогда полностью не удаляются из таблицы, они просто помечаются как удалённые. Как следствие, даже если количество элементов в таблице остаётся постоянным, но происходят вставки и удаления элементов, ему приходится делать периодические фиктивные ресайзы таблицы, что бы «подчистить мусор». Ещё там могут быть проблематичными рекурсивные ресайзы таблицы... ну ладно, это я уже удаляюсь от темы.

Теперь обещанный бонус — алгоритм bounded multi-producer/multi-consumer очереди без блокировок. Контейнер не использует динамического выделения/управления памятью в процессе работы (за исключением изначального выделения фиксированного буфера).
Каждая операция содержит всего по 1 Interlocked инструкции, и как следствие будет достаточно быстрой.
Тут ситуация существенно попроще, чем у Клифа с его таблицей (и это к лучшему). Каждая операция (чтение/запись) состоит из 2 атомарных действий. (1) поток проверяет и резервирует элемент для чтения/записи, и (2) после выполнения фактического чтения/записи, помечает элемент как доступный для следующей операции (записи/чтения соответственно). Тут есть только одно промежуточное состояние — между (1) и (2) — которое должным образом обрабатывается.
Далее собственно код с комментариями:
template<typename T>
class mpmc_bounded_queue
{
public:
    mpmc_bounded_queue(size_t buffer_size)
        : buffer_(new cell_t [buffer_size])
        , buffer_mask_(buffer_size - 1)
    {
        typedef char assert_nothrow [__has_nothrow_assign(T) || __has_trivial_assign(T) || !__is_class(T) ? 1 : -1];
        assert((buffer_size >= 2) && ((buffer_size & (buffer_size - 1)) == 0));
        for (size_t i = 0; i != buffer_size; i += 1)
            buffer_[i].sequence_.store(i, std::memory_order_relaxed);
        enqueue_pos_.store(0, std::memory_order_relaxed);
        dequeue_pos_.store(0, std::memory_order_relaxed);
    }

    ~mpmc_bounded_queue()
    {
        delete [] buffer_;
    }

    bool enqueue(T const& data)
    {
        cell_t* cell;
        // загружаем текущую позицию для добавления в очередь
        size_t pos = enqueue_pos_.load(std::memory_order_relaxed);
        for (;;)
        {
            // находим текущий элемент
            cell = &buffer_[pos & buffer_mask_];
            // загружаем статус (sequence) текущего элемента
            size_t seq = cell->sequence_.load(std::memory_order_acquire);
            intptr_t dif = (intptr_t)seq - (intptr_t)pos;
            // элемент готов для записи
            if (dif == 0)
            {
                // пытаемся сдвинуть позицию для добавления
                if (enqueue_pos_.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed))
                    break;
                // если не получилось, то начинаем сначала
            }
            // элемент ещё не готов для записи (очередь полна или типа того)
            else if (dif < 0)
                return false;
            // нас кто-то опередил
            // перезагружаем текущий элемент и начинаем сначала
            else /* if (dif > 0) */
                pos = enqueue_pos_.load(std::memory_order_relaxed);
        }

        // в данной точке мы зарезервировали элемент для записи

        // пишем данные
        cell->data_ = data;
        // помечаем элемент как готовый для потребления
        cell->sequence_.store(pos + 1, std::memory_order_release);

        return true;
    }

    bool dequeue(T& data)
    {
        cell_t* cell;
        // загружаем текущую позицию для извлечения из очереди
        size_t pos = dequeue_pos_.load(std::memory_order_relaxed);
        for (;;)
        {
            // находим текущий элемент
            cell = &buffer_[pos & buffer_mask_];
            // загружаем статус (sequence) текущего элемента
            size_t seq = cell->sequence_.load(std::memory_order_acquire);
            intptr_t dif = (intptr_t)seq - (intptr_t)(pos + 1);
            // элемент готов для извлечения
            if (dif == 0)
            {
                // пытаемся сдвинуть позицию для извлечения
                if (dequeue_pos_.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed))
                    break;
                // если не получилось, то начинаем сначала
            }
            // элемент ещё не готов для потребления (очередь пуста или типа того)
            else if (dif < 0)
                return false;
            // нас кто-то опередил
            // перезагружаем текущий элемент и начинаем сначала
            else /* if (dif > 0) */
                pos = dequeue_pos_.load(std::memory_order_relaxed);
        }

        // в данной точке мы зарезервировали элемент для чтения

        // читаем данные
        data = cell->data_;
        // помечаем элемент как готовый для следующей записи
        cell->sequence_.store(pos + buffer_mask_ + 1, std::memory_order_release);

        return true;
    }

private:
    struct cell_t
    {
        std::atomic<size_t>     sequence_;
        T                       data_;
    };

    static size_t const         cacheline_size = 64;
    typedef char                cacheline_pad_t [cacheline_size];

    cacheline_pad_t             pad0_;
    cell_t* const               buffer_;
    size_t const                buffer_mask_;
    cacheline_pad_t             pad1_;
    std::atomic<size_t>         enqueue_pos_;
    cacheline_pad_t             pad2_;
    std::atomic<size_t>         dequeue_pos_;
    cacheline_pad_t             pad3_;

    mpmc_bounded_queue(mpmc_bounded_queue const&);
    void operator = (mpmc_bounded_queue const&);
};


И вот реализация подмножества C++0x std::atomic, необходимого для компиляции очереди (MSVC, x86-32):
#include <intrin.h>

enum memory_order
{
    memory_order_relaxed,
    memory_order_consume,
    memory_order_acquire,
    memory_order_release,
    memory_order_acq_rel,
    memory_order_seq_cst,
};

class atomic_uint
{
public:
    unsigned load(memory_order mo) const volatile
    {
        (void)mo;
        assert(mo == memory_order_relaxed
            || mo == memory_order_consume
            || mo == memory_order_acquire
            || mo == memory_order_seq_cst);
        unsigned v = val_;
        _ReadWriteBarrier();
        return v;
    }

    void store(unsigned v, memory_order mo) volatile
    {
        assert(mo == memory_order_relaxed
            || mo == memory_order_release
            || mo == memory_order_seq_cst);

        if (mo == memory_order_seq_cst)
        {
            _InterlockedExchange((long volatile*)&val_, (long)v);
        }
        else
        {
            val_ = v;
            _ReadWriteBarrier();
        }
    }

    bool compare_exchange_weak(unsigned& cmp, unsigned xchg, memory_order mo) volatile
    {
        unsigned prev = (unsigned)_InterlockedCompareExchange((long volatile*)&val_, (long)xchg, (long)cmp);
        if (prev == cmp)
            return true;
        cmp = prev;
        return false;
    }

private:
    unsigned volatile           val_;
};

template<typename T>
class atomic;

template<>
class atomic<unsigned> : public atomic_uint
{
};



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
lock-free
Re: О lock-free алгоритмах (+бонус)
От: Sni4ok  
Дата: 10.03.10 18:25
Оценка: 3 (1)
раз пошла такая пьянка, можно я свой контейнер запощу?

суть его- один поток может только писать, а много потоков при этом могут читать, контейнер может только увеличиваеться со временем, максимальный размер ограничен параметрами шаблонов, при этом память выделяется блоками как в std::deque, все итераторы дествительные ранее- остаются действительными в дальнейшем, если end() — указывал на элемент за 10м, то и когда контейнер увеличится- он будет указывать на элемент за 10м.

#include <boost/array.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/interprocess/detail/atomic.hpp>

//with follower can work one writer and many readers without synchronization
template<typename type, boost::uint32_t block_size = 16384, boost::uint32_t num_blocks = 16384>
class follower : boost::noncopyable
{
    typedef typename boost::array<type*, num_blocks> bulks_type;
    bulks_type bulks;
    mutable volatile boost::uint32_t num_elems;
public:
    follower() : num_elems(){
    }
    ~follower(){
        boost::uint32_t end_bulk = num_elems / block_size;
        boost::uint32_t end_element = num_elems % block_size;
        if(end_element)
            ++end_bulk;
        for(boost::uint32_t i = 0; i != end_bulk; ++i)
            delete[] bulks[i];
    }
    void push_back(const type& value){
        boost::uint32_t end_bulk = num_elems / block_size;
        boost::uint32_t end_element = num_elems % block_size;

        if(!end_element)
            bulks[end_bulk] = new type[block_size];

        try{
            (bulks[end_bulk])[end_element] = value;
        }
        catch(...){
            if(!end_element)
                delete bulks[end_bulk];
            throw;
        }

        boost::interprocess::detail::atomic_inc32(&num_elems);
    }
    class const_iterator :  public boost::iterator_facade<
        const_iterator, const type, boost::random_access_traversal_tag>
    {
        const bulks_type* bulks;
        boost::uint32_t element;

        friend class follower;
        friend class boost::iterator_core_access;

        void advance(boost::int32_t diff){
            element += diff;
        }
        boost::int32_t distance_to(const const_iterator& to) const{
            return to.element - element;
        }
        void increment(){
            ++element;
        }
        const type& dereference() const{ 
            boost::uint32_t end_bulk = element / block_size;
            boost::uint32_t end_element = element % block_size;
            return ((*bulks)[end_bulk])[end_element];
        }
        bool equal(const_iterator const& other) const{
            return element == other.element;
        }
        const_iterator(const bulks_type& bulks, boost::uint32_t element) : bulks(&bulks), element(element){
        }
    public:
        const_iterator(){}
    };
    const_iterator begin() const{
        return const_iterator(bulks, 0);
    }
    const_iterator end() const{
        return const_iterator(bulks, boost::interprocess::detail::atomic_read32(&num_elems));
    }
};
Re[2]: О lock-free алгоритмах (+бонус)
От: jerry_ru  
Дата: 10.03.10 19:18
Оценка:
Sni4ok wrote:

> раз пошла такая пьянка, можно я свой контейнер запощу?


Очень красиво.
Posted via RSDN NNTP Server 2.1 beta
Re[2]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 10.03.10 19:19
Оценка:
Здравствуйте, Sni4ok, Вы писали:

S>раз пошла такая пьянка, можно я свой контейнер запощу?


S>суть его- один поток может только писать, а много потоков при этом могут читать, контейнер может только увеличиваеться со временем, максимальный размер ограничен параметрами шаблонов, при этом память выделяется блоками как в std::deque, все итераторы дествительные ранее- остаются действительными в дальнейшем, если end() — указывал на элемент за 10м, то и когда контейнер увеличится- он будет указывать на элемент за 10м.


Я ошибок не вижу, по-моему, всё корректно.
Тут достаточно простой паттерн синхронизации, т.к. поток, меняющий данные, только один; нет освобождения памяти во время работы; нет переиспользования объектов.

Единственное могу добавить только про параметры block_size и num_blocks, хотя это не имеет никакого отношения к корректности. Их выбор может быть достаточно проблематичен для пользователя, и вполне возможен существенный перерасход памяти на массив bulks. Такие контейнеры (типа concurrent_vector) зачастую делают следующим образом.
Первичный массив делается маленького размера, вторичные же массивы растут по экспоненте, как степени двойки. Таким образом можно (1) полностью освободить пользователя от подбора параметров, (2) обеспечить перерасход памяти не более N/2 (как это обычно бывает для std::vector), (3) не иметь ограничения на максимальное кол-во элементов (точнее иметь возможность заюзать весь диапазон size_t как для обычных контейнеров).
Более подробно: на 32-битной системе первичный массив имеет размер всего 32, вторичные массивы — 1, 2, 4, 8... На 64-битной системе первичный массив соотв. — 64. Для оптимизации так же обычно объединяют несколько первых массивов в единый блок; т.е. если объединить 3 первых массива, то размеры будут — 7, 8, 16, 32, 64...
Конечно, если речь идёт о единичном использовании и текущая реализация устраивает, то такое изменение не имеет смысла. Если же речь идёт о более широком переиспользовании, то рекомендую.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[3]: О lock-free алгоритмах (+бонус)
От: Sni4ok  
Дата: 10.03.10 22:59
Оценка:
Здравствуйте, remark, Вы писали:

R>Первичный массив делается маленького размера, вторичные же массивы растут по экспоненте, как степени двойки.


и поллучить bad alloc'и на x86 при очень небольшом колличестве эллементов
вся прелесть вектор'а(это имхо) по сравнению с деком не то, что колличество аллокаций пропорциональна логорифму от размера(хотя это конечно само посебе неплохо, если не учитывать оверхед на неиспользуемую память), а то, что доступ к элементу просто косвенный, в отличае от двойной косвенности для дека, тут от двойной косвенности избавиться нереально(только если сразу выделить память для максимально возможного колличества элементов), поэтому экспоненциальный рост каждого следующего блока- просто вреден.
Re[4]: О lock-free алгоритмах (+бонус)
От: K13 http://akvis.com
Дата: 11.03.10 06:20
Оценка: +1
S>и поллучить bad alloc'и на x86 при очень небольшом колличестве эллементов
S>вся прелесть вектор'а(это имхо) по сравнению с деком не то, что колличество аллокаций пропорциональна логорифму от размера(хотя это конечно само посебе неплохо, если не учитывать оверхед на неиспользуемую память), а то, что доступ к элементу просто косвенный, в отличае от двойной косвенности для дека, тут от двойной косвенности избавиться нереально(только если сразу выделить память для максимально возможного колличества элементов), поэтому экспоненциальный рост каждого следующего блока- просто вреден.

не используйте std::deque если у вас фрагментированная память -- обломится.

Как минимум в MS VS, каждый блок деки очень маленький, и объектов туда влазит немного.
Зато список блоков -- этот тот же самый std::vector, вид сбоку.

Я долго не мог понять, на кой хрен деке сотня метров одним куском... пока не залез в исходники.
Re: О lock-free алгоритмах (+бонус)
От: rus blood Россия  
Дата: 11.03.10 07:39
Оценка:
Здравствуйте, remark, Вы писали:

R>Каждая операция (чтение/запись) состоит из 2 атомарных действий. (1) поток проверяет и резервирует элемент для чтения/записи, и (2) после выполнения фактического чтения/записи, помечает элемент как доступный для следующей операции (записи/чтения соответственно). Тут есть только одно промежуточное состояние — между (1) и (2) — которое должным образом обрабатывается.

R>Далее собственно код с комментариями:

Кольцевой буфер -> ограничение на кол-во элементов. Ты же сам на каком-то из форумов, то ли гугловском, то ли ibm-овском, предложил использовать набор массивов, связанных в список:
— head и tail содержат пары (указатель на массив, индекс в массиве),
— head добавляет новый массив в голову списка, если его массив полностью записан,
— tail удаляет свой массив из хвоста списка, если тот полностью прочитан.

Еще ...
R>            if (dif == 0)
R>            {
R>                // пытаемся сдвинуть позицию для добавления
R>                if (enqueue_pos_.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed))
R>                    break;
R>                // если не получилось, то начинаем сначала
А тут не надо перезачитать pos заново? 
В этой ветке pos не перезачитывается.
R>            }
Имею скафандр — готов путешествовать!
Re: О lock-free алгоритмах (+бонус)
От: AcidTheProgrammer Россия https://hts.tv/
Дата: 11.03.10 10:53
Оценка:
Здравствуйте, remark, Вы писали:

R>[пост получился достаточно длинный, поэтому сразу скажу о бонусе — это простой и эффективный алгоритм очереди на основе буфера фиксированного размера — нетерпеливые могут сразу перемещаться к концу поста ]

R> ........

А можно спросить по поводу atomic_uint, что там за "махинации" делаются с load/store и _ReadWriteBarrier? Это для чего, сам не могу пока понять.
Re[4]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 11.03.10 15:43
Оценка:
Здравствуйте, Sni4ok, Вы писали:

R>>Первичный массив делается маленького размера, вторичные же массивы растут по экспоненте, как степени двойки.


S>и поллучить bad alloc'и на x86 при очень небольшом колличестве эллементов


Каким образом? Тут неиспользуемая память не более N/2, поэтому на небольшом кол-ве элементов нельзя получить bad_alloc.


S>вся прелесть вектор'а(это имхо) по сравнению с деком не то, что колличество аллокаций пропорциональна логорифму от размера(хотя это конечно само посебе неплохо, если не учитывать оверхед на неиспользуемую память), а то, что доступ к элементу просто косвенный, в отличае от двойной косвенности для дека, тут от двойной косвенности избавиться нереально(только если сразу выделить память для максимально возможного колличества элементов), поэтому экспоненциальный рост каждого следующего блока- просто вреден.


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

Это при индексации не избежать двойной косвенности, а в случае с итерированием для сегментированного контейнера тривиально сделать одинарную косвенность и общую стоимость итерирования равной итерированию по вектору.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[2]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 11.03.10 15:50
Оценка:
Здравствуйте, AcidTheProgrammer, Вы писали:

R>>[пост получился достаточно длинный, поэтому сразу скажу о бонусе — это простой и эффективный алгоритм очереди на основе буфера фиксированного размера — нетерпеливые могут сразу перемещаться к концу поста ]

R>> ........

ATP>А можно спросить по поводу atomic_uint, что там за "махинации" делаются с load/store и _ReadWriteBarrier? Это для чего, сам не могу пока понять.


Это реализация семантики std::atomic<> для MSVC, все эти махинации для обеспечения атомарности и упорядочивания
Автор: remark
Дата: 20.11.08
.
В принципе я не могу сказать, что при удалении там любой конструкции программа может сломаться (потому что некоторые конструкции там избыточные, но тут как в поговорке — кашу маслом не испортишь), но в целом они все нужны, а как без них это сделать?


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[2]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 11.03.10 15:54
Оценка:
Здравствуйте, rus blood, Вы писали:

RB>Еще ...

RB>
R>>            if (dif == 0)
R>>            {
R>>                // пытаемся сдвинуть позицию для добавления
R>>                if (enqueue_pos_.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed))
R>>                    break;
R>>                // если не получилось, то начинаем сначала
RB>А тут не надо перезачитать pos заново? 
RB>В этой ветке pos не перезачитывается.
R>>            }
RB>


compare_exchange_weak/strong обновляют comparand актуальным значением при неудаче.
Другие интерфейсы теряют либо флаг, либо актуальное значение, а они всегда нужны оба. Это самый вразумительный интерфейс.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[5]: О lock-free алгоритмах (+бонус)
От: Sni4ok  
Дата: 11.03.10 17:56
Оценка:
Здравствуйте, remark, Вы писали:

S>>и поллучить bad alloc'и на x86 при очень небольшом колличестве эллементов


R>Каким образом? Тут неиспользуемая память не более N/2, поэтому на небольшом кол-ве элементов нельзя получить bad_alloc.


"небольшое колличество" — понятие субьективное, скажем миллиона обьектов по 40 байт — 40 мб, вполне достаточно чтобы начались сыпаться bad alloc'и, при сильной фрагментации памяти.

R>Это при индексации не избежать двойной косвенности, а в случае с итерированием для сегментированного контейнера тривиально сделать одинарную косвенность и общую стоимость итерирования равной итерированию по вектору.


тут пожалуй вы правы.
Re[3]: О lock-free алгоритмах (+бонус)
От: AcidTheProgrammer Россия https://hts.tv/
Дата: 12.03.10 08:21
Оценка:
Здравствуйте, remark, Вы писали:

R>Здравствуйте, AcidTheProgrammer, Вы писали:


R>>>[пост получился достаточно длинный, поэтому сразу скажу о бонусе — это простой и эффективный алгоритм очереди на основе буфера фиксированного размера — нетерпеливые могут сразу перемещаться к концу поста ]

R>>> ........

ATP>>А можно спросить по поводу atomic_uint, что там за "махинации" делаются с load/store и _ReadWriteBarrier? Это для чего, сам не могу пока понять.


R>Это реализация семантики std::atomic<> для MSVC, все эти махинации для обеспечения атомарности и упорядочивания
Автор: remark
Дата: 20.11.08
.

R>В принципе я не могу сказать, что при удалении там любой конструкции программа может сломаться (потому что некоторые конструкции там избыточные, но тут как в поговорке — кашу маслом не испортишь), но в целом они все нужны, а как без них это сделать?

Да я в общем и не утверждаю что не нужны, я как раз интересуюсь в чем здесь тонкие моменты, зачем нужны короче .
Re[6]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 13.03.10 14:31
Оценка:
Здравствуйте, Sni4ok, Вы писали:

S>>>и поллучить bad alloc'и на x86 при очень небольшом колличестве эллементов


R>>Каким образом? Тут неиспользуемая память не более N/2, поэтому на небольшом кол-ве элементов нельзя получить bad_alloc.


S>"небольшое колличество" — понятие субьективное, скажем миллиона обьектов по 40 байт — 40 мб, вполне достаточно чтобы начались сыпаться bad alloc'и, при сильной фрагментации памяти.


Согласен, моё дело предложить...


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[4]: Барьеры памяти
От: remark Россия http://www.1024cores.net/
Дата: 13.03.10 14:59
Оценка: 15 (5)
Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>Да я в общем и не утверждаю что не нужны, я как раз интересуюсь в чем здесь тонкие моменты, зачем нужны короче .


Они нужны для обеспечения корректного взаимного упорядочивания обращений к памяти.
Основной паттерн такой — производитель записывает данные в объект, потом записывает указатель на этот объект в разделяемую переменную, потом потребитель считывает указатель на объект из разделяемой переменной, потом считывает данные из объекта. Этот паттерн используется и в очередях производитель-потребитель, и в ленивом многопоточном синглтоне, и в разделяемом хэш-мапе.

В многопоточном окружении *не* гарантируется последовательная консистентность (sequential consistency), т.е. другие потоки могут видеть обращения к памяти не так как они записаны в программе. Причин для неправильного упорядочивания есть 2: первая — переупорядочивания компилятором, вторая — переупорядочивания процессором.

А результате этих переупорядочиваний мы можем получить следующие неприятные ситуации: производитель может записать указатель на объект в разделяемую переменную ещё до записи в него данных и/или потребитель может считать данные из объекта ещё до считывания указателя на объект. В любом случае мы получаем UB.

В алгоритмах многопоточной синхронизации необходимо обеспечивать требуемый взаимный порядок обращений к памяти явно. Для этого служат барьеры памяти (memory barrier, memory fence), в C++0x будет стандартное АПИ для этого, пока же приходится довольствоваться компиляторо-зависимым средствами (в частности _ReadWriteBarrier() подавляет переупорядочивания компилятором вокруг себя).
Вот простой пример (в терминах C++0x):
std::atomic<obj_t*> g_obj; // = 0

// producer
obj->data = 123;
g_obj.store(obj, std::memory_order_release);

// consumer
if (obj_t* obj = g_obj.load(std::memory_order_acquire))
  assert(obj->data == 123);


std::memory_order_release гарантирует (не формально), что все предыдущие обращения к памяти будут завершены до данного сохранения.
std::memory_order_acquire гарантирует, что все последующие обращения к памяти будут начаты только после завершения данной загрузки.

Недавно я отвечал на подобный вопрос:
http://software.intel.com/ru-ru/forums/showthread.php?t=72142
(там есть примеры барьеров памяти для MSVC, gcc, SUN cc).

В частности вот пример кода, на котором вы можете наблюдать переупорядочивание обращений процессором на своём многоядерном процессоре х86:
http://software.intel.com/ru-ru/forums/showpost.php?p=110773


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: О lock-free алгоритмах (+бонус)
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.03.10 19:29
Оценка:
Здравствуйте, remark, Вы писали:

R>[пост получился достаточно длинный ... ]


Дык, не мудренно! Это же почти статья.

Уважаемый! Надо было оформить ее в нашем шаблоне и прислать на сабмит. А то ведь потеряется через некоторое время. А в виде статьи ею будут еще долго люди пользоваться и тебя благодарными словами вспоминать.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: О lock-free алгоритмах (+бонус)
От: night beast СССР  
Дата: 24.03.10 06:24
Оценка:
Здравствуйте, VladD2, Вы писали:

R>>[пост получился достаточно длинный ... ]


VD>Дык, не мудренно! Это же почти статья.


VD>Уважаемый! Надо было оформить ее в нашем шаблоне и прислать на сабмит. А то ведь потеряется через некоторое время. А в виде статьи ею будут еще долго люди пользоваться и тебя благодарными словами вспоминать.


а это будет считаться публикацией в ВАК журнале?
Re[3]: О lock-free алгоритмах (+бонус)
От: VladD2 Российская Империя www.nemerle.org
Дата: 24.03.10 16:27
Оценка:
Здравствуйте, night beast, Вы писали:

NB>а это будет считаться публикацией в ВАК журнале?


Публикацией конечно считаться будет. Вопрос только в том, что ценность у нее будет сугубо практическая (т.е. не очень научная).

Вообще публикация есть публикация. Что значит считаться или нет?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 25.03.10 05:37
Оценка:
Здравствуйте, VladD2, Вы писали:

R>>[пост получился достаточно длинный ... ]


VD>Дык, не мудренно! Это же почти статья.


VD>Уважаемый! Надо было оформить ее в нашем шаблоне и прислать на сабмит. А то ведь потеряется через некоторое время. А в виде статьи ею будут еще долго люди пользоваться и тебя благодарными словами вспоминать.


В очередной раз скачал AuthPack, теперь Avira находит в нём некий ADSPY/MDH.A.60 — стрёмно...
К тому же не вижу заявленной поддержки OpenOffice, а покупать из-за этого MSOffice...


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[4]: О lock-free алгоритмах (+бонус)
От: night beast СССР  
Дата: 25.03.10 07:08
Оценка:
Здравствуйте, VladD2, Вы писали:

NB>>а это будет считаться публикацией в ВАК журнале?


VD>Публикацией конечно считаться будет. Вопрос только в том, что ценность у нее будет сугубо практическая (т.е. не очень научная).


VD>Вообще публикация есть публикация. Что значит считаться или нет?


ну я краем уха слышал, что для получения к.ф.м.н. нужно сколько-то публикаций.
так и для Дмитрия польза (если решит в аспирантуру пойти), и для народа.
Re[3]: О lock-free алгоритмах (+бонус)
От: VladD2 Российская Империя www.nemerle.org
Дата: 25.03.10 16:01
Оценка:
Здравствуйте, remark, Вы писали:

R>В очередной раз скачал AuthPack, теперь Avira находит в нём некий ADSPY/MDH.A.60 — стрёмно...


Ну, так снеси ее. Authoring Pack просто физически не менялся уже черт знает сколько времени.
Вот здесь можешь взять Authoring Pack 2. Это пока что бэта, но по возможностям она сильно удобнее и в сотни раз быстрее старой.

Она использует .Net Framework 3.5.

R>К тому же не вижу заявленной поддержки OpenOffice, а покупать из-за этого MSOffice...


Поддержки OpenOffice скорее всего вообще не будет, так как те кто им пользуются находятся в неприличном меньшинстве.

Если Офиса нет, то статью можно присылать и в каком-нибудь другом формате который можно преобразовать в вордовский. Скажем RTF или HTML.

ЗЫ

Конкретно эту мини-статья мы обработали и через некоторое время выложим. Но в следующий раз, присылай плиз на сабмит.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[5]: О lock-free алгоритмах (+бонус)
От: VladD2 Российская Империя www.nemerle.org
Дата: 25.03.10 16:11
Оценка: 2 (1)
Здравствуйте, night beast, Вы писали:

NB>ну я краем уха слышал, что для получения к.ф.м.н. нужно сколько-то публикаций.

NB>так и для Дмитрия польза (если решит в аспирантуру пойти), и для народа.

Я в этом деле не специалист, но думаю, что важно не просто наличие публикаций в ВАК-овских журналах, а наличие публикация связанных с тематикой научной работы которая лежит в основе кандидатской. К тому же на кандидата статей нужно не так много. Вот на доктора не менее шести штук (если не ошибаюсь).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Чего тут не хватает
От: rm822 Россия  
Дата: 09.04.10 11:39
Оценка: :)
Я буду исходить из реальных задач.
Ну например — есть у меня какой-то кусок работы, который я решил распараллелить с помощью OMP. Пусть у меня в нем есть vector в который я запихиваю элементы, в последовательной версии он был один, а в параллельной есть выбор
-я могу оставить его и сделать синхронизацию через criticalsection. Я знаю что один Interlocked займет тиков 70, ну плюс еще затраты на мутекс — пускай 200 тиков = 270 тиков из которых 70 не параллелятся
-могу присобачить lockfree контейнер (предположим что они у вас хорошего качества). Overhead на их использование неизвестен и неизвестно какая часть не распараллеливается в принципе
-могу использовать отдельные вектора и получить overhead только на слиянии. Конечно этим шагом я снижу распараллеливаемость, но эти затраты легко померять

Т.к. я не имею представления об оверхэде на lockfree, а тестировать подробно на разных машинах — процесс трудоемкий, то этот вариант скорее всего будет исключен из рассмотрения
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re: Чего тут не хватает
От: remark Россия http://www.1024cores.net/
Дата: 10.04.10 17:18
Оценка:
Здравствуйте, rm822, Вы писали:

R>Я буду исходить из реальных задач.

R>Ну например — есть у меня какой-то кусок работы, который я решил распараллелить с помощью OMP. Пусть у меня в нем есть vector в который я запихиваю элементы, в последовательной версии он был один, а в параллельной есть выбор
R>-я могу оставить его и сделать синхронизацию через criticalsection. Я знаю что один Interlocked займет тиков 70, ну плюс еще затраты на мутекс — пускай 200 тиков = 270 тиков из которых 70 не параллелятся
R>-могу присобачить lockfree контейнер (предположим что они у вас хорошего качества). Overhead на их использование неизвестен и неизвестно какая часть не распараллеливается в принципе
R>-могу использовать отдельные вектора и получить overhead только на слиянии. Конечно этим шагом я снижу распараллеливаемость, но эти затраты легко померять

R>Т.к. я не имею представления об оверхэде на lockfree, а тестировать подробно на разных машинах — процесс трудоемкий, то этот вариант скорее всего будет исключен из рассмотрения


И чего тут не хватает? Твоего представления о lock-free алгоритмах?
Если серьёзно, то во-первых никто и не говорит, что какое-то решение подходит для всех проблем. Т.е. постановка не понятна, ты взял какую-то конкретную проблему, и что дальше? Даже если бы ты однозначно заключил, что lock-free алгоритм для неё полностью не подходит, это бы практически ничего не говорило о применимости lock-free алгоритмов. Как говорится — "в Англии есть как минимум одна овца, белая как минимум с одного бока"
Во-вторых, lock-free алгоритм, который содержит 1 атомарную RMW инструкцию на операцию практически всего лучше аналогичного mutex-based алгоритма, т.к. спин-мьютекс всегда содержит эту же самую 1 атомарную RMW инструкцию, а не спин мьютекс будет содержать как минимум 2.
В-третьих, lock-free как таковой — это не о производительности
Автор: remark
Дата: 27.04.08
, и это не надо забывать. Lock-free — это только forward-progress и termination-safety. Наивное, но распространённое, мнение "что вот сейчас я добавлю lock-free, и всё станет быстро и масштабируемо" мягко говоря не верно. Это то же самое, что "вот сейчас я добавлю SSE оптимизации в мою пузырьковую сортировку, и она станет супер-быстрой".
А если делать упор на производительности и масштабируемости, то это несколько другая область алгоритмов, в целом они вполне могут и использовать мьютексы на каких-то путях, и обычно это затрагивает не просто какой-то компонент, а скорее симбиоз между всеми уровнями приложения, начиная с самых высоких, и до самых низких, где производительность и масштабируемость "подкрепляется" некоторыми "lock-free техниками" по необходимости.
Для конкретно твоего примера никакие специальные concurrent контейнеры не нужны, и третий вариант скорее всего самый лучший и намного лучший (тут можно обойтись вообще без мьютексов, достаточно pthread_create/pthread_join). Тем более, что фаза слияния тоже иногда распараллеливается (например, слияние в merge-sort).


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[2]: Чего тут не хватает
От: rm822 Россия  
Дата: 11.04.10 14:35
Оценка:
Здравствуйте, remark, Вы писали:

Единственное что меня интересовало "Зато большинство lock-free алгоритмов ..... будут содержать больше тяжелых атомарных операций (2-5)."
Про все остальное — я в курсе, так что не переживайте — неправильно готовить я их не буду
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[3]: Чего тут не хватает
От: remark Россия http://www.1024cores.net/
Дата: 11.04.10 15:08
Оценка:
Здравствуйте, rm822, Вы писали:

R>Единственное что меня интересовало "Зато большинство lock-free алгоритмов ..... будут содержать больше тяжелых атомарных операций (2-5)."

R>Про все остальное — я в курсе, так что не переживайте — неправильно готовить я их не буду

Подожди, ты говорил только о скорости, тогда зачем тебе lock-free? Какая разница сколько там атомарных операций? Эти алгоритмы делаются не для скорости.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[4]: Чего тут не хватает
От: rm822 Россия  
Дата: 11.04.10 18:37
Оценка:
Здравствуйте, remark, Вы писали:

R>Подожди, ты говорил только о скорости, тогда зачем тебе lock-free? Какая разница сколько там атомарных операций? Эти алгоритмы делаются не для скорости.

С чего ты взял что не для скорости?

В условиях той задачи что я описал — скажем если merge займет 10% и не параллелиться (или параллелить его слишком сложно) от последовательного алгоритма, то на 16 процах я получу
10% + (100-10)/16 = ~16% времени т.е. скейл в 6-7 раз а не в 16

в услових lock-free и полного параллелизма
100/16 + х = 6.25% + х, где х — затраты на lockfree

т.е. в условиях 16 процов lockfree очень даже может быть выгоден,
а 5 атомарных операций как раз и дают мне оценку предела масштабирования

PS: ты случаем не с интеля?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[5]: Чего тут не хватает
От: remark Россия http://www.1024cores.net/
Дата: 12.04.10 11:07
Оценка:
Здравствуйте, rm822, Вы писали:

R>>Подожди, ты говорил только о скорости, тогда зачем тебе lock-free? Какая разница сколько там атомарных операций? Эти алгоритмы делаются не для скорости.

R>С чего ты взял что не для скорости?

R>В условиях той задачи что я описал — скажем если merge займет 10% и не параллелиться (или параллелить его слишком сложно) от последовательного алгоритма, то на 16 процах я получу

R>10% + (100-10)/16 = ~16% времени т.е. скейл в 6-7 раз а не в 16

R>в услових lock-free и полного параллелизма

R>100/16 + х = 6.25% + х, где х — затраты на lockfree

R>т.е. в условиях 16 процов lockfree очень даже может быть выгоден,

R>а 5 атомарных операций как раз и дают мне оценку предела масштабирования

Может быть и так.
Хотя обычно ситуация несколько сложнее: во-первых, нераспараллеливаемая часть зачастую тоже зависит от N, т.е. может составлять например для mergesort (1/k*logN) (т.е. уменьшается в ростом размерности задачи), во-вторых оверхед решения с разделяемым контейнером тоже будет зависеть от размерности, т.е. будет "100/16 + 100/х". Ну ладно, это всё детали.
Всё равно не понятно при чём тут lock-free. В случае с разделяемым контейнером тебе опять же нужен просто *быстрый* контейнер, а не lock-free контейнер. Контейнер, основанный на мьютексе, может быть просто быстрее при низкой конкуренции; а при высокой и lock-free контейнер начнёт так же отвратительно деградировать.
Хотя, конечно, может так случиться, что lock-free контейнер будет и быстрее. Но в общем случае QoS медленне best-effort, а real-time медленнее не real-time, т.к. им приходится обеспечивать дополнительные гарантии.

з.ы. ради справедливости надо отметить, что очередь в первом посте тоже не lock-free, она скорее больше ориентируется на скорость... насколько это возможно для MP/MC очереди.

R>PS: ты случаем не с интеля?


Нет, я сам по себе.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: О lock-free алгоритмах (+бонус)
От: Мишень-сан  
Дата: 20.07.10 05:55
Оценка:
Здравствуйте, remark, Вы писали:

[skipped]

Не подскажете, а можно ли в этой очереди применять не-POS элементы (при условии, что чтение.запись осуществляются достаточно быстро)? Например, класть в очередь смартпоинтеры?
Собственно смущает __has_trivial_assign(T). Если это такой вариант защиты от исключений, то приличный смартпоинтер вроде как гарантирует логикой работы отсутствие исключений при захвате владения.

Спасибо.
Re[2]: О lock-free алгоритмах (+бонус)
От: Мишень-сан  
Дата: 20.07.10 05:58
Оценка:
Здравствуйте, Мишень-сан, Вы писали:

МС>Здравствуйте, remark, Вы писали:


МС>[skipped]


МС>Не подскажете, а можно ли в этой очереди применять не-POS элементы (при условии, что чтение.запись осуществляются достаточно быстро)? Например, класть в очередь смартпоинтеры?

МС>Собственно смущает __has_trivial_assign(T). Если это такой вариант защиты от исключений, то приличный смартпоинтер вроде как гарантирует логикой работы отсутствие исключений при захвате владения.

МС>Спасибо.


А, извиняюсь, прозевал, что там или nothrow, или тривиальный конструктор, или POD, а не всё вместе.
Тогда такой вопрос: насколько сильно может нарушить работу очереди вызов деструктора для изымаемого объекта?
Re[3]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 20.07.10 07:27
Оценка:
Здравствуйте, Мишень-сан, Вы писали:

МС>>Не подскажете, а можно ли в этой очереди применять не-POS элементы (при условии, что чтение.запись осуществляются достаточно быстро)? Например, класть в очередь смартпоинтеры?

МС>>Собственно смущает __has_trivial_assign(T). Если это такой вариант защиты от исключений, то приличный смартпоинтер вроде как гарантирует логикой работы отсутствие исключений при захвате владения.

МС>А, извиняюсь, прозевал, что там или nothrow, или тривиальный конструктор, или POD, а не всё вместе.

МС>Тогда такой вопрос: насколько сильно может нарушить работу очереди вызов деструктора для изымаемого объекта?


В этой очереди можно сделать частичную поддержать исключений следующим образом. Если исключение происходит при добавлении элемента, то помечаем ячейку специальным флажком. Если при извлечении элемента мы обнаруживаем этот флажок, то помечаем ячейку как потребленную и пробуем извлечь элемент снова. Однако если исключение происходит при копировании во время извлечения элемента, то нам ничего не останется как просто "проигнорировать" этот элемент (т.е. он по-тихому потеряется). Так работает tbb::concurrent_queue.
Изначально я не хотел затуманивать алгоритм этой логикой. Да и в целом считаю, что передавать объекты, которые кидают, и в частности смарт-поинтеры — это не особо нужная затея. Обычно передают или поинтеры или POD структуры.
Хотя в C++0x это можно будет решить и элегантно и эффективно одновременно с помощью move semantics (это как раз то, что доктор прописал — мы же хотим *передать* элемент).



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: О lock-free алгоритмах (+бонус)
От: ilnar Россия  
Дата: 13.08.10 10:51
Оценка:
Здравствуйте, remark, Вы писали:

R>Теперь обещанный бонус — алгоритм bounded multi-producer/multi-consumer очереди без блокировок. Контейнер не использует динамического выделения/управления памятью в процессе работы (за исключением изначального выделения фиксированного буфера).


а нет ли у тебя случаем lock-free FIFO очереди (с фиксированной длиной) для случая single-producer, single-consumer?
или может есть реализация atomic_uint для linux?
Re: О lock-free алгоритмах (+бонус)
От: fddima  
Дата: 04.09.10 10:17
Оценка:
Здравствуйте, remark, Вы писали:

R>Это если поверхностно, в реальности там много деталей и есть некоторые негативные моменты, которые он сам же внёс дабы реализовать хэш полностью без блокировок. Например, элементы никогда полностью не удаляются из таблицы, они просто помечаются как удалённые. Как следствие, даже если количество элементов в таблице остаётся постоянным, но происходят вставки и удаления элементов, ему приходится делать периодические фиктивные ресайзы таблицы, что бы «подчистить мусор». Ещё там могут быть проблематичными рекурсивные ресайзы таблицы... ну ладно, это я уже удаляюсь от темы.

Маленькая запоздалая поправочка — помечать удалённые элементы специальным образом, вызвано тем, что Клиф использует хэш таблицу с открытой адресацией и только.
Re: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 22.10.10 11:04
Оценка:
Здравствуйте, remark, Вы писали:

Сорри, что вытаскиваю старый топик, надеюсь remark подписан на него, вопрос больше к нему.

R>Теперь обещанный бонус — алгоритм bounded multi-producer/multi-consumer очереди без блокировок.


Я еще не полностью разобрался с алгоритмом, но закрались подозрения: enqueue_pos_, sequence_, dequeue_pos_ постоянно увеличиваются (если я ничего не пропустил), правильно ли я понимаю, что в алгоритме есть ограничение на число операций enqueue, dequeue ведь size_t не бесконечен?
Re[2]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 22.10.10 11:07
Оценка:
Здравствуйте, vf, Вы писали:

vf>Я еще не полностью разобрался с алгоритмом, но закрались подозрения: enqueue_pos_, sequence_, dequeue_pos_ постоянно увеличиваются (если я ничего не пропустил), правильно ли я понимаю, что в алгоритме есть ограничение на число операций enqueue, dequeue ведь size_t не бесконечен?


Ограничений нет, они просто переполнятся в 0, и это должно быть корректно обработано алгоритмом.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[2]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 22.10.10 11:07
Оценка:
Здравствуйте, fddima, Вы писали:

F> Маленькая запоздалая поправочка — помечать удалённые элементы специальным образом, вызвано тем, что Клиф использует хэш таблицу с открытой адресацией и только.


Очевидно, что это не так. Однопоточные таблицы с открытой адресацией таких проблем не имеют.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[3]: О lock-free алгоритмах (+бонус)
От: fddima  
Дата: 22.10.10 11:25
Оценка:
Здравствуйте, remark, Вы писали:

R>Очевидно, что это не так. Однопоточные таблицы с открытой адресацией таких проблем не имеют.

R>
Имеют-имеют, когда у нас есть операция удаления. Если удалённый элемент сбросить в пустой, то мы можем разорвать цепочку коллизий, и поиск поломается.
Re[4]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 22.10.10 11:40
Оценка:
Здравствуйте, fddima, Вы писали:

F>Здравствуйте, remark, Вы писали:


R>>Очевидно, что это не так. Однопоточные таблицы с открытой адресацией таких проблем не имеют.

R>>
F> Имеют-имеют, когда у нас есть операция удаления. Если удалённый элемент сбросить в пустой, то мы можем разорвать цепочку коллизий, и поиск поломается.

Там мы можем элементарно переместить последний элемент из цепочки на место удаляемого, а тут не может.
Любой разумный однопоточный алгоритм не будет делать периодические ресайзы, только что бы "почистить" неиспользуемые ячейки.
Ну а уж как рекурсивные ресайзы связаны с открытой адресацией я совсем не вижу. Рекурсивный ресайз означает, что при поиске потоку потенциально надо пройти по цепочке из N старых таблиц, что бы найти самую последнюю (АФАИК).


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: О lock-free алгоритмах (+бонус)
От: Lexey Россия  
Дата: 22.10.10 11:59
Оценка:
Здравствуйте, remark, Вы писали:

R>    struct cell_t
R>    {
R>        std::atomic<size_t>     sequence_;
R>        T                       data_;
R>    };


Вопрос: а не будет ли тут false sharing'а при такой структуре элемента очереди? Может в нее тоже стоит выравнивание до размера линии кэша добавить?
"Будь достоин победы" (c) 8th Wizard's rule.
Re[5]: О lock-free алгоритмах (+бонус)
От: fddima  
Дата: 22.10.10 12:02
Оценка:
Здравствуйте, remark, Вы писали:

R>Там мы можем элементарно переместить последний элемент из цепочки на место удаляемого, а тут не может.

Ммм... не уверен, что можем, по крайней мере это не просто. Последний элемент в цепочке коллизий вполне может быть элементом на своём месте. Или элементом с предыдущих позиций. Имхо, проще метить как удалённый.

R>Любой разумный однопоточный алгоритм не будет делать периодические ресайзы, только что бы "почистить" неиспользуемые ячейки.

R>Ну а уж как рекурсивные ресайзы связаны с открытой адресацией я совсем не вижу. Рекурсивный ресайз означает, что при поиске потоку потенциально надо пройти по цепочке из N старых таблиц, что бы найти самую последнюю (АФАИК).
Опять же, имхо, но реализация Клифа настолько не прозрачна... оптимизации все эти я думаю он сделал исходя из практики, а не каких-то аналитических заключений. Без доступа к такому железу самому что-то подобное написать — нереально.

PS: Мои изыскания (для C#) показали, что lock-free hashtable с separate chaining для небольших таблиц оказывается быстрее, чем открытая адресация. Но потом открытая конечно рвёт всех. =)

Re[2]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 22.10.10 12:04
Оценка:
Здравствуйте, Lexey, Вы писали:

L>
R>>    struct cell_t
R>>    {
R>>        std::atomic<size_t>     sequence_;
R>>        T                       data_;
R>>    };
L>


L>Вопрос: а не будет ли тут false sharing'а при такой структуре элемента очереди? Может в нее тоже стоит выравнивание до размера линии кэша добавить?


Не будет ли тут false sharing'а при каких обращениях к каким элементам?


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[3]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 22.10.10 12:05
Оценка:
Здравствуйте, remark, Вы писали:

vf>>Я еще не полностью разобрался с алгоритмом, но закрались подозрения: enqueue_pos_, sequence_, dequeue_pos_ постоянно увеличиваются (если я ничего не пропустил), правильно ли я понимаю, что в алгоритме есть ограничение на число операций enqueue, dequeue ведь size_t не бесконечен?


R>Ограничений нет, они просто переполнятся в 0, и это должно быть корректно обработано алгоритмом.


Мне кажется вот этом месте будет первое переполнение:

R> bool dequeue(T& data)

R> {
R> ...
R> // помечаем элемент как готовый для следующей записи
R> cell->>sequence_.store(pos + buffer_mask_ + 1, std::memory_order_release);
R> return true;
R> }

Пусть массив будет из 8 элементов, а переполнение происходит при 15 + 1 -> 0
Тогда cell[].sequence должно выглядить примерно так, после записи нуля после переполнения:

[12] [13] [14] [15] [ 0] [ 9] [10] [11]
enqueue---------||
dequeue-------------------||


Но тогда, вот здесь при добавлении элемента:


 bool dequeue(T& data)
    {
..
        for (;;)
        {
...
            intptr_t dif = (intptr_t)seq - (intptr_t)(pos + 1); - будет всегда больше нуля
            if (dif == 0)
            {
            }
            else if (dif < 0)
                return false;
            // нас кто-то опередил
            // перезагружаем текущий элемент и начинаем сначала
            else /* if (dif > 0) */
                pos = dequeue_pos_.load(std::memory_order_relaxed);
        }
...
    }
Re[4]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 22.10.10 12:09
Оценка:
Я тут немного понапутал с кусками кода, но думаю идея понятна. Вторым шагом после переполнения, конечно же должно идти добавление элемента.
Re[3]: О lock-free алгоритмах (+бонус)
От: Lexey Россия  
Дата: 22.10.10 12:14
Оценка:
Здравствуйте, remark, Вы писали:

R>Не будет ли тут false sharing'а при каких обращениях к каким элементам?


Как это видится мне:
Есть два потока на разных ядрах — один кладет, другой вынимает. Первый положил элемент A в очередь, второй начал его вынимать, первый в этот момент кладет следующий B. Поскольку A и B попадают в одну линию кэша, запись B инвалидирует кэш и A будет читаться из памяти. Фолз шаринг в чистом виде.
"Будь достоин победы" (c) 8th Wizard's rule.
Re[4]: О lock-free алгоритмах (+бонус)
От: Lexey Россия  
Дата: 22.10.10 12:19
Оценка:
Здравствуйте, vf, Вы писали:

vf>Пусть массив будет из 8 элементов, а переполнение происходит при 15 + 1 -> 0


Э... будет 16. Откуда переполнение? Какие-то проблемы с переполнением там могут замаячить разве что при размере контейнера > 2**31. Но для этого еще и понадобиться сопоставимое число потоков. :D
"Будь достоин победы" (c) 8th Wizard's rule.
Re[6]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 22.10.10 12:22
Оценка:
Здравствуйте, fddima, Вы писали:

R>>Там мы можем элементарно переместить последний элемент из цепочки на место удаляемого, а тут не может.

F> Ммм... не уверен, что можем, по крайней мере это не просто. Последний элемент в цепочке коллизий вполне может быть элементом на своём месте. Или элементом с предыдущих позиций. Имхо, проще метить как удалённый.

В Hopscotch авторы это делают. При удалениях они всегда "уплотняют" таблицу так что бы элементы находились ближе (желательнов той же кэш-линии), что и рассчётное значение.


R>>Любой разумный однопоточный алгоритм не будет делать периодические ресайзы, только что бы "почистить" неиспользуемые ячейки.

R>>Ну а уж как рекурсивные ресайзы связаны с открытой адресацией я совсем не вижу. Рекурсивный ресайз означает, что при поиске потоку потенциально надо пройти по цепочке из N старых таблиц, что бы найти самую последнюю (АФАИК).
F> Опять же, имхо, но реализация Клифа настолько не прозрачна... оптимизации все эти я думаю он сделал исходя из практики, а не каких-то аналитических заключений.

Это не оптимизации, это побочные эффекты чистого lock-free. В TBB или Hopscotch concurrent кэштаблицах такой фигни нет.

F>Без доступа к такому железу самому что-то подобное написать — нереально.


Именно. Он делал алгоритм именно под своё железо с бесплатным uncontented CAS, только там он быстро и работает. А если ты будешь делать на x86, то у тебя получится другой алгоритм.



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[5]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 22.10.10 12:28
Оценка:
Здравствуйте, vf, Вы писали:

vf>Я тут немного понапутал с кусками кода, но думаю идея понятна. Вторым шагом после переполнения, конечно же должно идти добавление элемента.


Я не могу понять на каком элементе и когда будут проблемы.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[5]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 22.10.10 12:32
Оценка:
Здравствуйте, Lexey, Вы писали:

L>Здравствуйте, vf, Вы писали:


vf>>Пусть массив будет из 8 элементов, а переполнение происходит при 15 + 1 -> 0


L>Э... будет 16. Откуда переполнение? Какие-то проблемы с переполнением там могут замаячить разве что при размере контейнера > 2**31.


Я же написал "пусть", причем здесь размер контейнера когда "индексы" инкрементируются при каждой операции.
Re[7]: О lock-free алгоритмах (+бонус)
От: fddima  
Дата: 22.10.10 12:40
Оценка:
Здравствуйте, remark, Вы писали:

R>В Hopscotch авторы это делают. При удалениях они всегда "уплотняют" таблицу так что бы элементы находились ближе (желательнов той же кэш-линии), что и рассчётное значение.

Клёва.
Меня в своё время интересовала таблица без возможности удаления (атомизация объектов) — так что вопросом удаления не сильно был озабочен. Если удаление и происходит то только вместе со всей таблицей.

F>>Без доступа к такому железу самому что-то подобное написать — нереально.

R>Именно. Он делал алгоритм именно под своё железо с бесплатным uncontented CAS, только там он быстро и работает. А если ты будешь делать на x86, то у тебя получится другой алгоритм.
А можно по подробнее?
Для x86 я так понимаю ж ведь суть та же ж:
— читаем и проверям что прочитанные данные консистенты
— пишем через Interlocked (где нужно)
Re[6]: О lock-free алгоритмах (+бонус)
От: Lexey Россия  
Дата: 22.10.10 12:41
Оценка:
Здравствуйте, vf, Вы писали:

vf>Я же написал "пусть", причем здесь размер контейнера когда "индексы" инкрементируются при каждой операции.


Пусть у бабушки будет X, тогда это будет дедушка. Какое отношение твое "пусть" имеет к реальности? В алгоритме sequence number — это size_t. 2**32 на x86.
"Будь достоин победы" (c) 8th Wizard's rule.
Re[6]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 22.10.10 12:49
Оценка:
Здравствуйте, remark, Вы писали:

Пусть массив будет из 8 элементов, а переполнение происходит при 15 + 1 -> 0

Пусть будет вот такое состояния массива cell[].sequence, на некотором шаге:

То есть, если я правильно понял, то enqueue_pos_ & buffer_mask_ показывает на элемент в который будет писать. Сейчас enqueue сделать нельзя, мы догнали хвост (dif меньше нуля).

[12] [13] [14] [15] [ 8] [ 9] [10] [11]
enqueue--------------||
dequeue--------------||


Делаем dequeue, произошло переполнение, записали 0 вместо 16.

[12] [13] [14] [15] [ 0] [ 9] [10] [11]
enqueue--------------||
dequeue-------------------||


Но и сейчас enqueue сделать нельзя, ошибка?
Re[7]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 22.10.10 12:49
Оценка:
Здравствуйте, Lexey, Вы писали:

vf>>Я же написал "пусть", причем здесь размер контейнера когда "индексы" инкрементируются при каждой операции.


L>Пусть у бабушки будет X, тогда это будет дедушка. Какое отношение твое "пусть" имеет к реальности? В алгоритме sequence number — это size_t. 2**32 на x86.


2**4, 2**32 или 2**64 ничего принципиально не меняет, с 2**4 просто проще, т.к. не надо манипулировать числами типа 18446744073709551615.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[7]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 22.10.10 12:55
Оценка:
Здравствуйте, vf, Вы писали:

vf>Пусть массив будет из 8 элементов, а переполнение происходит при 15 + 1 -> 0


vf>Пусть будет вот такое состояния массива cell[].sequence, на некотором шаге:


vf>То есть, если я правильно понял, то enqueue_pos_ & buffer_mask_ показывает на элемент в который будет писать. Сейчас enqueue сделать нельзя, мы догнали хвост (dif меньше нуля).


vf>
vf>[12] [13] [14] [15] [ 8] [ 9] [10] [11]
vf>enqueue--------------||
vf>dequeue--------------||
vf>


vf>Делаем dequeue, произошло переполнение, записали 0 вместо 16.


vf>
vf>[12] [13] [14] [15] [ 0] [ 9] [10] [11]
vf>enqueue--------------||
vf>dequeue-------------------||
vf>


vf>Но и сейчас enqueue сделать нельзя, ошибка?


У нас же enqueue сейчас тоже равен 0. 0-0=0, значит можно добавлять.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[7]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 22.10.10 12:58
Оценка:
Здравствуйте, Lexey, Вы писали:

vf>>Я же написал "пусть", причем здесь размер контейнера когда "индексы" инкрементируются при каждой операции.


L>Пусть у бабушки будет X, тогда это будет дедушка. Какое отношение твое "пусть" имеет к реальности? В алгоритме sequence number — это size_t. 2**32 на x86.


Отношение прямое, выше я написал:

vf>>"индексы" инкрементируются при каждой операции.


То есть связано не с кол-во элементов, а с кол-во операций.

Че за беспонтовые дое..ки я мог бы в примере использовать 0xffffffff, смысл не меняется, читать не удобно?!
Re[8]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 22.10.10 12:58
Оценка:
Здравствуйте, remark, Вы писали:

R>У нас же enqueue сейчас тоже равен 0. 0-0=0, значит можно добавлять.


Они же все вместе переполняются. enqueue был равен 15, seq элемента был 15, положили в него элемент. Теперь seq переполнился в 0, и enqueue переполнился в 0.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[9]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 22.10.10 13:35
Оценка:
Здравствуйте, remark, Вы писали:

R>Они же все вместе переполняются. enqueue был равен 15, seq элемента был 15, положили в него элемент. Теперь seq переполнился в 0, и enqueue переполнился в 0.


Да, спасибо.
Re[8]: О lock-free алгоритмах (+бонус)
От: Lexey Россия  
Дата: 22.10.10 16:53
Оценка:
Здравствуйте, vf, Вы писали:

vf>Че за беспонтовые дое..ки я мог бы в примере использовать 0xffffffff, смысл не меняется, читать не удобно?!


Это не дое..ки. Переполнение в твоей модели абсолютно безвредно с любым модулем. Но для малых модулей там возможны гораздо более интересные эффекты, которые практически невозможны для больших (и, снижая размерность, ты их фактически вносишь). Правда, при размере буфера, равном степени двойки (и, соответственно, при модуле равном степени двойки) они невозможны и для малых модулей. Кстати, из этих соображений assert лучше бы сделать нормальной проверкой, чтобы он работал не только в дебаге, но и в релизе.
"Будь достоин победы" (c) 8th Wizard's rule.
Re[9]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 22.10.10 20:38
Оценка:
Здравствуйте, Lexey, Вы писали:

vf>>Че за беспонтовые дое..ки я мог бы в примере использовать 0xffffffff, смысл не меняется, читать не удобно?!


L>Но для малых модулей там возможны гораздо более интересные эффекты, которые практически невозможны для больших (и, снижая размерность, ты их фактически вносишь). Правда, при размере буфера, равном степени двойки (и, соответственно, при модуле равном степени двойки) они невозможны и для малых модулей. Кстати, из этих соображений assert лучше бы сделать нормальной проверкой, чтобы он работал не только в дебаге, но и в релизе.


Я разбираюсь с алгоритмом, увидел случай который мне показался подозрительным, попытался продемонстрировать когда может возникать, использовал разумные упрощения и допущения. О чем ты споришь???? Я что предлагал в программе заменить size_t на что-то еще?!

>Но для малых модулей там возможны гораздо более интересные эффекты, которые практически невозможны для больших (и, снижая размерность, ты их фактически вносишь)


Там нет таких случаев, если ты про ABA. Я ничего не вношу уменьшая модуль, по крайней мере я не нашел, может ты обоснуешь то что утверждаешь, примером? Возьми минимальные модуль и покажи как это негативно отразилось на алгоритме? А то бла-бла-бла...
Re: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 23.10.10 11:51
Оценка:
Здравствуйте, remark, Вы писали:

Начну новую ветку чтобы не путать с другим неверным подозрением связаным с переполнением.

Чем больше разбираюсь тем больше мне алгоритм нра, он компактный, красивый, очень хорошо вписывается под мою задачу/требования. Есть большое желание его использовать.

Два попутных вопроса:
1. А кто автор алгоритма, Вы?
2. Нет ли c# версии? Я его конечно переписал на шарп, но где-то видать накосячил, не взлетело (хотя в одном потоке работает).

Основной вопрос:

Возможна ли следующая ситуация:

Вызвали конструктор, имеем пустую очередь, и инициализированый след. образом seq массив:

enqueue = 0 
dequeue = 0
<0> <1> <2> <3>....


Первый поток начинает добавлять элемент, инкрементировал enqueue, но не успел обновить seq[0] — заснул. Имеем след. картину:

enqueue = 1
dequeue = 0
<0> <1> <2> <3>....


Второй поток добавляет след.элемент, получаем ([2] — скобками показываю что даже данные положили):

enqueue = 2
dequeue = 0
<0> [2] <2> <3>....


Сейчас в очереди имеется один элемент, пытаемся его вытащить, во втором потоке, первый поток все еще спит.

dequeue = 0
seq[0] == 0

а значит, нижний код вернет в dif==-1, и dequeue() false как будто элементов в очереди нет, но ведь он есть!

intptr_t dif = (intptr_t)seq - (intptr_t)(pos + 1);
Re[4]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 23.10.10 17:06
Оценка: 3 (1)
Здравствуйте, Lexey, Вы писали:

L>Есть два потока на разных ядрах — один кладет, другой вынимает. Первый положил элемент A в очередь, второй начал его вынимать, первый в этот момент кладет следующий B. Поскольку A и B попадают в одну линию кэша, запись B инвалидирует кэш и A будет читаться из памяти. Фолз шаринг в чистом виде.


С одной стороны — да, с другой — нет.
То, как ты описываешь, действительно имеет место быть. Однако, если разнести все элементы очереди в разные кэш линии, то получим свои негативные моменты. Если поток кладёт в очередь несколько элементов, то теперь ему надо будет модифицировать несколько кэш линий. Аналогично для потока, который достаёт элементы. Ну и в целом, на Н элементов будет передаваться Н кэш линий в лучшем случае, при плотной же укладке элементов — Н/К линий.
Я думаю, что можно подобрать такие синтетические тесты, где будет лучше и один вариант и другой. Однако на своих тестах я обычно наблюдаю, что плотная укладка элементов получается лучше. Хотя в целом окончательный ответ ты можешь получить только попробовав оба варианта в твоей программе.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[2]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 23.10.10 17:08
Оценка:
Здравствуйте, vf, Вы писали:

vf>Начну новую ветку чтобы не путать с другим неверным подозрением связаным с переполнением.


vf>Чем больше разбираюсь тем больше мне алгоритм нра, он компактный, красивый, очень хорошо вписывается под мою задачу/требования. Есть большое желание его использовать.


vf>Два попутных вопроса:

vf>1. А кто автор алгоритма, Вы?

Да.

vf>2. Нет ли c# версии?


Я его не портировал на c#.

vf>Я его конечно переписал на шарп, но где-то видать накосячил, не взлетело (хотя в одном потоке работает).


Код в студию!


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[2]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 23.10.10 17:17
Оценка:
Здравствуйте, vf, Вы писали:

vf>Основной вопрос:

vf>Возможна ли следующая ситуация:
vf>а значит, нижний код вернет в dif==-1, и dequeue() false как будто элементов в очереди нет, но ведь он есть!

Ситуация полностью возможна. Но элемента тут в очереди ещё нет. Элемент есть в очереди [по-определению] когда производитель установил seq соотв. образом.
В теории concurrent структур данных есть такое понятие как Linearizability, и в частности Linearization point. В данном алгоритме Linearization point функции enqueue() по отношению к потребителям есть как раз модификация seq элемента. После этого момента операция считается полностью вступившей в силу. До этого же она соотв. не вступившая в силу, и все модификации надо рассматривать только как некоторые внутренние детали алгоритма.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[3]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 23.10.10 17:45
Оценка:
Здравствуйте, remark, Вы писали:

vf>>Основной вопрос:

vf>>Возможна ли следующая ситуация:
vf>>а значит, нижний код вернет в dif==-1, и dequeue() false как будто элементов в очереди нет, но ведь он есть!

R>Ситуация полностью возможна. Но элемента тут в очереди ещё нет. Элемент есть в очереди [по-определению] когда производитель установил seq соотв. образом.


Я имел ввиду элемент добавленный вторым потоком, для него seq установлен, и функция enqueue полностью отработана. То есть меня волнует следующее развитие событий, допустим каждый поток кладет и берет один элемент в очередь в цикле, и если выше приведенная ситуация возможно, то выходит что поток положил элемент, но при попытке вытащить получает не обоснованные облом, потому что хотя бы один(его) элемент в очереди точно присутствует.

R>В теории concurrent структур данных есть такое понятие как Linearizability, и в частности Linearization point. В данном алгоритме Linearization point функции enqueue() по отношению к потребителям есть как раз модификация seq элемента.


Спасибо за ссылку, но мне кажется (я еще не вчитывался), что это не объясняет, повторюсь получается что операция над первым элементом мешает обращаться ко второму, для которого enqueue полностью отработала и linearization point пройдена, как я понимаю?
Re[4]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 24.10.10 06:14
Оценка:
Здравствуйте, vf, Вы писали:

R>>Ситуация полностью возможна. Но элемента тут в очереди ещё нет. Элемент есть в очереди [по-определению] когда производитель установил seq соотв. образом.


vf>Я имел ввиду элемент добавленный вторым потоком, для него seq установлен, и функция enqueue полностью отработана. То есть меня волнует следующее развитие событий, допустим каждый поток кладет и берет один элемент в очередь в цикле, и если выше приведенная ситуация возможно, то выходит что поток положил элемент, но при попытке вытащить получает не обоснованные облом, потому что хотя бы один(его) элемент в очереди точно присутствует.


Извиняюсь — невнимательно прочитал.
Да, такая фигня тоже возможна. Т.е. это — *не* lock-free очередь. Терминология в этой области полностью не установлена, зачастую это называют non-blocking, хотя фактически очередь блокирующая — вот такой "зависший" производитель будет блокировать прогресс потребителей. Однако стоит отметить, что очередь на мьютексах будет гораздо хуже, т.к. "зависший" под мьютексом поток будет блокировать все операции. Тут же зависший производитель будет блокировать только потребителей, и только когда они вытащят все предыдущие элемента (т.е. пока они не дошли до этого проблемного элемента, они могут свободно потреблять другие элементы; а когда они дойдут до этого, возможно, он уже будет и полностью положен в очередь). Так же зависший производитель не блокирует других производителей (пока очередь не полностью заполнена), что достаточно приятно по сравнению с мьютексами. И такая же зеркальная ситуация будет для "зависшего" потребителя.
Что бы такого не было совсем нужно использовать lock-free очередь. Однако lock-free очередь скорее всего будет медленнее — за дополнительные гарантии надо платить.
Вывод такой. Если тебе нужны гарантии forward progress
Автор: remark
Дата: 27.04.08
(например, для hard real-time системы), то надо использовать lock-free/wait-free. Однако я не знаю даже lock-free алгоритма для array-bases multi-producer/multi-consumer очереди. И при этом она скорее всего будет медленнее работать.
Если тебе нужна просто производительность (например, для throughput-oriented сервера), то нужно использовать что-то типа очереди, приведённой в этом топике. Она не даёт строгих гарантий прогресса, однако быстрая.
Мьютексы же оказываются не у дел, т.к. не дают ни производительности, ни гарантий прогресса.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[5]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 24.10.10 07:41
Оценка:
Здравствуйте, remark, Вы писали:

vf>>Я имел ввиду элемент добавленный вторым потоком, для него seq установлен, и функция enqueue полностью отработана. То есть меня волнует следующее развитие событий, допустим каждый поток кладет и берет один элемент в очередь в цикле, и если выше приведенная ситуация возможно, то выходит что поток положил элемент, но при попытке вытащить получает не обоснованные облом, потому что хотя бы один(его) элемент в очереди точно присутствует.


R>Да, такая фигня тоже возможна. Т.е. это — *не* lock-free очередь. Терминология в этой области полностью не установлена, зачастую это называют non-blocking, хотя фактически очередь блокирующая — вот такой "зависший" производитель будет блокировать прогресс потребителей. Однако стоит отметить, что очередь на мьютексах будет гораздо хуже, т.к. "зависший" под мьютексом поток будет блокировать все операции. Тут же зависший производитель будет блокировать только потребителей


Если бы производитель блокировал, он же не блокирует, потребителю очередь скажет что элементов нет, хотя их там может быть несколько. Так чтобы в статистику не уходить (хотя я все таки считаю что для большинства случаев это недопустимое поведение), конктретно в моей задача, это принципиальный момент, я буду создавать(уничтожать) лишний элемент когда не смогу его взять(положить) в очередь, а это тянет за собой работу GC для "старых" объектов, и тут большой вопрос что будет выгоднее тот же mutex(хотя есть и другие варианты) или работа GC.

R>Однако я не знаю даже lock-free алгоритма для array-bases multi-producer/multi-consumer очереди. И при этом она скорее всего будет медленнее работать.


Вот я находил, там по два CAS на добавление и один на получение элемента. Еще не пробовал реализовать.

R>Если тебе нужна просто производительность (например, для throughput-oriented сервера), то нужно использовать что-то типа очереди, приведённой в этом топике. Она не даёт строгих гарантий прогресса, однако быстрая.

R>Мьютексы же оказываются не у дел, т.к. не дают ни производительности, ни гарантий прогресса.

Глядя на все эти ньюансы и не устаявшуюся терминалогию , майкрософтовский подход — реализовать все через спинлоки — начинает казаться самым верным.
Re[6]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 24.10.10 14:50
Оценка:
Здравствуйте, vf, Вы писали:

vf>Если бы производитель блокировал, он же не блокирует, потребителю очередь скажет что элементов нет, хотя их там может быть несколько.


Почему не блокирует? Блокирует. Если бы это была очередь на мьютексе, считай, что потребитель вызывает try_lock(), который возвращает ему false. Трактуй это так.


vf>Так чтобы в статистику не уходить (хотя я все таки считаю что для большинства случаев это недопустимое поведение), конктретно в моей задача, это принципиальный момент, я буду создавать(уничтожать) лишний элемент когда не смогу его взять(положить) в очередь, а это тянет за собой работу GC для "старых" объектов, и тут большой вопрос что будет выгоднее тот же mutex(хотя есть и другие варианты) или работа GC.


А более конкретно можешь? Какой элемент? Для чего? Какого GC?


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[6]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 24.10.10 14:57
Оценка:
Здравствуйте, vf, Вы писали:

R>>Однако я не знаю даже lock-free алгоритма для array-bases multi-producer/multi-consumer очереди. И при этом она скорее всего будет медленнее работать.


vf>Вот я находил, там по два CAS на добавление и один на получение элемента. Еще не пробовал реализовать.


Каким боком M&S queue является array-based?
Плюс ещё добавь по 1 CAS на операцию на управление временем жизни узлов, т.к. алгоритм не работает без GC.
Да, и кстати, она не фига не linearizable, как они это утверждают и даже вроде как "доказывают". Подробнее я описывал тут:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/8344b10e0deb18dc

R>>Если тебе нужна просто производительность (например, для throughput-oriented сервера), то нужно использовать что-то типа очереди, приведённой в этом топике. Она не даёт строгих гарантий прогресса, однако быстрая.

R>>Мьютексы же оказываются не у дел, т.к. не дают ни производительности, ни гарантий прогресса.

vf>Глядя на все эти ньюансы и не устаявшуюся терминалогию , майкрософтовский подход — реализовать все через спинлоки — начинает казаться самым верным.


Это что за майкрософтовский подход? В любом случае это получается какой-то двойной стандарт. Ты думаешь свою инфраструктуру, ран-таймы, библиотеки для распараллеливания они на спинлоках делают? Отнюдь.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[7]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 24.10.10 17:04
Оценка:
Здравствуйте, remark, Вы писали:

vf>>Вот я находил, там по два CAS на добавление и один на получение элемента. Еще не пробовал реализовать.


R>Каким боком M&S queue является array-based?


Нет, она не array-based, но мне почему-то кажется, что в array-based от обычной перейти всегда можно?! Ведь по логике — это скорее упрощение.

R>Плюс ещё добавь по 1 CAS на операцию на управление временем жизни узлов, т.к. алгоритм не работает без GC.


Я думал это общий алгоритм, возможно что он и не подходит.

R>Да, и кстати, она не фига не linearizable, как они это утверждают и даже вроде как "доказывают". Подробнее я описывал тут:

R>http://groups.google.com/group/comp.programming.threads/browse_frm/thread/8344b10e0deb18dc

Если это так, тогда совсем плохо.

R>>>Если тебе нужна просто производительность (например, для throughput-oriented сервера), то нужно использовать что-то типа очереди, приведённой в этом топике. Она не даёт строгих гарантий прогресса, однако быстрая.

R>>>Мьютексы же оказываются не у дел, т.к. не дают ни производительности, ни гарантий прогресса.

vf>>Глядя на все эти ньюансы и не устаявшуюся терминалогию , майкрософтовский подход — реализовать все через спинлоки — начинает казаться самым верным.


R>Это что за майкрософтовский подход? В любом случае это получается какой-то двойной стандарт. Ты думаешь свою инфраструктуру, ран-таймы, библиотеки для распараллеливания они на спинлоках делают? Отнюдь.


Да, где проскакивало, что в 4.0 дот нете, tread-safe коллекции сделаны на spin-lock-ах. Опять же утверждать не буду, сам я не делал и рефлектором не смотрел.
Re[8]: О lock-free алгоритмах (+бонус)
От: fddima  
Дата: 24.10.10 17:28
Оценка:
Здравствуйте, vf, Вы писали:

vf>Да, где проскакивало, что в 4.0 дот нете, tread-safe коллекции сделаны на spin-lock-ах. Опять же утверждать не буду, сам я не делал и рефлектором не смотрел.

Ну и что, это ещё не значит, что это единственный подход. В XLinq (System.Xml.Linq) XHashtable — lock-free (блокируются только записи и только при ресайзе).
Re[7]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 24.10.10 17:36
Оценка:
Здравствуйте, remark, Вы писали:

vf>>Если бы производитель блокировал, он же не блокирует, потребителю очередь скажет что элементов нет, хотя их там может быть несколько.


R>Почему не блокирует? Блокирует. Если бы это была очередь на мьютексе, считай, что потребитель вызывает try_lock(), который возвращает ему false. Трактуй это так.


Здесь возникает не однозначность, я привык трактовать false возвращенный dequeue как отсутствие элементов в очереди. Дело даже не привычке, как различать два этих события? И тоже самое для enqueue?

vf>>Так чтобы в статистику не уходить (хотя я все таки считаю что для большинства случаев это недопустимое поведение), конктретно в моей задача, это принципиальный момент, я буду создавать(уничтожать) лишний элемент когда не смогу его взять(положить) в очередь, а это тянет за собой работу GC для "старых" объектов, и тут большой вопрос что будет выгоднее тот же mutex(хотя есть и другие варианты) или работа GC.


R>А более конкретно можешь? Какой элемент? Для чего? Какого GC?


Я могу, но мне кажется мы просто щас уйдем от темы. Таких примеров где, нужно знать что очередь пуста или полна я думаю Вы и сами можете придумать. А вот где не нужно, я не могу придумать? Пусть некий сервер, с термином throughput-oriented я не знаком, что он кладет запросы на обработку в такую очередь? А что если она заполниться, производители устроят гонку добавляя элементы, или наоборот когда пуста, как снизить кол-во "холостых" потребителей? То есть полюбому вырисовывается механизм, который будет считать число элементов, хотя бы приблизительно.

Конструктивное предложение — предлагаю добавить счетчик элеметов внутрь очереди, и нынешние функции dequeue/enqueue завернуть в цикл for(counter > 0)/for(counter<max) — тогда возвращаемы значения можно будет интерпретировать как принято для очереди.
Re[9]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 24.10.10 17:42
Оценка:
Здравствуйте, fddima, Вы писали:

vf>>Да, где проскакивало, что в 4.0 дот нете, tread-safe коллекции сделаны на spin-lock-ах. Опять же утверждать не буду, сам я не делал и рефлектором не смотрел.

F> Ну и что, это ещё не значит, что это единственный подход. В XLinq (System.Xml.Linq) XHashtable — lock-free (блокируются только записи и только при ресайзе).

Возможно. Я два поста назад, написал "все" в контексте коллекций — моя ошибка. Я не утверждаю, что это весь .нет написан таким образом. Извените что внес путаницу.
Re[8]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 24.10.10 18:09
Оценка:
Здравствуйте, vf, Вы писали:

R>>Почему не блокирует? Блокирует. Если бы это была очередь на мьютексе, считай, что потребитель вызывает try_lock(), который возвращает ему false. Трактуй это так.


vf>Здесь возникает не однозначность, я привык трактовать false возвращенный dequeue как отсутствие элементов в очереди. Дело даже не привычке, как различать два этих события? И тоже самое для enqueue?


А точно ли их надо различать? Как будет различаться обработка этих ситуаций в твоём случае?


vf>Я могу, но мне кажется мы просто щас уйдем от темы. Таких примеров где, нужно знать что очередь пуста или полна я думаю Вы и сами можете придумать. А вот где не нужно, я не могу придумать? Пусть некий сервер, с термином throughput-oriented я не знаком, что он кладет запросы на обработку в такую очередь? А что если она заполниться, производители устроят гонку добавляя элементы,


Их не интересует полна она или нет, их интересует можно класть сообщения в очередь или нет. Если нельзя, то какая особо разница почему. В любом случае можно выбрасывать сообщение, или ждать пока не станет можно класть.

vf>или наоборот когда пуста, как снизить кол-во "холостых" потребителей?


Опять же какая разница, пуста она или нельзя получать сообщения по какой-то другой причине?


vf>То есть полюбому вырисовывается механизм, который будет считать число элементов, хотя бы приблизительно.


Приблизительно считать в этой очереди можно — просто возьми enqueue — dequeue. Для какой-то статистики этой подойдёт. Однако, если поток хочет достать сообщение для обработки, и он видит, что очередь формально не пуста, но достать сообщение не может, то какая ему разница-то?


vf>Конструктивное предложение — предлагаю добавить счетчик элеметов внутрь очереди, и нынешние функции dequeue/enqueue завернуть в цикл for(counter > 0)/for(counter<max) — тогда возвращаемы значения можно будет интерпретировать как принято для очереди.


А что будет делать поток, которому такой dequeue() вернёт false? Опять ждать появления сообщений в очереди?


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[8]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 24.10.10 18:37
Оценка:
Здравствуйте, vf, Вы писали:

R>>Каким боком M&S queue является array-based?


vf>Нет, она не array-based, но мне почему-то кажется, что в array-based от обычной перейти всегда можно?! Ведь по логике — это скорее упрощение.


Ага, только не в мире lock-free.
Фишка динамических структур в контексте lock-free в том, что поток вначале полностью подготавливает узел (записывает в него данные сообщения, устанавливает другие указатели), а потом атомарно добавляет его одним CASом. С массивом это не пройдёт — поток не может просто так писать данные сообщения в какой-то элемент массива — при этом он будет конфликтовать с другими производителями, которые хотят записать свои сообщения туда же, будет конфликтовать с потребителями, которые уже хотят читать этот элемент.


R>>Плюс ещё добавь по 1 CAS на операцию на управление временем жизни узлов, т.к. алгоритм не работает без GC.


vf>Я думал это общий алгоритм, возможно что он и не подходит.


Добро пожаловать в мир "академического lock-free".


R>>Да, и кстати, она не фига не linearizable, как они это утверждают и даже вроде как "доказывают". Подробнее я описывал тут:

R>>http://groups.google.com/group/comp.programming.threads/browse_frm/thread/8344b10e0deb18dc

vf>Если это так, тогда совсем плохо.


Я достаточно уверен, что это так. И никто пока не оспорил, что это не так.
Грубо говоря, linearizablе — это "ведёт себя как аналогичная структура данных, основанная на мьютексе". Если же для некоторых программ заменить мьютекс очередь на M&S очередь, то они начнут падать.
Эта моя очередь тоже не linearizablе.



R>>Это что за майкрософтовский подход? В любом случае это получается какой-то двойной стандарт. Ты думаешь свою инфраструктуру, ран-таймы, библиотеки для распараллеливания они на спинлоках делают? Отнюдь.


vf>Да, где проскакивало, что в 4.0 дот нете, tread-safe коллекции сделаны на spin-lock-ах. Опять же утверждать не буду, сам я не делал и рефлектором не смотрел.


Нет, это не так.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[9]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 24.10.10 20:19
Оценка:
Здравствуйте, remark, Вы писали:

R>>>Почему не блокирует? Блокирует. Если бы это была очередь на мьютексе, считай, что потребитель вызывает try_lock(), который возвращает ему false. Трактуй это так.


vf>>Здесь возникает не однозначность, я привык трактовать false возвращенный dequeue как отсутствие элементов в очереди. Дело даже не привычке, как различать два этих события? И тоже самое для enqueue?


R>А точно ли их надо различать? Как будет различаться обработка этих ситуаций в твоём случае?


Создание лишнего не дешевого объекта при dequeue, и зеркально удаление того который можно было бы поместить в очередь.

vf>>Я могу, но мне кажется мы просто щас уйдем от темы. Таких примеров где, нужно знать что очередь пуста или полна я думаю Вы и сами можете придумать. А вот где не нужно, я не могу придумать? Пусть некий сервер, с термином throughput-oriented я не знаком, что он кладет запросы на обработку в такую очередь? А что если она заполниться, производители устроят гонку добавляя элементы,


R>Их не интересует полна она или нет, их интересует можно класть сообщения в очередь или нет. Если нельзя, то какая особо разница почему. В любом случае можно выбрасывать сообщение, или ждать пока не станет можно класть.


Разница принципиальна, один случай когда очередь переполнена, разумный выход — убить запрос. А другой случай, когда из-за ньансов реализации очереди при приемлемой нагрузке пользователи начнут получать отлуп.

vf>>или наоборот когда пуста, как снизить кол-во "холостых" потребителей?

R>Опять же какая разница, пуста она или нельзя получать сообщения по какой-то другой причине?

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

Я не могу придумать обратных примеров — когда различать не важно.

vf>>То есть полюбому вырисовывается механизм, который будет считать число элементов, хотя бы приблизительно.


R>Приблизительно считать в этой очереди можно — просто возьми enqueue — dequeue. Для какой-то статистики этой подойдёт. Однако, если поток хочет достать сообщение для обработки, и он видит, что очередь формально не пуста, но достать сообщение не может, то какая ему разница-то?


Ведь он же доставить не может из-за особенностей очереди — повторить попытку?! Вообще я считаю такое поведение очереди ошибочным, и что она должна обрабатывать такие ситуации внутри себя.

vf>>Конструктивное предложение — предлагаю добавить счетчик элеметов внутрь очереди, и нынешние функции dequeue/enqueue завернуть в цикл for(counter > 0)/for(counter<max) — тогда возвращаемы значения можно будет интерпретировать как принято для очереди.


R>А что будет делать поток, которому такой dequeue() вернёт false? Опять ждать появления сообщений в очереди?


Это абстрактный пример, я лишь пытаюсь найти случай где такую особенность можно считать обоснованной. Конктретно по вопросам, да поведение потока должно быть различно в этих ситуациях, если запрос из очереди не получен по вине очереди нужно повторить запрос, иначе можно не знаю — заснуть на каком нить евенте или вернуться в пул потоков.
Re[10]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 25.10.10 03:17
Оценка:
Здравствуйте, vf, Вы писали:

vf>>>Здесь возникает не однозначность, я привык трактовать false возвращенный dequeue как отсутствие элементов в очереди. Дело даже не привычке, как различать два этих события? И тоже самое для enqueue?


R>>А точно ли их надо различать? Как будет различаться обработка этих ситуаций в твоём случае?


vf>Создание лишнего не дешевого объекта при dequeue, и зеркально удаление того который можно было бы поместить в очередь.


Т.е. если не удалось достать сообщение из очереди, и сообщений там нет, то ты не будешь создавать новый объект. А если не удалось достать сообщение из очереди, и ты бы знал, что сообщение там всё же есть, то, ты бы создал какой-то новый объект. Так? А точно это не так, что если не удалось достать сообщение из очереди, то ты создаёшь новый объект?


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[10]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 25.10.10 07:42
Оценка:
Здравствуйте, vf, Вы писали:

R>>Приблизительно считать в этой очереди можно — просто возьми enqueue — dequeue. Для какой-то статистики этой подойдёт. Однако, если поток хочет достать сообщение для обработки, и он видит, что очередь формально не пуста, но достать сообщение не может, то какая ему разница-то?


vf>Ведь он же доставить не может из-за особенностей очереди — повторить попытку?! Вообще я считаю такое поведение очереди ошибочным, и что она должна обрабатывать такие ситуации внутри себя.


Смысл? Повторишь попытку, а он опять недоступен. С тем же успехом ты можешь повторять попытки и когда она пуста, а вдруг производитель уже вошёл в функцию enqueue() и сразу уснул? А с большим успехом, мы говорим потоку, что тут сейчас ловить нечего — иди или спи, или позанимайся чем-нибудь другим полезным.


vf>>>Конструктивное предложение — предлагаю добавить счетчик элеметов внутрь очереди, и нынешние функции dequeue/enqueue завернуть в цикл for(counter > 0)/for(counter<max) — тогда возвращаемы значения можно будет интерпретировать как принято для очереди.


R>>А что будет делать поток, которому такой dequeue() вернёт false? Опять ждать появления сообщений в очереди?


vf>Это абстрактный пример, я лишь пытаюсь найти случай где такую особенность можно считать обоснованной. Конктретно по вопросам, да поведение потока должно быть различно в этих ситуациях, если запрос из очереди не получен по вине очереди нужно повторить запрос, иначе можно не знаю — заснуть на каком нить евенте или вернуться в пул потоков.


Иии где разница? В обоих случаях ждём пока следующее сообщение не станет доступно. Только если мы заблокируем поток на бесконечных попытках будет фигня, что пока он мог бы заняться чем-то другим полезным (например взять сообщение из другой очереди), но будет зазря прожигать такты.
Ну приведи не абстрактный пример. Я пока не вижу, что это было нужно... И теперь даже если ты приведёшь такой пример, ну что ж, в той специфической ситуации придётся использовать более дорогую очередь, а на все распространенные типа той, что ты пока привёл, хватит и такой очереди.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[11]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 25.10.10 08:05
Оценка:
Здравствуйте, remark, Вы писали:

R>>>Приблизительно считать в этой очереди можно — просто возьми enqueue — dequeue. Для какой-то статистики этой подойдёт. Однако, если поток хочет достать сообщение для обработки, и он видит, что очередь формально не пуста, но достать сообщение не может, то какая ему разница-то?


vf>>Ведь он же доставить не может из-за особенностей очереди — повторить попытку?! Вообще я считаю такое поведение очереди ошибочным, и что она должна обрабатывать такие ситуации внутри себя.


R>Смысл? Повторишь попытку, а он опять недоступен. С тем же успехом ты можешь повторять попытки и когда она пуста, а вдруг производитель уже вошёл в функцию enqueue() и сразу уснул?


Абсолютно не с тем же, вероятность получить облом при наличии элементов в очереди очень небольшая и она ни как не равна вероятности появления новых объектов в пустой очереди. Я даже уверен, что в реальном приложении будет довольно сложно попасть на такое поведение очереди, но ситуация должна обрабатываться на мой взгляд.

vf>>>>Конструктивное предложение — предлагаю добавить счетчик элеметов внутрь очереди, и нынешние функции dequeue/enqueue завернуть в цикл for(counter > 0)/for(counter<max) — тогда возвращаемы значения можно будет интерпретировать как принято для очереди.


R>>>А что будет делать поток, которому такой dequeue() вернёт false? Опять ждать появления сообщений в очереди?


vf>>Это абстрактный пример, я лишь пытаюсь найти случай где такую особенность можно считать обоснованной. Конктретно по вопросам, да поведение потока должно быть различно в этих ситуациях, если запрос из очереди не получен по вине очереди нужно повторить запрос, иначе можно не знаю — заснуть на каком нить евенте или вернуться в пул потоков.


R>Иии где разница? В обоих случаях ждём пока следующее сообщение не станет доступно. Только если мы заблокируем поток на бесконечных попытках будет фигня, что пока он мог бы заняться чем-то другим полезным (например взять сообщение из другой очереди), но будет зазря прожигать такты.


Разница в вероятности, новое сообщение в пустой очереди и успешная попытка вытащить имющийся элемент — не равновероятны.

R>Ну приведи не абстрактный пример. Я пока не вижу, что это было нужно...


Из двух примеров, один — про пул объектов — не абстрактный. И в обоих примерах я вижу необходимость различной обработки. Что то мы переливаем из пустого в порожнее, предлагаю каждому остаться при своем мнении.
Re[10]: Concurrency & Linearizability
От: remark Россия http://www.1024cores.net/
Дата: 25.10.10 08:13
Оценка: 2 (1)
Здравствуйте, vf, Вы писали:

R>>Их не интересует полна она или нет, их интересует можно класть сообщения в очередь или нет. Если нельзя, то какая особо разница почему. В любом случае можно выбрасывать сообщение, или ждать пока не станет можно класть.


vf>Разница принципиальна, один случай когда очередь переполнена, разумный выход — убить запрос. А другой случай, когда из-за ньансов реализации очереди при приемлемой нагрузке пользователи начнут получать отлуп.


Ну так она и есть переполнена — производители дошли до элемента, который всё ещё не закончил потреблять *самый старый* потребитель.
Я не понимаю, почему ты в этом пытаешься увидеть плохое. Есть очереди, основанные на мьютексах, с поведением, которое ни у кого не вызывает вопросов. Эта очередь во всех отношениях ведёт себя только лучше. Ты подумай, что было бы если у тебя в мьютекс очереди поток заснул бы посреди операции добавления под мьютексом. Правильно — всё бы встало. Эта же очередь даём там, где это можно, другим потокам спокойно поработать. Например, можно потреблять из других частей очереди, можно добавлять элементы дальше. А блокировать работу других потоков она будет только там, где без этого абсолютно не обойтись.

Гляди, что происходит в этой очереди. Допустим очередь пустая. Приходит производитель, начинает класть сообщение в очередь, но перед тем, как установить seq, засыпает. Дальше приходит ещё один производитель и полностью кладёт сообщение в очередь (т.е. возвращается из enqueue()). Дальше приходит потребитель и не находит сообщения. Приходит ещё один потребитель и тоже не находит. Дальше первый тормозной производитель просыпается и устанавливает seq. Теперь возвращаются 2 наших потребителя и забирают сообщения. Правильно?

Теперь, что происходит в мьютекс-очереди. После того, как первый поток засыпает под мьютексом, все нафиг блокируются (первый негативный момент — второй производитель мог бы на самом деле положить сообщение). Дальше первый поток просыпается и освобождает мьютекс. Мьютекс захватывает первый потребитель и забирает сообщение (заметь не раньше чем в моей очереди! т.е. только после того, как первый производитель закончил). Теперь мьютекс захватывает второй потребитель и получает отбой — сообщений нет (второй негативный момент — в моей очереди он бы уже получил сообщение). Мьютекс захватывает второй производитель, кладёт сообщение. Мьютекс захватывает второй потребитель, берёт сообщение.

Ты берёшь за отправную точку, что сообщения в очереди есть, а моя очередь такая-плохая не даёт их забирать. Это не так. Отправная точка — это когда всё нафиг обламываются, а моя очередь наоборот даёт во многих ситуациях потокам успешно отработать без блокировки.

Когда приходит второй производитель у нас есть 2 выбора: (1) дать ему без блокировки спокойно положить сообщение и пойти заниматься другой полезной работой, или (2) заблокировать и его, не получив ничего взамен. Гляди, когда в очереди блокировки мьютекса заблокирован производитель с готовым сообщением, ты рассматриваешь это сообщение как уже произведённое? Нет? А почему? В чём отличие? Я просто вместо блокировки и переключения контекста даю ему "забуферизировать" своё сообщение.

Хорошо, как можно "исправить" мою очередь, что бы она получила "хорошее" с твоей т.з. поведение? Можно заблокировать второго производителя, что бы он вместо того, что бы положить сообщение в очередь и пойти заниматься полезным делом, бесполезно болтался на мьютексе. Тогда ты не будешь считать, что сообщение "уже произведено", правильно? И? Что ты получил кроме ухудшения ран-тайм свойств? Ничего. Мы стали чаще блокировать потоки, только для того, что бы ты не называл очередь такой-секой, не отдающий уже произведенные сообщения.
Т.е. всё, что мы будем делать, — это дополнительно задерживать некоторые потоки в некоторых местах, только что бы поведение выглядело более логичным для "однопоточного мозга программиста". Совершенно не будет такого, что какие сообщения вдруг станут доступны раньше, ничего подобного, дополнительные задержки не могу к этому привести.

Если ты привык работать с алгоритмами, основанными на мьютексах (которые под всеми имеющими смысл взглядами — однопоточные алгоритмы), то тебе надо немного поломать свой мозг, что бы понять как вещи происходят в действительно concurrent системах. Тут зачастую нету порядка между событиями, или сообщение потока может появиться в очереди через долго после того, как он вышел из enqueue() (мы просто не будет задерживать его до этого момента в enqueue()), и т.д.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[12]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 25.10.10 08:19
Оценка:
Здравствуйте, vf, Вы писали:

vf>Абсолютно не с тем же, вероятность получить облом при наличии элементов в очереди очень небольшая и она ни как не равна вероятности появления новых объектов в пустой очереди. Я даже уверен, что в реальном приложении будет довольно сложно попасть на такое поведение очереди, но ситуация должна обрабатываться на мой взгляд.


Вероятность вероятностью, а обрабатывать-то ты будешь одинаково — ждать доступности сообщения, или занять поток другой работой. И зачем тебе этот признак?



R>>Иии где разница? В обоих случаях ждём пока следующее сообщение не станет доступно. Только если мы заблокируем поток на бесконечных попытках будет фигня, что пока он мог бы заняться чем-то другим полезным (например взять сообщение из другой очереди), но будет зазря прожигать такты.


vf>Разница в вероятности, новое сообщение в пустой очереди и успешная попытка вытащить имющийся элемент — не равновероятны.


Вопрос был другой — как отличается обработка?
Или ты хочешь вставить в код:
if (message_is_unavailable_but_the_queue_is_not_empty)
  be_happy_most_likely_I_will_get_a_message_soon();




R>>Ну приведи не абстрактный пример. Я пока не вижу, что это было нужно...


vf>Из двух примеров, один — про пул объектов — не абстрактный. И в обоих примерах я вижу необходимость различной обработки. Что то мы переливаем из пустого в порожнее, предлагаю каждому остаться при своем мнении.


Ну так ты покажи, как бы у тебя код различался.



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[11]: Concurrency & Linearizability
От: Jolly Roger  
Дата: 25.10.10 08:43
Оценка:
Здравствуйте, remark, Вы писали:

R>Хорошо, как можно "исправить" мою очередь, что бы она получила "хорошее" с твоей т.з. поведение?


По-моему, это можно решить счётчиком производителей. Будет два дополнительных CAS в enqueue, вне цикла. Тогда dequeue сможет возвращать одно из значений перечисления — OK, empty, busy, а внешний код, соответственно, реагировать либо повтором попытки, либо переходом к другим занятиям. Немного замедлится enqueue, но зато, возможно, получится выигрыш во внешнем по отношению к очереди коде.
"Нормальные герои всегда идут в обход!"
Re[12]: Concurrency & Linearizability
От: remark Россия http://www.1024cores.net/
Дата: 25.10.10 08:50
Оценка:
Здравствуйте, Jolly Roger, Вы писали:

R>>Хорошо, как можно "исправить" мою очередь, что бы она получила "хорошее" с твоей т.з. поведение?


JR>По-моему, это можно решить счётчиком производителей. Будет два дополнительных CAS в enqueue, вне цикла. Тогда dequeue сможет возвращать одно из значений перечисления — OK, empty, busy, а внешний код, соответственно, реагировать либо повтором попытки, либо переходом к другим занятиям. Немного замедлится enqueue, но зато, возможно, получится выигрыш во внешнем по отношению к очереди коде.


Счётчики уже есть — это enqueue_ и dequeue_, через их разницу можно понять. Но речь не об этом, речь о том, что сделать это можно, но это будет бессмысленное усложнение АПИ. Если есть другая работать поделать, то делаем её, зачем вообще ждать. Иначе, попробовать ещё несколько раз имеет смысл *всегда*, т.к. это дешевле переключения потока. Пробовать бесконечное число раз не имеет смысл *никогда*, т.к. это чрезмерно прожигает такты.
З.ы. а за два дополнительных CAS можно поиметь и lock-free очередь без таких нюансов... только это будет еже компромиссное решение относительно мьютекса — медленнее, но lock-free. Моя же очередь win-win относительно мьютекса — и быстрее, и по по гарантиям прогресса лучше.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[13]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 25.10.10 09:02
Оценка:
Здравствуйте, remark, Вы писали:

R>Здравствуйте, vf, Вы писали:


vf>>Абсолютно не с тем же, вероятность получить облом при наличии элементов в очереди очень небольшая и она ни как не равна вероятности появления новых объектов в пустой очереди. Я даже уверен, что в реальном приложении будет довольно сложно попасть на такое поведение очереди, но ситуация должна обрабатываться на мой взгляд.


R>Вероятность вероятностью, а обрабатывать-то ты будешь одинаково — ждать доступности сообщения, или занять поток другой работой. И зачем тебе этот признак?


Нет, я же писал, что я буду обрабатывать по разному, если элементы есть то в твоей терминалогии я буду "ждать доступности сообщения", а если их нет "занять поток другой работой".

R>>>Иии где разница? В обоих случаях ждём пока следующее сообщение не станет доступно. Только если мы заблокируем поток на бесконечных попытках будет фигня, что пока он мог бы заняться чем-то другим полезным (например взять сообщение из другой очереди), но будет зазря прожигать такты.


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

R>Или ты хочешь вставить в код:

R>
R>if (message_is_unavailable_but_the_queue_is_not_empty)
R>  be_happy_most_likely_I_will_get_a_message_soon();
R>


Вот так, причем хочу я его вставить в саму очередь:

while (message_is_unavailable_but_the_queue_is_not_empty)
  item = queue.get();



R>>>Ну приведи не абстрактный пример. Я пока не вижу, что это было нужно...


vf>>Из двух примеров, один — про пул объектов — не абстрактный. И в обоих примерах я вижу необходимость различной обработки. Что то мы переливаем из пустого в порожнее, предлагаю каждому остаться при своем мнении.


R>Ну так ты покажи, как бы у тебя код различался.


while(x == null)
{
if(queue.isEmpty)
x = create_expensive_object();
else
x = queue.cheap_try_to_get_item();
}
Re[13]: Concurrency & Linearizability
От: Jolly Roger  
Дата: 25.10.10 09:07
Оценка:
Здравствуйте, remark, Вы писали:

R>Счётчики уже есть — это enqueue_ и dequeue_, через их разницу можно понять.


Ну да, можно и так

R>Но речь не об этом, речь о том, что сделать это можно, но это будет бессмысленное усложнение АПИ.


Да я-то с Вами согласен. Просто хотел сказать, что раз уж vf непременно это нужно, то, в принципе, можно и сделать относительно недорого.
"Нормальные герои всегда идут в обход!"
Re[14]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 25.10.10 09:16
Оценка:
Здравствуйте, vf, Вы писали:

R>>Вероятность вероятностью, а обрабатывать-то ты будешь одинаково — ждать доступности сообщения, или занять поток другой работой. И зачем тебе этот признак?


vf>Нет, я же писал, что я буду обрабатывать по разному, если элементы есть то в твоей терминалогии я буду "ждать доступности сообщения", а если их нет "занять поток другой работой".


Если есть другая работа, то надо занимать ей поток сразу. Вероятность вероятностью, а можно очень долго ждать сообщения, которое вроде как в очереди; и с другой стороны можно очень быстро получить сообщение, которого ещё нет в очереди. Это действительно не должно делать принципиальной разницы.



R>>>>Иии где разница? В обоих случаях ждём пока следующее сообщение не станет доступно. Только если мы заблокируем поток на бесконечных попытках будет фигня, что пока он мог бы заняться чем-то другим полезным (например взять сообщение из другой очереди), но будет зазря прожигать такты.


vf>Если он заблокируется на бесконечных попытках — то да это фигня, но это проблемы очереди, но я все же считаю что такое маловероятно, и при малом числе повторных попыток получить элемент поток его все таки получит. Ты же предлагаешь менять архитектуру приложения под очередь, причем под маловероятное событие в этой очереди. Во первых не всегда возможно, во вторых в данном случае не обосновано.


Я не предлагаю менять архитектуру, наоборот, я говорю, что не надо различать эти ситуации вообще.


R>>Или ты хочешь вставить в код:

R>>
R>>if (message_is_unavailable_but_the_queue_is_not_empty)
R>>  be_happy_most_likely_I_will_get_a_message_soon();
R>>


vf>Вот так, причем хочу я его вставить в саму очередь:


vf>
vf>while (message_is_unavailable_but_the_queue_is_not_empty)
vf>  item = queue.get();
vf>


Ну у тебя сейчас есть код:
while (queue_is_empty)
  item = queue.get();

который есть надмножество этого. Ничего больше делать не надо. QED.


R>>>>Ну приведи не абстрактный пример. Я пока не вижу, что это было нужно...


vf>>>Из двух примеров, один — про пул объектов — не абстрактный. И в обоих примерах я вижу необходимость различной обработки. Что то мы переливаем из пустого в порожнее, предлагаю каждому остаться при своем мнении.


R>>Ну так ты покажи, как бы у тебя код различался.


vf>while(x == null)

vf>{
vf>if(queue.isEmpty)
vf> x = create_expensive_object();
vf>else
vf> x = queue.cheap_try_to_get_item();
vf>}

Замени это на:
for (int try = 0; try != TRY_COUNT; try += 1)
{
  if (x = queue.cheap_try_to_get_item())
    break;
}
if (x == null)
  x = create_expensive_object();


и будет тебе счастье. Во-первых, даёшь некоторый шанс всё же вытащить объект из очереди даже если она пуста (хорошо — объект тяжёлый). Во-вторых, устраняешь неограниченное ожидание "мифического" объекта (хорошо — десятки потоков наяривающих в спин цикле в ожидании потока, вытесненного более высоко-приоритетным, отнюдь не весёлое зрелище). Различать ситуации нет надо. QED.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[11]: Concurrency & Linearizability
От: vf  
Дата: 25.10.10 09:30
Оценка:
Здравствуйте, remark, Вы писали:

R>Здравствуйте, vf, Вы писали:


R>>>Их не интересует полна она или нет, их интересует можно класть сообщения в очередь или нет. Если нельзя, то какая особо разница почему. В любом случае можно выбрасывать сообщение, или ждать пока не станет можно класть.


vf>>Разница принципиальна, один случай когда очередь переполнена, разумный выход — убить запрос. А другой случай, когда из-за ньансов реализации очереди при приемлемой нагрузке пользователи начнут получать отлуп.


R>Ну так она и есть переполнена — производители дошли до элемента, который всё ещё не закончил потреблять *самый старый* потребитель.

R>Я не понимаю, почему ты в этом пытаешься увидеть плохое. Есть очереди, основанные на мьютексах, с поведением, которое ни у кого не вызывает вопросов. Эта очередь во всех отношениях ведёт себя только лучше. Ты подумай, что было бы если у тебя в мьютекс очереди поток заснул бы посреди операции добавления под мьютексом. Правильно — всё бы встало. Эта же очередь даём там, где это можно, другим потокам спокойно поработать. Например, можно потреблять из других частей очереди, можно добавлять элементы дальше. А блокировать работу других потоков она будет только там, где без этого абсолютно не обойтись.

Вот здесь принципиальный момент — нельзя потреблять из других частей очереди, можно только добавлять!

R>Гляди, что происходит в этой очереди. Допустим очередь пустая. Приходит производитель, начинает класть сообщение в очередь, но перед тем, как установить seq, засыпает. Дальше приходит ещё один производитель и полностью кладёт сообщение в очередь (т.е. возвращается из enqueue()). Дальше приходит потребитель и не находит сообщения. Приходит ещё один потребитель и тоже не находит. Дальше первый тормозной производитель просыпается и устанавливает seq. Теперь возвращаются 2 наших потребителя и забирают сообщения. Правильно?


Правильно, только оцени затраты на ушел пришел и вероятность того что производитель заснул (скорее всего просто шестеренки не так встали), и какой смысл уходить-возвращаться потребителям в этой ситуации, когда каждый из них с очень большой вероятностью повторив попытку получить положительный ответ??? Так еще и архитектура приложения не слабо портиться из-за ушел-пришел, и ведь где-то там куда они ушли им все равно нужно будет как-то учитывать кол-во элементов, чтобы знать что нужно прийти, разве не так?

R>Теперь, что происходит в мьютекс-очереди. После того, как первый поток засыпает под мьютексом, все нафиг блокируются (первый негативный момент — второй производитель мог бы на самом деле положить сообщение). Дальше первый поток просыпается и освобождает мьютекс. Мьютекс захватывает первый потребитель и забирает сообщение (заметь не раньше чем в моей очереди! т.е. только после того, как первый производитель закончил). Теперь мьютекс захватывает второй потребитель и получает отбой — сообщений нет (второй негативный момент — в моей очереди он бы уже получил сообщение). Мьютекс захватывает второй производитель, кладёт сообщение. Мьютекс захватывает второй потребитель, берёт сообщение.


Про мьютексы никто не спорит. Если выбирать между lock vs. lock-free я за lock-free

R>Ты берёшь за отправную точку, что сообщения в очереди есть, а моя очередь такая-плохая не даёт их забирать. Это не так. Отправная точка — это когда всё нафиг обламываются, а моя очередь наоборот даёт во многих ситуациях потокам успешно отработать без блокировки.


Это не нормальное поведени для очереди в класическом ее понимании, как минимум на это нужно было указать в первом посте. Если она себя так ведет то это не совсем очередь. Помимо поток и блокировок, существуют еще данные, вот я приводил пример с сервером, приходит запрос поток пытается положить его в очередь и обламывается, что он должен сделать? Дать отлуп пользователю, при небольшой нагрузке, или куда деть данные чтобы заняться другими вещами??!

R>Когда приходит второй производитель у нас есть 2 выбора: (1) дать ему без блокировки спокойно положить сообщение и пойти заниматься другой полезной работой, или (2) заблокировать и его, не получив ничего взамен. Гляди, когда в очереди блокировки мьютекса заблокирован производитель с готовым сообщением, ты рассматриваешь это сообщение как уже произведённое? Нет? А почему? В чём отличие? Я просто вместо блокировки и переключения контекста даю ему "забуферизировать" своё сообщение.


Где забуферизировать?! У нас очередь для этого, ты предлагаешь городить другой паралельный механизм? Не проще ли повторить попытку?

R>Хорошо, как можно "исправить" мою очередь, что бы она получила "хорошее" с твоей т.з. поведение? Можно заблокировать второго производителя, что бы он вместо того, что бы положить сообщение в очередь и пойти заниматься полезным делом, бесполезно болтался на мьютексе. Тогда ты не будешь считать, что сообщение "уже произведено", правильно? И? Что ты получил кроме ухудшения ран-тайм свойств? Ничего. Мы стали чаще блокировать потоки, только для того, что бы ты не называл очередь такой-секой, не отдающий уже произведенные сообщения.


Я предлагаю не блокировать, я предлагаю повторять попытки.
Каким полезным делом куда потоку данные пристроить? Выкнуть?

R>Т.е. всё, что мы будем делать, — это дополнительно задерживать некоторые потоки в некоторых местах, только что бы поведение выглядело более логичным для "однопоточного мозга программиста". Совершенно не будет такого, что какие сообщения вдруг станут доступны раньше, ничего подобного, дополнительные задержки не могу к этому привести.


R>Если ты привык работать с алгоритмами, основанными на мьютексах (которые под всеми имеющими смысл взглядами — однопоточные алгоритмы), то тебе надо немного поломать свой мозг, что бы понять как вещи происходят в действительно concurrent системах. Тут зачастую нету порядка между событиями, или сообщение потока может появиться в очереди через долго после того, как он вышел из enqueue() (мы просто не будет задерживать его до этого момента в enqueue()), и т.д.


Ну.. я привык считать приложения с несколькими потоками — многопоточными, а мьютексы или lock-free это лишь способы синхронизации.
Re[10]: О lock-free алгоритмах (+бонус)
От: Lexey Россия  
Дата: 25.10.10 09:40
Оценка:
Здравствуйте, vf, Вы писали:

vf>Я разбираюсь с алгоритмом, увидел случай который мне показался подозрительным, попытался продемонстрировать когда может возникать, использовал разумные упрощения и допущения. О чем ты споришь???? Я что предлагал в программе заменить size_t на что-то еще?!


Да не спорю я уже не о чем. Просто то, что ты считал подозрительным, для меня было самоочевидным. Зато уменьшение размерности рождает другие подозрения.

vf>Там нет таких случаев, если ты про ABA.


Что такое ABA?

vf>Я ничего не вношу уменьшая модуль, по крайней мере я не нашел, может ты обоснуешь то что утверждаешь, примером? Возьми минимальные модуль и покажи как это негативно отразилось на алгоритме? А то бла-бла-бла...


В том конкретном примере не вносишь, потому что у тебя размер очереди — степень двойки (важность этого момента я изначально не заметил). Если его взять нечетным (например, 15), то будет весело. В случае же нормального размера sequence_number размер очереди практически не роляет.
"Будь достоин победы" (c) 8th Wizard's rule.
Re[15]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 25.10.10 09:51
Оценка:
vf>>while(x == null)
vf>>{
vf>>if(queue.isEmpty)
vf>> x = create_expensive_object();
vf>>else
vf>> x = queue.cheap_try_to_get_item();
vf>>}

R>Замени это на:

R>
R>for (int try = 0; try != TRY_COUNT; try += 1)
R>{
R>  if (x = queue.cheap_try_to_get_item())
R>    break;
R>}
R>if (x == null)
R>  x = create_expensive_object();
R>


R>и будет тебе счастье. Во-первых, даёшь некоторый шанс всё же вытащить объект из очереди даже если она пуста (хорошо — объект тяжёлый). Во-вторых, устраняешь неограниченное ожидание "мифического" объекта (хорошо — десятки потоков наяривающих в спин цикле в ожидании потока, вытесненного более высоко-приоритетным, отнюдь не весёлое зрелище). Различать ситуации нет надо. QED.


Это уже вопрос деталей, а именно величины TRY_COUNT = [1..INFINITY], а зависит она от стоимости объекта и вероятности облома при повторной попытке, я вероятность оцениваю как стремящуюся к нулю(даже в твоем примере с высоко-приоритетном потоком), и зависимость здесь обратнопропорциональная следовательно TRY_COUNT -> INF
Re[11]: О lock-free алгоритмах (+бонус)
От: ilnar Россия  
Дата: 25.10.10 09:53
Оценка: 8 (1)
Здравствуйте, Lexey, Вы писали:

L>Здравствуйте, vf, Вы писали:


vf>>Я разбираюсь с алгоритмом, увидел случай который мне показался подозрительным, попытался продемонстрировать когда может возникать, использовал разумные упрощения и допущения. О чем ты споришь???? Я что предлагал в программе заменить size_t на что-то еще?!


L>Да не спорю я уже не о чем. Просто то, что ты считал подозрительным, для меня было самоочевидным. Зато уменьшение размерности рождает другие подозрения.


vf>>Там нет таких случаев, если ты про ABA.


L>Что такое ABA?

http://en.wikipedia.org/wiki/ABA_problem

vf>>Я ничего не вношу уменьшая модуль, по крайней мере я не нашел, может ты обоснуешь то что утверждаешь, примером? Возьми минимальные модуль и покажи как это негативно отразилось на алгоритме? А то бла-бла-бла...


L>В том конкретном примере не вносишь, потому что у тебя размер очереди — степень двойки (важность этого момента я изначально не заметил). Если его взять нечетным (например, 15), то будет весело. В случае же нормального размера sequence_number размер очереди практически не роляет.
Re[3]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 25.10.10 14:59
Оценка:
Здравствуйте, remark, Вы писали:

R>Код в студию!


Здесь
Автор: vf
Дата: 25.10.10
выложил, баги вычистил вроде.
Re[9]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 25.10.10 19:52
Оценка:
Здравствуйте, remark, Вы писали:

R>>>Да, и кстати, она не фига не linearizable, как они это утверждают и даже вроде как "доказывают". Подробнее я описывал тут:

R>>>http://groups.google.com/group/comp.programming.threads/browse_frm/thread/8344b10e0deb18dc

vf>>Если это так, тогда совсем плохо.


R>Я достаточно уверен, что это так. И никто пока не оспорил, что это не так.

R>Грубо говоря, linearizablе — это "ведёт себя как аналогичная структура данных, основанная на мьютексе". Если же для некоторых программ заменить мьютекс очередь на M&S очередь, то они начнут падать.
R>Эта моя очередь тоже не linearizablе.

Прочитал этот тред, но это более частный случай, аппонент твой не согласился, да и объективно M&S гораздо ближе к linerizable. А где он конкретно спотыкается, что происходит при удалении очереди?
Re[10]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 28.10.10 03:44
Оценка:
Здравствуйте, vf, Вы писали:

R>>Я достаточно уверен, что это так. И никто пока не оспорил, что это не так.

R>>Грубо говоря, linearizablе — это "ведёт себя как аналогичная структура данных, основанная на мьютексе". Если же для некоторых программ заменить мьютекс очередь на M&S очередь, то они начнут падать.
R>>Эта моя очередь тоже не linearizablе.

vf>Прочитал этот тред, но это более частный случай, аппонент твой не согласился, да и объективно M&S гораздо ближе к linerizable. А где он конкретно спотыкается, что происходит при удалении очереди?


Мой аргумент очень простой — вот пример кода, который прекрасно работает с мьютекс-очередью, заменяем её на M&S очередь — начинает падать. А это есть основное практическое следствие из linearizability — можно спокойно так заменять и не должно быть никаких видимых изменений в поведении. Они доказывали свойство linearizability в неком академическом абстрактном коне в вакууме, в котором объекты не создаются и не удаляются динамически.

struct tcp_connection
{
  queue_t q;
  ...

};

void connection_thread(tcp_connection* c)
{
  for (;;)
  {
    msg_t* m = c->dequeue();
    if (m->type == MSG_DISCONNECT)
    {
      delete c;
      return;
    }
    process(m);
  }

}

void io_dispatch_thread()
{
  for (;;)
  {
    select(...);
    for_each(SOCKET s in read_set)
    {
      recv(s, buf, size);
      tcp_connection* c = find_connection(s);
      c->enqueue(msg_t(MSG_PACKET, data, size));
    }
    for_each(SOCKET s in exception_set)
    {
      tcp_connection* c = find_connection(s);
      c->enqueue(msg_t(MSG_DISCONNECT));
    }
  }
}



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[9]: c# array-based Michael & Scott queue
От: vf  
Дата: 01.11.10 09:05
Оценка:
Здравствуйте, remark, Вы писали:

R>Ага, только не в мире lock-free.


http://rsdn.ru/forum/src/4019420.1.aspx собственно.
Re[10]: c# array-based Michael & Scott queue
От: vf  
Дата: 01.11.10 09:06
Оценка:
Здравствуйте, vf, Вы писали:

Урл с названием попутал

Subj
Автор: vf
Дата: 31.10.10
собственно.
Re: О lock-free алгоритмах (+бонус)
От: brankovic  
Дата: 23.04.11 12:38
Оценка:
Здравствуйте, remark, Вы писали:

R>сразу скажу о бонусе — это простой и эффективный алгоритм очереди на основе буфера фиксированного размера


1. Честно прочитал тред.. правильно я понял, что алгоритм формально не lock-free, и не obstruction-free? Т.е. местами возникает подобие спинлока, так? (Википедия: Lock-freedom allows individual threads to starve but guarantees system-wide throughput.)

2. В связи с этим у меня есть вопрос: насколько это продакшн-реди, тестировалась ли производительность, есть ли опыт применения? Работаю с приложением, которое почти полностью состоит из разных локовых очередей. Оно бешено свитчится и тормозит (в топ не вылазит, но обрабатывать не успевает). Думаю, реально ли перейти на локфри малой кровью.
Re: О lock-free алгоритмах (+бонус)
От: pif_pif  
Дата: 24.04.11 20:17
Оценка:
Есть подозрение, что этот алгоритм не свободет от data race. Т.е. между этой строкой
intptr_t dif = (intptr_t)seq — (intptr_t)pos;
и этой проверкой
if (dif == 0)
значение pos может быть изменено в другом потоке, и проверка будет не валидной. Intel Parallel Inspector это подтверждает:
ID Description Problem Source Function Module State
X7 Read Data race lockfree.cpp:24 load lockfree.exe Not fixed
X9 Write Data race lockfree.cpp:41 store lockfree.exe Not fixed
X6 Write Data race lockfree.cpp:48 compare_exchange_weak lockfree.exe Not fixed
X8 Allocation site Data race newaop.cpp:7 new[] lockfree.exe Information

Код для теста использовался такой:

tbb_thread* tbbthrd_en[10];
for(int i=0;i<10;i++)
{
tbbthrd_en[i]=new tbb_thread(thrd_en);
}
for(int i=0;i<10;i++)
{
tbbthrd_en[i]->join();
}
Re[2]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 25.04.11 06:45
Оценка:
Здравствуйте, brankovic, Вы писали:

B>Здравствуйте, remark, Вы писали:


R>>сразу скажу о бонусе — это простой и эффективный алгоритм очереди на основе буфера фиксированного размера


B>1. Честно прочитал тред.. правильно я понял, что алгоритм формально не lock-free, и не obstruction-free? Т.е. местами возникает подобие спинлока, так? (Википедия: Lock-freedom allows individual threads to starve but guarantees system-wide throughput.)


Да, всё правильно. Пока поток работает с ячейкой (копирует в неё или из неё), она фактически залочена.


B>2. В связи с этим у меня есть вопрос: насколько это продакшн-реди, тестировалась ли производительность, есть ли опыт применения? Работаю с приложением, которое почти полностью состоит из разных локовых очередей. Оно бешено свитчится и тормозит (в топ не вылазит, но обрабатывать не успевает). Думаю, реально ли перейти на локфри малой кровью.


Тут нет ничего, что бы делало его не "продакш-реди". Попробуй её вставить и увидишь


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[2]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 25.04.11 06:47
Оценка:
Здравствуйте, pif_pif, Вы писали:

_>Есть подозрение, что этот алгоритм не свободет от data race. Т.е. между этой строкой

_> intptr_t dif = (intptr_t)seq — (intptr_t)pos;
_>и этой проверкой
_> if (dif == 0)
_>значение pos может быть изменено в другом потоке, и проверка будет не валидной.

Тогда последующий CAS не сработает.

_> Intel Parallel Inspector это подтверждает:

_>ID Description Problem Source Function Module State
_>X7 Read Data race lockfree.cpp:24 load lockfree.exe Not fixed
_>X9 Write Data race lockfree.cpp:41 store lockfree.exe Not fixed
_>X6 Write Data race lockfree.cpp:48 compare_exchange_weak lockfree.exe Not fixed
_>X8 Allocation site Data race newaop.cpp:7 new[] lockfree.exe Information


Inspector не умеет проверять такой код.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[3]: О lock-free алгоритмах (+бонус)
От: pif_pif  
Дата: 25.04.11 09:51
Оценка:
Насколько я понял код, dequeue_pos_ и enqueue_pos_ двигаются в одну сторону по buffer_ и нигде нет проверки того, что они не совпали (или dequeue_pos_ > enqueue_pos_). Parallel Inspector совершенно прав, что между enquee и dequee существует data race — из обеих функции есть несинхронизированный доступ к buffer_. Следовательно, мы можем вынимать из очереди несуществующие элементы, которые не были поставлены в очередь. Вы уверены, что такая очередь востребована?
Re[4]: О lock-free алгоритмах (+бонус)
От: pif_pif  
Дата: 25.04.11 14:33
Оценка:
Здравствуйте, pif_pif, Вы писали:

_>Насколько я понял код, dequeue_pos_ и enqueue_pos_ двигаются в одну сторону по buffer_ и нигде нет проверки того, что они не совпали (или dequeue_pos_ > enqueue_pos_). Parallel Inspector совершенно прав, что между enquee и dequee существует data race — из обеих функции есть несинхронизированный доступ к buffer_. Следовательно, мы можем вынимать из очереди несуществующие элементы, которые не были поставлены в очередь. Вы уверены, что такая очередь востребована?


Разобрался в коде, дезавуирую "мы можем вынимать из очереди несуществующие элементы, которые не были поставлены в очередь". На счет датарейсов пока сказать не могу, продолжаю анализировать.
Re: О lock-free алгоритмах (+бонус)
От: _nn_ www.nemerleweb.com
Дата: 27.04.11 08:47
Оценка:
Здравствуйте, remark, Вы писали:

R>Теперь обещанный бонус — алгоритм bounded multi-producer/multi-consumer очереди без блокировок. Контейнер не использует динамического выделения/управления памятью в процессе работы (за исключением изначального выделения фиксированного буфера).


А под какой лицензией выкладывается этот код ?
http://rsdn.nemerleweb.com
http://nemerleweb.com
Re: О lock-free алгоритмах (+бонус)
От: Мишень-сан  
Дата: 29.04.11 10:41
Оценка:
Здравствуйте, remark, Вы писали:

[skipped]

R>


Извиняюсь за возможно дурацкий вопрос.
Как оно будет себя вести при переполнении sequence counters?
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.