Как я упоминал в своих предыдущих заметках, основными трудностями при реализации lock-free структур данных являются ABA-проблема и удаление памяти. Я разделяю эти две проблемы, хоть они и связаны: дело в том, что существуют алгоритмы, решающие только одну из них.
В этой статье я дам обзор известных мне методов безопасного удаления памяти (safe memory reclamation) для lock-free контейнеров. Демонстрировать применение того или иного метода я буду на классической lock-free очереди Майкла-Скотта [MS98].

В предыдущей статье мы заглянули внутрь процессора, пусть и гипотетического. Мы выяснили, что для корректного выполнения параллельного кода процессору необходимо подсказывать, до каких пределов ему разрешено проводить свои внутренние оптимизации чтения/записи. Эти подсказки – барьеры памяти. Барьеры памяти позволяют в той или иной мере упорядочить обращения к памяти (точнее, кэшу, — процессор взаимодействует с внешним миром только через кэш). “Тяжесть” такого упорядочения может быть разной, — каждая архитектура может предоставлять целый набор барьеров “на выбор”. Используя те или иные барьеры памяти, мы можем построить разные модели памяти — набор гарантий, которые будут выполняться для наших программ.

В этой статье мы рассмотрим модель памяти C++11.

В этой статье я даю краткий обзор того, как применять библиотеку lock-free структур данных libcds. В реализацию я углубляться здесь не буду, — это просто взгляд извне, взгляд со стороны пользователя библиотеки.

Библиотека libcds имеет свою точку зрения на многие известные структуры данных. Отчасти это объясняется целевой областью – lock-free структуры данных довольно минималистичны по набору предоставляемых методов, — отчасти желанием выйти за ограничения и решения стандартной библиотеки STL. Что из этого получилось – решать пользователям libcds.

Кому интересно – добро пожаловать под кат

Построение lock-free структур данных зиждется на двух китах – атомарных операциях и способах упорядочения доступа к памяти. В этой статье речь пойдет об атомарности и атомарных примитивах.

Анонс. Спасибо за теплый прием Начал! Вижу, что тема lock-free интересна хабрасообществу, это меня радует. Я планировал построить цикл по академическому принципу, плавно переходя от основ к алгоритмам, попутно иллюстрируя текст кодом из libcds. Но часть читателей требует зрелищ не мешкая показать, как пользоваться библиотекой, особо не рассусоливая. Я согласен, в этом есть свой резон. В конечном счете, и мне не так интересно, что там внутри boost, — опишите, как его применять! Поэтому свой эпический цикл я разделю на три части: Основы, Внутри и Извне. Каждая статья эпопеи будет относится к одной из частей. В Основах будет рассказываться о низкоуровневых вещах, вплоть до строения современных процессоров; это часть для почемучек вроде меня. Внутри будет освещать интересные алгоритмы и подходы в мире lock-free, — это скорее теория о том, как реализовать lock-free структуру данных, libcds будет неисчерпаемым источником C++ кода. В Извне будут статьи о практике применения libcds, — программные решения, советы и FAQ. Извне будет питаться вашими вопросами/замечаниями/предложениями, дорогие хабражители.

А пока я судорожно готовлю начало Извне, — первая часть Основ. Статья во многом не о C++ (хотя и о нем тоже) и даже не о lock-free (хотя без atomic lock-free алгоритмы неработоспособны), а о реализации атомарных примитивов в современных процессорах и о базовых проблемах, возникающих при использовании таких примитивов.
Атомарность — это первый круг ада низкий уровень из двух.

Я надеюсь, что эта статья станет началом цикла заметок о lock-free структурах данных. Я хочу поделиться с хабрасообществом своим опытом, наблюдениям и размышлениями о том, что такое lock-free структуры данных, как их реализовывать, подходят ли концепции контейнеров стандартной библиотеки STL к lock-free контейнерам, и когда стоит (и стоит ли вообще) применять lock-free структуры данных.

