Покритикуйте мой lock-free:

template <class KEY_TYPE, class VALUE_TYPE>
class lock_free_map
{
public:
    lock_free_map ():_spinlock (0) {}
    
    void insert (const KEY_TYPE& key, const VALUE_TYPE &value)
    {
        while (InterlockedCompareExchange (&_spinlock, -1, 0)) {}
        _std_map.insert (make_pair (key, value));
        InterlockedExchange (&_spinlock, 0);
    }

    void remove (const KEY_TYPE& key)
    {
        while (InterlockedCompareExchange (&_spinlock, -1, 0)) {}
        _std_map.erase (key);
        InterlockedExchange (&_spinlock, 0);
    }

    void clear ()
    {
        while (InterlockedCompareExchange (&_spinlock, -1, 0)) {}
        _std_map.clear ();
        InterlockedExchange (&_spinlock, 0);
    }

    bool get (const KEY_TYPE& key, VALUE_TYPE &value)
    {
        LONG prev_spin;
        do
        {
            prev_spin = _spinlock;
            if (prev_spin >= 0)
                prev_spin = InterlockedCompareExchange (&_spinlock, prev_spin + 1, prev_spin);
        }
        while (prev_spin < 0);

        map <KEY_TYPE, VALUE_TYPE>::const_iterator it = _std_map.find (key);
        bool found = (it != _std_map.end());
        if (found)
            value = it->second;

        InterlockedDecrement (&_spinlock);

        return found;
    }

template <class KEY_TYPE, class VALUE_TYPE>
class lock_free_map
{
public:
    lock_free_map ():_spinlock (0) {}
    
    void insert (const KEY_TYPE& key, const VALUE_TYPE &value)
    {
        while (InterlockedCompareExchange (&_spinlock, -1, 0)) {}
        _std_map.insert (make_pair (key, value));
        InterlockedExchange (&_spinlock, 0);
    }

    void remove (const KEY_TYPE& key)
    {
        while (InterlockedCompareExchange (&_spinlock, -1, 0)) {}
        _std_map.erase (key);
        InterlockedExchange (&_spinlock, 0);
    }

    void clear ()
    {
        while (InterlockedCompareExchange (&_spinlock, -1, 0)) {}
        _std_map.clear ();
        InterlockedExchange (&_spinlock, 0);
    }

