Как стать автором
Обновить
1
Карма
0
Рейтинг
  • Публикации
  • Комментарии

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

ПрограммированиеC++
Перевод

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

Новости

Показать еще

Quotient filter

ПрограммированиеАлгоритмы
Quotient filter — это вероятностная структура данных, позволяющая проверить принадлежность элемента множеству. Она описана в 2011 г. как замена фильтру Блума. Ответ может быть:
— элемент точно не принадлежит множеству;
— элемент возможно принадлежит множеству.

Читать дальше →
Всего голосов 45: ↑43 и ↓2 +41
Просмотры14.4K
Комментарии 16

Ищем альтернативы Google Reader

IT-компании
Как недавно стало известно, с 1 июля закрывается Google Reader. Незамедлительно я начал искать альтернативы.
В данном посте я рассматриваю только онлайн-ридеры. Плагины типа Feedly не рассматриваю.
Читать дальше →
Всего голосов 72: ↑57 и ↓15 +42
Просмотры100.2K
Комментарии 133

Жонглирование. Теория. Практика

Научно-популярное
Настороженно отношусь к непрофильным топикам, но решил написать этот по следующим причинам:
  • У жонглирования есть своя теория — стройная и математически привлекательная!
  • Мы живем не только работой. Жонглирование — отличное развлечение и разминка после долгого сидения за компом.
  • В пятницу приятно немного расслабиться и почитать не очень серьезные статьи. К тому же, будет чем заняться на выходные, особенно если у вас не было определенных планов.

Теория


Утверждать, что жонглирование — это последовательность бросков, все равно, что сказать, что музыка — это просто последовательность нот. Нельзя назвать это неправдой, но любой, хоть немного знакомый с музыкальной теорией, возмутится последним определением — столь поверхностным и недалеким.
Читать дальше →
Всего голосов 252: ↑242 и ↓10 +232
Просмотры19K
Комментарии 45

Модель функционального разделения сознания и бессознательного. Введение

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

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

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

Здесь я дам отрефакторинную версию одной моей научно-популярной статьи 2006 года, которая как я думал стоит в том же ряду по смысловой нагрузке, как те которые выше я критиковал. Но теперь я все же вижу, что стилистика хоть и такая же, но за моей статьей может стоять (и стоит) четкая техническая постановка. О ней мы поговорим позже, а пока так сказать лирическое вступление. Но важно то, что я лирически подвожу к одной существенной нерешенной проблеме из области ИИ.

Читать дальше →
Всего голосов 39: ↑30 и ↓9 +21
Просмотры5.3K
Комментарии 69

«Жидкий перцептрон» или гипотеза как реализовать реальную парралельность

БиотехнологииИскусственный интеллект
В комментариях к статье Алгоритмическая неразрешимость – это не препятствие для алгоритмического ИИ я высказался, в свете того, что

Почему-то все зациклились на задачах NP. Но никто почему то не ставит задачи БЫСТРЕЕ решать задачи класса P (вплоть до мгновенного ответа)


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

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


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

Но все по порядку.

Читать дальше →
Всего голосов 42: ↑31 и ↓11 +20
Просмотры1.9K
Комментарии 89

Алгоритмическая неразрешимость – это не препятствие для алгоритмического ИИ

Искусственный интеллект
В замечательном произведении Аркадия и Бориса Стругацких «Понедельник начинается в субботу» есть такой диалог:
– Голубчики, – сказал Фёдор Симеонович озабоченно, разобравшись в почерках. – Это же проблема Бен Бецалеля. Калиостро же доказал, что она не имеет решения.
– Мы сами знаем, что она не имеет решения, – сказал Хунта, немедленно ощетиниваясь. – Мы хотим знать, как её решать.
– Как-то странно ты рассуждаешь, Кристо… Как же искать решение, когда его нет? Бессмыслица какая-то…
– Извини, Теодор, но это ты очень странно рассуждаешь. Бессмыслица – искать решение, если оно и так есть. Речь идёт о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, к сожалению, не доступен.
Читать дальше →
Всего голосов 94: ↑89 и ↓5 +84
Просмотры11.5K
Комментарии 167

Splay-деревья

