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

Различные классы сложности сортируют задачи в иерархическом виде. Один класс может содержать все задачи другого, плюс задачи, требующие дополнительных вычислительных ресурсов.

Какова фундаментальная сложность задачи? Такова постановка базовой задачи специалистов по информатике, пытающихся рассортировать задачи по т.н. классам сложности. Это группы, содержащие все вычислительные задачи, требующие не более фиксированного количества вычислительных ресурсов – таких, как время или память. Возьмём простой пример с большим числом типа 123 456 789 001. Можно задать вопрос: является ли оно простым числом – таким, которое делится только на 1 и себя? Специалисты по информатике могут ответить на него при помощи быстрых алгоритмов – таких, что не начинают тормозить на произвольно больших числах. В нашем случае окажется, что это число не является простым. Затем мы можем задать вопрос: каковы его простые множители? А вот для ответа на него быстрого алгоритма не существует – только если использовать квантовый компьютер. Поэтому специалисты по информатике считают, что две этих задачи относятся к разным классам сложности.

Работа с числовыми матрицами в целом и решение систем линейных алгебраических уравнений в частности — классическая математическая и алгоритмическая задача, широко используемая при моделировании и расчёте огромного класса бизнес-процессов (например, при расчёте себестоимости). При создании и эксплуатации конфигураций «1С:Предприятия» многие разработчики сталкивались с необходимостью вручную реализовывать алгоритмы расчёта СЛАУ, а после — с проблемой длительного ожидания решения.

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

Он оптимизирован для использования на данных, имеющих разреженную структуру (то есть содержащие не более 10% ненулевых коэффициентов в уравнениях) и в среднем и в лучшем случаях демонстрирует асимптотику Θ(n⋅log(n)⋅log(n)), где n — количество переменных, а в худшем (при заполненности системы ~100%) его асимптотика сопоставима с классическими алгоритмами ( Θ(n³)). При этом на системах, имеющих ~10⁵ неизвестных, алгоритм показывает ускорение в сотни раз по сравнению с реализованными в специализированных библиотеках линейной алгебры (например, superlu или lapack).


Важно: статья и описанный алгоритм требуют понимания линейной алгебры и теории графов на уровне первого курса университета.

Введение

Решил проанализировать статью, описывающую некоторые интересные детали потоковой обработки ровно один раз: exactly-once. Дело в том, что некоторые авторы очень странно понимают термины. Разбор статьи как раз позволит прояснить многие детали более глубже, т.к. выявление нелогичностей и странностей позволяет более полноценно прочувствовать понятия и смысл.

Приступим.

Анализ

Начинается все очень даже неплохо:

Введение

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

Для решения эллиптических уравнений в случае нескольких измерений используют численные методы, позволяющие преобразовать дифференциальные уравнения или их системы в системы алгебраических уравнений. Точность решения опреде­ляется шагом координатной сетки, количеством итераций и разрядной сеткой компьютера [1]

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

Введение

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

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

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

(1)

Обозначим через вектор неизвестных и определим вектор-функцию Тогда система (1) записывается в виде уравнения:

(2)

Теперь вернёмся к всеми любимому Python и отметим его первенство среди языков программирования, которые хотят изучать [1].



Этот факт является дополнительным стимулом рассмотрения числительных методов именно на Python. Однако, среди любителей Python бытует мнение, что специальные библиотечные функции, такие как scipy.optimize.root, spsolve_trianular, newton_krylov, являются самым лучшим выбором для решения задач численными методами.

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

Улица Заставская. Входим в бизнес-центр “МегаПарк”, охрана, лифт, жмем на кнопку — 8 этаж. Первое, что нас встречает каждое утро, — ярко-зеленый мох и внушительных размеров логотип хостинга. На часах 8:45, скоро начнется новый рабочий день офиса, на кухне шумно, коллеги спешат на свои места.

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

Прошло почти 2 года с момента первого релиза обновленного продукта — VDS Evo на нашем сайте Timeweb.com. Мы успели перейти с гипервизора XEN на KVM, улучшить железо под капотом, создать недорогие тарифы и мобильное приложение, создать обновленную собственную панель управления и… вернуться на Хабр.

Сегодня мы заглянем в каждый кабинет в нашем офисе, чтобы рассказать о работе над VDS в разрезе одного дня. Наливайте кофе, пойдемте с нами!

СДСМ-15. Про QoS. Теперь с возможностью Pull Request'ов.

И вот мы дошли до темы QoS.

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

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

