Recent content on bazhenov.me
Introduction Link to heading I needed a straightforward way to check programmatically how much time a process spends on P-cores vs E-cores. There’s no high-level API for it, at least not that I know of – and yet this information matters whenever you care about consistent performance on Apple Silicon. I ran into this while working on Tango.rs , a benchmarking framework. When comparing two…
Introduction Link to heading Imagine you opened Activity Monitor to check how much memory your application consumes. But wait, which number should you actually look at? Suppose there’s “Memory” showing 800 MB, and “Real Memory” showing 1 GB. What’s the difference? Note Activity Monitor doesn’t display those two readings by default. To show them, you need…
Introduction Link to heading Good weather is specific weather. Conclusion: there is no such thing as good weather. Pilot’s proverb TLDR: The very same machine code, placed at different addresses, can exhibit drastically different performance. As software developers, we often assume that the performance of a specific piece of code is determined solely by the code itself and the hardware it…
Introduction Link to heading In this article, I discuss the challenges associated with testing algorithm performance, focusing primarily on microbenchmarks rather than overall application performance, although some principles apply to both. I provide a brief overview of efforts to address these challenges and highlight some limitations we’re encountering. Subsequently, I introduce an…
Introduction Link to heading Varint is a widely recognized technique used for compressing integer streams. Essentially, it suggests that it can be more efficient to encode a number using a variable-length representation instead of a fixed-size binary representation. By removing leading zeros from the binary number, the overall representation size can be reduced. This technique works particularly…
Introducton Link to heading Binary search is a very fast algorithm. Due to its exponential nature, it can process gigabytes of sorted data quickly. However, two problems make it somewhat challenging for modern CPUs: predictability of instruction flow; predictability of memory access. At each step, binary search splits the dataset into two parts and jumps to one of those parts based on a midpoint…
Introduction Link to heading Suppose we need to write a function that computes the next set of numbers in a range and stores them in a slice, as shown below: let pl = RangePl :: new ( 1 .. 12 ); let mut buffer = [ 0 u64 ; 4 ]; pl . next_batch ( 0 , & mut buffer ); // returns 4, buffer[..] = [1, 2, 3, 4] pl . next_batch ( 0 , & mut buffer ); // returns 4, buffer[..] = [5, 6, 7, 8] pl . next_batch (…
In recent years, criticism of the classic object-oriented analysis and design ideas has grown increasingly louder. One example of such criticism is Clean Code, Horrible Performance by Case Muratori. Here’s a quote that explains the author’s idea: It simply cannot be the case that we’re willing to give up a decade or more of hardware performance just to make programmers’ lives a…
Недавно на работе произошла следующая ситуация, потребовавшая не совсем тривиальной диагностики. Есть Java-приложение, выполняющее пакетную обработку информации. Обработка выполняется последовательно в несколько стадий. Каждая стадия выполняется в нескольких потоках. Несмотря на высокую требовательность к процессорному времени, приложение не может полностью утилизировать ресурсы сервера. В чем же…
Линейный счётчик — это очень простой алгоритм оценки мощности множества . Тем не менее, у него есть одна не очевидная и очень полезная особенность. Побитовая сумма (логическое ИЛИ) двух линейных счётчиков позволяет оценить мощность объединения двух множеств. Например, у вас есть два множества $A$ и $B$, а также их линейные счётчики $A’$, $B’$. Тогда: $$L_{A’ | B’} \approx…
Иногда по долгу службы приходится проводить деструктивные эксперименты. Делаем мы это лишь для того чтобы сделать нашу систему более стабильной и надёжной. Недавно мы провели такой эксперимент, связанный с проверкой алгоритма балансировки внутри поисковой системы. Суть эксперимента заключалась в проверке того, что алгоритм в состоянии распределить запросы между репликам в соответствии с их текущей…
Работая над более менее сложным проектом, приходится поддерживать окружение необходимое для корректного функционирования системы. Нередко это выливается в ситуацию, когда на машине установлено такое количество пакетов и зависимостей, что возникает масса проблем: окружение становится тяжёло воспроизвести на другой машине (например, новому разработчику); окружение становится хрупким. Обновляя…
О новых фичах Java 8 было сказано уже довольно много . В основном обсуждают замыкания, Stream’ы, новое API для работы со временем, default-методы в интерфейсах, класс Optional и отсутствие Permanent Generation. Но помимо жирных фич, в Java 8 сильно изменилась стандартная библиотека по перифирии. В частности, в уже существующие классы было добавлено много методов существенно упрощающих…
Наивный байесовский классификатор , о котором я уже писал, один из самых простых классификационных алгоритмов. В этой заметке я опишу более сложный алгоритм — метод максимальной энтропии , который, в ряде случаев, может оказаться существенно более точным. К своему удивлению, я не нашел в рунете более менее полного описания этого алгоритма классификации. Поэтому, считаю полезным поделиться этими…
Для использования линейного счетчика необходимо заранее знать приблизительное количество уникальных элементов в потоке. На основании этого количества, а также необходимого вам уровня точности, вычисляется длина битовой маски счетчика. Допустим, вы хотите создать линейный счетчик для оценки количества элементов в потоке, с максимальным количеством уникальных элементов равным 10 миллионам. Какой…
Так уж получилось, что последние несколько лет я занимаюсь вопросами, связанными с поиском. Один из проектов, завершенных в прошлом году, был связан с модифицированием архитектуры нашей поисковой системы. В итоге мы получили результаты, которыми, как я считаю, имеет смысл поделиться. So, here we go. Функциональность поисковой системы Link to heading Но для начала было бы неплохо конкретизировать,…
Допустим, вам необходимо рассчитать количество уникальных строк в файле. Причем, файл большой – миллионы или десятки миллионов строк. Типичный shell’овский однострочник который позволяет решить эту задачу выглядит следующим образом: sort | uniq | wc -l И все бы хорошо, но есть одна проблема. Имя ей sort . Сортировка $O(n \log n)$ по времени и $O(n)$ по памяти, поэтому время её работы очень…
Существует один очень простой и эффективный способ улучшения алгоритмов классификации, который называется feature selection (выбор классификационных признаков). Этот метод позволяет при построении модели выбрать только самые показательные признаки (например, слова) и отсеять остальные. Что такое показательные признаки? Если мы говорим о задаче классификации текстовых документов, то это слова…
Автокомплит вещь удобная. Он позволяет экономить время на наборе текста, когда множество значений поля закрыто. Хороший автокомплит отличается следующими качествами: он должен быть быстрый. Если мы хотим экономить силы пользователя, то мы должны ему предложить вариант как можно быстрее; он не должен предлагать к вводу варианты которые заведомо неверны; он должен быть толерантен к пользовательскому…
Продолжая тему реализации автоматической классификации необходимо обсудить следующий очень важный вопрос. Как оценивать качество алгоритма? Допустим, вы хотите внести изменения в алгоритм. Откуда вы знаете что эти изменения сделают алгоритм лучше? Конечно же надо проверять алгоритм на реальных данных. Тестовая выборка Link to heading Основой проверки является тестовая выборка в которой проставлено…
В прошлой заметке я в общих чертах описал задачу классификации, а также традиционные подходы используемые для классификации текстовых документов. В этой заметке я более детально расскажу о том как работает самый простой, но вместе с тем один из самых часто используемых при обработке натуральных языков алгоритм классификации – наивный байесовский классификатор . Заметка разбита на две части:…
В этом и следующих постах, я хочу на пальцах описать процесс создания простого классификатора текстовых документов, а также рассказать о некоторых нетипичных с обывательской точки зрения подходах используемых при классификации документов. Классификатор – это алгоритм соотносящий некие входные данные с одним или несколькими классами. В отличие от алгоритмов кластеризации эти классы должны быть…
Некоторое время назад мне довелось участвовать в одном из подпроектов целью которого было извлечение упоминаний об автомобилях из произвольного текста с использованием экспертной информации. Это задачу в простонародье называют парсингом :). Так или иначе, этот класс задач имеет свою специфику связанную с относительно большим количеством различных операций над коллекциями. Связано это с…
Сегодня я хочу обсудить следующую проблему. Как мониторить CPU usage на многопроцессорной машине? Конечно же мониторить метрики выдываемые mpstat . Эта программа выдает процент времени который процессор проводит в различных состояниях ( user , system , iowait , idle и т.д.). $ mpstat 1 Linux 2.6.32-200.13.1.el5uek (search-personal2.vfarm.loc) 05/05/2012 _x86_64_ (16 CPU) 11:35:52 AM CPU %usr %nice…
Вам наверное приходилось слышать что-то вроде: “Этого не может быть. Вероятность этого менее одной миллионной”. В бытовом понимании одна миллионная это некая несвершимая вероятность. Другими словами, этого просто не может произойти. Но насколько это вeрятное событие, если вы повторите эксперимент миллион раз? Конечно, вероятность наблюдать событие растет если вы повторяете эксперимент…
В последнее время все чаще говорят о высоконагруженных приложениях. Нельзя не заметить что это теперь очень популярная, можно даже сказать модная, область знаний. Сам же термин “высоконагруженная система” при этом не имеет в нашей отрасли четкого определения. В этой заметке я хочу привести свои рассуждения по этому вопросу. Я не ставлю перед собой цель дать исчерпывающее определение…
В продолжение предыдущего поста хочу немного рассказать о том как у нас происходит deploy. В прошлый раз мы закончили на том что артефакт доставлен на production и готов к развертыванию. Начинается самое интересное, процесс деплоя. Но для начала надо немного описать платформу на которую мы деплоим наши приложения. В качестве servlet-container’а мы используем Jetty . Есть два основных типа…
Не так давно у нас на собеседовании был кандидат, который произвел довольно хорошее впечатление, поэтому было решено предложить ему более сложную задачу, которую обычно мы не спрашиваем. Вот ее немного видоизмененный вариант. Переделайте следующий код оставив его многопоточным таким образом, чтобы лампочки зажигались и гасли строго по очереди и в любой момент времени должна быть включена только…
Помните фильм “Пятый элемент”? Там была сцена, когда Зорг опрокидывает стакан на пол и роботы тут же начинают уборку помещения. Всего лишь одно маленькое действие привело в жизнь десяток машин, которые сразу же начали подметать и мыть полы, а в конце еще и налили воды хозяину. Что-то похожее происходит в коллективе с налаженным build процессом, когда разработчик коммитит изменения в…
Коллеги давно просили меня описать процесс сборки и настройки своего NAS-сервера. Этим постом я искупаю свою вину. К тому же тема действительно актуальная и, мне кажется, многим будет интересно с какими проблемами я столкнулся, какое железо и софт использовал. NAS у меня исполняет несколько обязанностей: файловое хранилище “жирного” контента (фильмы, etc); сервер для Apple TimeMachine…
В этом году я побывал на HighLoad++ . Event довольно интересный, поэтому я попытаюсь вкратце описать свои впечатления, а так же основные тенденции наблюдаемые на конференции. Во-первых, стоит отметить, что тезисы докладов и презентации доступны на официальном сайте конференции. Я живу во Владивостоке, поэтому мне пришлось пролететь очень большое расстояние чтобы попасть на конференцию. Этим…
Простота. Краеугольный камень нашей профессии. Наверняка вам приходилось слышать от своих коллег: “это можно сделать гораздо проще”. Или вы говорили это вашим коллегам: “смотри, можно сделать так. Это ведь гораздо проще”, а в ответ получали взгляд полный непонимания, как бы говорящий вам: “и это ты считаешь проще?”. В программной инженерии определенно произошла инфляция слова “простота”. Простота…
Представьте себе типичную задачу, есть поток событий и этот поток событий надо разделить между несколькими пользователями системы. Типичный пример: модерация. Скажем, есть три модератора, которые просматривают добавляемый пользователями контент (допустим рекламные кампании). Мы хотим “распилить” поток событий между модераторами, чтобы они не делали одну и ту же работу дважды. В самом…
Does anybody know why we do what we do? Why do we wake up everyday and go to our workplaces? It seems that the most obvious reason is money. We need money to function in the society. We need some funds to make some plans, if you wish. It turns out that not only money motivate people to do their job. OSS is the proof. Well, yes, we can make money from open source projects. And a lot of companies do…
И снова про инструменты разработки. Часто бывает необходимо сравнить производительность/пропускную способность того или иного участка кода, а писать тестирующий код ой как не хочется. А ведь надо всего-то, запустить нужный метод N раз и померять время выполнения. Вот сегодня у меня возник вопрос. Сколько процессору надо времени, чтобы проитерироваться по массиву с заданной длинной? Недолго думая,…
Не так давно у нас на работе (Виктор, Игорь, Олег привет вам) состоялась дискуссия на тему: должны ли программисты знать как работает железо на котором выполняются их программы? И я еще раз убедился в том, что большинство программистов придерживаются мнения: “железо само по себе, а я сам по себе”. Точка зрения вполне ожидаемая и ничего принципиально неправильного в ней нет, но я хотел…
Как вы думаете во сколько раз может быть быстрее ваша программа, если вам дадут в два раза более “крутое” железо: в два раза более быстрый процессор, в два раза больше памяти и т.д. Интуитивный ответ — в два раза. Раньше я уже писал о том, что не все так безоблачно. Взвесив все аргументы вы можете сказать: “окей, максимум в два раза”. Но что если бы я вам сказал, что при…
Сегодня в разговоре с одним знакомым всплыл следующий вопрос. В случае, если для дистрибуции ключей по нодам кластера используется типичная схема остатка от деления на количество серверов, какая доля ключей осуществляют миграцию, если один из серверов выводится из схемы? Интуитивным ответом является: “почти все” или “большинство”. Тем не менее, если вы любите тренировать…
Раньше я уже писал о том, что нам приходится разрабатывать дополнительный инструментарий для себя. Еще одна сфера которую над которой мы плодотворно поработали — это логгирование. Здесь я не буду говорить о пользе логгирования и о том как надо логгировать. В интернете полно информации по этим аспектам. Я хочу рассказать о том, как мы анализируем логи. Дело в том, что в сутки у нас генерируется…
В последнее время в web-программировании появился очередной тренд — Key-Value базы данных. Существует просто великое множество KV-решений, — одно лучше другого. Но так ли они важны и какая от них польза? Разрешите мне немного порассуждать о происхождении KV-хранилищ. Нет дыма без огня Link to heading Недовольство реляционными базами данных начало появляться давно. Оказалось что на некоторых use…
Если вы пишете на объектно-ориентированном языке, то вы должны быть знакомы с “джентльменским набором” принципов, которые очень полезны при написании кода. К таким принципам относятся: single responsibility principle , open-closed principle , interface segregation principle и другие. Общий эффект их использования заключается в том, что количество сущностей (классов и интерфейсов) в…
Один мой коллега является адептом философии “дефолтных настроек”. Эта философия пропагандирует следующий подход: не пытайтесь менять environment под свои нужды, — просто научитесь пользоваться стандартным environment’ом. Несмотря на то что сам по себе этот подход довольно спорен, в нем есть свои плюсы. Умение решать задачи штатными средствами особенно выручает когда необходимо…
В прошлой заметке , я затронул тему порядка доставки сообщений MQ-системами. Отсутствие гарантий в отношении этого порядка вызвало некоторое возмущение со стороны читателей, поэтому я решил раскрыть эту тему более полно. Почему же многие очереди сообщений не гарантирую порядок? И так ли он вообще важен — этот порядок доставки? Почему многие системы очередей не гарантируют порядок доставки? Link to…
В прошлый раз я писал про оптимистическую блокировку . Сегодня я хочу описать одну разновидность прикладного применения оптимистической блокировки. Это прикладное применение относится к области систем асинхронного обмена сообщений (таких как ActiveMQ, RabbitMQ, OpenMQ, memcacheQ и другие). Очереди сообщений — это очень полезная разновидность промежуточного хранилища данных. В очередь можно…
Shared state, как известно необходимо защищать. Иначе параллельные потоки могут его “поломать”. Это относится и к web-приложениям. Несмотря на отсутствие вменяемой поддержки параллелизма в большинстве web-ориентированных языков (PHP, Python, Ruby), concurrency в web-приложениях хватает. Запросы приходят на web-сервер параллельно, исполняются на разных процессорах параллельно и т.д. По…
Недавно еще раз встретился с некорректной обработкой InterruptedException в java. InterruptedException — это checked exception генерируемый многими методами стандартной библиотеки, которые блокируют поток исполнения. К таким относятся: interruptible версии lock’ов , метод Thread.sleep() , некоторые операции над блокирующими очередями , некоторые операции над каналами и другие. По своей сути,…
Существует одна очень старая и эффективная техника — конвейерная обработка данных (pipelining). Ее смысл заключается в том, что разные физические исполнители, которые могут работать не блокируя друг друга (хвала DMA ), такие как: процессоры, жесткие диски, сетевые карты, — должны работать не блокируя друг друга. Это позволяет повысить их утилизацию, и, если правильно все организовать, не допустить…
Если вы не знаете, то с PHP/5.3 поставляется новый mysql драйвер — mysqlnd . У него есть несколько особенностей и воможностей, которые отличают его от libmysql. Первое не очень интерестно. Теперь при fetch’e результата не происходит копирования из памяти libmysql в память, находящуюся под управлением zend engine. Фактически весь result set находится в памяти zend engine. Это значит что…
Все таки интернет индустрия развивается. Теперь на каждом углу высоконагруженные проекты, миллионы пользователей, требования к high-availability, масштабиремости. Причем вот ведь странно. К масштабиремости всегда относятся как-то однобоко. Иногда ее путают с производительностью. А иногда не понимают что масштабируют. Dan Pritchett, один из архитекторов eBay (теперь уже бывший), еще в 2006 году…
Сегодня со мной произошел форс-мажор. Я приехал на работу на велосипеде так что, когда рабочий день закончился, я сел на вел и сопровождаемый прохладным ветерком покатил в центр города. Далеко уехать не получилось. Буквально через 40-50 метров я услышал хруст и педаль под ногой резко провалилась. Оказалось, что я поломал крепление заднего переключателя. Вообще, поломать крепление заднего…