Архив метки: программирование

Сага о скорости sscanf

В нашем проекте есть одно из мест при чтении, когда надо распарсить строчку с числами вида «{ 123, 234, 345, 456, 567 }». Там всегда стоял сишный код декодирования через scanf. Ну а потом там пришлось все переделывать, и я на автомате написал декодирование в Qt стиле. А потом решил проверить что же будет быстрее.

Итого, у нас 2 варианта:
1) Ищем каждую первую цифру из каждого из чисел, после чего натравливаем scanf()
2) Сплитим строчку по разделителю, после чего для каждой полученной строки исполняем QString().toInt()

Для проверки что же работает быстрее я написал следующий код:

#include <QCoreApplication>
#include <QtGlobal>

#include <QElapsedTimer>
#include <QString>
#include <QStringList>
#include <QDebug>

#include <stdio.h>

int main(int argc, char *argv[])
{
    QByteArray r;
    for (int i = 0; i < 1000000; i++) {
        float a;
        int b = rand();
        a = *reinterpret_cast<float*>(&b);
        r += QString::number(rand()).toUtf8() + '\0';
    }

    //------------------------------------------
    //------------------------------------------

    QElapsedTimer timer;
    timer.start();

    QList<QByteArray> l = r.split('\0');
    float res = 0;
    for (int i = 0; i < l.size(); i++) {
        res += l.at(i).toFloat();
    }

    qDebug() << res << timer.elapsed();

    //------------------------------------------

    timer.start();

    const char *data = r.data();
    int size = r.size() - 1;
    res = 0;
    float f;
    for (int i = 0; i < size; i++)
        if (data[i] == '\0') {
            sscanf(data + i + 1, "%f", &f);
            res += f;
        }

    qDebug() << res << timer.elapsed();

    return 0;
}

Дебаг сборка
Qt: 165мс на декодирование
Си: 171мс на декодирование

Релиз сборка
Qt: 144мс
Си: 153мс

Массив чисел можно генерить как из целых, так и из float — скорость от этого особо не изменится. Зато скорость знатно меняется, если в качестве разделителя использовать не \0, а, допустим, просто пробел.

В таком случае, если уменьшить количество чисел с 1000000 до 100000, скорости будут такими (релиз):
Qt: 18мс
Си: 963мс

Знаете что это значит? Это значит, что если втупую написать код на Си, ожидая что он будет работать быстрее, то он не только может оказаться медленнее, он может совершенно случайно начать работать за квадрат вместо линии, которую обеспечивает Qt. Остается только догадываться насколько эффективно можно использовать еще более быстрый инструмент — ассемблер.

Ни дня без коммитов

Мой github

Прожил 73 дня, ежедневно модифицируя BSA-Analytics. Первые пару недель непрерывность была случайной, потом она стала искусственной. По внутренним правилам нельзя было переводить часы, заводить фиктивные задачи и отправлять коммиты с пробелами. Стрик был прерван случайно, я в тот день физически возился с сервером и просто забыл про отсутствие коммитов.

Положительные эффекты:

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

Отрицательные эффекты:

  • Размывается граница между отдыхом и работой. Иногда все же требуется на пару дней забыть о проекте
  • Постоянно приходится помнить о проекте. Иногда это весело, один раз я вспомнил об отсутствии коммитов в 23:56, и вполне успел реализовать конкретную фичу, но большей частью это просто неудобно
  • Начинается некоторое растягивание задач по времени. Например сначала открывается задача в багтрекере, а на следующий день закрывается. Еще получается удобно кодить около 11 вечера. Тогда можно сделать коммиты сразу за 2 дня
  • Не учитывается физический вклад. Конечно можно открывать и закрывать задачи вида «Сходить поставить программу на счет», но этому не место в моем уютном багтрекере