QoS настолько опутан аурой шаманизма и недоступности, что все молодые (и не только) инженеры стараются тщательно игнорировать его существование, считая, что достаточно закидать проблемы деньгами, и бесконечно расширяя линки. Правда пока они не осознают, что при таком подходе их неизбежно ждёт провал. Или бизнес начнёт задавать неудобные вопросы, или возникнет масса проблем, почти не связанных с шириной канала, зато прямо зависящих от эффективности его использования. Ага, VoIP активно машет ручкой из-за кулис, а мультикастовый трафик ехидно поглаживает вас по спинке.

Поэтому давайте просто осознаем, что QoS это обязательно, познать его придётся так или иначе, и почему-бы не начать сейчас, в спокойной обстановке.

Представляю вашему вниманию перевод моей статьи из блога Проекта Darling. Маленькая справка по используемым понятиям: Darwin – операционная система с открытым исходным кодом, лежащая в основе macOS, iOS и других ОС от Apple; Mach-O – бинарный формат исполняемых файлов и библиотек, использующийся в Darwin; dyld – динамический загрузчик, использующийся в Darwin для загрузки файлов Mach-O; dylib – динамически загружаемая библиотека (обычно имеет расширение .dylib).

Цель Проекта Darling – сделать возможным запуск macOS-приложений под Linux, и умение загружать бинарные файлы в формате Mach-O – один из ключевых шагов к достижению этой цели.

Исходно, Darling был выстроен вокруг собственной реализации загрузчика Mach-O и идеи транслирования вызовов между высокоуровневым Darwin API и его Linux-аналогами. С тех пор наш фокус сместился на запуск кода во всё более и более изолированном Darwin-контейнере. С тех пор как мы перешли на использование Mach-O для внутренних компонентов Darling, у нас появилась возможность использовать исходный dyld от Apple, а также собирать многие другие компоненты Darwin с открытым исходным кодом. Нам всё ещё нужен простой загрузчик Mach-O, чтобы загружать сам dyld.

Уже немало лет прошло, как я познакомился с инструкциями MMX, SSE, а позже и AVX на процессорах Intel. В своё время они казались какой-то магией на фоне x86 ассемблера, который уже давно стал чем-то обыденным. Они меня настолько зацепили, что пару лет назад у меня появилась идея написать свой собственный софт рендерер для одной известной игры. Сподвигло меня на это то, какую производительность обещали эти инструкции. В какой-то момент я даже думал об этом написать. Но писать текст оказалось куда сложнее кода.

В то время я хотел избежать проблем с поддержкой на разных процессорах. Хотелось иметь возможность проверить мой рендерер на максимально доступном количестве. У меня до сих пор остались знакомые со старыми AMD процессорами, и их потолок был SSE3. Поэтому на тот момент я решил ограничиться максимум SSE3. Так появилась векторная математическая библиотека, чуть менее, чем полностью реализованная на SSE, с редким включением до SSE3. Однако в какой-то момент мне стало интересно, какую максимальную производительность я смогу выжать из процессора для ряда критичных операций векторной математики. Одной из таких операций является умножение матриц float 4 на 4.

Дополнение (2 июля 2018 г): сотрудники поддержки Google Cloud Platform (GCP) заверили, что такое больше не повторится. Их слова: «Многие люди (в рамках GCP) заинтересованы в том, чтобы улучшить ситуацию не только для вас, но для всех клиентов».

Примечание: это пост не о качестве облачных сервисов Google. Они превосходны, наравне с AWS. Речь идёт о «резких движениях без предупреждения», когда они полностью отключают все ваши системы, если сотрудники (или машины) вдруг решили: что-то не так. C нами это случилось второй раз.

Предыстория

Наш проект в продакшне использует GCP для мониторинга сотен ветроэнергетических установок (ВЭУ) и десятков солнечных электростанций, разбросанных по восьми странам. У нас центры управления с экранами на всю стену: там приборные панели, набитые метриками, за которыми следят круглосуточно. Менеджеры объектов используют эту систему для контроля в реальном времени состояния отдельных ВЭУ и солнечных установок. Если требуется вмешательство, оно производится немедленно. Команды разработки и прогнозирования используют систему для отработки алгоритмов на данных в BigQuery. Все действия непосредственно транслируются в нашу прибыль. Мы имеем дело с ветровой/солнечной энергией — скоропортящимся товаром. Если мы генерируем излишек, то не можем сохранить его и продать позже. Если генерируем недостаточно, то платим штрафы. По этой причине объекты нужно отслеживать 24/7, чтобы не выходить за рамки потребностей энергосистемы и заключенных соглашений о покупке электроэнергии.

Это вторая лекция с Я.Субботника по базам данных — первую мы опубликовали пару недель назад.

