Дмитpий Hecтepук

Блог о программировании — C#, F#, C++, архитектура, и многое другое

Posts Tagged ‘parsing

Короткий опыт использования С++

7 комментариев

Хочу поделиться опытом решения задачи, для которой я вместо C# решил использовать C++. История, мне кажется, очень поучительная, т.к. хорошо иллюстрирует все казусы использования этого «древнего» языка.

Сценарий

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

  • Некоторые численные значения поставлены не как число, а как строка, например 12345.00000. Эту строку естественно надо «парсить» чтобы получить значение типа double.

  • Все даты в файле поставлены как строки в формате 1991.11.11 11:11:11.111.

  • В данных много повторяющихся строковых литералов, которые можно удалить полностью.

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

Первая попытка

Первой моей попыткой было, конечно же, тупо подключить к драйверу SQLite модель на базе Entity Framework. Но из этого ничего не получилось – я кажется установил все драйвера которые только можно, и оно все равно не заработало.

Поэтому я решил написать «выдиралку» с использованием только Connection/Command объектов – это как раз тот ADO.NET подход который был популярен во времена .NET 1.1 примерно 8 лет назад.

Написав, я столкнулся с рядом весьма очевидных проблем, главной из которых стала производительность. Например, я понял что использование BinaryFormatter для сериализации структур привело к таким тормозам, что нужно было все сразу переписывать на ручную сериализацию через BinaryReader/BinaryWriter. Производительность увеличилась, но я понял, что если я хочу переконвертировать все данные, мне придется просто оставить компьютер работать на неделю-другую.

Переход на C++

В связи со всем этим, я решил что лучше написать один раз, но написать качественно и так чтобы быстро работало. Создал новый проект С++, перевел его на компилятор Intel (для тех кто не знает, я – ярый фанат использования Intel Parallel Studio), и начал писать. Сразу оговорюсь, что писал я с уклоном на то, что результирующие бинарные данные все равно будут использовться в .NET.

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

Второй шаг – это конечно подключение библиотеки Boost, которая мне потребовалась для обработки дат. И вот тут уже началось веселье. В частности, библиотека работы с датой и временем — апокалиптична. Неподготовленному человеку в ней не разобраться без нескольких часов читания доков. Не то что System.DateTime! Вот например как происходит конверсия в .NET-совместимую эпоху:

static uint64_t netEpochOffset = 441481536000000000LL;
static ptime netEpoch(date(1400,1,1), time_duration(0,0,0));
static int64_t Util::TimeToTicks(ptime time)
{
  time_duration td = time - netEpoch;
  uint64_t nano = td.total_microseconds() * 10LL;
  return nano + netEpochOffset;
}

И подобная магия тут везде. Вот в .NET у нас тоже один большой long определяет всю дату, но DateTime имеет кучу методов для того чтобы получить кол-во часов, дней, и так далее. Тут все по-другому, тут дата – это сколько вы отсчитали от той или иной эпохи, и чтобы вычитать, например, только время из даты, придется сильно попотеть. Соответственно, для того чтобы определить определенное время дня мне приходилось писать вот такой код:

time_duration _19_00 = time_from_string("1900/01/01 19:00:00.000").time_of_day();

Знаю что экспертам по Boost это покажется смешным, но для трезвого дот-нетчика, вся эта библиотека кажется адом. Даже Boost.Math, который я использую в другом проекте, и то порой эклектичен.

Работа с коллекциями

Коллекции в С++ хранятся ‘by value’, поэтому по-хорошему любой ваш список будет иметь тип vector<boost::shared_ptr<MyObject>> и разыменовывание надо будет делать через (*itr)->DoSomething, что само по себе бесит. Более того, даже работая с примитивными структурами, понимаешь что нехватает массы методов. Например, у .NETного Dictionary есть метод ContainsKey() который проверяет наличие записи с таким ключем. А что происходит с С++‘ным map, где такого метода нет? Вот, полюбуйтесь:

boost::shared_ptr<FullBarrel> barrel;
auto candidate = futureBarrels.find(instrument->InstrumentID);
if (candidate != futureBarrels.end())
  barrel = candidate->second;
else {
  barrel = boost::shared_ptr<FullBarrel>(new FullBarrel);
  futureBarrels.insert(candidate, BarrelDictionary::value_type(instrument->InstrumentID, barrel));
}

Следующее, что убивает, это const-корректность – наивный и жалкий механизм, с помощью которого С++ пытается контролировать, какие элементы можно менять а какие нет. Выливается это в то, что например задекларированный вами vector внезапно нельзя менять внутри for_each. Понятное дело, что для «зубров» С++ эти проблемы разруливаются, да и я смог разобраться, но это еще один пример того, как устаревшая парадигма языка не привносит ничего полезного, зато добавляет массу головной боли.

Сериализация

Поскольку все мои данные – численные (в основном либо double либо int64_t), я решил использовать обычную структуру, т.е. struct, для хранения данных. К счастью, С++ умеет сериализовывать эту структуру в файл полностью, считывая из нее всю память:

ofstream ofs(filename, ios::out | ios::binary);
ofs.write((char*)&myStruct, sizeof(MyStructure));
ofs.close();

Единственный сюрприз ждал меня когда я начал читать эти данные в .NET-е. Во-первых, я не угадал сначала какой размер данных у enum-ов (4 байта), а во-вторых, я забыл про упаковку данных.

Упаковка данных (structure packing) – это механизм, который выравнивает структуры на границах байтов. Очень полезно для процессора, но мой .NETный BinaryReader естественно ничего про подобное не знает и пытается читать заглушечные данные в память переменных.

Решение было простое – добавить директиву #pragma pack(1) в С++ чтобы выравнивать по одному байту, т.е. не добавлять промежуточных данных вообще. Внезапно, все заработало в .NET.

Оптимизации

Я был поражен увеличением скорости в конечной реализации, поэтому не слишком сильно напрягался насчет профилирования. Единственное, что действительно хотелось оптимизировать – это механизм разбора строковых значений вроде 12345.000 и их переведения в тип double. Конечный результат выглядит вот так:

double Util::powersOf10[] = { 1.0, 10.0, 100.0, 1000.0, 10000.0, 100000.0, 1000000.0, 10000000.0 };
static double Util::StringToDouble(string& s)
{
  auto dotPos = s.find('.');
  s.erase(s.begin() + dotPos);
  return _atoi64(s.c_str())/powersOf10[s.length() - dotPos] ;
}

В примере выше, мы просто переводим число в целое, парсим его как целое, а потом делим на степень 10-ти их заранее приготовленной таблицы.

Заключение

Конечный результат дал примерно 10-кратное увеличение производительности. За счет компактности С++ных structов, данные получилось ужать примерно в 100 раз. С другой стороны, производительность разработчика упала раз в 5 (а может и более). Спасает лишь то, что это единовременная проблема.

Мне кажется что вывод тут может быть один: нужно использовать правильный язык для правильной ситуации. Ведь анализ конечных данных я все равно буду проводить с использованием C#, т.е. работать на языке где нет LINQ – это как-то совсем архаично. Но многие ведь работают, не так ли?

P.S.: для работы с данными использовался SSD — к сожалению не Revo или FusionIO, а обычный Vertex 3. Обработка велась в несколько потоков на одном физическом диске, т.е. одновременно писалось и читалось несколько файлов.

Реклама

Written by Dmitri

29 марта 2012 at 1:01

Опубликовано в С++

Tagged with , ,