Все мы знаем эту историю, когда нужно скопировать какую-нибудь большую структуру, внутри которой множество указателей на другие структуры. Руками это делать лень, поэтому берём какую-нибудь библиотеку и быстро делаем копию. А потом в свободное время решаем проверить, что там с оверхедом.
Меня зовут Егор Гартман, я работаю в бекэнде Авито и я решил протестировать несколько библиотек Deep Copy. А потом сделал свою — быстрее и эффективнее.
![](https://habrastorage.org/getpro/habr/upload_files/bb9/fdd/039/bb9fdd0394bc274c365749f825602a7b.png)
Сравнение готовых решений
Для сравнения я выбрал три библиотеки глубокого копирования и два способа копирования через маршалинг:
json marshal > unmarshal,
msgpack marshal -> unmarshal.
Критерии отбора были простейшие:
звёзды на Github — максимум у Mohae,
первая строка выдачи Google — Barkimedes,
комбайн для копирования, который посоветовали в рабочем чате — Jinzu.
Все бенчмарки я запускал на своем MacBook Pro 2019 на Core i5. Я использовал простейшую структуру из пяти полей:
type benchSimpleStruct5 struct {
I1 int
F1 float64
S1 string
B1 byte
C1 bool
}
Результат получился не отличный, но и не плохой. Практически все испытуемые работают на несколько порядков медленнее прямого копирования:
![В третьей строке находится комбайн, который предназначен для копирования из Map в структуры и обратно, из структур одного типа в структуры другого типа. Из-за этого он работает медленно. Дальше я его не тестировал В третьей строке находится комбайн, который предназначен для копирования из Map в структуры и обратно, из структур одного типа в структуры другого типа. Из-за этого он работает медленно. Дальше я его не тестировал](https://habrastorage.org/getpro/habr/upload_files/b85/ed7/c00/b85ed7c0090e79b921a0ff62a7d25296.png)
После я начал менять разные параметры в структуре и измерять оверхед. Во всех графиках ниже на оси Y указан оверхед в секундах, на X — изменяемый параметр.
Проверил, что будет, если увеличить количество полей. Лучше всего с плоскими структурами из большого числа полей справляется mohae:
![](https://habrastorage.org/getpro/habr/upload_files/aa6/3fb/f7e/aa63fbf7e65f8dad8e3609f90c731713.png)
Затем стал наращивать уровень вложенности структур. Результат получился такой же — с вложенными структурами лучше справляются библиотеки, а не маршалинг:
![](https://habrastorage.org/getpro/habr/upload_files/658/ffe/965/658ffe965d8e8e19adc16b4fcec8dfec.png)
Затем проверил, как на оверхед влияет объем данных. Начал с примитивных — обычный массив byte[]
: Здесь лучше всего справляются msgpack — работает почти мгновенно даже на большом объёме данных:
![](https://habrastorage.org/getpro/habr/upload_files/a7b/f89/ed4/a7bf89ed455fb020f6a6d0f34ed8a7f1.png)
И второе измерение оверхеда по объёму данных, только на массиве структур по три поля в каждой. Со структурами ожидаемо лучше справляются библиотеки Deep Copy:
![](https://habrastorage.org/getpro/habr/upload_files/51c/dc6/3f7/51cdc63f7b4cd0c103813f447f0c83f4.png)
Ещё я тестировал кейс, близкий к реальному при работе с нашей инфомоделью: копировать нетипизированный набор полей, завёрнутый в мапу. Первым был пустой интерфейс map[string]any
:
map [string] any {
"int": 1,
"float": 2. ,
"string": "3",
"bytes" make([]byte, 128),
"structs": []*simpleStruct{
{1, 2., "3"},
{1, 2., "3"},
{1, 2., "3"},
},
"nested": map[string]any{
"int": 1,
"float": 2. ,
},
}
Для такой Map быстрее всего работает маршалинг: msgpack и чуть хуже json. А вот библиотека самая медленная, еще и аллокаций в ней дикое количество:
![](https://habrastorage.org/getpro/habr/upload_files/ac1/b44/56d/ac1b4456daa4f16745d4b4d68c1219b3.png)
Второй пример, приближённый к реальности — сложная структура. Это и есть то, ради чего я использовал библиотеки Deep Copy и из-за чего начал их сравнивать.
type complexStructForBench struct {
Int int
Float64 float64
String string
Struct simpleStructBenchmark
Interface barer
PointerToInt *int
PointerToFloat64 *float64
PointerToString *string
PointerToStruct *simpleStructBenchmark
ArrayOfInt [10]int
ArrayOfSimpleStruct [5]simpleStructBenchmark
SliceOfInt []int
SliceOfSimpleStruct []simpleStructBenchmark
SliceOfPtrsToInt []*int
SliceOfStructPtrs []*simpleStructBenchmark
}
Здесь msgpack не дал никакого результата, потому что сломалась сериализация интерфейса. Хороший результат по времени показала библиотека, а по оверхеду и аллокациям лучшим стал json.
![](https://habrastorage.org/getpro/habr/upload_files/ab1/42a/64d/ab142a64d3473e70aa32ba0e36f7c978.png)
После всех измерений я пришёл к общему выводу: для эффективного копирования важно знать, что именно копируешь. Немного банально, но это действительно так.
Сложность копирования будет O{N}, то есть растёт линейно для всех параметров — по времени, памяти, аллокациям. Причём не важно, что именно наращивать при измерении: количество полей или вложенность структур.
Но не всё так хорошо. На каждый int тратится 8 байт дополнительной памяти, а если спрятать его в структуру — то целых 16 байт. Ещё и время копирования по сравнению с прямым растёт на 2 порядка — даже для лучшего по скорости кандидата. Мне хотелось более эффективного копирования.
Сравнение стратегий глубокого копирования
Задачка «сделать эффективную Deep Copy» оказалась не такой уж простой. Напомню, что в Go их 26 типов (про kind of type в предлагаю почитать в документации). Я их разделил на 5 видов по стратегии копирования:
примитивные,
указатели,
коллекции (Map, слайсы, массивы),
структуры,
всё остальное.
Теперь подробнее, как копировать каждый из видов.
Примитивные. Это различные логические, числовые и строковые типы: bool, int, float, complex, string. Их можно копировать как есть.
package main
import (
"fmt"
"unsafe"
)
func main() {
var str = "some string"
bptr := unsafe. StringData(str)
*bptr = 'b' // panic: SIGSEGV: segmentation violation
fmt.Println(str)
}
Такая строка не является примитивным типом, но её всё равно можно копировать как есть, потому что она всегда read only.
Указатели. Сам по себе указатель скопировать очень легко: создаём копию переменной и затем новый указатель на эту копию. Сложнее, если указатель — это часть структуры.
type Foo struct {
iptr1 *int
iptr2 *int
}
var (
i = int(10)
foo = Foo{&i, &i}
)
var (
sliceOfIntPtrs = []*int{&i, &i, &i}
arrayOfIntPtrs = [...]*int{&i, &i, &i}
mapIntToPtr = map[int]*int{1:&i, 2:&i}
)
Допустим, что указатели в структуре Foo ссылаются на одну и ту же переменную. Логично, что копия должна сохранять это свойство. Есть кейсы, когда это важно: например, кольцевые ссылки. Контроль ссылок решает проблему с их копированием, это важный и приятный бонус.
К сожалению, не все библиотеки Deep Copy поддерживают такое копирование. Многие сваливаются в panic, если встречают объект с кольцевой ссылкой.
Коллекции. Здесь особых сложностей нет. Чтобы скопировать Map, нам нужна копия пар «ключ-значение», и новая Map для копии. Для массива так же: копируем элементы и записываем их в новый массив.
Небольшая сложность возникает только при копировании массивов со слайсами, которые могут ссылаться на одну область памяти.
type strct struct{
Arr [10]int
S1 []int
S2 []int
}
var(
arr = [...]int{1,2,3,4,5,6,7,8,10}
s1 := arr[:3]
s2 := arr[5:]
copyMeIfYouCan := strct{
arr, s1, s2
}
)
Важно, чтобы копия поддерживала это свойство. Если есть слайсы, которые ссылаются на массив, то при изменении элементов в массиве, они должны меняться и в слайсах.
Простой Map со ссылками тут не обойтись, потому что слайс ссылается не на underline array, а на первый элемент. Я не смог придумать способ копирования таких массивов, который бы не тянул за собой большой оверхед. Если есть идеи — поделитесь в комментариях.
Структуры. Если все поля в структуре экспортируемые, то их можно просто скопировать по очереди. Для неэкспортируемых полей я протестировал три стратегии: deep copy, shallow copy или просто не копировать их. Выбор стратегии я оставил за пользователем, потому что нужная стратегия зависит от его задачи.
Первая и очевидная стратегия — сделать deep copy всей структуры целиком. В этом случае может возникнуть проблема — одна структура тянет за собой много других. На частном примере структуры Time:
type Time struct {
wall uint64
ext int64
loc *Location
}
type Location struct {
name string
zone []zone
tx []zoneTrans
extend string
cacheStart int64
cacheEnd int64
cacheZone *zone
}
В Time есть указатель на другую структуру — Location. А в ней лежат все переходы на зимнее или летнее время, отмены зимнего и переход на постоянное летнее время, изменения часовых поясов и так далее.
Если делать deep copy структуры Time, то придется копировать и всё, что лежит в Location. Это очень долго — время копирования вырастает в сотню раз.
![](https://habrastorage.org/getpro/habr/upload_files/3e0/eed/326/3e0eed3267195a9d40f2c38ba8964f95.png)
Вторая стратегия — выполнить поверхностную копию (shallow copy). Для структуры Time этот способ подойдёт, но в других случаях может не сработать.
Третья стратегия — не копировать структуру библиотекой. Тоже вариант для некоторых случаев.
Остальные типы. Сюда я отнёс интерфейсы, функции, каналы и unsafePointer. Для интерфейсов копируем underlying value, а функции и каналы не трогаем. unsafePointer копируем как есть, раз уж автор кода решил добавить его в структуру. Пусть сам с ним и разбирается.
Я тут рассказал совсем немного про сложности в deep copy. Если хотите погрузиться — советую почитать на Github issue с предложением включить Deep Copy в стандартную библиотеку.
После того, как я разобрался с копированием разных типов, осталось оптимизировать библиотеку Deep Copy.
Моя экспериментальная библиотека Kamino
Свою библиотеку я оптимизировал так, чтобы при глубоком копировании она давала минимальный оверхед. При этом постарался практически не использовать методы unsafe и добавил Generics для простоты использования библиотеки.
В первую очередь я оптимизировал копирование структур. Для этого нужно было сократить количество аллокаций. В лучшей библиотеке с Github их восемь, а я хотел оставить одну.
![](https://habrastorage.org/getpro/habr/upload_files/96e/c1e/6f5/96ec1e6f54a5b260d9181fba0357853f.png)
Какие из них нужные, а какие можно убрать? Одна аллокация выделяется на reflect.Value
оригинала, еще одна — для объекта, который будет собственно копией.
По аллокации выделяется на каждое поле original.Type().Field(i
) для сравнения переменной PkgPath
с пустой строкой. Эта строка кода проверяет, можно ли экспортировать поле.
В структуре Field
есть массив Index, в котором лежит собственно индекс. Этот массив нужен для доступа к вложенным полям методом FieldByIndex
. Он позволяет добраться до любого значения в структурах любой вложенности по массиву последовательных индексов.
![](https://habrastorage.org/getpro/habr/upload_files/3c4/fe5/eff/3c4fe5eff01624dc946c30c1a6059479.png)
Причина, почему эта аллокация вообще есть — вызов метода FieldByIndex
. Создатель библиотеки даже оставил в коде комментарий о том, что это единственное решение, которое удалось найти.
Ещё одна, на мой взгляд, странная аллокация — это cpy.Interface()
, которая нужна для преобразования reflect.Value
в интерфейс. В ней под капотом происходит повторное копирование содержимого интерфейса, причём сами авторы оставили комментарий, что делать этого не нужно.
![](https://habrastorage.org/getpro/habr/upload_files/5e5/ca7/cf0/5e5ca7cf0cd95a8e51fa48bed3d7798b.png)
Убрать эту аллокацию просто. Нужно использовать метод CanSet() для original. Он проверяет экспортируемость и адресуемость поля. Если этот метод вызывается от оригинала, то он возвращает false. Это справедливо для всех случаев, когда в переменной original — не указатель, то есть, она не адресуемая.
![](https://habrastorage.org/getpro/habr/upload_files/515/571/c83/515571c8305edec6d278278484467dac.png)
Дальше я решил убрать оставшиеся аллокации. Для этого пришлось вспомнить основы: передача аргумента в функцию, по сути, и есть копирование. То есть, нужно получить адресуемое значение из переданного аргумента.
В нашем случае это будет reflect.Value
из копии, в которой мы будем рекурсивно копировать данные при необходимости. Тогда мы получим всего одну аллокацию. Но оказалось, что получить адресуемое reflect.Value не так просто. Я попробовал три метода и корректно работает только последний из них.
-
Просто передать
reflect.ValueOf
нельзя — это неадресуемый параметр, и с этим ничего нельзя сделать.func copy(x any) any { value := reflect.ValueOf(x) copyNessesaryInplace(value) return x }
-
Метод
reflect.NewAt()
под капотом выполняет анбоксинг: разбирает интерфейс any на reflect.Value и указатель на данные. Чтобы получить этот указатель, приходится использовать unsafe, а мне этого не хотелось.func copy(x any) any { //не тот поинтер value := reflect.NewAt(reflect.TypeOf(x), unsafe.Pointer(&x)) copyNessesaryInplace(value) return x }
-
Рабочий способ — использовать указатель на аргумент
reflect.ValueOf()
func copy(x any) any { value := reflect.ValueOf(&x).Elem() copyNessesaryInplace(value) return x }
На этом я закончил оптимизацию структур и перешёл к массивам. Здесь всё очень просто: библиотека аллоцирует память на весь массив и копирует сразу все данные, а затем выполняет Deep Copy, если это необходимо.
![](https://habrastorage.org/getpro/habr/upload_files/6a9/9d0/281/6a99d0281322ce3d6aeb985898c174df.png)
Оптимизация Map тоже достаточно простая. Для копирования Map создаю новый Map сразу нужного для копии размера. Для этого есть метод reflect.MakeMapWithSize()
. Также, чтобы не плодить лишние аллокации, сразу инициализирую пару key-value и уже ими прохожу по новой Map.
![](https://habrastorage.org/getpro/habr/upload_files/ed2/649/995/ed26499958786960c4aadeff43852b53.png)
Для примитивных типов добавил проверки, потому что их можно копировать без Deep Copy и не тратить на них ресурсы.
Сравнение Kamino и других решений для глубокого копирования
Для тестирования я использовал те же бенчмарки: простая структура с разными параметрами, интерфейс Map и сложная структура.
На плоских структурах Kamino даёт неплохой результат по оверхеду в зависимости от количества полей:
![](https://habrastorage.org/getpro/habr/upload_files/ad1/184/13f/ad118413f0586723e9c0e18192bc123f.png)
Оверхед в зависимости от вложенности почти такой же, как у другой библиотеки, но всё-таки чуть лучше:
![](https://habrastorage.org/getpro/habr/upload_files/9aa/90a/c0f/9aa90ac0ffc7b360ffc86c6c79d24f0a.png)
Оверхед по массиву byte[]
, результат почти как у предыдущего чемпиона MsgPack:
![](https://habrastorage.org/getpro/habr/upload_files/341/dec/abe/341decabeb69052f858587b6af4cbf32.png)
И оверхед для массива структур []struct
тоже довольно неплохой:
![](https://habrastorage.org/getpro/habr/upload_files/8e7/fdb/3b0/8e7fdb3b0e75ef92545638fda0aaecfa.png)
На более приближённых к реальности примерах результаты получились очень хорошие. Результат для интерфейса map[string]any
: по времени и количеству аллокаций Kamino лучше:
![](https://habrastorage.org/getpro/habr/upload_files/9c7/9de/ff8/9c79deff8d79c633bdcfc613d52be98a.png)
Для сложной структуры результат более показательный. По времени Kamino обогнал самую быструю библиотеку, а по числу аллокаций победил всех:
![](https://habrastorage.org/getpro/habr/upload_files/73a/3ea/f99/73a3eaf9950ef830e86150a50b796365.png)
Библиотека Kamino пока на стадии тестирования, в будущем я буду её дорабатывать и улучшать. Буду рад вашим вопросам и комментариям здесь или на Github.
Предыдущая статья: Как реализовать ролевую систему доступа через Open Policy Agent. Опыт PaaS Авито
bat
Норм. Спасибо, что поделились.
В начале подумал что это для DTO и все порешает кодогенерация, пока не дочитал до интерфейсов и сабслайсов ))
А нельзя сделать интрефейс, реализацией которого тип берет на себя ответственность копирование всякого странного?
lastpossum Автор
Да, хорошая идея, вполне разумно отдать пользователю управление копированием всякого странного.