Fast iterating over xml nodes by MSXML

Волею судеб мне приходится иметь дело с MSXML. Не самая лучшая библиотека для работы с xml, но так вот получилось. И будучи любителем конструкции for_each, обход дочерних нод в моем коде выглядит так:

BOOST_FOREACH(IXMLDOMNodePtr Node, ChildNodes(RootNode))
    DoSomething(Node);

ChildNodes отдает пару итераторов, которые дают доступ по IXMLDOMNodeList через IXMLDOMNodeList::item(). Так вот на обработке большого xml файла заметил, что такая конструкция очень жутко тормозит. Я было хотел списать все это со словами "ну этож MSXML тормозная - ничего не поделаешь...". Но как оказалось, правдива только первая часть этой фразы, а "поделать" все-таки что-то можно: если перебирать ноды через IXMLDOMNodeList::nextNode(), то вместо исходных 450мс получалось обойти ноды всего за 28:

IXMLDOMNodeListPtr NodeList = RootNode->childNodes;
for (IXMLDOMNodePtr Node; Node = NodeList->nextNode(); )
    DoSomething(Node);

Видимо про такие случаи Спольски рассказывал байку про маляра, который красил забор. За первый день он покрасил 20 метров забора, за второй - 10, за третий - всего 2 (цифры привожу по памяти, память дырявая). Когда его спросили, почему он так стал тормозить, ответ был великолепен: "Насяльника, так за краской все дальше и дальше ходить!" Видимо IXMLDOMNodeList::item() работает таким же образом, как и тот маляр, так что beware!

Calculating XPath expressions by MSXML

Если посчитать выражение XPath, что может получиться?
Согласно спецификации XPath:
- список узлов
- строка
- логическое значение
- число

В .NET-е можно получить все из вышеперечисленного. А вот MSXML предлагает API только для получения списка узлов - selectNodes.

А что, если нужно получать значения других типов? Товарищи в форумах предлагают хитрый трюк - обернуть XPath выражение в XSLT, наложить его на нужный узел или документ, а в результате получить строку. Даже закрывая глаза на производительность такого трюка, таким способом не удается получить всю информацию - а именно информацию о типе результата. Ведь на выходе - всегда строка.

Если выражение - "наше", то тип результата сразу знаем. Но если "чужое", и нам нужно узнать тип результата, то в таком случае мы в тупике - из полученной строки не получится извлечь тип. Вот, 123 - это строка "123" или число 123?

Я узнал о следующем - в MSXML можно использовать JavaScript внутри XSLT. Тогда все становится достаточно просто:

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0"
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:msxsl="urn:schemas-microsoft-com:xslt"
    xmlns:js="urn:custom-javascript"
    exclude-result-prefixes="msxsl js" >
    <xsl:template match="/">
        <xsl:variable name="value" select="выражение"/>
        <result>
            <value>
                <xsl:value-of select="$value"/>
            </value>
            <type>
                <xsl:value-of select="js:TypeOf($value)"/>
            </type>
        </result>
    </xsl:template>
    <msxsl:script language="JavaScript" implements-prefix="js">
        function TypeOf(strText) { return typeof strText; }
    </msxsl:script> 
</xsl:stylesheet>

Специальная JavaScript-функция вернет нам тип выражения, остается только не думать какая у всего этого производительность ;)

Unicode: life-hack

Мой обычный сценарий при создании новых файлов в проекте:
1. right click в Windows explorer на папке, где нужно создать файл
2. выбор Create/"New Text File.txt"
3. ввод имени файла
4. right click на файле
5. SVN/Add
6. Перетаскивание файла в IDE

Небольшой лайф-хак позволяет сразу создавать файлы в UTF-8:

Файл создается с BOM для UTF-8.

Yo!

Отсортировать строки по алфавиту очень просто - все необходимые сведения о порядке символов есть в классе std::locale. Остается только надеяться что std::locale не подведет. А, как оказалось, она может. Вот пример:

struct lexicographical_order
{
    std::locale Locale;

    lexicographical_order(std::locale Locale) : Locale(Locale)
    {
    }

