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

Теория (греч. θεωρία — рассмотрение, исследование) — учение, система идей или принципов (вики). Именно в таком, самом широком смысле в обычно речи мы употребляем слово «теория» в каждодневной речи. Например, у меня есть теория почему машина не заводится — некоторый набор идей и выводов, объясняющий поломку. Однако, в научном мире теория имеет достаточно строгое и формальное значение и обязательно удовлетворяет определенному набору важных критериев.

Под катом много картинок и примеров, и совсем нет формул.

Праздничная неделя подходит к концу, но мы продолжаем публиковать лекции от Школы анализа данных Яндекса для тех, кто хочет провести время с пользой. Сегодня очередь курса, важность которого в наше время сложно переоценить – «Параллельные и распределенные вычисления».

Что внутри: знакомство с параллельными вычислениями и распределёнными системами обработки и хранения данных, а также выработка навыков практического использования соответствующих технологий. Курс состоит из четырех основных блоков: concurrence, параллельные вычисления, параллельная обработка больших массивов данных и распределенные вычисления.



Лекции читает Олег Викторович Сухорослов, старший научный сотрудник Центра грид-технологий и распределенных вычислений ИСА РАН. Доцент кафедры распределенных вычислений ФИВТ МФТИ. Кандидат технических наук.

Для некоторых мне известны возможные решения. Некоторые изредка встречаются на собеседованиях, реже чем об обедающих философах. Интересно было ознакомиться, как развлекаются в МассТехе.

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

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

Как только я заинтересовался 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 структуры данных, как их реализовывать, подходят ли концепции контейнеров стандартной библиотеки STL к lock-free контейнерам, и когда стоит (и стоит ли вообще) применять lock-free структуры данных.

Меня давно занимал вопрос: «а что, если попробовать прогнать цифровую запись песни через преобразование Фурье, посмотреть зависимость спектра от времени и попытаться вытащить из полученной информации аккорды песни?». Вот, наконец, нашел время попробовать…

Привет, %username%!
Недавно на хабре была опубликована очень спорная статья под названием «Эксперты призывают готовиться к криптоапокалипсису». Честно говоря, я не согласен с выводами авторов о том, что «голактеко опасносте», все скоро взломают и подорожает гречка. Однако я хочу поговорить не об этом.
В комментариях к той статье я высказал мнение, что кое в чем докладчики правы и переходить на эллиптическую криптографию уже давно пора. Ну в самом деле, кто-нибудь видел в интернете ECDSA сертификат? Хотя стандарту уже без малого 13 лет, мы продолжаем по старинке использовать старый добрый RSA. В общем сказал я это, и как это часто бывает, задумался а так ли необходим переход на «эллиптику»? Да и что это за зверь такой эллиптическая криптография? Какие имеет плюсы, минусы, тонкости. Одним словом, давайте разбираться.

Обычно в таких статьях делают заголовок вида «аналог await/async для C++», а их содержимое сводится к описанию ещё одной библиотеки, выложенной где-то в интернете. Но в данном случае нам не требуется ничего подобного и заголовок точно отражает суть статьи. Почему так смотрите ниже.

Управление памятью – центральный аспект в работе операционных систем. Он оказывает основополагающее влияние на сферу программирования и системного администрирования. В нескольких последующих постах я коснусь вопросов, связанных с работой памяти. Упор будет сделан на практические аспекты, однако и детали внутреннего устройства игнорировать не будем. Рассматриваемые концепции являются достаточно общими, но проиллюстрированы в основном на примере Linux и Windows, выполняющихся на x86-32 компьютере. Первый пост описывает организацию памяти пользовательских процессов.

Введение

Данная статья является продолжением цикла статей: Использование паттерна синглтон [1], Синглтон и время жизни объекта [2], Обращение зависимостей и порождающие шаблоны проектирования [3], Реализация синглтона в многопоточном приложении [4]. Сейчас я хотел бы поговорить о многопоточности. Эта тема настолько объемна и многогранна, что охватить ее всю не представляется возможным. Здесь я заострю внимание на некоторых практичных вещах, которые позволят вообще не думать о многопоточности, ну или думать о ней в крайне минимальном объеме. Если говорить точнее, то думать о ней только на этапе проектирования, но не реализации. Т.е. будут рассмотрены вопросы о том, как сделать так, чтобы автоматически вызывались правильные конструкции без головной боли. Такой подход, в свою очередь, позволяет значительно уменьшить проблемы, вызванные состояниями гонок (race condition, см. Состояние гонки [5]) и взаимными блокировками (deadlock, см. Взаимная блокировка [6]). Этот факт уже сам по себе представляет немалую ценность. Также будет рассмотрен подход, который позволяет иметь доступ к объекту из нескольких потоков одновременно без использования каких-либо блокировок и атомарных операций!

Доброго времени суток, уважаемые Хабраюзеры!

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

Рисунок 1 – Взаимная блокировка 1-го рода с участием сигнальной переменной.

В рамках этого поста мы рассмотрим проблемы, которые возникают при использовании сигнальных переменных, и покажем, как их можно избежать.

Небольшое предисловие

Этот текст является продолжением поста , в котором автор попытался как можно более просто и без сложных математических выкладок описать понятия формального языка и грамматики. На этот текст пришло достаточно много откликов и автор счел себя обязанным написать продолжение.