Образовательные проекты JetBrainsАлгоритмыМатематика
Tutorial
Сбалансированное дерево поиска является фундаментом для многих современных алгоритмов. На страницах книг по Computer Science вы найдете описания красно-черных, AVL-, B- и многих других сбалансированных деревьев. Но является ли перманентная сбалансированность тем Святым Граалем, за которым следует гоняться?

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

Сегодня я расскажу о splay-деревьях. Эти деревья не являются перманентно сбалансированными и на отдельных запросах могут работать даже линейное время. Однако, после каждого запроса они меняют свою структуру, что позволяет очень эффективно обрабатывать часто повторяющиеся запросы. Более того, амортизационная стоимость обработки одного запроса у них , что делает splay-деревья хорошей альтернативой для перманентно сбалансированных собратьев.
Читать дальше...
Всего голосов 88: ↑83 и ↓5 +78
Просмотры52.9K
Комментарии 26

Решение задачи кластеризации методом градиентного спуска

Data MiningАлгоритмы
Привет. В этой статье будет рассмотрен способ кластеризации данных, используя метод градиентного спуска. Честно говоря данный способ носит больше академический характер, нежели практический. Реализация этого метода мне понадобилась в демонстрационных целях для курса по машинному обучению, что бы показать как одинаковые задачи можно решить различными способами. Хотя конечно если вы планируете осуществить кластеризацию данных, используя дифференцируемую метрику, для которой вычислительно труднее найти центроид, нежели подсчитать градиент на некотором наборе данных, то этот метод может быть полезным. Итак если вам интересно как можно решить задачу k-means кластеризации с обобщенной метрикой используя метод градиентного спуска, прошу под кат. Код на языке R.
Читать дальше →
Всего голосов 50: ↑48 и ↓2 +46
Просмотры24.9K
Комментарии 8

Создание виртуальной волны

Mail.ru GroupРазработка игр


Как всем известно, 71% поверхности Земли занимает вода. К сожалению или к счастью, корректно изобразить океан умеют единицы. Иван Айвазовский вошел в учебники живописи благодаря одним только морским пейзажам. В компьютерных играх все еще сложнее. Когда-то море в них обозначали скоплением синих пикселей, раскрашенных белыми квадратами пены. Со временем виртуальные моря стали больше похожи на снимки из отпуска, научились качать волну и покрываться рябью, в которой иногда даже отражались очертания парусников. Но они оставались самостоятельной стихией: натолкнувшись на берег, волна превращалась в незамысловатые угловатые полигоны. Настоящий прибой логично взаимодействует с пляжем, увлажняет песок и с шуршанием откатывается назад. Такого правдоподобия удалось добиться только в современных играх. В том числе в нашем Skyforge. И хоть в основные события будут разворачиваться на суше, игроки попадут и на тропические острова, и в шумные порты. Вода будет постоянно рядом. Ее «правильный» облик будет играть большую роль. И воссоздание морской стихии – серьезная математическая задача. Расскажу об этапах ее реализации.
Читать дальше →
Всего голосов 178: ↑164 и ↓14 +150
Просмотры58.2K
Комментарии 33

Моделирование гидродинамики: Lattice Boltzmann Method

АлгоритмыМатематика
Извержение вулкана
Моделирование извержения вулкана
с помощью Lattice Boltzmann Method. (с) Источник

В этой статье я расскажу о численном методе моделирования гидродинамики Lattice Boltzmann Method, LBM. На русском—метод решёточных уравнений Больцмана. Он превосходит другие известные методы (например, finite element method) в легкости распараллеливания, возможности моделирования многофазных потоков, моделировании потоков в пористых средах. Кроме того, вычислительный алгоритм содержит только простейшие арифметические операции. Метод весьма новый, первые коммерческие продукты на его основе стали появляться около 2010 года.
Читать дальше →
Всего голосов 33: ↑31 и ↓2 +29
Просмотры45.9K
Комментарии 25

Создание конструктора кирпичной кладки для сайта

Разработка веб-сайтовPHPОбработка изображений
Из песочницы
Компания Сиджеко занимается поддержкой сайта организации Реконстрой, которая продаёт и доставляет кирпич, черепицу, архитектурный декор и многие другие строительные материалы в Центральном Черноземье.

