В 1986 Полторак стал нам физико-химические основы неорганической химии, и в разделе "Термометрия" сказал дословно следующее:
Измерение температуры построено на двух предположениях, первое из которых произвольно, а второе заведомо ошибочно. Первое - выбор реперных точек. Второе - утверждение, что шкала между ними линейна.
В реальности размер ключа не фиксированный, но, казалось бы, для хэш-таблицы это влияет только на её физический размер, и ограничений там быть не должно.
Типичный размер словаря ключей немного поработавшей перимущественно русскояычной полнотекстовой машины - за миллион (~60,000 русской общей лексики из активного запаса, два по столько орфографических ошибок, формально годящихся в русские слова, остальное - числа и иероглифы вроде rs232).
Тут под соседей заметкой меня практически спросили, зачем нужен другой полнотекстовый поиск, если есть Apache Lucene. Не дословно, конечно, но это подразумевалось.
Да, вы совершенно правы: если нужна оценка размера некоторой массивной и кучерявой структуры данных, то GetBufLen проделывает весь путь Serialize, а время на её исполнение пропорционально времени Serialize с коэффициентом, равным отношению времени операции суммирования ко времени операции записи в конкретный коллектор.
С другой стороны, такая оценка нужна ровно в двух случаях: либо если вы собираетесь сделать дамп в памяти и хотите понять, сколько её надо резервировать, либо если вам надо строить внутренние таблицы релокации внутри такого дампа.
Эта была сделана в своё время для построения дампов словарных данных, по которым можно эффективно искать, не десериализуя.Где активно и используется (libmorph).
Так всё-таки к разработке каких известных полнотекстовых поисковых движков вы имели отношение? Или хотя бы к эксплуатации?
---
Пардон, заглянул - там Apache Lucerne, разработка двадцатилетней давности, довольно громоздкая и с низким качеством поиска (отношение правильно найденных к общему количеству найденных), на сегодня - прошлый век.
Видимо, проделана большая работа над тем, чтобы оно таки шевелилось.
1 и 2 справедливы для обоих подходов - и для упомянутой вами хэш-таблицы,и для сериализованного базисного дерева.
Однако у хэш-таблиц есть очевидный недостаток: построить по ней итератор, перебирающий ключи в порядке возрастания (убывания) сложно и дорого. А в прикладных задачах полнотекстового поиска этот итератор важен и нужен.
Хэш-таблица, демонстрирующая o(1), будет к тому же, вероятно, очень разреженной, а значит, "жирной" по размеру.
А про скорость поговорим в следующей заметке, добавим хэш-таблицу в сравнение производительности.
Нет. Это не так. Если передать по ссылке, то, например, для сериализации в память надо будет писать специальную обёртку, а не использовать простой char* - указатель, а вместо возврата nullptr в случае ошибки придётся бросаться exception'ами.
Для записи числа, которое можно представить 2 байтами (0 - 65535) нужен 1 байт, если число меньше 128, 2 байта, если число меньше 16384 и три байта в остальных случаях. В моих задачах это даёт экономию размера примерно 7%, а для uint32_t и того больше. Впрочем, писать таким способом или иным - вопрос выбора.
Сравнивать же с flatbuffers или с protobuf некорректно - это совсем разный функционал. Этот код, конечно же, быстрее, чем flatbuffers/protobuf, компактнее, если не использовать компрессию (zlib) и не имеет и половины того функционала, что есть в названных библиотеках.
Повторюсь, это инструмент сериализации данных в виде, позволяющем работать с ними без явной десериализации, то есть гарантировать, например, отсутствие операций резервирования памяти при эксплуатации такого словаря.
В следующей статье я покажу работу сериализованного базисного дерева, небольшое (~10%) замедление при работе по сравнению с его развёрнутой формой при снижении требований к памяти более чем на порядок.
Проверка LE/BE в данном случае не нужна, так как целочисленные значения сериализуются последовательно семибитными порциями со сдвигом вправо на 7 бит после каждого записанного байта:
они лезут в настройки pthread, после чего любой ВАШ поток при старте хапнет 70 метров памяти вместо 4 (после вызова инициализации gRPC);
сборка проекта будет увлекательным квестом, так как надо будет регулярно переделывать порядок линковки с бесконечными мелкими библиотеками Google;
у вас в проекте появится второй STL - библиотека absl, дублирующая std;
при эксплуатации вы обнаружите функцию GPR_malloc, потому посмотрите ней в глаза до того, как решите использовать это индийское чудо;
ну и изюминка под конец - асинхронные серверы gRPC на C++ при нагрузках в несколько сотен RPS через пять-десять минут перестают обрабатывать запросы, потому что прекращает работать CompletionQueue; как с этим бороться, мы не знаем, как воспроизвести на примере из самого gRPC - знаем точно.
В 1986 Полторак стал нам физико-химические основы неорганической химии, и в разделе "Термометрия" сказал дословно следующее:
Измерение температуры построено на двух предположениях, первое из которых произвольно, а второе заведомо ошибочно. Первое - выбор реперных точек. Второе - утверждение, что шкала между ними линейна.
Да, разумно.
В реальности размер ключа не фиксированный, но, казалось бы, для хэш-таблицы это влияет только на её физический размер, и ограничений там быть не должно.
Типичный размер словаря ключей немного поработавшей перимущественно русскояычной полнотекстовой машины - за миллион (~60,000 русской общей лексики из активного запаса, два по столько орфографических ошибок, формально годящихся в русские слова, остальное - числа и иероглифы вроде rs232).
Да ладно...
Тут под соседей заметкой меня практически спросили, зачем нужен другой полнотекстовый поиск, если есть Apache Lucene. Не дословно, конечно, но это подразумевалось.
Да, вы совершенно правы: если нужна оценка размера некоторой массивной и кучерявой структуры данных, то GetBufLen проделывает весь путь Serialize, а время на её исполнение пропорционально времени Serialize с коэффициентом, равным отношению времени операции суммирования ко времени операции записи в конкретный коллектор.
С другой стороны, такая оценка нужна ровно в двух случаях: либо если вы собираетесь сделать дамп в памяти и хотите понять, сколько её надо резервировать, либо если вам надо строить внутренние таблицы релокации внутри такого дампа.
Размер ключа у полнотекстовой поисковой машины невелик: от 3-4 до 20-25 байт. В зависимости от того, словарная это лексема или неизвестная.
А как вы хотите на hash-таблице сделать итератор по ключам? Например, для реализации поиска с усечением - сло*?
Выложил для того, чтобы было на что ссылаться при выкладке библиотеки полнотекстового поиска.
Эта была сделана в своё время для построения дампов словарных данных, по которым можно эффективно искать, не десериализуя.Где активно и используется (libmorph).
Непременно прочту.
Так всё-таки к разработке каких известных полнотекстовых поисковых движков вы имели отношение? Или хотя бы к эксплуатации?
---
Пардон, заглянул - там Apache Lucerne, разработка двадцатилетней давности, довольно громоздкая и с низким качеством поиска (отношение правильно найденных к общему количеству найденных), на сегодня - прошлый век.
Видимо, проделана большая работа над тем, чтобы оно таки шевелилось.
Терешке, думаю, тяжело пришлось обосновывать TCO.
Ну так какой из больших или хотя бы малых полнотекстовых движков вы сделали? Или хотя бы поучаствовали, хотя бы в качестве сеньора?
Из больших - Апорт!, Рамблер от 2000 года и дальше, украинскую Мету.
Эти три спроектировал, в значительной мере написал, последние два потом развивал и эксплуатировал.
И несколько поменьше.
А вы?
"Любимые БД" сильно просаживает производительность поисковых движков.
Требуют много памяти и медленно работают.
А я веду именно туда.
1 и 2 справедливы для обоих подходов - и для упомянутой вами хэш-таблицы,и для сериализованного базисного дерева.
Однако у хэш-таблиц есть очевидный недостаток: построить по ней итератор, перебирающий ключи в порядке возрастания (убывания) сложно и дорого. А в прикладных задачах полнотекстового поиска этот итератор важен и нужен.
Хэш-таблица, демонстрирующая o(1), будет к тому же, вероятно, очень разреженной, а значит, "жирной" по размеру.
А про скорость поговорим в следующей заметке, добавим хэш-таблицу в сравнение производительности.
Нет. Это не так. Если передать по ссылке, то, например, для сериализации в память надо будет писать специальную обёртку, а не использовать простой char* - указатель, а вместо возврата nullptr в случае ошибки придётся бросаться exception'ами.
В данном случае замечание про владение очень не к месту.
Требовать здесь unique_ или shared_ptr - это примерно как возвращать из vector<>::data() или string::c_str() вместо указателя - std::*_ptr(), право!
::Serialize никоим образом и ни в один момент времени не является владельцем объекта по указателю.
А что не так с "сырыми" указателями?
Для записи числа, которое можно представить 2 байтами (0 - 65535) нужен 1 байт, если число меньше 128, 2 байта, если число меньше 16384 и три байта в остальных случаях. В моих задачах это даёт экономию размера примерно 7%, а для uint32_t и того больше. Впрочем, писать таким способом или иным - вопрос выбора.
Изначально это делалось для словарей, так что данные, созданные на одной платформе, должны верно читаться и на обратном порядке следования байт (см. словари libmorph). Порции для записи берутся арифметическими операциями (см. код https://github.com/big-keva/mtc/blob/557336ee9bfe935c4a7afe31a2a06ee8fa9ab189/serialize.h#L227).
Сравнивать же с flatbuffers или с protobuf некорректно - это совсем разный функционал. Этот код, конечно же, быстрее, чем flatbuffers/protobuf, компактнее, если не использовать компрессию (zlib) и не имеет и половины того функционала, что есть в названных библиотеках.
Повторюсь, это инструмент сериализации данных в виде, позволяющем работать с ними без явной десериализации, то есть гарантировать, например, отсутствие операций резервирования памяти при эксплуатации такого словаря.
В следующей статье я покажу работу сериализованного базисного дерева, небольшое (~10%) замедление при работе по сравнению с его развёрнутой формой при снижении требований к памяти более чем на порядок.
Ну да, похожий подход.
Я этот текст написал как материал, на который можно ссылаться в следующих статьях.
Сейчас пишу "Работу с сериализованными данными без десериализации". То есть вообще без резервирования памяти.
Проверка LE/BE в данном случае не нужна, так как целочисленные значения сериализуются последовательно семибитными порциями со сдвигом вправо на 7 бит после каждого записанного байта:
- записываем-байт-как-младшие-семь-бит-и-старший-бит-если-есть-биты-старше
- сдвигаем-сериализуемое-значение-на-семь-бит-вправо
- если-не-ноль-повторяем-цикл
Это позволяет в большинстве случаев записывать компактнее. И это избавляет от проблем с записью на одной, а чтением на другой платформе.
Как сказано выше, для ряда классов из std:: сделаны специализации сериализатора, а для собственных классов следует прописывать функцию-член Serialize.
Согласен, примеров использования стоило бы добавить.
Согласен. Благодарю за дельное замечание.
Мытищи.
Из опыта работы с gRPC на C++:
они лезут в настройки pthread, после чего любой ВАШ поток при старте хапнет 70 метров памяти вместо 4 (после вызова инициализации gRPC);
сборка проекта будет увлекательным квестом, так как надо будет регулярно переделывать порядок линковки с бесконечными мелкими библиотеками Google;
у вас в проекте появится второй STL - библиотека absl, дублирующая std;
при эксплуатации вы обнаружите функцию GPR_malloc, потому посмотрите ней в глаза до того, как решите использовать это индийское чудо;
ну и изюминка под конец - асинхронные серверы gRPC на C++ при нагрузках в несколько сотен RPS через пять-десять минут перестают обрабатывать запросы, потому что прекращает работать CompletionQueue; как с этим бороться, мы не знаем, как воспроизвести на примере из самого gRPC - знаем точно.