    bool get (const KEY_TYPE& key, VALUE_TYPE &value)
    {
        LONG prev_spin;
        do
        {
            prev_spin = _spinlock;
            if (prev_spin >= 0)
                prev_spin = InterlockedCompareExchange (&_spinlock, prev_spin + 1, prev_spin);
        }
        while (prev_spin < 0);

        map <KEY_TYPE, VALUE_TYPE>::const_iterator it = _std_map.find (key);
        bool found = (it != _std_map.end());
        if (found)
            value = it->second;

        InterlockedDecrement (&_spinlock);

        return found;
    }

protected:
    map <KEY_TYPE, VALUE_TYPE> _std_map;
    volatile LONG _spinlock;
};

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

S>

S>template <class KEY_TYPE, class VALUE_TYPE>
S>class lock_free_map
S>{
S>public:
S>    lock_free_map ():_spinlock (0) {}

S>protected:
S>    map <KEY_TYPE, VALUE_TYPE> _std_map;
S>    volatile LONG _spinlock;
S>};
S>

Правильно ли я понимаю что весь "лок-фри" заключается в накрутке спин-лока? Если да, то:

1. Вы не поняли о чем "лок-фри".
2. Замените на mutex и будет намного лучше чем сейчас.

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

_>Правильно ли я понимаю что весь "лок-фри" заключается в накрутке спин-лока? Если да, то:

задача стояла следующая:
читать можно всем, если никто не записывает (чтение блокирует только запись)
писать только одному, если никто не читает (запись блокирует чтение и запись другим потокам)

_>2. Замените на mutex и будет намного лучше чем сейчас.

мутексом будет обеспечен доступ только одному потоку, при чем не важно чтение или запись

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

S>Покритикуйте мой lock-free:

Это не локфри, а просто чертовски дорогие фьютексы. (fast userspace mutex)

Как тебе такой сценарий:
Первый поток входит в критическую секцию, взводит флажок, входит в недра операции с мапом, и тут его вытесняют по окончании кванта, или потому что проснулся другой, реалтаймовый, поток.
Спустя несколько квантов...
Второй поток подходит к критической секции, начинает активно дёргать флажок. И делает это до окончания кванта, пока его не вытеснят.
Спустя несколько квантов...
Первый поток просыпается, выходит из недр, опускает флажок и выходит из критической секции.
Спустя несколько квантов...
Второй поток просыпается, снова дёргает флажок, ура — входит в секцию.

Итого:
— целый квант мы жрали 100% процессора
— неизвестно сколько времени протупили
— нет гарантий против голодания (если третий поток влезет после первого, то второй продолжит своё активное ожидание)

Да лучше уж использовать штатный микрософтовский фьютекс CRITICAL_SECTION. У него тоже спинлок есть, но не такой беспощадный.

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

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

_>>Правильно ли я понимаю что весь "лок-фри" заключается в накрутке спин-лока? Если да, то:

S>задача стояла следующая:
S>читать можно всем, если никто не записывает (чтение блокирует только запись)
S>писать только одному, если никто не читает (запись блокирует чтение и запись другим потокам)

_>>2. Замените на mutex и будет намного лучше чем сейчас.

S>мутексом будет обеспечен доступ только одному потоку, при чем не важно чтение или запись

Смотрите про boost::shared_mutex или shared_lock (на счет названия не уверен) А паттерн называется MRSW (Multiple Reader Single Writer)

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

S>

S>template <class KEY_TYPE, class VALUE_TYPE>
S>class lock_free_map
S
S>

Самое первое и главное замечание, безотносительно реализации — это не map. Где итераторы? Где поиск?

Здравствуйте, Кодт, Вы писали:

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

S>>Покритикуйте мой lock-free:

К>Это не локфри, а просто чертовски дорогие фьютексы. (fast userspace mutex)

идем в википедию (извините, что в русскую):

Без блокировок (англ. lock-free)
Для алгоритмов без блокировок гарантируется системный прогресс по крайней мере одного потока. Например поток, выполняющий операцию «сравнение с обменом» в цикле, теоретически может выполняться бесконечно, но каждая его итерация означает, что какой-то другой поток совершил прогресс, то есть система в целом совершает прогресс.

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

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

S>задача стояла следующая:
S>читать можно всем, если никто не записывает (чтение блокирует только запись)
S>писать только одному, если никто не читает (запись блокирует чтение и запись другим потокам)

Это называется RW-Lock.

Реализаций полно — хоть велосипедных, хоть даже апишных. Начиная с WinVista, есть Slim Reader-Writer Lock (SRWLock):
http://msdn.microsoft.com/en-us/library/windows/apps/aa904937%28v=vs.85%29.aspx
Кстати, и условные переменные в винапи тоже с висты появились.

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

S>Покритикуйте мой lock-free:
это lock based алгоритм
для вашей задачи нужен RW lock

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

S>идем в

рекомендую сходить сюда: http://www.1024cores.net/home/lock-free-algorithms/introduction

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

S>у меня хотя бы один поток или пишет, или читает. конечно при условии, что система не тормознула его. я не прав?

У всех всегда хотя бы один поток или пишет, или читает. Вопрос в том, что делают остальные. Если ждут (и тут не важно тратят ли при этом процессорное время впустую) то это уже не wait-free. И если есть на чём ждать, то есть есть состояния то и не lock-free.
Проверяется очень просто. Если заморозыть один из потоков на каком либо этапе, остановит ли это работу всех остальных? Если такое возможно, то алгоритм не lock-free.

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

Вот это не стоит игнорировать:
S>

каждая его итерация означает, что какой-то другой поток совершил прогресс

В случае со спинлоком поток делает кучу итераций впустую. Как именно, выше описал Кодт.

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

S>у меня хотя бы один поток или пишет, или читает. конечно при условии, что система не тормознула его. я не прав?

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

Лок-фри выглядит иначе:
— два или более потока пришли, возникло состояние гонки
— в этой гонке кто-то победил, а другой либо сразу оказался на втором месте (wait-free), либо пошёл на второй круг
Если тот, кто собрался победить, заснул на полпути, — победит второй.

Лок-фри алгоритмы так сделаны, что состояние гонки ни при каких условиях не ломает инвариант. В отличие от обычного состояния гонки.

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

S>у меня хотя бы один поток или пишет, или читает. конечно при условии, что система не тормознула его. я не прав?

здесь

Автор: remark
Дата: 27.04.08

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

S>Покритикуйте мой lock-free:

Мне понравилось. Только его надо назвать правильно — heavy-cpu-load map

А за что мне Vzhyk оценку поставил? Я ведь всего-лишь поприкалывался. Тем более, что отвечающие выше вроде как всё "разжевали".

05.09.2013 19:35, ArtDenis пишет:

> А за что мне Vzhyk оценку поставил? Я ведь всего-лишь поприкалывался.
Хорошее название придумал.

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


L>Самое первое и главное замечание, безотносительно реализации — это не map. Где итераторы? Где поиск?


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

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

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

S>>у меня хотя бы один поток или пишет, или читает. конечно при условии, что система не тормознула его. я не прав?

Ops>здесь

Автор: remark
Дата: 27.04.08

Первый же абзац:

Обычно это означает, что используются только такие примитивы как atomic_exchange, atomic_increment, atomic_fetch_and_add (InterlockedExchange, InterlockedIncrement, InterlockedExchangeAdd), и в алгоритме нет циклов, на выполнение которых могут повлиять другие потоки. atomic_compare_exchange (InterlockedCompareExchange) обычно не используется

InterlockedIncrement часто реализуется через InterlockedExchangeAdd который реализуется через InterlockedCompareExchange