Сравниваем скорость и оверхеды библиотек Deep Copy для Go

Все мы знаем эту историю, когда нужно скопировать какую-нибудь большую структуру, внутри которой множество указателей на другие структуры. Руками это делать лень, поэтому берём какую-нибудь библиотеку и быстро делаем копию. А потом в свободное время решаем проверить, что там с оверхедом.

Меня зовут Егор Гартман, я работаю в бекэнде Авито и я решил протестировать несколько библиотек Deep Copy. А потом сделал свою — быстрее и эффективнее.

Сравнение готовых решений

Для сравнения я выбрал три библиотеки глубокого копирования и два способа копирования через маршалинг:

• github.com/mohae/deepcopy,

• github.com/barkimedes/go-deepcopy,

• github.com/jinzhu/copier,

• 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
}

Результат получился не отличный, но и не плохой. Практически все испытуемые работают на несколько порядков медленнее прямого копирования:

После я начал менять разные параметры в структуре и измерять оверхед. Во всех графиках ниже на оси Y указан оверхед в секундах, на X — изменяемый параметр. 

Проверил, что будет, если увеличить количество полей. Лучше всего с плоскими структурами из большого числа полей справляется mohae:

Затем стал наращивать уровень вложенности структур. Результат получился такой же — с вложенными структурами лучше справляются библиотеки, а не маршалинг:

Затем проверил, как на оверхед влияет объем данных. Начал с примитивных — обычный массив byte[]: Здесь лучше всего справляются msgpack — работает почти мгновенно даже на большом объёме данных:

И второе измерение оверхеда по объёму данных, только на массиве структур по три поля в каждой. Со структурами ожидаемо лучше справляются библиотеки Deep Copy:

Ещё я тестировал кейс, близкий к реальному при работе с нашей инфомоделью: копировать нетипизированный набор полей, завёрнутый в мапу. Первым был пустой интерфейс 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. А вот библиотека самая медленная, еще и аллокаций в ней дикое количество:

Второй пример, приближённый к реальности — сложная структура. Это и есть то, ради чего я использовал библиотеки 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.

После всех измерений я пришёл к общему выводу: для эффективного копирования важно знать, что именно копируешь. Немного банально, но это действительно так. 

Сложность копирования будет 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. Это очень долго — время копирования вырастает в сотню раз.

Вторая стратегия — выполнить поверхностную копию (shallow copy). Для структуры Time этот способ подойдёт, но в других случаях может не сработать. 

Третья стратегия — не копировать структуру библиотекой. Тоже вариант для некоторых случаев.

Остальные типы. Сюда я отнёс интерфейсы, функции, каналы и unsafePointer. Для интерфейсов копируем underlying value, а функции и каналы не трогаем. unsafePointer копируем как есть, раз уж автор кода решил добавить его в структуру. Пусть сам с ним и разбирается.

Я тут рассказал совсем немного про сложности в deep copy. Если хотите погрузиться — советую почитать на Github issue с предложением включить Deep Copy в стандартную библиотеку.

После того, как я разобрался с копированием разных типов, осталось оптимизировать библиотеку Deep Copy. 

Моя экспериментальная библиотека Kamino

Свою библиотеку я оптимизировал так, чтобы при глубоком копировании она давала минимальный оверхед. При этом постарался практически не использовать методы unsafe и добавил Generics для простоты использования библиотеки.

В первую очередь я оптимизировал копирование структур. Для этого нужно было сократить количество аллокаций. В лучшей библиотеке с Github их восемь, а я хотел оставить одну.

Какие из них нужные, а какие можно убрать? Одна аллокация выделяется на reflect.Value оригинала, еще одна — для объекта, который будет собственно копией. 

По аллокации выделяется на каждое поле original.Type().Field(i) для сравнения переменной PkgPath с пустой строкой. Эта строка кода проверяет, можно ли экспортировать поле.

В структуре Field есть массив Index, в котором лежит собственно индекс. Этот массив нужен для доступа к вложенным полям методом FieldByIndex. Он позволяет добраться до любого значения в структурах любой вложенности по массиву последовательных индексов.

