Введение
Здравствуйте, это Сугавара Юта, автор предыдущей статьи Как я создал самый быстрый декодер JSON в Go. Если вы еще не читали предыдущую статью, надеюсь, вы сможете прочитать ее вместе со мной, потому что она поможет мне объяснить процесс.
После
После этого я получил вопрос от goccy, автор go-json сказал, что он провел собственный бенчмаркинг и обнаружил, что производительность не так хороша, как в README. Похоже, что goccy выполнил свой бенчмаркинг с относительно небольшими файлами JSON, поэтому я сделал это сам и обнаружил, что результаты были намного медленнее, чем я ожидал. Возможно, тот факт, что я тестировал только декодирование больших JSON-файлов, обернулся против меня, но разница все же была значительной. их вам.
сугаварайюта/сонет
Функции
- В отличие от прошлого раза, он проходит все тесты для стандартной библиотеки Go, «encoding/json».
- Добавлен энкодер для совместимости. Это также проходит все тесты.
- Скорость декодирования небольших структур теперь вдвое выше.
- Несколько методов (описанных ниже) значительно сократили использование памяти.
Ориентиры
Бенчмарки взяты из репозитория goccy.
Если кому интересно, рекомендую взять собственные бенчмарки
Выполнение
- Как создать карту, доступ к которой можно получить одновременно
Раньше я использовал «sync.Mutex», но если вы можете использовать «unsafe», «sync/atomic.XXXPointer» часто работает быстрее для чтения. (Причина, по которой я не могу сказать этого о записи, заключается в том, что, насколько мне известно, единственный способ сделать это — каждый раз создавать новую карту, копировать содержимое и затем вставлять указатель, если он не изменился. )
- Совершенные хэш-функции
Раньше я использовал метод хэширования Робин Гуда, но после того, как я закончил его создавать, я понял, что могу создать идеальную хеш-функцию, если пара ключ/значение была известна с самого начала и никакие изменения не могли произойти.
Поэтому я использовал хэш-функцию, которая берет начальное число (в данном случае hash/maphash.String и т. д.) и перемешивает начальное число до тех пор, пока при вставке не останется дубликатов, что представляет собой простой поиск O(1) время.
- Хеш-функция для идеальных хеш-функций
Сначала хэширование производилось написанным на ассемблере пакетом fast maphash, но бенчмарки показали, что прямое использование memhash или strhash, которые используются внутри, быстрее и избавляет от лишних операций, поэтому я переключился на них. В конце я перешел на ФНВ-1а, который встраивается и разворачивается вручную. Причина была в том, что ручное встраивание было проще, потому что оно считывало по одному символу за раз (я думал об этом, потому что узким местом хэш-функции был вызов функции, а не побитовая операция), и если все символы в ASCII, вы можно использовать таблицу поиска, которая изменяет все 256 символов на строчные. ) Если символы полностью состоят из ASCII, таблица поиска со всеми 256 символами, преобразованными в нижний регистр, может использоваться для одновременного нижнего регистра символов и создания хэша.
- Побитовые операции (SWAR)
SWAR — это тема, о которой я больше всего хотел поговорить на этой сессии. Официальное название — SIMD в регистре, что просто означает технологию, которая может обрабатывать несколько байтов одновременно, даже в средах, где SIMD недоступен. Как вы могли догадаться, услышав термин несколько байтов, его можно использовать для поиска символов. Если искомый символ находится в единственном числе, то, вероятно, лучше всего использовать bytes.IndexByte, который использует ассемблер за кулисами, но если нет, вы можете использовать это. Рабочий пример показан ниже.
package main
import (
"encoding/binary"
"fmt"
"math/bits"
)
const mapper uint64 = 0x0101010101010101
func main() {
u8s := []uint8("01234567")
// Use encoding/binary for simplicity
u64 := binary.LittleEndian.Uint64(u8s)
// XOR a uint64 with byte '5' mapped to all bytes.
// XOR outputs 0 if a match is found.
u64 ^= mapper * '5'
// Subtract uint64 where 1 is mapped to all bytes.
// overflows if the previous result is 0.
u64 -= mapper * 1
// AND uint64 with 0x80 mapped to every byte
// (scoop out the most significant bit of each uint8)
u64 &= mapper * 0x80
if u64 != 0 {
// If the output is not zero, it means it was found somewhere, so,
// divide by 8 to see how far the bits are 0.
fmt.Println("found at:", bits.TrailingZeros64(u64)/8)
return
}
fmt.Println("couldn't find the character")
}
В своем коде я использую небезопасно вместо кодирование/бинарность, но я делаю то же самое. Если вы хотите увидеть больше подобных фокусов, предлагаю посмотреть статью здесь
- Поэтапный бассейн
Хотя «sync.Pool» великолепен — параллельный доступ, быстрее, чем использование каналов и т. д. — он может быть неудобным, потому что у вас нет возможности узнать, какой объект вернется в следующий раз, когда вы «Get». (Например, «Мне нужен фрагмент размером 2048 байт».)
Чтобы решить эту проблему, я создал массив пулов и определил размер каждого из них. Чтобы определить, куда поместить их обратно в массив или откуда их взять, я делю на 1024 и вычисляю длину этого бита. Это позволяет мне создавать (и повторно использовать) слайсы, которые увеличиваются примерно в 2 раза практически без выделения памяти.
- Резка струн
Проблема, возникающая при повторном использовании фрагментов байтов, как указано выше, заключается в том, как разделить возвращаемое значение. Если вы приведете повторно используемый массив к строке, используя «unsafe», возвращаемое значение, содержимое, будет изменено, когда значение будет перезаписано позже. Чтобы решить эту проблему, мне приходилось каждый раз делать копию каждой строки, но поскольку выделение становилось слишком большим, если приходилось делать это для каждой строки, мне нужно было решение этой проблемы. Сначала нужно было создать массив примерно из 1024 строк, вырезать только то, что было необходимо, и объединить остаток для повторного использования.
