elizarov

Вчера состоялось торжественное открытие 36-го Международного Студенческого Командного Чемпионата Мира по Программированию (ACM ICPC). В этом 2012 году финал этого самого престижного соревнования среди программистов проводит Варшавский Университет в Польше. Эта честь вполне заслужена, так как команды этого вуза два раза становились чемпионами мира (в 2003 и 2007 годах). Организаторы постарались на славу чтобы принять 112 лучших студенческих команд программистов (по 3 человека в команде, не считая тренера) со всего мира. Это лучшие из лучших команды, отобранные среди более чем 2200 вузов из 85 стран. В оборочных соревнования разного уровня, за право попасть на финал, в этом году сражались более 30 тысяч студентов.

Завтра состоится сам финал соревнования и определится имя нового чемпиона. Безусловно, я болею за команды нашего Северо-Восточного Европейского Региона (NEERC). Ежегодно мы проделываем большую работу, чтобы отобрать те команды, которые смогут лучше всего выступить на финале. У них есть знания, умения, и опыт. Всё что им нужно для победы это собранность, концентрация, и удача. Успехов им всем!

Описание атмосферы соревнования от первого лица можно прочитать в этом блоге второго тренера команды МГУ, члена жюри NEERC Петра Митричева, так же известного как programmer.

На сайте ICPC Live идет репортаж о соревновании в режиме реального времени и будет живая видео-трансляция соревнования для всех болельщиков. Оно начнется в четверг, 17-го мая, в 12:00 по Московкому времени.

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

( Подробности с цифрами под катом... )

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

( Read more... )

12 мая 2012 года я выступаю с докладом на конференции Application Developer Days. Мой доклад будет посвящен написанию высокопроизводительных структур данных и будет служить продолжением моей серии статей про производительность. Я покажу весь путь дизайна на примере конкретной задачи. Это задача кэширования данных загруженных из БД, которая очень часто возникает в бизнес приложениях. Безусловно, есть множество готовых каркасов, которые решают эту задачу совершенно прозрачно для программиста. Но что делать, если вы создаете высоконагруженное приложение, оперирующее миллионами объектов и вынужденное постоянно к мим обращаться для выполнения тех или иных стоящих перед вами задач? Например, высокопроизводительные приложения для торговли на финансовых рынках, по типу тех, которые мы создаем в Devexperts.

( Продолжение под катом с конкретным кодом и результатами тестирования )

Вчера вечером услышал по радио комментарий трейдера Василия Олейника по поводу сбоя на бирже РТС-ММВБ: "Технические сбои бывают именно в те неподходящие моменты, когда очень сильно конъюнктура на внешних площадках меняется." Сразу оговорюсь. Несмотря на то, что и Фондовая Биржа РТС и ММВБ были нашими клиентами еще до объединения, и остаются таковыми после, мы (Devexperts) не имеем отношения к коду собственно их торговых систем, поэтому про технические подробности этого конкретного сбоя я ничего сказать не могу (но если бы мы и имели бы отношение к этому коду, то я бы тоже сказать ничего не мог бы из-за обычного в таких случаях NDA). А вот о технических сбоях вообще расскажу подробней.

( Read more... )

Недавно sorhed и akuklev опубликовали очень интересные слайды, в которых они подробно описывают как можно расширить язык Scala таким образом, чтобы тип функции описывал все её возможные эффекты. Причем не только для того, чтобы просто отличать чистые функции без побочных эффектов от всего остального, а с полной поддержкой всего многообразия промежуточных вариантов: функции выводящие в лог, пишущие и читающие из определенных файлов, кидающие определенные исключения и т.п. При этом результирующий код не сильно отличается от обычного императивного кода и подробно указывать типы по сути нужно только при объявлении функции. Большое преимущество кода написанного таким образом в том, что четкий контроль над эффектами потенциально позволяет безопасно паралеллизовывать выполнения тех веток кода, которые не зависят друг от друга. Да и вообще такой универсальный механизм позволяет на этапе компиляции контролировать множество различных аспектов кода, которые сейчас порой приходится описывать в его документации. Но я не будут вдаваться в подробности, а расскажу про то, как это связано с проверяемыми исключениями.

( Что такое проверяемые исключения? )

Я опубликовал вводную часть руководства по dxFeed API на сайте dxFeed и хочу подробней остановиться на обработке ошибок в API высокого уровня. Посмотрите на типичное синхронное API по работе с файлами или сетью в любой операционной системе или в любом языке программирования общего назначения. Вы увидите набор методов для открытия файла или соединения, набор методов для отсылки и получения данных, для закрытия. В случае ошибки они возвращают какой-нибудь специальный результат для индикации ошибки или создают исключение (как например IOException). Асинхронное API отличается тем, что вызов метода дает лишь сигнал начать операцию, а её выполнение будет произведено позже. Тем не менее, сигнал об ошибке так или иначе является частью результата, который будет получен позже. Для API низкого уровня явная индикация всех ошибок это естественное поведение. Ведь на основе этого API стоится множество различных приложений с различными требованиями. Реакция на ошибку сильно зависит от конкретного приложения.

( А вот в API высокого уровня... )

В сети появилась презентация "Java 8: Selected Updates". В ней перечислены основные изменения, которые планируется включить в Java 8 и дана весьма подробная информация про Проект Лямбда, включая исчерпывающее объяснение того, как лямбда-выражения будут представлены в скомпилированном байт-коде и почему так. Вообще, Java 8 имеет шанс переплюнуть даже Java 1.5 по общему количеству изменений в языке. Это не удивительно, ибо работа над всеми этими изменениями идет уже очень давно. Я слежу за всеми ими уже много лет и далеко не все первоначальные идеи были всесторонне продуманы. Тем приятней видеть, что дополнительное потраченное на проработку время пошло только на пользу.

( Поговорим об изменениях языка чуть подробней )

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

( Прошло почти 20 лет... )