Как вы, наверное, догадались, эта статья посвящена lock-free очередям.

Очереди бывают разные. Они могут различаться по числу писателей (producer) и читателей (consumer) – single/multi producer — single/multi consumer, 4 варианта, — они могут быть ограниченными (bounded, на основе предраспределенного буфера) и неограниченными, на основе списка (unbounded), с поддержкой приоритетов или без, lock-free, wait-free или lock-based, со строгим соблюдением FIFO (fair) и не очень (unfair) и т.д. Подробно типы очередей описаны в этой и этой статьях Дмитрия Вьюкова. Чем более специализированы требования к очереди, тем, как правило, более эффективным оказывается её алгоритм. В данной статье я рассмотрю самый общий вариант очередей — multi-producer/multi-consumer unbounded concurrent queue без поддержки приоритетов.

Со времени предыдущего поста из жизни lock-free контейнеров прошло немало времени. Я рассчитывал быстро написать продолжение трактата об очередях, но вышла заминка: о чем писать, я знал, но реализации на C++ этих подходов у меня не было. «Не годится писать о том, что сам не попробовал», — подумал я, и в результате я попытался реализовать в libcds новые алгоритмы очередей.
Сейчас настал момент, когда я могу аргументированно продолжить свой цикл. В данной статье закончим с очередями.

Кратко напомню, на чем я остановился. Были рассмотрены несколько интересных алгоритмов lock-free очередей, а под занавес приведены результаты их работы на некоторых синтетических тестах. Главный вывод — всё плохо! Надежды на то, что lock-free подход на магическом compare-and-swap (CAS) даст нам пусть не линейный, но хотя бы какой-то рост производительности с увеличением числа потоков, не оправдались. Очереди не масштабируются. В чем причина?..

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

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

Давайте ещё раз. Бывают хорошие условия, бывают нормальные, бывают плохие. Одни можно превратить в другие. Но если вы понимаете, что из плохих условий не сделать нормальные, то единственный логичный выход – остановить переговоры как можно быстрее. Вам не нужны компромиссы, странные пути решения и долгие разговоры. Вам нужно встать и уйти.

Разработка игр — постоянно актуальная тема: всем нравится играть в игры, их охотно покупают, поэтому их выгодно продавать. Но при разработке хороших игр следует обращать немало внимания на производительность. Никому не понравится игра, «тормозящая» или работающая рывками даже на не самых мощных устройствах.
В этой статье я покажу, как разработать простую футбольную 3D игру с использованием Microsoft DirectX и C++, хотя главным образом я занимаюсь разработкой на C#. В прошлом я довольно много работал с C++, но теперь этот язык для меня уже не столь прост. Кроме того, DirectX для меня является новинкой, поэтому эту статью можно считать точкой зрения новичка на разработку игр. Прошу опытных разработчиков простить меня за возможные ошибки.

4 октября прошел финальный раунд крупнейшей в России ежегодной олимпиады по спортивному программированию Russian Code Cup. Победителем Russian Code Cup 2014 и обладателем главного приза — $10000 — стал Геннадий Короткевич. Второе место занял Петр Митричев — он получил $5000. Третьим финишировал Егор Куликов, его денежный приз составил $3000. Также в этом году впервые были награждены все участники, вошедшие в первую десятку: обладатели 4-10 мест получили по $1000.

Хакатоны Imagine Cup – это уникальные двухдневные мероприятия, которые проводит Майкрософт совместно с Фондом Развития Интернет-Инициатив (ФРИИ) специально для тех, кто хотел бы научиться создавать современные мобильные и облачные приложения. В ближайшие пару месяцев мы посетим 8 разных городов России, чтобы помочь начинающим разработчикам придумать и создать новые приложения на платформе Майкрософт, а также провести незабываемую ночь в компании с компьютерами и единомышленниками.

