Привет! В двух моих последних статьях я говорил о том, как СУБД в оперативной памяти обеспечивают сохранность данных. Найти их можно здесь и здесь.

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

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

Итак, у нас есть СУБД, хранящая все данные в оперативной памяти. Как я уже упоминал в моей предыдущей статье, для снятия снимка состояния необходимо все эти данные записать на диск. Это означает, что нам нужно пройтись по всем таблицам и по всем строкам в каждой таблице и записать все это на диск одним файлом через системный вызов write. Довольно просто на первый взгляд. Однако проблема в том, что данные в базе постоянно изменяются. Даже если замораживать структуры данных при снятии снимка, в итоге на диске можно получить неконсистентное состояние базы данных.

Сальвадор Дали, Дезинтеграция постоянства памяти. 1952—1954. Холст, масло.

Всем привет. Кто-то из вас, возможно, уже знаком с СУБД для данных в оперативной памяти, но на всякий случай — по ссылке можно найти их общее описание. Если вкратце, такие СУБД хранят данные целиком в оперативной памяти. Что это означает? Каждый раз, отправляя запрос на поиск или обновление данных, вы обращаетесь только к оперативной памяти в обход жесткого диска — на нем никакие операции не производятся. И это хорошо, потому что оперативная память работает намного быстрее любого диска. Примером такой СУБД является Memcached.

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

Можно ли объединить достоинства хранения данных в оперативной памяти с надежностью проверенных временем СУБД вроде MySQL или Postgres? Конечно! Повлияет ли это на производительность? Вы удивитесь, но нет!

С удивлением обнаружил, что про явление алиасинга (aliasing) здесь постов нет. Ситуацию нужно исправить, тк. алиасинг в любой сколько-то сложной C++ программе обязательно хоть где-нибудь, да есть. Это может быть хорошо, давая возможность ловких оптимизаций, а может быть плохо, внося повышенной паршивости баги. Под катом вкратце про оба случая (ну и неизменное «компилятор бьет спина», конечно; для разнообразия сегодня это gcc).

Содержание

1. Введение в Computer Science
2. Структуры данных и Алгоритмы
3. Системное программирование
4. Распределенные системы
5. Базы данных
6. Объектно-ориентированный дизайн и разработка софта
7. Искусственный интеллект
8. Машинное обучение
9. Веб-разработка и интернет-технологии
10. Concurrency
11. Компьютерные сети
12. Разработка мобильных приложений
13. Математика для программистов
14. Теория информатики и языки программирования
15. Архитектура компьютера
16. Безопасность
17. Компьютерная графика
18. Работа с изображениями и компьютерное зрение
19. Интерфейс Человек-Компьютер
20. Вычислительная биология
21. Прочее

Данная статья (и я надеюсь что серия статей) посвящена нестандартным расширениям языков C и C++, которые существуют практически в каждом компиляторе.

Языковые расширения — это дополнительные возможности и фичи языка, не входящие в стандарт, но тем ни менее поддерживаемые компиляторами. Исследовать эти расширения очень интересно — в первую очередь потому, что они возникли не на пустом месте; каждое расширение — результат насущной необходимости, возникавшей у большого числа программистов. А мне интересно вдвойне — поскольку мне нравятся языки программирования и я разрабатываю свой, часто оказывается что многие мои идеи реализованы именно в расширениях языка. Стандарты языков C и C++ развиваются крайне медленно, и порой, читая описание расширений, так и хочется воскликнуть «ну это же очевидно! почему этого до сих пор нет в стандарте?».

Языковые расширения — это такая «серая», теневая область, про которую обычно мало пишут и мало знают. Но именно этим она и и интересна!

Предварительно могу сказать, что будут рассмотрены компиляторы общего назначения gcc, msvs, clang, intel, embarcadero, компиляторы для микроконтроллеров iar и keil, и по возможности многие другие компиляторы. Больше всего расширений в GCC, что не удивительно — свободная разработка способствует воплощению разных языковых фич. К тому же, информация по расширениям GCC вся собрана в одном месте, а информацию по остальным компиляторам придется собирать по крупицам. Поэтому начнем с GCC.

