• German Strings
• Глубокое погружение в German Strings

Перевод/заметки A Deep Dive into German Strings

«Strings are Everywhere»! По крайней мере, так утверждается в DBTest Paper 2018 года, подготовленном командой Hyper из Tableau. На самом деле, строки составляют почти половину данных, обрабатываемых в Tableau.

В нашей предыдущей статье в блоге мы познакомили вас с оптимизированным layout German Strings, который уже присутствовал в системе Hyper и с тех пор получил широкое распространение. Наш пост привлек много внимания и, что еще важнее, вопросов об их внутреннем устройстве. Пользуясь случаем, в этом посте мы хотим углубиться в тонкости их реализации и рассказать о том, почему оптимизации, описанные в нашем предыдущем посте, необходимы для высокопроизводительной обработки строк.

Преимущества 16B представление строк

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

Экономия места

Начнем с очевидного преимущества использования 16 байт вместо 24 байт, как в std::string C++: Это экономит 8 байт на строку. На первый взгляд, эта экономия фиксированного размера может показаться незначительной для типа данных переменного размера. В конце концов, в зависимости от кодировки строки она соответствует всего 8 символам. Однако система базы данных должна загружать строку только тогда, когда ей нужно с ней взаимодействовать. Для всех операторов, которые непосредственно не изменяют, не агрегируют и не сортируют строку, важно только ее представление.

Например, рассмотрим TPC-H запрос 21 и выходной столбец s_name. В зависимости от плана запроса 66% операторов, обрабатывающих имя поставщика s_name, материализуют его строковое представление без доступа к базовым строковым значениям. Для всех этих операторов, хранение только 16 байт вместо 24, напрямую сокращает пространство, необходимое для этого столбца, на 33%.

Оптимизации вызова функций

Менее очевидное, но немаловажное преимущество, которое мы получаем от небольших headers строк, заключается в том, что передавать строки в функции и из функций стало гораздо эффективнее. System V calling convention предписывает передавать большие структуры через стек. Однако значения до 16B будут передаваться через два регистра.

Поэтому оставаться в рамках магического лимита в 16B очень выгодно, так как это позволяет избежать дорогостоящего обхода стека при каждом вызове функции. Рассмотрим следующий небольшой пример, в котором мы передаем две строки в функцию compare():

#include <cstdint>
#include <string>
struct data128_t { uint64_t v[2]; };
void compare(data128_t, data128_t);
void compare(std::string, std::string);

void compareData128() {
    data128_t abc = {0x0300'0000'4142'4300, 0x0300'0000'0000'0000};
    data128_t def = {0x0300'0000'4445'4600, 0x0300'0000'0000'0000};
    compare(abc, def);
}
void compareStrings() {
    std::string abc = "abc";
    std::string def = "def";
    compare(move(abc), move(def));
}

И compareData128, и compareStrings выполняют вызов функции сравнения и оба сравнивают строки «abc» и «def». Однако compareData128 использует наше 16-байтовое представление, а compareStrings - представление std::string. Если вы быстро посмотрите на сгенерированный ассемблер в Compiler Explorer, то увидите разницу в коде для вызовов обеих функций. Наш формат строки, смоделированный здесь с помощью небольшой структуры, передается напрямую через регистры процессора, что приводит к выполнению всего 4 инструкций. Версия той же функции для std::string, напротив, требует 37 инструкций для вызова. Хотя частично это связано с non-destructive moves C++, все же разница в создании вызова функции значительна. А при том объеме данных, который ежедневно обрабатывает система баз данных, такие небольшие различия быстро увеличиваются!

Pointer Tagging

Много вопросов было связано с использованием pointer tagging, которые нам необходимо использовать, чтобы не выходить за рамки 16-байтового ограничения и получить преимущества, описанные выше. Хотя теги указателей никоим образом не являются специфическими для German Strings, мы хотим сделать небольшой экскурс, чтобы ответить на наиболее часто задаваемые вопросы.

Почему используются старшие биты для метки?

Указатели могут быть помечены либо в старших битах, то есть в битах, которые еще не используются, поскольку не существует машин с 128 Пбайт оперативной памяти, либо в младших битах. Преимущество использования меток в младших битах заключается в том, что эти биты не подвержены изменениям архитектуры, они используются уже сегодня. И в этом заключается проблема их использования для тегов. Чтобы иметь возможность помечать два младших бита, все данные должны быть выровнены по 4 байтам, так что эти два бита всегда гарантированно будут нулевыми. Хотя некоторые типы данных выровнены по словам, мы хотим хранить наши строки как можно компактнее и поэтому требуем побайтовой адресации наших указателей. Это исключает использование младших битов для маркировки.

Безопасен ли pointer tagging?

Зависит от ситуации. Хотя разыменование маркированного указателя невозможно на некоторых архитектурах, ни одна архитектура не использует все 64 бита адреса. На самом деле, даже последнее расширение x86-64 использует не более 57 бит, оставляя 7 бит для приложения, чтобы впихнуть в указатель больше информации. Однако некоторые архитектуры, включая x86-64, требуют, чтобы указатели были в канонической форме для всех операций с памятью. Поэтому перед разыменованием указателя мы должны убедиться, что все метки удалены. Поэтому в обозримом будущем можно смело использовать указатели, помеченные в старших битах, если только мы удалим метки перед использованием. Как при использовании меток в младших, так и в старших битах необходимо удалять метки перед выполнением операций с памятью.

Преимущества работы с короткими строками

Еще одно преимущество German Strings заключается в том, что мы можем работать с короткими строками, то есть с теми, длина которых не превышает 12 символов, непосредственно в регистрах процессора. Но даже это требует дополнительной осторожности. Например, давайте посмотрим на проверку равенства строк:

#include <cstdint>
#include <cstring>
struct data128_t { uint64_t v[2]; };

bool isEqual(data128_t a, data128_t b) {
    if (a.v[0] != b.v[0]) return false;
    auto len = (uint32_t) a.v[0];
    if (len <= 12) return a.v[1] == b.v[1];
    return memcmp((char*) a.v[1], (char*) b.v[1], len) == 0;
}

bool isEqualAlt(data128_t a, data128_t b) {
    auto aLen = (uint32_t) a.v[0];
    auto aPtr = aLen <= 12 ? (char*)&a.v + 4 : (char*)a.v[1]; 
    auto bLen = (uint32_t) b.v[0];
    auto bPtr = bLen <= 12 ? (char*)&b.v + 4 : (char*)b.v[1];
    return memcmp(aPtr, bPtr, aLen) == 0;
}

И isEqual, и isEqualAlt делают одно и то же. Однако в isEqual мы добавляем специальный путь, чтобы использовать преимущества нашего string layout. Для объединений и фильтров в системе баз данных подавляющее большинство сравнений обычно приводит к неравенству. Чтобы оптимизировать этот путь, мы сначала проверяем, что обе строки имеют одинаковую длину и префикс, что можно сделать с помощью простого сравнения регистра первых 8 байт нашего string layout. В большинстве случаев эта проверка будет неудачной, что позволит нам ответить на подавляющее большинство сравнений строк с помощью очень дешевой инструкции CMP.

Для строк, которые вписываются в наше короткое представление, мы можем добавить дополнительный путь оптимизации. Вместо того чтобы переносить указатели строк в стек и вызывать memcmp, мы можем выполнить сравнение, просто сравнив вторые 8 байт.

В сгенерированном коде в Compiler Explorer видно, что для выполнения одного и того же действия isEqualAlt должен выполнить несколько операций над стеком. Из одних только этих операций видно, что это явно намного дороже, чем перестановка регистров.

Комментарии в Telegram-группе!