    bool operator()(std::wstring const &lhs, std::wstring const &rhs) const
    {
        return boost::ilexicographical_compare(lhs, rhs, Locale);
    }
};

int main()
{
    std::vector v;
    v.push_back(L"яблоко");
    v.push_back(L"апельсин");
    v.push_back(L"банан");
    v.push_back(L"персик");
    v.push_back(L"ёжик");
 
    std::locale Locale(""); // используем текущую локаль системы
    std::cout << Locale.name() << std::endl;
    std::sort(v.begin(), v.end(), lexicographical_order(Locale));

    _setmode(_fileno(stdout), _O_U16TEXT);
    std::copy(v.begin(), v.end(), std::ostream_iterator(std::wcout, L"\n"));
    return 0;
}

Под русской Windows получаем:

Russian_Russia.1251
ёжик
апельсин
банан
персик
яблоко

Буква "ё" явно пользуется у данной локали большей популярностью, чем все остальные. Ну прям хоть свою локаль пиши...

Boost Tuple Serialization

Сложно поверить, но в Boost-е нет сериализации для tuple.

Видимо вся фигня в том, что при сериализации кортежей нужно написать сериализацию для кортежей 0..N элементов, а это можно сделать:
а) руками: написать вручную сериализацию для 0, 1, 2 и т.д. элементов, что совсем не кошерно;
б) препроцессором: использовать boost preprocessor - тоже считается не очень кошерно;
в) компилятор: но тут вся загвоздка как я понял в том, что это нельзя сделать используя публичный интерфейс tuple, можно только зная особенности реализации (details), что тоже вроде бы не очень кошерно.

В результате был выбран списоб "г" - вообще не писать сериализацию для tuple. Что я считаю полным бредом.

PS. Если что - есть готовая реализация через препроцессор.

Sorting by several fields

Как вы сортируете по нескольким критериям?

struct foo
{
    A a; B b; C c; D d;
    X x; Y y;
};

// нужно отсортировать по a, затем по b, затем по c, ну а затем еще и по d
// по x и y сортировать не нужно
bool s(foo const &l, foo const &r)
{
    if (l.a < r.a) return true;
    if (l.a > r.a) return false;
    if (l.b < r.b) return true;
    if (l.b > r.b) return false;
    if (l.c < r.c) return true;
    if (l.c > r.c) return false;
    return l.d < r.d;
}

std::vector<foo> f;
std::sort(f.begin(), f.end(), s);

Признаюсь, я примерно так раньше и сортировал. Хотя по сути-то [a,b,c,d] - это ж по-сути обычный кортеж, а для них уже есть готовые библиотеки. И операции сравнения кортежей там должны быть, в этих библиотеках. Нужно просто загнать l и r в кортежи (только для скорости - не в [A,B,C,D], а в [const&A,const&B,const&C,const&D]), и сравнить:

#include <boost/tuple/tuple_comparison.hpp>

bool s(foo const &l, foo const &r)
{
    return boost::tie(l.a, l.b, l.c, l.d) < boost::tie(r.a, r.b, r.c, r.d);
}

Static member definition

Интересно, что статический член класса нельзя определить прямо в декларации класса:

class foo
{
    static std::string s('hello world');
};

А иногда сильно этого хочется - например в декларации шаблона. Или просто в каком-нибудь header-only классе. Самое интересное, что внутри функции такое провернуть можно. Поэтому можно сделать финт ушами - сделать доступ к статическому члену через member-функцию:

class foo
{
    static std::string &s()
    {
        static std::string impl('hello world');
        return impl;
    }
};

Синтаксис при обращении немного поменяется - s() вместо s, но часто оно того стоит.

Fast parsing

Чем вы парсите всякую "мелочёвку" типа целочисленных значений и прочее? Самописными парсерами с приправами вроде boost::tokenizer, boost::lexical_cast или даже atoi, etc.? Я обычно использовал boost::regex + lexical_cast. А тут недавно посмотрел презентацию Spirit-а с BoostCon-а, даже немного проникся. Раньше как-то я к Спириту более равнодушен был.

