Это решение работает только если обе стороны поля четные, потому что основывается на факте, что при повороте вентеля четность посчитанной по вашему алгоритму величины поменяется только для клетки, для которой вы поворачиваете вентель, что для случая с нечетными сторонами не так. А автор предлагает играть в игру, где размер поля не обязательно 4 на 4.
Есть подозрение, что решить за линию от количества вентелей для случая когда одна из сторон (или обе) нечетна, нельзя.
Мало того, что он использует cast, он использует C-style cast, который в С++ по хорошему не должен применяться никогда. Выше объяснили, почему такой вариант как раз-таки работать не обязан.
Использование union — это хороший способ реализовать 64-ех битный tagged pointer в данной ситуации и избежать casts.
Какой вариант вы предлагаете, если union — это «крайне вредная оптимизация»?
union не обязателен, но важно не разбивать это присвоение на две команды. union упрощает с той точки зрения, что CAS принимает как аргумент long, и не придется делать каст, если сделать union.
Ваша точка зрения, что компилятор сообразит эти два присвоения преобразовать в одно 64-ех битное копирование неверно.
Почему -- смотрите под спойлер.
В следующем коде, если бы ваше предположение было верно, все три блока в thread2 были бы идентичны, и ни один из них никогда бы ничего не вывел. На деле же скомпилированный G++ код многократно выводят OMG1
Несколько комментариев:
1. Структура данных в статье — это стек, а не очередь, она не FIFO, а LIFO. Реализовать lock-free очередь очень сложно. Почти все статьи о lock-free очередях на связных списках не верны.
2. Из статьи не понятно, зачем нужен ocount. Это реализация так назвыемых tagged pointer. Идея в том, что если бы его не было, то возможен был бы такой сценарий (называется проблемой ABA — поэтому и структура в статье называется top_aba_t):
Пусть операция pop выглядит примерно так:
do {
long snapshot = stack->head;
long next = snapshot->next;
} while (!cas(&stack->head, next, snapshot));
В принципе код deque в статье делает именно это, но с ocount. Теперь рассмотрим такой сценарий: на вершине стека лежит элемент А, за ним элемент B (стек выглядит как A -> B). Мы запомнили snapshot = A, next = B.
В этот момент другой поток убрал элемент A, затем вставил элемент C, и вставил обратно А. Теперь стек выглядит как:
A -> C -> B
Операция pop просыпается, и ее CAS срабатывает (stack->head == snapshot, они оба равны A), и заменяет stack->head на B. Элемент C теряется.
С ocount такого не произойдет, потому что свежевставленный A будет иметь другой ocount, и CAS провалится.
ocount спасает конечно только на практике. В теории после того как мы запомнили snapshot и next другой поток может удалить A 2^18 раз, пока ocount не примет такое же значение как было, и ABA проблема опять произойдет.
На современном железе конечно никто не отводит под указатель 48 бит. Вместо этого используется две 64-битных переменных, идущих подряд, первая под указатель, вторая под ocount (теоретический сценарий с вставкой элемента А много раз становится еще более теоретическим), и используется double cas.
И пара мелких недочетов — в коде в реализации стека (очереди в терминологии статьи :)) ocount для новой переменной не копируется со старой, то есть он всегда будет равен единице (или, что более вероятно, какому-то мусору — переменная заводится на стеке, и конструктора у нее нет).
И вот такие конструкции:
Вообще говоря опасны — queue->both может поменяться между этими двумя строками. Кажется, что в этом случае это не приведет ни к чему страшному, просто провалится cas и начнется другая итерация, но не понятно, почему не присвоить в одну операцию (например можно top_aba_t сделать union с long long, и копировать этот long long).
Обычно описание ключевого слова сразу приводит пример с данными, которые могут быть в любой момент изменены из другой нити, аппаратным обеспечением или операционной системой.
Использовать volatile для переменных, к которым возможен доступ из нескольких потоков — это хороший способ прострелить себе ногу. Для этой цели есть atomic, а использование volatile почти всегда неверно.
Книжка со спрайтами в конце — это я полагаю книжка Владимира Шамиса? Где еще в первой главе вместо Hello World он писал про купающихся в море негритят? :)
Была таже самая ситауция — книжка по С++, из которой примеры не компилируются в C++ Builder, и вот эта книжкой Шамиса, которую понять было очень тяжело не понимая хорошо С++. И тоже помню как я прозрел, когда дошел до главы со спрайтами. Ну и похоже что писать стратегии в те времена было модно: о)
Я использую Кинезис. Мой главный страх был, что привыкнув к Кинезису я не смогу писать на обычной клавиатуре. Но так как кинезис только на работе, а дома вечером я все равно пишу на обычном лэптопе, то навыки сохраняются и те и те.
Клавиатура на картинке визуально имеет большинство преимуществ кинезиса — клавиши вертикально, все достижимо без движения рук. Не понятно только насколько удобно нажимать Backspace. Предполагается нажатие большим пальцем или указательным? Другая причина почему я люблю кинезис — это потому что для нажатия на фигурные скобки надо просто опустить безымянный палец и мизинец. На этой клавиатуре к ним надо тянуться мизинцем, либо двигать руку (как и на обычной) — это не удобно, и легко промахнуться.
Педали от кинезиса я бы не советовал. Есть не нулевой шанс, что перепрограммировать их не получится (по умолчанию педали соответствуют кнопкам мыши), потому что перепрограммировать их можно только на Windows XP. Я их купил, а компьютер с Windows XP ищу до сих пор. Windows 7 в режиме совместимости не залетала.
Я думаю причиной этого небольшого разногласия является мое устаревшее представление о быстром умножении. Лучшее, что я знаю, работает за степень примерно 2.7. На графе с 10000 вершин разница с кубом будет в 15 раз, но быстрое возведение в степень потребует еще логарифм, который от 10000 даст 14, и смысл потеряется, потому что у быстрого умножения костанта выше, чем у флойда.
Если есть алгоритм быстрого умножения заметно быстрее, чем за (N^2.7), то тогда мои размышления о флойде, вероятно, заметно отличались бы.
Даже если при больших N быстрое возведение в степень с быстрым умножением будут быстрее, чем флойд, я бы все равно остановился на флойде, хотя бы из-за его простоты.
Вариант с поисками в ширину тоже приятный — у него тоже кубическая сложность на плотных графах (а на разряженных еще меньше), но зато его можно легко запустить на нескольких процессорах сразу. Аналогично, если надо найти не матрицу достижимости, а все кратчайшие пути, на современном железе, наверное, N дийкстр будут очень эффективны, потому что их можно тоже легко распараллелить, сохраняя все ту же кубическую сложность.
Есть подозрение, что решить за линию от количества вентелей для случая когда одна из сторон (или обе) нечетна, нельзя.
Вариант в коде в статье использует casts:
Мало того, что он использует cast, он использует C-style cast, который в С++ по хорошему не должен применяться никогда. Выше объяснили, почему такой вариант как раз-таки работать не обязан.
Использование union — это хороший способ реализовать 64-ех битный tagged pointer в данной ситуации и избежать casts.
Какой вариант вы предлагаете, если union — это «крайне вредная оптимизация»?
Ваша точка зрения, что компилятор сообразит эти два присвоения преобразовать в одно 64-ех битное копирование неверно.
Ключи компиляции, которые я использовал:
g++ -std=c++0x test.cpp -pthread -m64 -O2
1. Структура данных в статье — это стек, а не очередь, она не FIFO, а LIFO. Реализовать lock-free очередь очень сложно. Почти все статьи о lock-free очередях на связных списках не верны.
2. Из статьи не понятно, зачем нужен ocount. Это реализация так назвыемых tagged pointer. Идея в том, что если бы его не было, то возможен был бы такой сценарий (называется проблемой ABA — поэтому и структура в статье называется top_aba_t):
Пусть операция pop выглядит примерно так:
В принципе код deque в статье делает именно это, но с ocount. Теперь рассмотрим такой сценарий: на вершине стека лежит элемент А, за ним элемент B (стек выглядит как A -> B). Мы запомнили snapshot = A, next = B.
В этот момент другой поток убрал элемент A, затем вставил элемент C, и вставил обратно А. Теперь стек выглядит как:
A -> C -> B
Операция pop просыпается, и ее CAS срабатывает (stack->head == snapshot, они оба равны A), и заменяет stack->head на B. Элемент C теряется.
С ocount такого не произойдет, потому что свежевставленный A будет иметь другой ocount, и CAS провалится.
ocount спасает конечно только на практике. В теории после того как мы запомнили snapshot и next другой поток может удалить A 2^18 раз, пока ocount не примет такое же значение как было, и ABA проблема опять произойдет.
На современном железе конечно никто не отводит под указатель 48 бит. Вместо этого используется две 64-битных переменных, идущих подряд, первая под указатель, вторая под ocount (теоретический сценарий с вставкой элемента А много раз становится еще более теоретическим), и используется double cas.
И пара мелких недочетов — в коде в реализации стека (очереди в терминологии статьи :)) ocount для новой переменной не копируется со старой, то есть он всегда будет равен единице (или, что более вероятно, какому-то мусору — переменная заводится на стеке, и конструктора у нее нет).
И вот такие конструкции:
Вообще говоря опасны — queue->both может поменяться между этими двумя строками. Кажется, что в этом случае это не приведет ни к чему страшному, просто провалится cas и начнется другая итерация, но не понятно, почему не присвоить в одну операцию (например можно top_aba_t сделать union с long long, и копировать этот long long).
Использовать volatile для переменных, к которым возможен доступ из нескольких потоков — это хороший способ прострелить себе ногу. Для этой цели есть atomic, а использование volatile почти всегда неверно.
Была таже самая ситауция — книжка по С++, из которой примеры не компилируются в C++ Builder, и вот эта книжкой Шамиса, которую понять было очень тяжело не понимая хорошо С++. И тоже помню как я прозрел, когда дошел до главы со спрайтами. Ну и похоже что писать стратегии в те времена было модно: о)
Клавиатура на картинке визуально имеет большинство преимуществ кинезиса — клавиши вертикально, все достижимо без движения рук. Не понятно только насколько удобно нажимать Backspace. Предполагается нажатие большим пальцем или указательным? Другая причина почему я люблю кинезис — это потому что для нажатия на фигурные скобки надо просто опустить безымянный палец и мизинец. На этой клавиатуре к ним надо тянуться мизинцем, либо двигать руку (как и на обычной) — это не удобно, и легко промахнуться.
Педали от кинезиса я бы не советовал. Есть не нулевой шанс, что перепрограммировать их не получится (по умолчанию педали соответствуют кнопкам мыши), потому что перепрограммировать их можно только на Windows XP. Я их купил, а компьютер с Windows XP ищу до сих пор. Windows 7 в режиме совместимости не залетала.
Использование volatile может легко попасть в те самые 99%. Почти всегда, когда люди используют volatile, они должны использовать atomic вместо этого.
Изменить слово — cw.
Если есть алгоритм быстрого умножения заметно быстрее, чем за (N^2.7), то тогда мои размышления о флойде, вероятно, заметно отличались бы.
Вариант с поисками в ширину тоже приятный — у него тоже кубическая сложность на плотных графах (а на разряженных еще меньше), но зато его можно легко запустить на нескольких процессорах сразу. Аналогично, если надо найти не матрицу достижимости, а все кратчайшие пути, на современном железе, наверное, N дийкстр будут очень эффективны, потому что их можно тоже легко распараллелить, сохраняя все ту же кубическую сложность.