Причина, почему эта аллокация вообще есть — вызов метода FieldByIndex.  Создатель библиотеки даже оставил в коде комментарий о том, что это единственное решение, которое удалось найти. 

Ещё одна, на мой взгляд, странная аллокация — это cpy.Interface(), которая нужна для преобразования reflect.Value в интерфейс. В ней под капотом происходит повторное копирование содержимого интерфейса, причём сами авторы оставили комментарий, что делать этого не нужно.

Убрать эту аллокацию просто. Нужно использовать метод CanSet() для original. Он проверяет экспортируемость и адресуемость поля. Если этот метод вызывается от оригинала, то он возвращает false. Это справедливо для всех случаев, когда в переменной original — не указатель, то есть, она не адресуемая.

Дальше я решил убрать оставшиеся аллокации. Для этого пришлось вспомнить основы: передача аргумента в функцию, по сути, и есть копирование. То есть, нужно получить адресуемое значение из переданного аргумента.

В нашем случае это будет reflect.Value из копии, в которой мы будем рекурсивно копировать данные при необходимости. Тогда мы получим всего одну аллокацию. Но оказалось, что получить адресуемое reflect.Value не так просто. Я попробовал три метода и корректно работает только последний из них. 

1. Просто передать reflect.ValueOf нельзя — это неадресуемый параметр, и с этим ничего нельзя сделать. 

   func copy(x any) any {
     value := reflect.ValueOf(x)
   
     copyNessesaryInplace(value)
   
     return x
   }

2. Метод reflect.NewAt() под капотом выполняет анбоксинг: разбирает интерфейс any на reflect.Value и указатель на данные. Чтобы получить этот указатель, приходится использовать unsafe, а мне этого не хотелось. 

   func copy(x any) any {
       //не тот поинтер
       value := reflect.NewAt(reflect.TypeOf(x), unsafe.Pointer(&x))
   
       copyNessesaryInplace(value)
   
       return x
   }

3. Рабочий способ — использовать указатель на аргумент reflect.ValueOf()

   func copy(x any) any {
     value := reflect.ValueOf(&x).Elem()
   
     copyNessesaryInplace(value)
   
     return x
   }

На этом я закончил оптимизацию структур и перешёл к массивам. Здесь всё очень просто: библиотека аллоцирует память на весь массив и копирует сразу все данные, а затем выполняет Deep Copy, если это необходимо.

Оптимизация Map тоже достаточно простая. Для копирования Map создаю новый Map сразу нужного для копии размера. Для этого есть метод reflect.MakeMapWithSize(). Также, чтобы не плодить лишние аллокации, сразу инициализирую пару key-value и уже ими прохожу по новой Map. 

Для примитивных типов добавил проверки, потому что их можно копировать без Deep Copy и не тратить на них ресурсы. 

Сравнение Kamino и других решений для глубокого копирования

Для тестирования я использовал те же бенчмарки: простая структура с разными параметрами, интерфейс Map и сложная структура. 

На плоских структурах Kamino даёт неплохой результат по оверхеду в зависимости от количества полей:

Оверхед в зависимости от вложенности почти такой же, как у другой библиотеки, но всё-таки чуть лучше:

Оверхед по массиву byte[], результат почти как у предыдущего чемпиона MsgPack:

И оверхед для массива структур []struct тоже довольно неплохой:

На более приближённых к реальности примерах результаты получились очень хорошие. Результат для интерфейса map[string]any : по времени и количеству аллокаций Kamino лучше:

Для сложной структуры результат более показательный. По времени Kamino обогнал самую быструю библиотеку, а по числу аллокаций победил всех:

Библиотека Kamino пока на стадии тестирования, в будущем я буду её дорабатывать и улучшать. Буду рад вашим вопросам и комментариям здесь или на Github.

Предыдущая статья: Как реализовать ролевую систему доступа через Open Policy Agent. Опыт PaaS Авито