Руководитель группы СУБД общего назначения Дмитрий Сарафанников рассказал об эволюции хранилища данных в Яндексе: о том, как мы решили делать S3-совместимый интерфейс, почему выбрали PostgreSQL, на какие грабли наступили и как с ними справились.


— Всем привет! Меня зовут Дима, в Яндексе я занимаюсь базами данных.

Привет, Хабр! В этой статье я расскажу про создание математической модели длинного трубопровода для CAE-программы SimulationX на языке Modelica. Речь пойдёт о расчёте волновых процессов (пульсации давления, гидроудар и т.п.) в гидравлической линии методом характеристик. Несмотря на то, что этот метод довольно старый, в рунете довольно мало информации о его применении для решения прикладных задач.

Под катом я постараюсь объяснить зачем вообще нужно учитывать волновые процессы в трубопроводах, осветить проблемы, с которыми я столкнулся при программировании и в конце приведу сравнение процесса пульсаций давления при работе трёхплунжерного водяного насоса высокого давления на простой длинный трубопровод в модели и на стенде фирмы URACA в Германии.

Задача: в Техническом Задании на комплексную IT-систему был пункт – «выполнить расчет коэффициента готовности системы».

Решение: использовать материалы из ГОСТ, запросить дополнительные данные у вендоров по элементам оборудования и использовать несложную математику для выполнения итогового расчета.

Фьютекс (futex — сокращение от «Fast userspace mutex») — это механизм, предложенный разработчиками Linux из IBM в 2002 году и вошедший в ядро в конце 2003 года. Основной идеей было предоставить более эффективный способ синхронизации пользовательских потоков с минимальным количеством обращений к ядру ОС.

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

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

Как считать хиты страницы google.com? А как хранить счётчик лайков очень популярных пользователей? В этой статье предлагается рассмотреть решение этих задач с помощью CRDT (Conflict-free Replicated Data Types, что по-русски переводится примерно как Бесконфликтные реплицированные типы данных), а в более общем случае — задачи синхронизации реплик в распределённой системе с несколькими ведущими узлами.

Не так давно у меня произошёл очередной разговор с коллегой на извечную тему: "по ссылке, или по значению". В результате возникла данная статья. В ней я хочу изложить результаты моего исследования по этой и смежным темам. Далее будут рассмотрены:

• Регистры и их назначение при вызове функций.
• Передача и возврат простых типов и структур.
• Как передача по ссылке и по значению влияют на оптимизации тела функции компилятором.
• Как используется место при многочисленных вызовах функций.
• Механизм виртуальных вызовов.
• Оптимизация хвостовых вызовов и рекурсии.
• Инициализация структур, массивов и векторов.

Осторожно! Статья содержит большое количество кода на C++ и ассемблере (Intel ASM с комментариями), а также множество таблиц с оценками производительности. Всё написанное актуально для x86-64 System V ABI, который используется во всех современных Unix операционных системах, к примеру, в Linux и macOS.

Введение

В этой статье мы попробуем разобраться чем на практике отличается механизм epoll от портов завершения (Windows I/O Completion Port или IOCP). Это может быть интересно системным архитекторам, проектирующим высокопроизводительные сетевые сервисы или программистам, портирующим сетевой код с Windows на Linux или наоборот.

Обе эти технологии весьма эффективны для обработки большого количества сетевых соединений.

Они отличаются от других методов по следующим пунктам:

• Нет ограничений (кроме общих ресурсов системы) на общее количество наблюдаемых дескрипторов и типов событий
• Масштабирование работает достаточно хорошо — если вы уже мониторите N дескрипторов, то переход к мониторингу N + 1 займёт очень мало времени и ресурсов
• Достаточно легко задействовать пул потоков для параллельной обработки происходящих событий
• Нет никакого смысла использовать при единичных сетевых соединениях. Все преимущества начинают проявляться при 1000+ соединений

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

(Upd: данная статья — перевод)

Поводом к написанию статьи стал выход нового учебного курса DBA3 «Администрирование PostgreSQL 10. Резервное копирование и репликация». Мысли о его появлении и возможном содержании были у нас давно. Но обо всем по порядку.

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

В этой статье мы рассмотрим:

• select()
• poll()
• epoll()
• libevent

Мне сообщили, что на новых компьютерах некоторые регрессиионные тесты стали медленнее. Обычное дело, такое бывает. Неправильная конфигурация где-то в Windows или не самые оптимальные значения в BIOS. Но в этот раз нам никак не удавалось найти ту самую «сбитую» настройку. Поскольку изменение значительное: 9 против 19 секунд (на графике синий — это старое железо, а оранжевый — новое), то пришлось копать глубже.