В процессе работы над сайтом возникла идея конструктора кладки.

У немецкого концерна «Feldhaus Klinker» существуют модельные ряды кирпича «Vascu Mix» и «Sintra Mix», которые специально предназначены для смешивания в разных пропорциях и создания неповторимого рисунка кладки. К ним существует ряд замазок «Quick Mix», применяемых при замазывании швов кладки между кирпичами. Для демонстрации этого подхода мы решили сделать конструктор кирпичной кладки, аналогов которому в рунете я пока не видел (буду рад примерам).

Конструктор кирпичной кладки

Подробности создания
Всего голосов 45: ↑30 и ↓15 +15
Просмотры21.9K
Комментарии 25

Где таится история космоса

DIY или Сделай сам
Надеюсь все знают про НПО им. С.А. Лавочкина – предприятие которое с 1965 года реализует все межпланетные миссии СССР и России. По крайней мере, наверняка все слышали об их продукции: «Луна-3», «Луна-9», «Луна-16», «Луноход», «Марс-3», «Марс-5», «Венера-7», «Венера-13», «Вега», «Фобос-Грунт», «Радиоастрон», «Электро-Л»… Как всякое предприятие космической отрасли оно находится под режимом секретности, и даже в музей можно попасть только по предварительной заявке и в составе групповой экскурсии.

Всего месяц назад я с удивлением узнал, что в НПОЛ, помимо музея, еще есть загадочное место под ироничным названием «Ангар 18».



В отличие от американского аналога, он скрывает не инопланетные корабли, а земные. Но богатство коллекции, собранной на незначительной площади, уверенно может конкурировать с ныне разгромленным павильоном «Космос» на ВДНХ. Увидев такое космическое изобилие, я поначалу был просто ошеломлен. Потом узнал, что Луноход – это ходовая модель; «Венера-7» — технологический макет, проходивший термовакуумные испытания перед полетом в 1970 году; и почти все модели содержат элементы, которые создавались для реальных аппаратов, успехами которых я вдохновлялся еще в детстве. Короче, состояние шока отпустило далеко не сразу. Но обо всем по порядку.
Читать дальше →
Всего голосов 201: ↑200 и ↓1 +199
Просмотры51.9K
Комментарии 66

Введение в Android NDK

JavaC++Разработка под Android
Из песочницы
Для разработки приложений под ОС Android, Google предоставляет два пакета разработки: SDK и NDK. Про SDK существует много статей, книжек, а так же хорошие guidelines от Google. Но про NDK даже сам Google мало что пишет. А из стоящих книг я бы выделил только одну, Cinar O. — Pro Android C++ with the NDK – 2012.

Эта статья ориентирована на тех, кто ещё не знаком (или мало знаком) с Android NDK и хотел бы укрепить свои знания. Внимание я уделю JNI, так как мне кажется начинать нужно именно с этого интерфейса. Так же, в конце рассмотрим небольшой пример с двумя функциями записи и чтения файла. Кто не любит много текста, тот может посмотреть видео версию.
Читать дальше →
Всего голосов 64: ↑60 и ↓4 +56
Просмотры211.9K
Комментарии 28

Поиск решений в логических играх на примере гомоку

Алгоритмы
Из песочницы

Вступление


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

image

За такой нехитрой игрой мы прослушали не одну лекцию. Меня всегда раздражало, что моя блестящая стратегия разбивается о собственную невнимательность. Ну ничего, думал я, вот напишу программу, которая не будет делать ошибок, я тогда всем им покажу! Раз плюнуть! Пару циклов, правда, надо повозиться с пользовательским интерфейсом, но за пару вечеров управлюсь. С момента окончания института прошло 10 лет, а программу я всё ещё не написал.
Читать дальше
Всего голосов 40: ↑39 и ↓1 +38
Просмотры40.1K
Комментарии 11

Создаем платформер за 30 минут

C++Разработка игр
Tutorial
Здравствуйте! Сегодня мы будем писать платформер, используя C++, Box2D и SFML, а также редактор 2D карт для игр Tiled Map Editor.