Доброго вам дня, коллеги. Предлагаю вам прочитать статью о базовом аспекте вычислительной геометрии — точном вычислении предикатов.

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

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

• геометрический предикат «поворот»;
• противоречивость «наивной» реализации поворота;
• применение интервальной арифметики для упрощения расчета предикатов;
• длинная арифметика и несколько альтернативных способов вычислений предикатов;
• расчет погрешности вычисления поворота в числах с плавающей точкой.

Итак, если вы хотите знать, почему вычислительная геометрия не является «наукой о подборе эпсилонов» и как можно корректно и эффективно реализовать геометрический алгоритм, жмите

В последнее время все технологические компании твердят о машинном обучении. Мол, столько задач оно решает, которые раньше только люди и могли решить. Но как конкретно оно работает, никто не рассказывает. А кто-то даже для красного словца машинное обучение называет искусственным интеллектом.


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

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


Начнём с очевидных фактов. Итак:

• Мозг у нас один.
• Мозг работает по-разному, в зависимости от того, чем вы занимаетесь.
• Есть «приятные» процессы (например, привычные действия, общение с доброжелательно настроенными людьми или что-то, связанное с умеренной физической активностью).
• Есть «неприятная» активность мозга, вызывающая почти болезненные ощущения (например, начальный период изучения совершенно нового для вас иностранного языка или языка программирования).
• Мы стремимся минимизировать неприятные ощущения.
• Мечты и «хотелки» в основном являются стремлением к определённым формам работы мозга и состояниям сознания, а вовсе не ситуативными достижениями (хотя мы обычно думаем иначе).

Многие программисты утверждают, что знают С. Ну что ж, у него самый известный синтаксис, он существует уже 44 года и он не захламлен непонятными функциями. Он прост!

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

Если вы думаете что он прост — пройдите этот тест. В нем всего 5 вопросов. Каждый вопрос в принципе одинаковый: какое будет значение возврата?

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

При съемке книжного разворота с помощью камеры мобильного устройства неизбежно возникают некоторые из нижеперечисленных дефектов (а возможно, что и все сразу):

• цифровой шум,
• тени и блики,
• расфокусировка и смаз,
• перекос,
• перспективные искажения,
• кривые строки,
• лишние объекты в кадре.

Обработка таких фотографий для последующего OCR – довольно трудоемкая задача даже для человека, хорошо владеющего навыками работы в Photoshop. Как быть, если мы хотим это сделать автоматически, с помощью программы? Сразу оговоримся, что подробное описание всех этапов алгоритма сделало бы публикацию чересчур объемной, поэтому мы сейчас расскажем только о том, как решать одну из подзадач – найти линию корешка на таких фотографиях. О том, как устранять тени и блики на фотографиях мы уже рассказывали. Про устранение цифрового шума написано много статей. А про автоматическое исправление перспективы и кривых строк мы расскажем в следующий раз.

В прошлый раз в статье «Поиск линии корешка на фотографиях книжных разворотов» мы обещали рассказать о том, что случается с фотографией книжного разворота после этого, а именно — про устранение перспективных искажений и разгибание кривых строк текста. Без этого получить качественные результаты OCR практически невозможно.

Итак, считаем, что мы уже нашли на фотографии линию корешка, воспользуемся этим знанием, чтобы определить ваниш-точки для страниц разворота (vanishing point). Ваниш-точки – это точки схождения параллельных прямых в перспективной проекции книги на плоскость изображения. Они обе должны располагаться на продолжении этой линии, но для каждой из страниц положение точки может быть свое. Схематически это показано на следующей иллюстрации (на самом деле, это лог для отладки). Линия корешка выделена красным, линии, пересекающиеся в ваниш-точках, – зеленым.

Многие студенты, впервые сталкиваясь с описанием какой-нибудь хитроумной штуки, вроде алгоритма Кнута – Морриса – Пратта или красно-чёрных деревьев, тут же задаются вопросами: «К чему такие сложности? И это, кроме авторов учебников, кому-нибудь нужно?». Лучший способ доказать пользу алгоритмов – это примеры из жизни. Причём, в идеале – конкретные примеры применения широко известных алгоритмов в современных, повсеместно используемых, программных продуктах.