Описывать грамматику на C++ и потом давать компилятору [несколько минут] это компилировать - это, конечно, большой изврат. Но весьма забавно. И, говорят, работает потом очень быстро. Даже если нужно просто число распарсить - говорят быстрее всех парсит.

std::string buffer("1234");
int value = 0;

using namespace boost::spirit;
bool r = qi::parse(buffer.begin(), buffer.end(), int_, value);
assert(r && value == 1234);

Visual Studio debug visualizers

Начиная с Visual Studio 2005 можно писать свои правила для отображения значений в отладчике. Более подробнее об этом можно почитать в блоге virtualdub.

Правила для Boost-овских типов можно найти на Boost Wiki. Единственное, не нашел там то, что искал — для boost::variant. Набросал на коленке:

boost::variant<*,*,*,*,*,*,*,*,*,*,*> {
    preview (
        #(
            #switch($c.which_)
            #case 0 ( *($T1 *)&($c.storage_.data_) )
            #case 1 ( *($T2 *)&($c.storage_.data_) )
            #case 2 ( *($T3 *)&($c.storage_.data_) )
            #case 3 ( *($T4 *)&($c.storage_.data_) )
            #case 4 ( *($T5 *)&($c.storage_.data_) )
            #case 5 ( *($T6 *)&($c.storage_.data_) )
            #case 6 ( *($T7 *)&($c.storage_.data_) )
            #case 7 ( *($T8 *)&($c.storage_.data_) )
            #case 8 ( *($T9 *)&($c.storage_.data_) )
            #case 9 ( *($T10 *)&($c.storage_.data_) )
        )
    )
    children
    (
        #(
        value:
            #switch($c.which_)
            #case 0 ( *($T1 *)&($c.storage_.data_) )
            #case 1 ( *($T2 *)&($c.storage_.data_) )
            #case 2 ( *($T3 *)&($c.storage_.data_) )
            #case 3 ( *($T4 *)&($c.storage_.data_) )
            #case 4 ( *($T5 *)&($c.storage_.data_) )
            #case 5 ( *($T6 *)&($c.storage_.data_) )
            #case 6 ( *($T7 *)&($c.storage_.data_) )
            #case 7 ( *($T8 *)&($c.storage_.data_) )
            #case 8 ( *($T9 *)&($c.storage_.data_) )
            #case 9 ( *($T10 *)&($c.storage_.data_) )
        )
    )
}

Container with a preallocated buffer

STL-ные контейнеры - замечательная вещь, вот только хранят они все на куче. А иногда ведь так хочется, чтобы они использовали какой-нибудь буфер внутри объекта. Что-то типа такого:

template <typename T, size_t N>
struct Container
{
   size_t size; // сколько элементов в контейнере
   T storage[N]; // заранее выделенный буфер для объектов
};

Такой контейнер будет полезен, например, когда создается временный контейнер на стеке, максимальное количество элементов в нем предполагается известным. Или, например, когда нам нужен контейнер на небольшое нефиксированное количество элементов. Ну правда, стоит ли из-за контейнера на 1-2 небольших элемента заниматься выделением-освобождением памяти на куче (что довольно затратно по времени)?

Есть похожие на это контейнеры:
- boost.array, но он хранит только фиксированное количество элементов, для переменного количества не подойдет
- boost.optional - это почти то, что нужно, но если нужно хранить не более 1 элемента ;)

Нужный мне контейнер есть в стандартной библиотеке C++, которая поставляется с Visual C++, называется он basic_string. В этой реализации (возможно и в каких-то других) он имеет буфер на небольшое количество символов - чтобы для небольших по размеру строк не лазить на кучу. Однако, размер буфера там не регулируется "снаружи", да и нет смысла полагаться на конкретную реализацию - в другой стандартной библиотеке может быть все по-другому, да и эта может "изменить" в любой момент.

В boost-е планируется к review нужный контейнер - auto_buffer. Его еще немного допилят по интерфейсу, но пользоваться уже можно смело. В добавок он может, как и basic_string, расти в кучу, если нужно.

