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

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

Есть база пользователей 10 миллионов:

class User{
 int id; 
 time_t birthday; // дата рождения
 int gender;      // пол
 int city_id;     // место проживания
 time_t time_reg; // дата регистрации
};

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

• город;
• город, пол;
• пол, возраст.

Данные выдачи должны быть отсортированы по дате регистрации пользователей, и выдаваться постранично по 100 пользователей.

Подсказка 1: СУБД не даст нужной скорости.
Подсказка 2: Вспомнить сложность операций со множествами, сложность стандартных алгоритмов.
Подсказка 3: Проверить время поиска реализованного алгоритма, неплохой результат это порядка 0.005 сек.

У большинства администраторов, работающих с телефонией на базе Asterisk, в компаниях, где штат превышает 500+ сотрудников, рано или поздно встает вопрос о полноценной кластеризации Active/Active. Предпосылками к этому может быть и наличие региональных ответвлений, и желание сделать систему надежнее. Тема обширная и не является целью данной статьи в полном объеме, которая написана с целью показать один из самых быстрых и надежных способов добыть информацию о регистрации устройств на серверах в кластере, с целью последующей централизации или/и дистрибуции внутри кластера. Логично предположить, что самый производительный способ — это быть частью самого Asterisk.

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

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

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


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

5 октября 2016-го года вышел Visual Studio «15» Preview 5. Команда разработчиков сфокусировалась на повышении производительности IDE. В этой статье мы рассмотрим некоторые из улучшений. Запускайте инсталлятор и, пока он устанавливается, читайте о нововведениях в этой статье или в оригинальных release notes.

Значительный шаг вперёд в производительности и экономии памяти

Я хотел бы начать с видео, которое очень хорошо показывает рост производительности в данном превью. Здесь показана загрузка проекта Roslyn, которая ранее занимала 60 секунд, а в новом превью полностью заканчивается уже к 30-ой секунде.

Рано или поздно в программе что-нибудь идет не так. Не открылся файл, не создалась рабочая нить, не выделилась память… И с этим нужно как-то жить. В небольшом однопоточном приложении довольно просто: можно прервать всю работу и рестартовать. Это один из факторов, благодаря которому Erlang снискал себе заслуженную популярность, ведь идеология fail fast является одним из краеугольных камней Erlang-а с его легковесными процессами. Если же приложение большое, сложное и многопоточное, то не разумно рестартовать все приложение, если лишь одна из его нитей столкнулась с проблемами. Еще хуже в ситуации с реализациями Модели Акторов, в которых сотни тысяч акторов могут работать на десятках рабочих нитей. Проблема одного актора вряд ли должна сказываться на всех остальных акторах.

В данной статье мы расскажем, как мы подошли к обработке ошибок в своем фреймворке SObjectizer.

Исключениям – да, кодам возврата – нет!

Когда SObjectizer-4 появился в 2002-ом году, мы сделали большую ошибку – предпочли использовать коды возврата исключениям. И весь последующий опыт разработки на SObjectizer-4 снова и снова убеждал в одной простой истине: если ошибка может быть прогнорирована разработчиком, то она будет им проигнорирована. Поэтому при создании SObjectizer-5 мы решили использовать исключения для информирования об ошибках.

В августе этого года в Казани прошла Международная олимпиада по программированию для школьников — IOI 2016. Российская команда стала второй в общем зачете.

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

Денис Солонков — многократный победитель Всероссийских олимпиад по программированию и Moscow CTF School, выпускник Школы программистов, ныне студент ВШЭ.

В прошлом уроке мы таки осилили открытие окна и примитивный пользовательский ввод. В этом уроке мы разберем все азы вывода вершин на экран и воспользуемся всеми возможностями OpenGL, вроде VAO, VBO, EBO для того, чтобы вывести пару треугольников.
Заинтересовавшихся прошу под кат.

25 октября 2016 года Майкл Фезерс, Director of R7K Research & Conveyance и автор книги «Working Effectively with Legacy Code», выступит на uDev Tech Events с лекцией на тему «Micro Refactoring and Macro Refactoring: Strategies and Techniques».

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

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

const char *pStr = PSTR("Hello");	// В этом месте ошибка.
	// error: statement-expressions are not allowed outside functions nor in template-argument lists

int main() {…}

В этой статье мы рассмотрим один из вариантов реализации отложенного освещения на OpenGL ES 2.0.

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

