1. Мы тут недавно выложили fuzztest. В целом если вы используете GTest, то вы можете написать что-то вроде
И всё, у вас автоматически вместе с тестами фаззинг вашего API. То есть можно не только писать юнит тесты, но и тестировать свойства вашего API в том же файле.
После этого хоть и требуется настройка как гонять это на continuous basis, но если вы действительно паритесь насчёт тестирования ваших программ на C++, то вы добавите continuous testing на это. А локально можете выбрать, сколько вы хотите потестировать ваше API.
К сожалению, только на Bazel, но я решил портировать на CMake:
https://github.com/danlark1/fuzztest_cmake. Welcome
2. Тут zstd рассматривает одну интересную семантическую оптимизацию: нахождение оптимательного количества бит для дерева Хаффмана.
https://github.com/facebook/zstd/pull/3302
В Zstd сжатие хаффмана используется, когда сжимаются литеральные строки -- то есть данные, которые нужно скопировать как есть.
Чтобы лучше понять контекст, Zstd использует два метода сжатия -- Huffman и FSE: первый очень стандартный, когда мы символам присваиваем префиксный код, а второй исправляет недочёты Huffman: например, если какой-то символ встречается 90% раз, то теория информации говорит, что мы можем кодировать это log2(1/0.9)=0.15 битами, когда как дерево Хаффмана присваивает минимум 1. Чтобы достичь лимита придумали FSE, пока в детали углубляться не стоит, но суть в том, чтобы менять биты ответственные за символы по ходу декодирования.
Huffman быстрее, FSE медленнее из-за нестатической таблицы. FSE хорошо работает, когда данных побольше, Huffman на маленьких данных не видит большой разницы с FSE.
Zstd делит данные на две категории -- Literals и Sequences -- первое -- обычные данные, которые стоит копировать (можете для простоты думать, что это словарь), а Sequences -- команды, откуда копировать, нужно ли копировать из уже раскодированных данных. Решение о том, чтобы кодировать литералы Huffman интересное, их не очень много по сравнению с командами о копировании.
Чтобы подобрать оптимальное дерево Хаффмана мы все знаем алгоритм -- взять два самых невстречающихся, соединить, суммировать их вероятности, удалить старые.
К сожалению, чтобы записать информацию о дереве Хаффмана, нужно тоже место:
1. Для весов
2. Для самого алфавита литералов
В итоге это баланс между Huffman header и compression estimation. Чем меньше веса, тем легче их сжать, поэтому выбирается эвристика, сколько максимум бит в высоту можно заиспользовать дереву Хаффмана. Спецификация не разрешает больше, чем 11 бит -- оно скорее логично, алфавиты до 255, высоты 10 должно хватить для литералов часто. Также из интересного спецификация не хранит веса, а хранит какой высоты должен быть символ.
Эти "высоты" сами сжимаются FSE кодированием, потому что высоты чаще повторяются: 255 значений, там скорее всего много значений высоты 5, 6, 7 и тд хорошо сжимаются.
Чтобы найти этот оптимальный баланс, ничего не придумаешь, кроме как перебрать высоты: если у вас данные из алфавита A, то будете перебирать от log2(|A|) до 11: не совсем понятно как уменьшение высоты (более встречающиеся символы начинают иметь более длинные коды) влияет на суммарное сжатие (бОльшие веса сложнее кодировать), эта функция не унимодальная.
Тем не менее, большинство из них унимодальны. Такую эвристику и решают выбрать -- взять какую-то точку и попытаться пойти в обе стороны пока уменьшается результат суммарного сжатия на блоке сжатых данных.
В итоге на 200MB при стандартном блоке выигрывается около 3КБ, когда блок поменьше (то есть FSE не очень сильно помогает сжимать), то разница уже в 360KB. Маленькие блоки встречаются в сжатии со словарем, когда очень много мелких данных приходит -- сообщения, посты, и тд.
Перф не просаживается на больших блоках, на маленьких 15%. Интересный PR, посмотрим, вольют или нет. Или другую эвристическу придумать можно.
void MyApiAlwaysSucceedsOnPositiveIntegers(int i) {
bool success = MyApi(i);
EXPECT_TRUE(success);
}
FUZZ_TEST(MyApiTest, MyApiAlwaysSucceedsOnPositiveIntegers)
.WithDomains(/*i:*/fuzztest::Positive<int>());
И всё, у вас автоматически вместе с тестами фаззинг вашего API. То есть можно не только писать юнит тесты, но и тестировать свойства вашего API в том же файле.
После этого хоть и требуется настройка как гонять это на continuous basis, но если вы действительно паритесь насчёт тестирования ваших программ на C++, то вы добавите continuous testing на это. А локально можете выбрать, сколько вы хотите потестировать ваше API.
К сожалению, только на Bazel, но я решил портировать на CMake:
https://github.com/danlark1/fuzztest_cmake. Welcome
2. Тут zstd рассматривает одну интересную семантическую оптимизацию: нахождение оптимательного количества бит для дерева Хаффмана.
https://github.com/facebook/zstd/pull/3302
В Zstd сжатие хаффмана используется, когда сжимаются литеральные строки -- то есть данные, которые нужно скопировать как есть.
Чтобы лучше понять контекст, Zstd использует два метода сжатия -- Huffman и FSE: первый очень стандартный, когда мы символам присваиваем префиксный код, а второй исправляет недочёты Huffman: например, если какой-то символ встречается 90% раз, то теория информации говорит, что мы можем кодировать это log2(1/0.9)=0.15 битами, когда как дерево Хаффмана присваивает минимум 1. Чтобы достичь лимита придумали FSE, пока в детали углубляться не стоит, но суть в том, чтобы менять биты ответственные за символы по ходу декодирования.
Huffman быстрее, FSE медленнее из-за нестатической таблицы. FSE хорошо работает, когда данных побольше, Huffman на маленьких данных не видит большой разницы с FSE.
Zstd делит данные на две категории -- Literals и Sequences -- первое -- обычные данные, которые стоит копировать (можете для простоты думать, что это словарь), а Sequences -- команды, откуда копировать, нужно ли копировать из уже раскодированных данных. Решение о том, чтобы кодировать литералы Huffman интересное, их не очень много по сравнению с командами о копировании.
Чтобы подобрать оптимальное дерево Хаффмана мы все знаем алгоритм -- взять два самых невстречающихся, соединить, суммировать их вероятности, удалить старые.
К сожалению, чтобы записать информацию о дереве Хаффмана, нужно тоже место:
1. Для весов
2. Для самого алфавита литералов
В итоге это баланс между Huffman header и compression estimation. Чем меньше веса, тем легче их сжать, поэтому выбирается эвристика, сколько максимум бит в высоту можно заиспользовать дереву Хаффмана. Спецификация не разрешает больше, чем 11 бит -- оно скорее логично, алфавиты до 255, высоты 10 должно хватить для литералов часто. Также из интересного спецификация не хранит веса, а хранит какой высоты должен быть символ.
Эти "высоты" сами сжимаются FSE кодированием, потому что высоты чаще повторяются: 255 значений, там скорее всего много значений высоты 5, 6, 7 и тд хорошо сжимаются.
Чтобы найти этот оптимальный баланс, ничего не придумаешь, кроме как перебрать высоты: если у вас данные из алфавита A, то будете перебирать от log2(|A|) до 11: не совсем понятно как уменьшение высоты (более встречающиеся символы начинают иметь более длинные коды) влияет на суммарное сжатие (бОльшие веса сложнее кодировать), эта функция не унимодальная.
Тем не менее, большинство из них унимодальны. Такую эвристику и решают выбрать -- взять какую-то точку и попытаться пойти в обе стороны пока уменьшается результат суммарного сжатия на блоке сжатых данных.
В итоге на 200MB при стандартном блоке выигрывается около 3КБ, когда блок поменьше (то есть FSE не очень сильно помогает сжимать), то разница уже в 360KB. Маленькие блоки встречаются в сжатии со словарем, когда очень много мелких данных приходит -- сообщения, посты, и тд.
Перф не просаживается на больших блоках, на маленьких 15%. Интересный PR, посмотрим, вольют или нет. Или другую эвристическу придумать можно.