Presentations from BoostCon 2009

Доступны для скачивания презентации с BoostCon 2009.

Range concatenation

В библиотеках для работы с итераторами (Boost.Iterators, Boost.Range, RangeEx) куча полезных вещей, но почему-то нигде не нашел механизма "склеить" два диапазона в один. Такого, чтобы можно было сделать вот так:

template <class Range> void process_range(Range const &);

std::vector<foo> v = ...;
std::list<foo> l = ...;
process_range(concat(v, l));

Вот разбить диапазон на части - пожалуйста, перемещать значения в случайном порядке - да не вопрос, а вот склеить - нифига.

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

С использованием boost::variant все получилось достаточно компактно, хотя не максимально эффективно:

template <class TIterator1, class TIterator2, ...>
class ConcatIterator : public boost::iterator_facade<...>
{
public:
    reference dereference() const
    {
        return boost::apply_visitor(DereferenceVisitor<reference>(), It);
    }

    void increment()
    {
        boost::apply_visitor(IncrementVisitor(), It);
        StabilizeForward();
    }

    void decrement()
    {
        StabilizeBackward();
        boost::apply_visitor(DecrementVisitor(), It);
    }

    bool equal(const ConcatIterator& lhs) const
    {
        return (Range == lhs.Range) && (It == lhs.It);
    }

private:
    size_t Range; // 0 for the first range, 1 for the second range
    boost::variant<TIterator1, TIterator2> It, End1, Begin2;
};

PS. Нет худа без добра. Мой велосипед вдохновил разработчиков Boost.Range добавить объединение диапазонов в RangeEx.

Unexpected side effect

У каждого windows-процесса есть такая "глобальная переменная" - текущая директория. Её можно прочитать функцией GetCurrentDirectory() и изменить функцией SetCurrentDirectory().

Вот чего я не ожидал, что её меняют кто попало. Например, она может изменится после вызовов GetSaveFileName(), GetOpenFileName(). В их документации такое поведение описано и дана возможность его отключить. Но другое дело, что она может измениться внутри... функции StartDoc(). Это такая функция, которая "The StartDoc function starts a print job.", вобщем начинает печать.

И вот почему такое может происходить: драйвер принтера Microsoft Office Document Image Writer - поставляется с Microsoft Office и "печатает" в TIFF-файлы. При получении новой задачи он спрашивает куда же нужно сохранить создаваемый файл. Делает он это, я полагаю, с помощью GetSaveFileName(). Та, в свою очередь, меняет текущую директорию. Я бы сказал что врядли рядовой программист будет ожидать такие побочные эффекты от функции StartDoc().

Мораль (кроме той, что нужно драйвер подправить, добавив флажок OFN_NOCHANGEDIR) - старайтесь не менять глобального окружения кроме случаев, где это будет очевидно.

RangeEx

Концепция итераторов в STL - замечательная вещь. Можно сказать это C++-ная замена С-шным указателям, причем обратно совместимая с последними. Но вот в реальной жизни пользоваться только итераторами не настолько удобно - чаще больше подходят более высокоуровневые концепции - диапазоны (ranges) и контейнеры. Чаще бывает удобнее писать copy(from, to), чем copy(from.begin(), from.end(), make_back_inserter(to)). Да и вернуть диапазон вместо пары итераторов гораздо удобнее:

encode(substring());

вместо

pair<iterator, iterator> sub(substring());
encode(sub.first, sub.second);

Помню как-то читал как Александреску в языке D активно продвигает диапазоны вообще на замену итераторам. Можно так критично не относиться к итераторам, но я при написании кода вовсю стараюсь специализировать алгоритмы не только для итераторов, но и диапазонов. Алгоритмы в Boost, кстати, тоже очень range-friendly.

И очень правильный шаг в этом направлении - [Boost.]RangeEx. Эта библиотека позволяет сильно упростить код, который до этого использовал итераторы. Конечно, раньше кое-как спасал Boost.Iterators, но код был не в пример этому:

boost::copy(rng |
    boost::adaptors::filtered(pred) |
    boost::adaptors::unique,
    out)