image

Вот результат (карта создавалась 5 минут + во время сьемки игра тормозила + экран не так растянут — дефект Bandicam):



Исходники и exe — внизу статьи.
Читать дальше →
Всего голосов 88: ↑84 и ↓4 +80
Просмотры142.8K
Комментарии 14

Алгоритм Ахо-Корасик

ПрограммированиеC++Алгоритмы
Из песочницы

Вступление


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

Начальное описание


Алгоритм Ахо-Корасик реализует эффективный поиск всех вхождений всех строк-образцов в заданную строку. Был разработан в 1975 году Альфредом Ахо и Маргарет Корасик.
Опишем формально условие задачи. На вход поступают несколько строк pattern[i] и строка s. Наша задача — найти все возможные вхождения строк pattern[i] в s.

Суть алгоритма заключена в использование структуры данных — бора и построения по нему конечного детерминированного автомата. Важно помнить, что задача поиска подстроки в строки тривиально реализуется за квадратичное время, поэтому для эффективной работы важно, чтоб все части Ахо-Корасика ассимптотически не превосходили линию относительно длинны строк. Мы вернемся к оценке сложности в конце, а пока поближе посмотрим на составляющие алгоритма.
Читать дальше →
Всего голосов 69: ↑66 и ↓3 +63
Просмотры73.4K
Комментарии 16

Симуляция океана на WebGL

Разработка веб-сайтов
image

Небольшое красивое демо, выложенное Дэвидом Ли — посмотреть (обсуждение).



Большая часть «магии» сделана при помощи шейдеров GLSL на GPU, код на JavaScript с матрицами — необходимая заготовка для работы с 3D графикой. Алгоритм движения волн основан на методе, описанном Джерри Тессендорфом в статье «Симуляция волн океана», опубликованной на SIGGRAPH 2002 (по ссылке есть исходный код, который написан на С++); по теме можно почитать вот это.
Читать дальше →
Всего голосов 111: ↑105 и ↓6 +99
Просмотры50K
Комментарии 54

Использование Lua и C++ для обработки и хранения данных

C++Разработка игрLua
Из песочницы
Код статьи можно посмотреть здесь.
Чем так хорош Lua?

Когда-то я разрабатывал свою игру и задался вопросом: а какой формат данных лучше использовать для конфигурационных файлов?
Ведь удобно, когда создаёшь какой-либо объект, задавать различные начальные параметры не в самом коде, а в отдельных файлах. Это позволяет изменять некоторые параметры объектов без рекомпиляции, да и вообще даёт возможность менять их людям далёким от программирования.
Разработчики используют разные форматы: одни используют JSON, другие — XML, либо другие форматы данных. Ну а некоторые вообще хранят данные в .txt файлах или пишут свои парсеры. После рассмотрения различных форматов я остановился на Lua.

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

Вот, что выделяет Lua на фоне других форматов:
  • Lua легко использовать без дополнительных зависимостей (кроме одной библиотеки Lua и трёх .h файлов).
  • В Lua файлах данные можно инициализировать с помощью математических выражений или функций, написанных на Lua. Например:
    some_variable = math.sqrt(2) * 2
    some_variable2 = 64 * 16 - 32
    

  • Lua — очень быстрый язык, который к тому же не занимает много памяти.
  • У Lua лицензия MIT, которая позволяет использовать этот язык как в бесплатных, так и в коммерческих проектах, причём без всякой возни с бумагами. Как написано на сайте: «просто скачайте и пользуйтесь».
  • Lua комплируется практически везде, т.к. он написан на чистом C без использования дополнительных библиотек.
  • Данные можно хранить и сортировать в приятном глазу виде. Их легко читать и модифицировать в любом текстовом редакторе.

Начнём с простого примера, а затем я перейду к реализации класса.
Читать дальше →
Всего голосов 45: ↑44 и ↓1 +43
Просмотры38.2K
Комментарии 28

Создание 1k/4k intro для Linux, часть 4

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

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


Читать дальше →
Всего голосов 108: ↑104 и ↓4 +100
Просмотры31.7K
Комментарии 11

Информация

В рейтинге
5,773-й
Зарегистрирован
Активность