Ниже описывается формализм порождающих грамматик Хомского. Методы задания языка с помощью порождающих грамматик сейчас довольно популярны, особенно для машинной обработки компьютерных языков. Но обычно изучение порождающих грамматик в теории трансляторов заканчивается на контекстно-свободных грамматиках. Последние являются довольно узким специальным классом порождающих грамматик Хомского и обычно используются как вид категориальных грамматик (как конкретно это делается, будет показано ниже) для задания синтаксических анализаторов. Последнее обстоятельство только затуманивает понимание подхода Хомского. Дальнейшее изложение предназначено тем, кому интересно понять, в чем состоит этот подход.

На хабре уже было несколько статей про lock-free алгоритмы. Этот пост — это перевод статьи моего коллеги, которую мы планируем публиковать в нашем корпоративном блоге. По роду деятельности мы пишем огромное количество lock-free алгоритмов и структур данных, и этой статьей хочется показать, насколько это интересно и сложно одновременно.



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

Просматривая одно из обучающих видео "Школы разработки интерфейсов" Яндекса, наткнулся на ссылку на офигенный труд израильской веб-программистки Тали Гарсиэль (Tali Garsiel) "How browsers work" (Как работают браузеры).

Она в течение нескольких лет отслеживала всю издаваемую информацию о внутреннем устройстве браузеров, изучала исходный код WebKit и Gecko и, в конце концов, собрала все воедино. Вот что пишет сама Тали:

Когда на 90% компьютеров был установлен IE, приходилось мириться с тем, что это загадочный «черный ящик», однако теперь, когда более половины пользователей выбирает браузеры с открытым исходным кодом, пришло время разобраться, что скрывается у них внутри, в миллионах строк программного кода на C++...

Пролистав, я был поражен — отличная работа. Внутреннее устройство браузеров, алгоритмы разбора — все хорошо иллюстрировано, доступно и понятно. И без излишних подробностей, страниц на 30-40. Как раз то, что нужно. Решил — это надо обязательно перевести. Покопался еще немного — оказалось перевод уже как 1,5 года есть!

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

Под катом содержание перевода, чтобы решить стоит ли читать.

У современных процессоров архитектуры Core i7 существует очевидный, документированный, но отчего-то не очень известный даже среди многих специалистов сценарий priority inversion. Его я опишу в этом посте. В нем есть код на С, три диаграммы, и некоторые подробности работы кэшей в процессорах архитектуры Core i7. Никаких покровов не срывается, вся информация давно общедоступна.

Priority inversion – ситуация, когда низкоприоритетный процесс может блокировать или замедлять высокоприоритетный. Обычно имеется в виду очередность доступа к исполнению на ядре для высокоприоритетного кода относительно низкоприоритетного. С этим должно неплохо справляться ядро ОС. Однако помимо вычислительных ядер, которые несложно распределять посредством affinity и MSI-X, в процессоре есть ресурсы, общие для всех задач – контроллер памяти, QPI, общий кэш третьего уровня, PCIe устройства. В вопросы PCIe я углубляться не буду, т.к. не являюсь экспертом в данной теме. Priority inversion на почве доступа к памяти и QPI я давно не наблюдал – пропускной способности современного многоканального контроллера как правило хватает и высокоприоритетным, и низкоприоритетным задачам. Остановлюсь на кэшах.

Эта небольшая заметка о том, как с приходом нового стандарта C++11 изменились требования стандартных контейнеров к своим элементам. В C++98 от элемента контейнера требовалось, по сути, наличие «разумных» конструктора копирования и оператора присваивания. Если, например, объект вашего класса владеет каким-либо ресурсом, копирование обычно становится невозможным (по крайней мере, без «глубокого» копирования ресурса). В качестве примера давайте рассмотрим следующий класс-обертку вокруг FILE*, написанную на C++98:

class File
{
    FILE* handle;
public:
    File(const char* filename) {
        if ( !(handle = fopen(filename, "r")) )
            throw std::runtime_error("blah blah blah");
    }
    ~File() { if (handle) fclose(handle); }
    // ...
private:
    File(const File&); //запретить копирование
    void operator=(const File&); //запретить присваивание
};

Если ты всегда мечтал написать свой язык программирования — добро пожаловать. Здесь ты наверняка найдёшь для себя что-нибудь интересное.

GitHub-юзер yawnt собрал чудесную подборку ссылок для любителей драконов, языков и прочих вкусных внутренностей. А знающие камрады в комментариях наверняка поделятся с тобой и другими яствами.

Пишет yawnt следующее:

С каждым днём мне всё интереснее тема компиляторов, интерпретаторов и дизайна языков программирования в целом. И я решил поделиться с народом ссылками на собранные мной материалы (большую часть мне самому ещё предстоит прочитать :<). Надеюсь, кому-нибудь они окажутся полезными.

Я не включил (и не собираюсь) в список ссылки на официальную документацию, т. к. считаю очевидным, что первым делом следует смотреть именно туда ;P.

(Сокращённый перевод статьи Пьера-Хьюза Шарбонне)

Как уже сообщалось ранее на Java One, в Java 8 версии HotSpot планируется отказаться от PermGen пространства в пользу новой его вариации — Metaspace. Ранний доступ к JDK 8 даёт возможность наблюдать Metaspace в действии, чем и воспользовался автор оригинальной статьи чтоб узнать, какие преимущества даёт MetaSpace в сравнении с PermGen, и убедится во всём непосредственно.

Подробнорсти под катом.

На слуху множество разнообразных проектов, успешно получивших финансирование на Kickstarter. И если обычно они относятся к тематике Habrahabr лишь в том, что тут есть хаб Crowdfunding, то этот случай более примечателен — требуемая сумма была набрано проектом по финансированию конференции по языку программирования D.