Комментарии 16
Очень круто. Спасибо.
- for _, x := range xs { // Copies 2048 bytes
+ for _, x := range &xs { // No copyНе совсем ясно, что имелось в виду, потому что данный код не компилируется:
./prog.go:9:14: cannot range over &xs (type *[]byte)Update: А, ясно, это применимо только для массивов, а не для срезов.
Правда, я всё ещё не понимаю, каким образом изменение типа избавит нас от копирования. Ведь копирование элемента массива происходит потому, что используется форма range с двумя переменными, и элементы массива копируются во вторую переменную. Изменения типа на ссылку на массив никак не меняет тип второй переменной, соответственно никак не отменяет копирование в неё всех элементов массива.
Там копирование не элемента, а массива. Это для многих неожиданное поведение, поэтому и привел пример такой инспекции. Иногда в циклах поиска по короткому словарю (иногда это массив, а не слайс), делается лишнее копирование, в итоге вместо оптимизации получаем деградацию.
Явно в спеке нигде это не указывается, по-моему, но это можно вывести из того, что аргументы цикла "присваиваются" как обычные переменные. А массивы копируются при присваивании. Вот пример, где всё было бы очевидно:
var arr [10]int
_iter := arr // Вот тут весь массив копируется
for i := 0; i < len(_iter); i++ {
el := _iter[i]
}Итого у вас будет 2N копий. Сначала весь массив во временную переменную, а потом ещё N для каждой итерации. Проверьте лично или гляньте -S вывод компилятора, если нужны доказательства.
Если же там указатель, вы присвоите в _iter указатель, скопируя 8 байтов, что не страшно. Go умеет делать range по указателю на массив, поэтому всё будет работать без последствий.
А зачем вообще range нужно копировать исходный массив?
Ну т.е. речь о том, что компилятор копирует аргумент range в отдельную переменную, хотя в этом нет никакой необходимости. И чинить это в компиляторе никто не планирует (и чтобы не усложнять его, и потому что range по большим массивам это не такая уж частая ситуация), поэтому предлагается "оптимизировать" это вручную разработчикам.
И чинить это в компиляторе никто не планирует (и чтобы не усложнять его, и потому что range по большим массивам это не такая уж частая ситуация), поэтому предлагается "оптимизировать" это вручную разработчикам.
В общем, вы правы, но тут "чинить" не очень корректное слово. Это не баг, а поведение по спеке. Плюс, как вы уже тоже отметили, это редкий кейс, но если он появляется в программе, есть шанс, что это была ошибка программиста, а фикс очень простой...
Если "починить", сломается код, который ожидает, что массив копируется. Эти программы корректные по спецификации языка.
Если копию не делать, конкуррентные программы могут измениться. Можно, конечно, делать анализ, не доступен ли массив для такого доступа, но чаще всего массивы для оптимизаций — глобальны, а Go слабовато пока такое оптимизирует и анализирует. И не факт, что когда-либо gc (компилятор от Google) будет такое делать, потому что есть требование держать время компиляции под контролем, а флаги -O они не хотят.
Это не баг, а поведение по спеке. … Если "починить", сломается код, который ожидает, что массив копируется. Эти программы корректные по спецификации языка.
Я не вижу в спеке информации о том, что for/range копирует свой аргумент. Можете процитировать, где это сказано?
В целом, если программа запускает горутину до for, то она и так уже некорректная, т.к. никто не гарантирует что выполнится раньше — код в горутине или копирование массива в range. А если программа запускает горутину внутри for… ну, да, она вполне может сломаться. Но, будем откровенны, не факт, что в мире сейчас в принципе есть программы, которые делают range по массиву и запускают горутину внутри for которая рассчитывает, что for не увидит вносимые горутиной изменения в этот массив. А вот программы, производительность которых немного улучшится от этого изменения — скорее всего есть, и их немало. В общем, если спека явно это поведение не декларирует, то я не вижу смысла его сохранять. Оно, мягко говоря, неочевидное, и скорее вредное, нежели полезное.
Я не вижу в спеке информации о том, что for/range копирует свой аргумент. Можете процитировать, где это сказано?
В спеке явно не написано, но вот из этого выводится:
The range expression x is evaluated once before beginning the loop, with one exception: if at most one iteration variable is present and len(x) is constant, the range expression is not evaluated.
Если x — это массив, то его "evaluation" в контексте выражений — это копирование.
А вот почему нет копирования, когда используется только 1 range value, это отдельно описано:
If at most one iteration variable is present, the range loop produces iteration values from 0 up to len(a)-1 and does not index into the array or slice itself.
Прочитайте внимательно For statements with range clause, взял оттуда.
И чинить это в компиляторе никто не планирует (и чтобы не усложнять его, и потому что range по большим массивам это не такая уж частая ситуация), поэтому предлагается "оптимизировать" это вручную разработчикам.
А вот программы, производительность которых немного улучшится от этого изменения — скорее всего есть, и их немало.
Вы сами предположили, что это редкий кейс. Я могу это подтвердить, он реально редкий и проверял я на Go корпусе при тестировании go-critic, где эта диагностика есть. Имхо, это такой редкий зверь, что даже нашего диалога не стоит.
Я не буду говорить, хорошо это или плохо, что в gc компиляторе неохотно делают оптимизации, которые:
a) срабатывают очень редко и легко правятся в коде (явно, в 1 символ)
b) когда цикл работает 1 раз в каком-нибудь init, то разницы нет, есть эта оптимизация или нет
Такая вот политика. Она может нравиться или не нравиться, нам об этом спорить толку мало.
Насколько мне известно, там ещё 1 нюанс есть: если массив маленький, по копии пройти может быть быстрее, потому что тогда у нас будет a[i] для доступа к элементу, который на каждой итерации генерируется для range value. А если это указатель, то будет (*a)[i] (массив — это указатель на данные под капотом, а указатель на массив будет указателем на указатель). Мне больше нравится подход, где мы говорим программисту: "здесь может быть что-то подозрительное, разберись, пожалуйста" (как это делает go-critic).
Если x — это массив, то его "evaluation" в контексте выражений — это копирование.
Эмм… Это довольно сомнительное трактование. Например, выражение a[1] при "evaluation" обходится без копирования массива a. Равно как и len(a). (Наверняка есть и другие примеры, эти два просто сходу в голову пришли.) В общем, я допускаю, что Вы можете быть правы, а вышеупомянутые примеры оговорены в спеке как частные случаи (аналогично упомянутому Вами примеру с range), но это как минимум не очевидно.
(Про то, как трактовать тот параграф в спеке можно порассуждать, но ценность не очень высокая. Я на 100% не могу утверждать, но это та интерпретация, которую я видел в нескольких обсуждениях.)
Если отбросить спеку в сторону, так как не понятно, как её правильно читать, то a[i] имеет семантику, как в C. У нас массив — это просто указатель и длина только на этапе компиляции хранится. Чтобы взять элемент, копирования не нужно.
А в случае цикла иногда копия лучше, посмотрите мой update, пожалуйста:
Насколько мне известно, там ещё 1 нюанс есть: если массив маленький, по копии пройти может быть быстрее, потому что тогда у нас будет a[i] для доступа к элементу, который на каждой итерации генерируется для range value. А если это указатель, то будет (*a)[i] (массив — это указатель на данные под капотом, а указатель на массив будет указателем на указатель).
Там банально не так очевидно, стоит ли всегда оптимизировать.
При этом x должен быть addressable, чтобы от него можно было взять адрес. Если там вызов функции, то уже не прокатит.
Я вот попробовал такой пример:
package main
import "fmt"
func main() {
var xs [2048]byte
for _, x := range xs {
printb(x)
}
}
//go:noinline
func printb(b byte) {
fmt.Println(b)
}
И в дизассемблированном варианте я копирования не вижу
Есть только выделение массива на стеке, его обнуление и цикл по самому массиву — не по копии.
"".main STEXT size=122 args=0x0 locals=0x818
0x0000 00000 (main.go:5) TEXT "".main(SB), ABIInternal, $2072-0
0x0000 00000 (main.go:5) MOVQ (TLS), CX
0x0009 00009 (main.go:5) LEAQ -1944(SP), AX
0x0011 00017 (main.go:5) CMPQ AX, 16(CX)
0x0015 00021 (main.go:5) JLS 115
0x0017 00023 (main.go:5) SUBQ $2072, SP
0x001e 00030 (main.go:5) MOVQ BP, 2064(SP)
0x0026 00038 (main.go:5) LEAQ 2064(SP), BP
0x002e 00046 (main.go:5) FUNCDATA $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
0x002e 00046 (main.go:5) FUNCDATA $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
0x002e 00046 (main.go:5) FUNCDATA $2, gclocals·39825eea4be6e41a70480a53a624f97b(SB)
0x002e 00046 (main.go:7) PCDATA $0, $1
0x002e 00046 (main.go:7) PCDATA $1, $0
// set 2048 bytes to zero
0x002e 00046 (main.go:7) LEAQ ""..autotmp_2+16(SP), DI
0x0033 00051 (main.go:7) MOVL $256, CX
0x0038 00056 (main.go:7) XORL AX, AX
0x003a 00058 (main.go:7) PCDATA $0, $0
0x003a 00058 (main.go:7) REP
0x003b 00059 (main.go:7) STOSQ
0x003d 00061 (main.go:7) XORL AX, AX
0x003f 00063 (main.go:7) JMP 91
// start print loop
0x0041 00065 (main.go:7) MOVQ AX, ""..autotmp_6+8(SP)
0x0046 00070 (main.go:7) MOVBLZX ""..autotmp_2+16(SP)(AX*1), CX
0x004b 00075 (main.go:8) MOVB CL, (SP)
0x004e 00078 (main.go:8) CALL "".printb(SB)
0x0053 00083 (main.go:7) MOVQ ""..autotmp_6+8(SP), AX
0x0058 00088 (main.go:7) INCQ AX
0x005b 00091 (main.go:7) CMPQ AX, $2048
0x0061 00097 (main.go:7) JLT 65
// end print loop
0x0063 00099 (<unknown line number>) MOVQ 2064(SP), BP
0x006b 00107 (<unknown line number>) ADDQ $2072, SP
0x0072 00114 (<unknown line number>) RET
0x0073 00115 (<unknown line number>) NOP
0x0073 00115 (main.go:5) PCDATA $1, $-1
0x0073 00115 (main.go:5) PCDATA $0, $-1
0x0073 00115 (main.go:5) CALL runtime.morestack_noctxt(SB)
0x0078 00120 (main.go:5) JMP 0
Попробуйте эти 2 функции и сравните их асм: https://play.golang.org/p/u4jQsQAKdHe
Для удобства, вот он: https://gist.github.com/quasilyte/99aa5bbff0906b38cdcd9525c25b11d4
Обратить внимание на то, что в первой функции есть DUFFCOPY.
Проверял на 1.13 и на go-tip.
В новых версиях компилятора, возможно, ввели оптимизацию при каком-то размере массива, надо посмотреть. Моя информация примерно годичной давности, но до ~1000 байтах копирование всё ещё есть.
Лучше в код компилятора посмотреть, конечно. Скорее всего, ответ стоит искать в cmd/compile/internal/gc. Если вдруг разберётесь, можете здесь написать ответ, думаю, многим полезно будет (в том числе мне).
Сам пример с arrayExprCopy был примером того, что можно детектировать через правила и что правится 1-им символом. Альтернативный фикс — делать слайс от массива, чтобы цикл шёл уже по слайсу.
Я всё-таки полез в исходники.
Вот несколько подсказок, куда сначала стоит посмотреть:
- range.go подсказывает, что в order.go может подготавливаться копия.
- order.go создаёт копию. Причём по-моему всегда.
А дальше нужно понять, кто эту лишнюю копию удаляет: при каких условиях, точно ли удаляет, а не заменяет на что-то хитрое (я там видел вызовы DUFFCOPY на размер меньший массива при некоторых N, не сразу понятно, что это). Это может быть как в том же фронтенде (gc), либо в ssa.
Из комментария "array ranges use value multiple times. make copy." как будто бы следует, что эта копия им нужна, чтобы сгенерировать код, который обращается к этой "переменной" (на уровне кодогенерации) для взятия n-го элемента внутри цикла. То есть:
for i, v := range arr { <range body> }
Превращается во что-то типа:
{
tmp := arr // Вот здесь по семантике Go копирование массива
tmp_i := 0
for tmp_i < len(tmp_arr) {
i, v = tmp_i, tmp_arr[tmp_i]
<range body>
}
}
(Я слегка упростил.)
ha уже может быть копией после order.go.
Гипотетически, этой копии можно избежать, если мы можем доказать, что ha не изменяется. Это сложно, если ha — глобальная переменная. Для локальных массивов, наверное, и сейчас кто-то успешно копию удаляет.
Ещё кто-то натолкнулся на эту особенность:
https://utcc.utoronto.ca/~cks/space/blog/programming/GoRangeCopying
https://utcc.utoronto.ca/~cks/space/blog/programming/GoForRangeNudging
ruleguard: динамические проверки для Go