Посмотрим, что можно обнаружить в коде ядра Linux, браузера Chromium и ещё в некоторых проектах.

Я уверен, что многим программистам знакома формула:


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

Вычисляет она относительную яркость цвета (relative luminance или в некоторых контекстах luma; не путать с lightness и brightness) и широко применяется для преобразования цветного RGB-изображения в Grayscale и связанных с этим задач.

Формула растиражирована и процитирована в тысячах статей, форумных обсуждений и ответов на StackOverflow… Но дело в том, что единственно-правильное её место — на свалке истории. Использовать её нельзя. Однако же используют.

Но почему нельзя? И откуда же взялись именно такие коэффициенты?

Недавно на isocpp.org была опубликована ссылка на статью Eli Bendersky «Perfect forwarding and universal references in C++». В этой небольшой статье есть простой ответ на простой вопрос — для решения каких задач и как нужно использовать rvalue-ссылки.

Как известно, в современных архитектурах x86(_64) и ARM виртуальная память процесса линейна и непрерывна, ибо, к счастью, прошли времена char near* и int huge*. Виртуальная память поделена на страницы, типичный размер которых 4 KiB, и по умолчанию они не отображены на физическую память (mapping), так что работать с ними не получится. Чтобы посмотреть текущие отображённые интервалы адресов у процесса, в Linux смотрим /proc/<pid>/maps, в OS X vmmap <pid>. У каждого интервала адресов есть три вида защиты: от исполнения, от записи и от чтения. Как видно, самый первый интервал, начинающийся с load address (соответствующий сегменту .text у ELF в Linux, __TEXT у Mach-O в OS X), доступен на чтение и исполнение — очень логично. Ещё можно увидеть, что стек по сути ничем не отличается от других интервалов, и можно быстро вычислить его размер, вычтя из конечного адреса начальный. Отображение страниц выполняется с помощью mmap/munmap, а защита меняется с помощью mprotect. Ещё существуют brk/sbrk, deprecated древние пережитки прошлого, которые изменяют размер одного-единственного интервала «данных» и в современных системах эмулируются mmap’ом.

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

• оптимально управляет уже выделенной памятью;
• значительно уменьшает количество обращений к ядру (ведь mmap / sbrk — это syscall);
• вообще абстрагирует программиста от виртуальной памяти, так что многие пользуются malloc’ом, вообще не подозревая о существовании страниц, таблиц трансляции и т. п.

Довольно теории! Будем щупать malloc на практике. Проведём три эксперимента. Работа будет возможна на POSIX-совместимых операционках, в частности была проверена работа на Linux и на OS X.

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

В этом посте мы попробуем применить технику символьного выполнения на примере символьной ВМ KLEE для решения простого ASCII-лабиринта. Как вы думаете, сколько верных решений мы сможем найти?

Развлекаемся, «распутывая» код на языке Си

Вызов: Прежде чем лезть под кат, скомпилируйте в голове заголовок статьи, что он дает на выходе?


Когда я в очередной раз просматривал книгу «Expert C programming», я вдруг наткнулся на раздел «light relief» в международном конкурсе на самый запутанный код на Си (IOCCC). Это соревнование по написанию как можно более нечитабельного кода. То, что такие конкурсы устраиваются для Си, наверное, говорит что-что об этом языке. Мне хотелось увидеть работы участников этого соревнования. Не найдя никакой информации в интернете, я решил поискать их самостоятельно.

IOCCC был придуман Стивеном Борном, когда он решил использовать препроцессор Си и написать Unix shell как бы на языке Си, но больше похожем на язык Algol-68, с его явными окончаниями операторов, например:

if
  ...
fi 

Он добился этого, сделав:

#define IF if(
#define THEN ){
#define ELSE } else {
#define FI ;}

Что позволило ему писать так:

IF *s2++ == 0
THEN return(0);
FI