• 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 без поддержки приоритетов.
      Читать дальше →
      • +68
      • 40.6k
      • 8
    • Lock-free структуры данных. Эволюция стека


        В предыдущих своих заметках я описал основу, на которой строятся lock-free структуры данных, и базовые алгоритмы управления временем жизни элементов lock-free структур данных. Это была прелюдия к описанию собственно lock-free контейнеров. Но далее я столкнулся с проблемой: как построить дальнейший рассказ? Просто описывать известные мне алгоритмы? Это довольно скучно: много [псевдо-]кода, обилие деталей, важных, конечно, но весьма специфических. В конце концов, это есть в опубликованных работах, на которые я даю ссылки, и в гораздо более подробном и строгом изложении. Мне же хотелось рассказать интересно об интересных вещах, показать пути развития подходов к конструированию конкурентных контейнеров.
        Хорошо, — подумал я, — тогда метод изложения должен быть такой: берем какой-то тип контейнера — очередь, map, hash map, — и делаем обзор известных на сегодняшний день оригинальных алгоритмов для этого типа контейнера. С чего начать? И тут я вспомнил о самой простой структуре данных — о стеке.
        Читать дальше →
      • Lock-free структуры данных. Внутри. RCU


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

          Речь пойдет об ещё одной технике безопасного освобождения памяти для lock-free контейнеров — RCU. Эта техника существенно отличается от рассмотренных ранее алгоритмов a la Hazard Pointer.

          Read – Copy Update (RCU) – техника синхронизации, предназначенная для «почти read-only», то есть редко изменяемых, структур данных. Типичными примерами такой структуры являются map и set – в них большинство операций является поиском, то есть чтением данных. Считается, что для типичного map'а более 90% вызываемых операций — это поиск по ключу, поэтому важно, чтобы операция поиска была наиболее быстрой; синхронизация поиска в принципе не нужна — читатели при отсутствии писателей могут работать параллельно. RCU обеспечивает наименьшие накладные расходы как раз для read-операций.

          Откуда взялось название Read – Copy Update? Первоначально идея была очень проста: есть некоторая редко изменяемая структура данных. Если нам требуется изменить её, то мы делаем её копию и производим изменение — добавление или удаление данных — именно в копии. При этом параллельные читатели работают с первоначальной, не измененной структурой. В некоторый безопасный момент времени, когда нет читателей, мы можем подменить структуру данных на измененную копию. В результате все последующие читатели будут видеть изменения, произведенные писателем.

          Читать дальше →
        • Lock-free структуры данных. Внутри. Схемы управления памятью


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

            Читать дальше →
          • Lock-free структуры данных. Основы: Модель памяти


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

              В этой статье мы рассмотрим модель памяти C++11.
              Читать дальше →
              • +66
              • 69.2k
              • 8
            • Lock-free структуры данных. Извне: введение в libcds


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

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

                Кому интересно – добро пожаловать под кат
                Читать дальше →
                • +49
                • 27.2k
                • 5
              • Lock-free структуры данных. Основы: откуда пошли быть барьеры памяти

                • Translation

                Как только я заинтересовался lock-free алгоритмами, меня стал мучить вопрос – а откуда взялась необходимость в барьерах памяти, в «наведении порядка» в коде?
                Конечно, прочитав несколько тысяч страниц руководств по конкретной архитектуре, мы найдем ответ. Но этот ответ будет годен для этой конкретной архитектуры. Есть ли общий? В конце концов, мы же хотим, чтобы наш код был портабелен. Да и модель памяти C++11 не заточена под конкретный процессор.
                Наиболее приемлемый общий ответ дал мне мистер Paul McKenney в своей статье 2010 года Memory Barriers: a Hardware View of Software Hackers. Ценность его статьи – в общности: он построил некоторую упрощенную абстрактную архитектуру, на примере которой и разбирает, что такое барьер памяти и зачем он был введен.
                Вообще, Paul McKenney – известная личность. Он является разработчиком и активным пропагандистом технологии RCU, которая активно используется в ядре Linux, а также реализована в последней версии libcds в качестве ещё одного подхода к безопасному освобождению памяти (вообще, о RCU я хотел бы рассказать отдельно). Также принимал участие в работе над моделью памяти C++11.
                Статья большая, я даю перевод только первой половины. Я позволил себе добавить некоторые комментарии, [которые выделены в тексте так].
                Передаю слово Полу
              • Lock-free структуры данных. Основы: Атомарность и атомарные примитивы


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

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

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

                    Представьте, что вы натыкаетесь на магазин или частного продавца, который настолько пророс корнями в США, да к тому же еще и параноидален, что его система биллинга наотрез отказывается принимать ваши православные визы и мастеркарды, эмитированные отечественными банками.

                    Казалось бы, ничего не остается, как купить у соответствующих товарищей credit card with US billing понуро закрыть страницу магазина, уйдя на поиски более дружелюбного продавца, как тут вы замечаете знакомый шильдик PayPal, который повесил владелец сайта, приглашая всех приобрести его товар, заплатив максимально удобным для вас способом. И вот она, победа, вы деловито шествуете по страницам чекаут процесса, как вдруг осознаете, что продавец малого того, что не принимает православные карты к оплате, так еще и на настолько обнаглел, что отправляет свой товар только в пределах своей отчизны, забивая на весь мир и связанные с международной отправкой проблемы.

                    Если получить адрес для получения посылок в США уже давно не проблема, то вот как получить американский адрес, доступный для выбора при оплате PayPal? Да, система PayPal не позволяет штатным образом владельцам аккаунтов, зарегистрированных в стране, отличной от США, добавить американский адрес доставки.

                    Но на каждую хитрую жопу, как известно…
                    Читать дальше →
                  • Краткое введение в rvalue-ссылки

                    • Translation
                    Перевод статьи «A Brief Introduction to Rvalue References», Howard E. Hinnant, Bjarne Stroustrup, Bronek Kozicki.

                    Rvalue ссылки – маленькое техническое расширение языка C++. Они позволяют программистам избегать логически ненужного копирования и обеспечивать возможность идеальной передачи (perfect forwarding). Прежде всего они предназначены для использования в высоко производительных проектах и библиотеках.

                    Введение


                    Этот документ даёт первичное представление о новой функции языка C++ – rvalue ссылке. Это краткое учебное руководство, а не полная статья. Для получения дополнительной информации посмотрите список ссылок в конце.

                    Rvalue ссылка


                    Rvalue ссылка – это составной тип, очень похожий на традиционную ссылку в C++. Чтобы различать эти два типа, мы будем называть традиционную C++ ссылку lvalue ссылка. Когда будет встречаться термин ссылка, то это относится к обоим видам ссылок, и к lvalue ссылкам, и к rvalue ссылкам.
                    Читать дальше →
                  • Избавление от артефактов сжатия PVRTC текстур

                    Проблематика


                    При разработке мобильных игр многие сталкиваются с необходимостью уменьшения занимаемой оперативной памяти или размера дистрибутива. Чаще всего самые тяжеловесные ассеты в проекте это текстуры. Несжатая текстура размером 1024х1024 занимает в районе 4 Мб. А в сцене обычно таких текстур не мало. И если мы хотим, чтобы сцены нашей игры загружались быстрее и не занимали слишком много оперативной памяти, мы вынуждены подвергать текстуры компрессии. В unity3d для мобильных устройств существует несколько типов сжатия. Думаю, описанный здесь подход для повышения качества результата компрессии текстур будет справедлив для всех алгоритмов, но рассматривать мы будем на примере PVRTC. У него есть один большой плюс, и один большой минус. Размер текстур уменьшается в восемь раз, но при этом появляются ужасные артефакты, особенно на прозрачных текстурах. Данная тема призвана помочь в борьбе с последними.
                    Узнать как
                  • Смешивание текстур ландшафта

                    • Tutorial


                    В данной статье я расскажу об алгоритме смешивания текстур, который позволяет привести внешний вид ландшафта ближе к естественному. Этот алгоритм легко может быть использован как в шейдерах 3D игр, так и в 2D играх.

                    Статья рассчитана на начинающих разработчиков игр.
                    Читать дальше →
                  • Как получить американский диплом о высшем образовании дистанционно

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

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

                      Читать дальше →
                    • Знай сложности алгоритмов

                      • Translation
                      Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!
                      Читать дальше →
                    • Путешествие через вычислительный конвейер процессора

                      Так как карьера программиста тесно связана с процессором, неплохо бы знать как он работает.

                      Что происходит внутри процессора? Сколько времени уходит на исполнение одной инструкции? Что значит, когда новый процессор имеет 12, или 18, или даже 31-уровневый конвейер?

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

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

                      Эта статья рассказывает, как устроен вычислительный конвейер x86 процессора.
                      Читать дальше →
                    • Архив интересного кода

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

                        Примеры на сайте преимущественно закодированы в C++, поскольку STL предоставляет прекрасную базу для выражения алгоритмов, работающих с различными типами данных. Структуры данных реализованы на Java.

                        Кит Шварц дает разрешение использовать свой код всем желающим без всяких ограничений.
                        Читать дальше →
                      • Разработка на PC и производительность — Memory Latency

                          Herb Sutter (автор Exceptional C++, бывший глава ISO C++ standards committee, мистер Free Lunch Is Over и прочая, и прочая) работает в Microsoft и иногда по средам читает атомные лекции.

                          Я наконец-то на одну такую попал, и очень радовался. На умных мужиков всегда радостно поглядеть и послушать.
                          Для отчета — кроме Херба, видел живого Олександреску и живого Walter Bright (который "D").

                          Лекция называлась «Machine Architecture: Things Your Programming Language Never Told You» (здесь можно скачать презентацию и видео) и была про конкретную часть abstraction penalty — Memory Latency.

                          Я попытаюсь коротко рассказать о ключевой мысли лекции. Она простая, очевидная и тысячу раз сказанная. Думаю, еще раз повторить азбуку — никогда не повредит.
                          Читать дальше →
                        • Единорог вновь готов к общению с Си++ программистами

                            Единорог вернулся
                            Приглашаю Си/Си++ программистов присоединиться к блогу PVS-Studio. Вы узнаете о разных интересных вещах из мира Си/Си++ и о том, кто, где и как программирует. Расскажу немного о том, что не было опубликовано на Хабре за время нашего отсутствия здесь.
                            Читать дальше →
                          • Хорошая беседа о борьбе с прокрастинацией

                            • Tutorial
                            Давно знаком и являюсь поклонником Яны Франк (ака Миумау в ЖЖ — www.miumau.lj.ru). Был на ее встрече позавчера, записал всю встречу на видео. Что мне понравилось: много дельных советов о борьбе с творческим кризисом, прокрастинацией в личном развитии и астенизацией. Все эти подходы применимы не только среди «художников», или тех чьи профессии считаются «творческими», но и вообще среди людей, которые хотят получать удовольствие от работы.

                            Вначале пару минут вступления-хождения.

                          • Как я Quake в браузере делал


                              2 месяца назад я выложил на GitHub первую бета-сборку WebQuake — порта первого Quake, работающего в браузере через WebGL.

                              В этом посте я бы хотел вам рассказать о подробностях разработки и реализации движка: как сделана графика, как работает звук, и так далее.
                              Читать дальше →