Забавные моменты:

  • Один раз пришлось все делать на экстрим-скорости: я вспомнил о BSA-Analytics в 23:56. К счастью, я весь день крутил в голове что и как надо сделать, поэтому успел за 15 секунд до полуночи
  • Три недели назад я остался без клавиатуры на ноуте, поэтому пяток коммитов был полностью сделан с помощью экранной клавиатуры
  • Один из коммитов пришлось по техническим причинам делать по дороге в Москву с экранной клавиатуры и мобильного интернета

Пущинская Новогодняя 2016

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

МГУ, ВМК, medialab, видеогруппа

Ровно год назад, 26 марта, я сидел в пустом кабинете и решал простую задачу. Надо было компенсировать два кадра, был дан шаблон под visual studio. Не работал поиск блоков 8×8.

Читать далее

Веселая школьная олимпиада 2013

К сожалению, в те времена я еще не вел блог, это единственная причина, по который не написал об этом ранее. Какая это была олимпиада я, честно говоря, уже забыл (их много). Но по количеству участников и модели своего ноута я все восстановил.

Читать далее

Сервис создания панорам

Есть такой грант — УМНИК. Если вам от 18 до 28 лет, и у вас есть проект, который потенциально способен приносить прибыль, то вы можете получить 400 тысяч на 2 года на реализацию этого проекта. Требуется только делать отчеты о проделанной работе. Ну и показать, то что ваш проект лучше, чем у всех остальных. И вот, в один прекрасный понедельник, мне приходит письмо от моего научного руководителя, мол, все на Умник. Все — это вся видеогруппа, кроме тех кто его уже получил. Я тогда, естественно, только посмеялся — куратора нету, окклюжены не коммерционализируемы, о чем речь вообще? Потом приехал куратор, а мне было предложено назвать 3 темы, а уж они то выберут.

У меня тогда нехило испортилось настроение, потому как я не собирался идти с проектом, на который нельзя получить грант. Если идти — то с возможностью выиграть. Но в результате душевных терзаний, мучений и споров, тема все-таки была придумана и одобрена — «Сервис создания панорам».
Читать далее

Пущинская новогодняя олимпиада 2015

Сегодня провели традиционную новогоднюю олимпиаду. На этот раз было куча народу из Дубны, аж с двух площадок. 51 не ноль в таблице. Провели без значительных косяков, к счастью я вырезал задачу I за полчаса до начала. Тесты были сделаны отменно — было всего лишь две посылки получившие 100 баллов и при этом не прошедшие тесты из условия. Мои задачи были недостаточно гробовыми — их решил приехавший из СУНЦа одиннадцатиклассник — Леша Соловьев. Собственно, он ухитрился решить мою задачу на 10% быстрее чем я на том же алгоритме. Посмотрев его код нашел пасхалку.

Правильные дефайны: +10% к скорости работы

Правильные дефайны: +10% к скорости работы

Программирование на ВМК

Я очень часто повторяю, что на ВМК не учат программировать. Большинство людей такие фразы абсолютно не понимают, а объяснять мне обычно лень. Но вот недавно я увидел код ВМКшника, в котором была задача прочитать бинарный файл. Задача несколько осложнялась тем, что ожидаемый (а может быть и требуемый) язык реализации был C/C++. Как бы вы считали бинарный файл? Я бы открыл его fopen’ом (плохо знаю плюсы, надо бы, конечно, какой-нибудь datastream использовать). А по возможности использовал бы Qt, который позволил бы удалиться на более высокий уровень, почти не потеряв в скорости. Этот товарищ использовал системные вызовы. Он читал файл через open и read. Это ужасно. Совершенно не к месту системные вызовы, которые еще и медленнее будут, если что-то пойдет не так с кешами. А если хочешь кеши — придется их самому написать. Может возникнуть вопрос — а зачем использовались системные вызовы то? Ответ прост — нам рассказывали только их. Поэтому, если вы видите странный код, изобилующий системными вызовами вместо нормальных библиотечных функций — перед вами с большой вероятностью ВМКшник. Этот пример не единственный. Я уже насмотрелся на однострочные комментарии «конструктор», «деструктор», «выделение памяти», «освобождение памяти», а также удаление дефолтных операторов присваивания, дефолтных конструкторов и прочей ереси, которую удалять совсем не обязательно.

