Готовлю Merkle-tree-based хэширование в signed-data
Во время написания (
4eed9f47294d277e84f8ba1451b1b4ced04a09de)
enveloped-data контейнера на основе KEKS, я задумался о
производительности скорости подписывания данных. chacha20-poly1305 у
меня выдаёт почти ГиБ/сек, а вот скорость подписывания больших данных
зависит от скорости хэша, где BLAKE2b всё равно будет медленнее ChaPoly.
Распараллелить ChaPoly, раз я бью на независимые блоки по 64КиБ, можно
без проблем. А вот хэш уже нет. Но кто ж помешает добавить опциональный
режим хэширования в виде деревьев Меркле? Я такое уже делал в NNCP, но
там это было нужно для возможности "дохэширования" данных, а
распараллеливание я не делал.
Пока все наработки в отдельной ветке, в master ещё не попали, но
2+ГиБ/сек я могу и на SHA2-512 достичь на своём компьютере. Но я не
один день бился над тем, чтобы попытаться утилизировать все процессоры.
Видимо, мне не хватает базовых знаний по структурам/алгоритмам. Задачи я
раздаю через каналы заранее запущенным горутинам считающие хэш.
Результаты собираю из другого канала. Делая чтение из stdin в буфер, а
дальше его запись в io.Pipe+io.ReadFull, у меня не однократное
копирование присутствует. Если размер блока Меркле дерева 128КиБ, то я
легко достигаю 2+ГиБ/сек пропускной способности. Если же 8КиБ, как
изначально хотел, то с трудом поднимаюсь выше 1.1. На данный момент я
дошёл профилированием и оптимизациями до того, что я по сути упираюсь в
производительность каналов Go. А точнее в частые использования mutex.
Пробовал использовать попадающиеся под руку lock-free реализации каналов
пригодных для моей задачи -- 10-20% прироста есть, но не более. Добавил
возможность хэшировать из mmap-нутого файла, избавляясь от чтений из
stdin и записей в hash.Hash -- это тоже дало только ~10%
производительности. Я в итоге не мог утилизировать все ядра процессора
для BLAKE2b. Коллега предложил решение в виде круговых буферов с
lock-free взаимодействием с ним, но это прям сильно неканонично с точки
зрения Go будет, который гласит "Don't communicate by sharing memory;
share memory by communicating".
Как освобожусь от более насущных задач, то снова вернусь к задаче.
Возможно уже ничего не будут менять, ибо 2-2.5ГиБ/сек
хэширования/подписи + шифрование (которое тоже надо распараллелить) на
остающихся свободных ядрах на моём компьютере это тоже очень не плохо.
Стрибога, очень не быстрой реализации без ассемблерных вставок, это
позволит очень хорошо распараллелить. Но ещё и на Си это же всё стоит
реализовать параллельно.