Этот пост предназначается всем любителям платформы .NET и языка C#. Думаю, многие встречали на просторах сети разнообразные задачки на понимание тех или иных особенностей платформы или языка. Я большой любитель подобных задачек и головоломок. Они помогают глубже понять определённые области и повысить собственные программистские навыки. Однажды я решил сделать подборку подобных задачек, чтобы можно было показывать другим людям и обсуждать нюансы работы с .NET/C#. Когда задачек накопилось достаточное количество, появилась новая мысль — оформить мою подборку в виде книжки. Вашему вниманию предоставляется текущий вариант этого сочинения под названием «Задачник.NET».


Читать online
Скачать PDF-версию
Исходные коды на GitHub

Привет, Хабр!
Ничего не писал со времен своей первой статьи, решил, что пора это исправить.

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

Ниже я даю рецензии на книжки, которые считаю очень полезными в различных разделах computer science, которые используются в геймдеве. Я намеренно опускаю книги по C++ и алгоритмам: мне кажется, эта тема уже настолько изучена и освещена, что больше про нее не стоит рассказывать.

Я старался покрыть максимальное количество разных топиков, особенно тех, что спрашивают на собеседованиях. Я старался воздерживаться от domain-specific литературы: профессионалы и так знают. Все картинки содержат ссылки на амазон.

А какие книжки нравятся вам?
Также в комментах можете писать, на какие темы вам были бы интересны посты.

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

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

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

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

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

Если вы недовольны своей работой, вам наверняка порой приходит в голову мысль: «Пора бросать это дело». Так почему же вы не бросаете?

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

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

Мы в Alconost перевели для вас статью Александра Кьерульфа, называющего себя одним из мировых экспертов по счастью на работе. Он проанализировал 10 самых распространенных оправданий, мешающих людям бросить опостылевшее рабочее место.

Статья “Как обсуждать деньги с руководством или почему иногда останавливаются карьеры?” неожиданно набрала +165 и под 100 тысяч просмотров, и мы решили продолжить переговорно-зарплатную тематику.

Сегодня публикуем статью нашего коллеги Дмитрия Коткина, уже полюбившегося хабровчанам по теме противостояния давлению в переговорах.

Признаться, мы долго думали, публиковать ли этот материал, потому что тема денег — крайне неоднозначна, и всегда поляризует аудиторию. Более того, статья была написана не для ИТ-шников. Но в конце концов решили статью запостить, потому что приемы там изложены, как нам показалось, достаточно универсальные, и в конце концов там не предлагается вести себя на собеседовании как здесь:

Дмитрий Коткин “Переговоры о зарплате. Практические рекомендации.”

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

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

Disclaimer: Статья носит чисто информационно-развлекательный характер, поскольку мне не известны приложения предлагаемой информации. Также, мне интересно упорядочить обрывочные сведения, которые мне удалось выяснить. И, возможно, обнаружить в них шероховатости. Возможно, мне придут в голову новые эксперименты.

Надеюсь, что статья развлечет вас, хотя я буду писать четко и по делу.

Иллюстрация к последней задаче.

Существуют задачи с простыми и, казалось бы, очевидными решениями, которые, однако, трудно найти. При их решении опасно полагаться на интуицию, ведь правильный ответ зачастую совсем не совпадает с тем, который она подсказывает. В данной статье я предлагаю подборку из 10 таких заданий, упорядоченных по возрастанию сложности; их решения убраны под спойлер. Для получения верных ответов не нужно обладать какими-то специальными знаниями, достаточно лишь находчивости и знания школьной программы.

В прошедшее воскресенье состоялся отборочный раунд Russian Code Cup 2014. В нем участвовало 802 программиста, показавшие лучшие результаты в четырех квалификациях. В этом этапе участникам предстояло за 3 часа решить шесть задач, что на один час и на одну задачу больше, чем в квалификационных раундах. Да и задачи были существенно сложнее, чем предыдущие. За время соревнования из 802-х только 444 участника смогли решить хотя бы одну задачу. Всего было отправлено 3271 решения, из них правильных 1402.