Сравнение значений в Golang
Практическая статья с примерами бенчмарков и советами по оптимизации
Автор — Владимир Балун
ex-TeamLead в Яндекс
Откроется после 4-ой главы
В языке программирования Go операции сравнения на первый взгляд выглядят банально: сравнили строки, объекты структур данных или другие значения — получили результат. Но у этих операций есть ряд важных особенностей, которые могут существенно влиять на производительность программ. Особенно это становится заметно в высоконагруженных системах, при работе с большими объемами данных и в горячих участках кода.
В этой статье разберём, как именно Go сравнивает строки и структуры данных, почему порядок полей в структурах данных имеет значение, а также как интернирование может радикально ускорить сравнения.
В этой статье разберём, как именно Go сравнивает строки и структуры данных, почему порядок полей в структурах данных имеет значение, а также как интернирование может радикально ускорить сравнения.
Сравнение строк в Go
Строка в Go — это неизменяемая (immutable) структура данных, которая концептуально состоит из указателя на массив байт и длины строки
При сравнении двух строк Golang действует по следующему алгоритму:
- Сравниваются указатели и длина строк
- Если и указатели, и длина совпадают, строки считаются равными
- Если указатель или длина отличаются, Go переходит к побайтовому лексикографическому сравнению массивов байт
Приведу в пример два сценария:
Сценарий №1:
- создается большой срез (более 1 MB);
- из него создаются две строки путём копирования;
- эти две строки указывают на разные участки памяти.
func BenchmarkComparison(b *testing.B) {
bs := make([]byte, 1<<26)
s0 := string(bs)
s1 := string(bs)
b.ResetTimer()
for i := 0; i < b.N; i++ {
_ = s0 == s1
}
}Сценарий №2:
- создается тот же самый срез;
- первая строка создается копированием;
- вторая строка создаётся таким образом, чтобы обе строки указывали на один и тот же массив байт
func BenchmarkComparisonOptimized(b *testing.B) {
bs := make([]byte, 1<<26)
s0 := string(bs)
s1 := s0
b.ResetTimer()
for i := 0; i < b.N; i++ {
_ = s0 == s1
}
}При сравнении строк во втором сценарии Go завершает операцию после сравнения указателей и длины. В первом же случае требуется полное побайтовое сравнение строк, что на больших строках даёт ощутимую разницу в производительности.
Запускаем бенчмарк и видим различия:
Запускаем бенчмарк и видим различия:
BenchmarkComparison-8 | 406 | 3421149 ns/op
BenchmarkComparisonOprimized-8 | 1000000000 | 0.3315 ns/op
BenchmarkComparisonOprimized-8 | 1000000000 | 0.3315 ns/op
Происходит так потому, что первоначально мы сравниваем указатели и размер строки. Если указатели и размер строки равны, не имеет смысла идти побайтово сравнивать строки. Но если либо размер, либо указатель отличается, нам придётся идти побайтово сравнивать строки лексикографически.
Почему одного лишь указателя недостаточно для сравнения строк?
Потому что из строки можно получить другую подстроку. Поэтому помимо сравнения указателей, необходимо проверять и размер строки. Если указатели и размер равны, то и строки будут равны, потому что они в Go неизменяемые.
Сравнение структур данных и порядок полей
Теперь перейдём к структурам данных. На практике при описании структур данных разработчики чаще всего думают о выравнивании, читаемости кода или логической группировке полей. Однако редко задумываются о том, как эти структуры данных могут часто сравниваться в программе.
В Go объекты структур данных сравниваются поле за полем, в порядке их объявления
Рассмотрим пример: две абсолютно одинаковые структуры, которые отличаются только порядком описания полей.
type Data1 struct {
size int32
values [10 << 20]byte
}
type Data2 struct {
values [10 << 20]byte
size int32
}В примере используется структура данных с большим массивом (около 10 MB) и дополнительным числовым полем.
Если у этих структур данных отличные числовые поля и числовое поле находится в начале структуры, Go сможет завершить сравнение быстрее при несовпадении этого поля.
Если же оно находится в конце, Go сначала сравнит большой массив, который может быть идентичен, и только затем перейдет к сравнению числового поля.
Далее описаны два бенчмарка, которые отличаются только числовым полем
func BenchmarkComparisonData1(b *testing.B) {
data1 := Data1{size: 100}
data2 := Data1{size: 101}
for i := 0; i < b.N; i++ {
_ = data1 == data2
}
}
run benchmark | debug benchmark
func BenchmarkComparisonData2(b *testing.B) {
data1 := Data2{size: 100}
data2 := Data2{size: 101}
for i := 0; i < b.N; i++ {
_ = data1 == data2
}
}Запускаем бенчмарк и смотрим на разницу:
BenchmarkComparisonData1-8 | 495707469 | 2.367 ns/op
BenchmarkComparisonData2-8 | 2233 | 538687 ns/op
BenchmarkComparisonData2-8 | 2233 | 538687 ns/op
При запуске бенчмарков становится очевидно:
- структуры данных с «дешёвыми» полями в начале сравниваются заметно быстрее
- разница особенно заметна на больших структурах данных
Конечно, этот пример специально подобран, чтобы разница была наглядной. Но вывод остается справедливым:
