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

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

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

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы покажутся чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он будет полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Введение

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

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

От переводчика: Это пятая статья из цикла о Node.js от команды Mozilla Identity, которая занимается проектом Persona.

Все статьи цикла:

1. "Охотимся за утечками памяти в Node.js"
2. "Нагружаем Node под завязку"
3. "Храним сессии на клиенте, чтобы упростить масштабирование приложения"
4. "Производительность фронтэнда. Часть 1 — конкатенация, компрессия, кэширование"
5. "Пишем сервер, который не падает под нагрузкой"
6. "Производительность фронтэнда. Часть 2 — кешируем динамический контент с помощью etagify"
7. "Приручаем конфигурации веб-приложений с помощью node-convict"
8. "Производительность фронтенда. Часть 3 — оптимизация шрифтов"
9. "Локализация приложений Node.js. Часть 1"
10. "Локализация приложений Node.js. Часть 2: инструментарий и процесс"
11. "Локализация приложений Node.js. Часть 3: локализация в действии"
12. "Awsbox — PaaS-инфраструктура для развёртывания приложений Node.js в облаке Amazon"

---

Как написать приложение Node.js, которое будет продолжать работать даже под невозможной нагрузкой? В этой статье показана методика и библиотека node-toobusy, её воплощающая, суть которой наиболее кратко может быть передана этим фрагментом кода:

var toobusy = require('toobusy');
 
app.use(function(req, res, next) {
  if (toobusy()) res.send(503, "I'm busy right now, sorry.");
  else next();
});

В чём заключается проблема?

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

Это может быть и злонамеренный всплеск трафика, например от DoS-атаки. Первый шаг к борьбе с такими атаками — написание сервера, который не падает.

Введение

Numenta NuPIC — открытая реализация алгоритмов, моделирующих процессы запоминания информации человеком, происходящие в неокортексе. Исходные коды NuPIC на github

В двух словах, назначение NuPIC можно описать как «фиговина, выявляющая, запоминающая и прогнозирующая пространственные и временные закономерности в данных». Именно этим большую часть времени занимается человеческий мозг — запоминает, обобщает и прогнозирует. Очень хорошее описание этих процессов можно найти в книге Джеффа Хокинса «On Intelligence» (есть русский перевод книги под названием «Об интеллекте»).

На сайте Numenta есть подробный документ, детально описывающий алгоритмы и принципы работы, а также несколько видео.

Предлагаю перейти на сторону зла, на темную сторону программирования. Ситхи сильнее джедаев. И печенек хватит на всех. Предупреждаю, прежде чем начнете читать далее. Характер при переходе на темную сторону портится.
Прошу под кат

Я полагаю что все в общих чертах знают о существовании такого замечательного математического инструмента как преобразование Фурье. Однако в ВУЗах его почему-то преподают настолько плохо, что понимают как это преобразование работает и как им правильно следует пользоваться сравнительно немного людей. Между тем математика данного преобразования на удивление красива, проста и изящна. Я предлагаю всем желающим узнать немного больше о преобразовании Фурье и близкой ему теме того как аналоговые сигналы удается эффективно превращать для вычислительной обработки в цифровые.

(с) xkcd

Без использования сложных формул и матлаба я постараюсь ответить на следующие вопросы:

• FT, DTF, DTFT — в чем отличия и как совершенно разные казалось бы формулы дают столь концептуально похожие результаты?
• Как правильно интерпретировать результаты быстрого преобразования Фурье (FFT)
• Что делать если дан сигнал из 179 сэмплов а БПФ требует на вход последовательность по длине равную степени двойки
• Почему при попытке получить с помощью Фурье спектр синусоиды вместо ожидаемой одиночной “палки” на графике вылезает странная загогулина и что с этим можно сделать
• Зачем перед АЦП и после ЦАП ставят аналоговые фильтры
• Можно ли оцифровать АЦП сигнал с частотой выше половины частоты дискретизации (школьный ответ неверен, правильный ответ — можно)
• Как по цифровой последовательности восстанавливают исходный сигнал

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

Натолкнулся на довольно странное поведение системы и решил поделиться опытом. Итак, имеем свежесозданного пользователя и пытаемся выполнить вход. И, совершенно неожиданно, получаем следующую ошибку (пример использует вход через runas с загрузкой профиля):
Замечу, что с примерно похожей ошибкой завершится и попытка обычного входа. На Windows 8 сообщение следующее: «Службе „Служба профилей пользователей“ не удалось войти в систему». Внимание, вопрос: что же пошло не так?!

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


Если взять Mandriva Linux, добавить скриптов linux-live.org и дополнить модульной архитектурой slax…
А потом, конечно же, немного обработать напильником — получим magos-linux ©


 От стандартных live-image дистров с сохранением, MagOS отличается модульностью, в squashfs помещается не целиком дистрибутив, а для каждой программы выделяется свой mem/loop сегмент, в который из модуля на-лету распаковывается исполняемый код.

Сегодня вышло обновление.

Недавно в нашем блоге появилась статья о NUMA-системах, и я хотел бы продолжить тему, поделившись своим опытом работы в Linux. Сегодня я расскажу о том, что бывает, если неправильно использовать память в NUMA и как диагностировать такую проблему с помощью счётчиков производительности.

Почти каждый представляет себе, что такое DDoS-атака. Но лучше один раз увидеть, чем сто раз услышать. Сайт VideoLAN на днях подвергся довольно необычной DDoS-атаке. Хотя интенсивность запросов была не очень велика — от 400 до 1600 запросов в секунду, ботнету удалось создать очень большую нагрузку на сервер, так как компьютеры-зомби не просто заходили на одну из страниц сайта, а скачивали дистрибутив VLC-плеера весом в 22 мегабайта. Пиковая нагрузка на серверы доходила до 292 гигабит в секунду. С помощью logstalgia — инструмента, который превращает логи сервера в наглядную анимацию — администраторы сайта сделали и опубликовали на Youtube визуализацию, благодаря которой можно увидеть, как выглядит DDoS-атака:

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

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

Если когда-нибудь вы задумывались над тем, что значат слова «the processor supports precise aborts» в даташите, прошу под кат.

Есть места, в которых сложно побывать, но посмотреть и узнать про которые очень бы хотелось. И речь даже не о подборке «100 мест, которые надо увидеть за свою жизнь» — достаточно просто взять даже какой-нибудь интересный музей, который находится чёрт знает где. Вот хочется в нём побывать и всё тут, а сделать это не получается. В таком случае на помощь приходят фотографии, которые хотя бы частично, но позволяют «побывать» в новом месте. Ну или просто помогают понять, стоит ехать туда или нет.



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

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

Эксперимент можно провести на обычном листке в клеточку из школьной тетради.

СОревнования среди чат-ботов «AI Loebner» проводится каждый год, и каждый год находится программа, чат-бот, которая может убедить судей в том, что она является человеком. Само собой, судьи не знают, с кем общаются — с реальным человеком, или с программой. Поэтому предвзятость жюри просто исключена. В основе соревнования лежит тест Тьюринга. Конечно, до настоящего момента полный тест Тьюринга не смогла пройти ни одна программа (и, соответственно, приз в 100 тысяч долларов ожидает того разработчика, который создаст такую программу). Однако, убедить судей в том, что чат-бот — живой человек, все же удается некоторым программам.

Предисловие

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

Не можешь сам — заставь компьютер. Сказано — сделано. В результате написанному по наитию алгоритму пришлось работать всю ночь, чтобы найти все 4 уникальных решения. В процессе гугления решений для сравнения, я нашёл программу Burr Tools, которая справилась с этой задачей за 3 минуты на моём ноутбуке.

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

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

Привет, Хабр!
Вы слышали первую в мире песню, синтезированную компьютером IBM 7094?

Изначально искал маленькую ёмкую шпаргалку по FreeBSD, которую в итоге и нашёл, но через пару минут перед моими глазами предстало

НЕЧТО

БОЛЬШЕЕ И

ВСЕОБЪЕМЛЮЩЕЕ

P.S. pdf inside
P.P.S. и не только по FreeBSD…