Короче, учат не тому. А после просмотра подобного кода сразу видно какие курсы посещал человек. И не дай бог ему понравился ассемблер…

О чужом коде

Пару лет назад я посмотрел код OpenSSL. Он был ужасен. Особенно меня поразила примерно такая конструкция:

if (0) {
    L1:
    // some code
}

if (condition)
    goto L1;

Через некоторое время я решил что конструкция в принципе нормальная. А прочие ужасы кода свалил на то, что он написан математиками.

Но сейчас я решил расковырять другой продукт. Дело в том, что в CoolReader при ресайзе окна в управлении kwin происходит неприятный баг — он перематывает текст на конец. Это невероятно разражает — по сути единственный выход, это не ресайзить окно. Я решил найти в чем же проблема и полез в исходники. Исходники оказались страшноваты, но следующий код — это…

#define XS_IMPLEMENT_SCHEME 1
#include "../include/fb2def.h"

#if 0
void SaveBase64Objects( ldomNode * node )
{
    if ( !node->isElement() || node->getNodeId()!=el_binary )
    return;
    lString16 name = node->getAttributeValue(attr_id);
    if ( name.empty() )
    return;
    fprintf( stderr, "opening base64 stream...\n" );
    LVStreamRef in = node->createBase64Stream();
    if ( in.isNull() )
    return;
    fprintf( stderr, "base64 stream opened: %d bytes\n", (int)in->GetSize() );
    fprintf( stderr, "opening out stream...\n" );
    LVStreamRef outstream = LVOpenFileStream( name.c_str(), LVOM_WRITE );
    if (outstream.isNull())
    return;
    //outstream->Write( "test", 4, NULL );
    fprintf( stderr, "streams opened, copying...\n" );
    /*
     lUInt8 dbuf[128000];
     lvsize_t bytesRead = 0;
     if ( in->Read( dbuf, 128000, &bytesRead )==LVERR_OK )
     {
     fprintf(stderr, "Read %d bytes, writing...\n", (int) bytesRead );
     //outstream->Write( "test2", 5, NULL );
     //outstream->Write( "test3", 5, NULL );
     outstream->Write( dbuf, 100, NULL );
     outstream->Write( dbuf, bytesRead, NULL );
     //outstream->Write( "test4", 5, NULL );
     }
     */
    LVPumpStream( outstream, in );
    fprintf(stderr, "...\n");
}
#endif

А вот так элегантно решается вопрос об индикаторе батареи:

Пора кодить!

Сессия была страшной и мозг включается тяжело. В ноуте новый кулер — тот самый, который мне пришлось поменять пару месяцев назад. К счастью, гарантия была на три месяца. Ноут на коленях. На ноуте механическая клава — явный признак того, что пора кодить. Рядом кофе. Для атмосферы. Сверху выползает консоль. В консоли открыт консольный плеер. Это именно то, что мне не хватало. Я давно забыл про тебя, moc. Где-то в километре от меня находится сервер. На сервере 2 процессора перемалывают один из самых ужасных кодов, которые я когда-либо писал — BSA-Analytics. Но он работает. Пульсары находятся. В двух метрах от меня стоит ноут с замененной по гарантии материнкой. Он стоит без крышки и экраном вниз — так эффективнее работает охлаждение. Занимается тем же самым. На другой вкладке консоли к нему открыта ssh-сессия. SSH-сессия идет не напрямую, а через нидерландский сервер — так удобнее. В ssh-сессии открыт screen. Screen — это вещь. В screen’e rsync перебрасывает посчитанные данные на четвертый сервер — он находится во Франции. Люблю современный уровень абстракций!