Синтакис очень знаком:

ls | grep ".xml" | wc -l

Вобщем, я очень проникся и вам советую попробовать.

Прибирайте за собой

Довольно просто на стороне клиента открыть полученный с сервера файл в его родном приложении: ShellExecute(..., FileName, ...)

Единственное, перед этим нужно сохранить файл на диск. Например, во временную папку. Вопрос только - когда его удалять? Сразу же после вызова ShellExecute() это делать вряд ли разумно - запущенное приложение может не успеть еще забрать данные из файла. А может успеть открыть файл, и оставить его заблокированным на время просмотра.

Ничего красивее чем MoveFileEx(FileName, NULL, MOVEFILE_DELAY_UNTIL_REBOOT) в голову не приходит. Правда до ближайшего ребута может быть много лет, но на клиентских машинах такое редко бывает. С другой стороны - многие вообще не прибирают за собой временные файлы, так что это лучше чем ничего.

Интересно, есть ли более элегантное решение?

Container as a stream

Как быть, если есть данные в контейнере, а нужно получить доступ к нему в виде стандартного потока (basic_iostream)? Например, данные лежат в памяти, а нужно скормить их какой-нибудь функции из third party библиотеки, которая принимает iostream?

typedef std::deque<char> container;
container c;

В примерах boost::iostreams есть замечательная штука, не знаю почему ее не включили в саму библиотеку - адаптер для контейнеров. Использовать можно так:

#include <boost/../libs/iostreams/example/container_device.hpp>

typedef boost::iostreams::example::container_device<container> device;
boost::iostreams::stream<device> stream(c);

stream << "hello, world";
stream >> variable;

Different libraries

На новогодних праздниках нашлось время посмотреть разные C++ библиотеки. А то несправедливо — люди во всю стараются, делают всякие удобные, мощные, гибкие, быстрые и стабильные библиотеки со вкусными лицензиями, а я тут сижу велосипеды изобретаю.

Краткий список того, что нашел для себя интересного.

Futures
В C++0x будет замечательная вещь — futures. Коротко говоря — это лениво-вычисляемые функции. Причем их можно "отправить" вычисляться на другой тред, а потом просто забрать результат. А еще можно организовать обмен сообщениями между тредами. Парочка реализаций futures уже предлагается для включения в Boost, в том числе и версия от Anthony Williams, по которой и писался стандарт C++0x в части futures (доступна также полностью соответствующая стандарту C++0x библиотека threads).

Boost.MPI
Библиотека для взаимодействия между процессами с крайне удобным интерфейсом. Приведенные примеры использования вдохновляют.

Any Iterator
Давно подумывал написать обертку для итераторов, которая преобразует статический полиморфизм STL-ных итераторов в динамический. Например, если вы хотите иметь интерфейс с парочкой виртуальных функций RangeBegin() и RangeEnd(), то какой тип они будут возвращать? std::vector<T>::iterator или std::list<T>::iterator? Или даже boost::transform_iterator<...>? Вам не нужно знать какой конкретно тип итераторов будет использовать та или иная реализация интерфейса. Вместо этого вы делаете тип возвращаемого значения RangeBegin() и RangeEnd() как any_iretator<T>, а внутри реализации автоматически преобразовываете свой std::deque<T>::iterator или my::whatever<T>::iterator к этому типу. Подробнее — в статье, там же ссылка на саму библиотеку.

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

unique_ptr
Для тех кто уже понял чем unique_ptr лучше auto_ptr (первый заменяет собою второй в C++0x), но еще пользуется компиляторами без поддержки C++0x — готовая библиотека эмуляции unique_ptr. Да, кстати, а в Boost будет эмуляция rvalues для "старых" компиляторов.

Traversal
Boost.Iterators предоставляют хорошие возможности по трансформации итераторов, однако по иерархическим структурам с помощью них бегать достаточно трудновато. Как-то я писал STL-style итераторы для MS XML и MS DOM, так вот там бы пригодилась новая библиотека Traversal — позволяет итерироваться по иерархиям.