Я не могу пройти мимо открытых исходников мессенджера ICQ. Это культовый проект, и когда исходные коды появились на сайте GitHub, вопрос, когда мы проверим его с помощью PVS-Studio, стал лишь вопросом времени. Конечно, у нас много и других интересных проектов, ждущих проверки. Например, недавно мы проверили GCC, GDB, Mono. Теперь наконец очередь дошла и до ICQ.

ICQ

ICQ (от англ. I seek you) это централизованная служба мгновенного обмена сообщениями, в настоящее время принадлежащая инвестиционному фонду Mail.ru Group. Количество пользователей ICQ снижается, но всё равно это приложение крайне популярно и широко известно среди IT-сообщества.

ICQ по меркам программистов является маленьким проектом. Я насчитал в нём 165 тысяч строк кода. Для сравнения, голое ядро анализатора PVS-Studio для анализа C++ кода реализуется с помощью 206 тысяч строк кода. Голое C++ ядро анализатора — это точно маленький проект.

Из интересного стоит отметить маленький процент комментариев. Утилита SourceMonitor утверждает, что в исходных кодах ICQ только 1,7% cтрок являются комментариями.

Исходники ICQ доступны для скачивания на сайте github: https://github.com/mailru/icqdesktop.

В прошлом уроке мы подготовили рабочее пространство и теперь мы полностью готовы создать окно.
Данный перевод подготовлен совместно с FERusM за что ему большое спасибо.
Заинтересовавшихся прошу под кат.

Использование текстур в OpenGL довольно распространенная тема на различных обучающих сайтах и форумах. Но кода необходима сделать анимированную текстуру все становится не так просто. Мне известно 2 способа это сделать и 1 из них я опишу.

В чем проблема текстовых форматов обмена данными? Они медленные. И не просто медленные, а чудовищно медленные. Да, они избыточны, по сравнению с бинарными протоколами и, по идее, текстовый сериализатор должен быть медленнее примерно на столько же, на сколько он избыточен. Но на практике получается, что текстовые сериализаторы иной раз на порядки уступают бинарным аналогам.

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

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

В прошлом уроке мы разобрались с тем, что такое OpenGL. В этом уроке мы поговорим о причине необходимости использования GLFW, GLEW и CMake, а также рассмотрим как их использовать. А также освежим в памяти, разницу между статической и динамической линковкой.

Заинтересовавшихся прошу под кат.

Алгоритмы сортировки

В этой статье речь пойдет о сравнении некоторых алгоритмов сортировки, реализованных на C++ для последовательности не упакованных BCD чисел большого размера.



Данный анализ я проводил в качестве летней практики в компании «Программные технологии».
Сортируемая последовательность не имеет заголовка, числа в ней имеют различную разрядность и хранятся без выравнивания. Между числами стоят разделители (0xFF).

Для осуществления сортировки с помощью библиотечной функции вводится дополнительный уровень данных – контейнер, содержащий указатели на области памяти, каждая из которых содержит одно BCD число. В сравнении участвуют:

1. Сортировка слиянием;
2. Сортировка слиянием без использования буфера;
3. Естественная сортировка слиянием;
4. Естественная сортировка слиянием без использования буфера;
5. Модифицированная естественная сортировка слиянием;
6. Модифицированная естественная сортировка слиянием без использования буфера;
7. std::sort.

Блокировки в общем и мьютексы, как их частная реализация, имеют давнюю историю неправильной оценки скорости их работы. Ещё в 1986-ом году в одной из Usenet-конференций Matthew Dillon написал: «Большинство людей ошибочно уяснили себе, что блокировки работают медленно». Сегодня, спустя многие годы, можно констатировать, что ничего не изменилось.

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

Одна из причин заблуждений о скорости работы блокировок состоит в том, что многие программисты не отличают понятия «легковесный мьютекс» и «мьютекс, как объект ядра ОС». Всегда используйте легковесные мьютексы. К примеру, если вы программируете на С++ под Windows, то ваш выбор это критические секции.

Второй причиной заблуждений могут служить, как это ни парадоксально, бенчмарки. К примеру, далее в этой статье мы будем измерять производительность блокировок под высокой нагрузкой: каждый поток будет требовать блокировку для выполнения любого действия, а сами блокировки будут очень короткими (и, в результате, очень частыми). Это нормально для эксперимента, но такой способ написания кода — это не то, что вам нужно в реальном приложении.