Ускоряем hugo на 20% простым изменением в пакете reflect +24


Найти значительное узкое место в производительности стандартной библиотеки или зрелого приложения — это редкость.


Я был удивлён, когда в top10 списке CPU-профиля hugo при сборке digitalgov.gov на первой позиции находился метод reflect.Type.MethodByName().


      flat  flat%   sum%        cum   cum%
     8.84s  6.28%  6.28%     57.85s 41.10%  reflect.(*rtype).MethodByName
     7.93s  5.63% 11.92%      8.50s  6.04%  reflect.name.readVarint
     7.56s  5.37% 17.29%    111.79s 79.43%  reflect.Value.call
     7.53s  5.35% 22.64%     23.33s 16.58%  runtime.mallocgc
     7.29s  5.18% 27.82%     16.10s 11.44%  reflect.name.name

В этой статье я расскажу вам о том, как так вышло и что с этим можно было бы сделать.


Почему MethodByName такой медленный


Давайте откроем исходники MethodByName:


func (t *rtype) MethodByName(name string) (m Method, ok bool) {
    // <лишний код вырезан>

    // TODO(mdempsky): Binary search.
    for i, p := range ut.exportedMethods() {
        if t.nameOff(p.name).name() == name {
            return t.Method(i), true
        }
    }
    return Method{}, false
}

MethodByName использует линейный поиск. Если экспортируемых методов у типа много, то работать это может очень долго, особенно если искомый метод будет находиться где-то в конце слайса.


Как можно ускорить MethodByName


Вариант первый: не использовать MethodByName. Или кешировать результат. Но будем считать, что мы не можем этого сделать.


func (t *rtype) MethodByName(name string) (m Method, ok bool) {
    // <лишний код вырезан>

    if len(methods) > 8 {
        i := sort.Search(len(methods), func(i int) bool {
            return t.nameOff(methods[i].name).name() >= name
        })
        if i < len(methods) && t.nameOff(methods[i].name).name() == name {
            return t.Method(i), true
        }
    } else {
        for i, p := range methods {
            if t.nameOff(p.name).name() == name {
                return t.Method(i), true
            }
        }
    }
    return Method{}, false
}

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


Если мы напишем бенчмарки, то получим примерно такие цифры:


name                           old time/op  new time/op  delta
MethodByName/4_first-8          426ns ± 2%   423ns ± 1%     ~   
MethodByName/4_last-8           482ns ± 1%   476ns ± 1%   -1.33%
MethodByName/4_nonexisting-8   57.8ns ± 0%  57.3ns ± 1%   -0.78%
MethodByName/16_first-8         427ns ± 1%   538ns ± 0%  +25.97%
MethodByName/16_last-8          643ns ± 1%   519ns ± 1%  -19.24%
MethodByName/16_nonexisting-8   194ns ± 0%   105ns ± 0%  -46.03%
MethodByName/32_first-8         429ns ± 1%   552ns ± 1%  +28.78%
MethodByName/32_last-8          831ns ± 0%   540ns ± 2%  -34.97%
MethodByName/32_nonexisting-8   396ns ± 1%   125ns ± 1%  -68.56%
MethodByName/64_first-8         431ns ± 1%   580ns ± 2%  +34.64%
MethodByName/64_last-8         1.36µs ± 1%  0.56µs ± 1%  -58.95%
MethodByName/64_nonexisting-8   759ns ± 0%   146ns ± 1%  -80.82%
[Geo mean]                      430ns        303ns       -29.58%

Как и ожидалось, новый метод работает хуже для случаев, когда искомый метод находится в начале слайса. Если учесть, что это вырожденный случаи и в среднем метод будет находиться где-то в середине, то выигрыш довольно очевиден.


Проверяем влияние на hugo


Изначально, указанный выше сайт собирался за 20.4 секунды.


Соберём hugo с обновлённым пакетом reflect и запустим сборку сайта ещё раз.


Невероятно, сборка сайта теперь занимает 16.5 секунд!


А что же там с профилем?


(pprof) top 20
Showing nodes accounting for 50.85s, 44.61% of 114s total
Dropped 1174 nodes (cum <= 0.57s)
Showing top 20 nodes out of 194
      flat  flat%   sum%        cum   cum%
     8.64s  7.58%  7.58%     25.01s 21.94%  runtime.mallocgc
     7.69s  6.75% 14.32%     87.02s 76.33%  reflect.Value.call
     4.17s  3.66% 17.98%      5.39s  4.73%  runtime.heapBitsSetType
     2.88s  2.53% 20.51%         4s  3.51%  runtime.findObject
     2.83s  2.48% 22.99%      2.83s  2.48%  runtime.nextFreeFast (inline)
     2.79s  2.45% 25.44%      9.46s  8.30%  runtime.scanobject
     2.74s  2.40% 27.84%      2.74s  2.40%  runtime.duffcopy
     1.82s  1.60% 29.44%      1.88s  1.65%  runtime.pageIndexOf
     1.76s  1.54% 30.98%      1.76s  1.54%  runtime.memclrNoHeapPointers
     1.69s  1.48% 32.46%      3.24s  2.84%  runtime.mapaccess2
     1.66s  1.46% 33.92%      1.83s  1.61%  syscall.Syscall
     1.49s  1.31% 35.23%      1.61s  1.41%  reflect.name.readVarint
     1.43s  1.25% 36.48%      3.07s  2.69%  reflect.name.name
     1.42s  1.25% 37.73%     10.54s  9.25%  reflect.FuncOf
     1.37s  1.20% 38.93%      1.75s  1.54%  github.com/gohugoio/hugo/...
     1.34s  1.18% 40.11%      4.99s  4.38%  sync.(*Map).Load
     1.33s  1.17% 41.27%      1.33s  1.17%  reflect.(*rtype).Kind
     1.29s  1.13% 42.40%      1.29s  1.13%  cmpbody
     1.28s  1.12% 43.53%      1.28s  1.12%  runtime.resolveNameOff
     1.23s  1.08% 44.61%      1.30s  1.14%  runtime.heapBitsForAddr

MethodByName, который был на 1-ой позиции, теперь не входит даже в top20.


Но нам стоит копнуть глубже, чтобы делать какие-либо выводы. Давайте посчитаем сколько там было вызовов MethodByName и каково распределение размеров слайсов exportedMethods и позиций, на которых метод был найден.


Общее количество вызовов за сборку сайта: 17042238.


15920637 times | 120 methods
493669 times | 29 methods
227736 times | 16 methods
180098 times | 8 methods
143846 times | 39 methods
31371 times | 6 methods
14636 times | 1 methods
10933 times | 31 methods
10094 times | 9 methods
9026 times | 4 methods
102 times | 113 methods
85 times | 7 methods
4 times | 114 methods
1 times | 0 methods

Большая часть вызовов была над типом, у которого 120 экспортируемых методов.


12998952 times | 98 index pos
1203864 times | 70 index pos
515978 times | 102 index pos
354191 times | 110 index pos
262965 times | 6 index pos
200819 times | 11 index pos
178457 times | 19 index pos
170806 times | 97 index pos
147510 times | 74 index pos
136927 times | 3 index pos
123071 times | 20 index pos
106250 times | 9 index pos
87190 times | 7 index pos
62767 times | 31 index pos
62192 times | 5 index pos
50170 times | 51 index pos
49120 times | 69 index pos
45325 times | 72 index pos
42236 times | 115 index pos
38646 times | 0 index pos
37106 times | 28 index pos
22744 times | 108 index pos
21521 times | 14 index pos
18134 times | 92 index pos
17341 times | 4 index pos
11535 times | 103 index pos
10791 times | 63 index pos
10303 times | 2 index pos
9170 times | 10 index pos
7278 times | 68 index pos
5936 times | 15 index pos
5466 times | 65 index pos
5385 times | 16 index pos
5172 times | 47 index pos
4478 times | 43 index pos
3032 times | 40 index pos
2340 times | 17 index pos
2265 times | 25 index pos
1516 times | 44 index pos
1068 times | 88 index pos
843 times | 1 index pos
709 times | 71 index pos
358 times | 109 index pos
100 times | 67 index pos
50 times | 64 index pos
40 times | 42 index pos
33 times | 34 index pos
17 times | 86 index pos
15 times | 83 index pos
15 times | 41 index pos
15 times | 33 index pos
12 times | 118 index pos
5 times | 8 index pos
5 times | 27 index pos
4 times | 66 index pos

Распределение индексов искомых методов тоже подсказывает, что линейный поиск в данном случае — не лучший выбор. Большая часть методов находилась на позиции 98.


Подводные камни


В коде выше я использовал sort.Search, но он не доступен для пакета reflect.


Дело в том, что пакет sort импортирует reflect, поэтому мы получаем ошибку циклических импортов.


Чтобы этого избежать, можно продублировать реализацию sort.Search в пакете reflect или создать новый internal пакет для Go, где будет некоторое подмножество пакета sort, не зависящее от reflect.


Этот фактор немного затрудняет внедрение предлагаемого патча, ведь самый красивый вариант реализации нам недоступен.


Как воспроизвести результаты, собрать профили


$ git clone https://github.com/GSA/digitalgov.gov.git
$ cd digitalgov.gov
$ hugo --profile-cpu cpu.out

Далее используем go tool pprof для анализа профиля cpu.out.


Я использовал hugo с коммита c8b5ab75b743914f89b51046eee8e3daa2eb1eec. Но думаю примерно такие же результаты можно получить и с других версий.


В digitalgov.gov надо будет поправить пару файлов, убрав использования getenv или добавив их в исключения.


    modified:   themes/digital.gov/layouts/partials/core/head.html
    modified:   themes/digital.gov/layouts/partials/core/set-env.html

Версия Go особо значения не имеет, потому что линейный поиск в MethodByName был всегда.


Выводы


Я выслал CL с изменениями в Go, но не знаю, примут его или нет (spoiler: скорее всего нет).


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


Немного другого я ожидал от hugo с заголовком "The world’s fastest framework for building websites."


Если вдруг вы хотите поставить +1 к высланному патчу, сделать это можно, оставив реакцию к golang/issue50617.




Комментарии (9):

  1. youROCK
    /#23942135 / +6

    Честно говоря, ни разу не очевидно, что MethodByName() имеет сложность O(N), и, видимо, для большинства других программистов на Go, даже для таких крупных проектов, как Hugo, тоже. Спасибо за статью и за патч! Поставил плюсик issue

  2. DabjeilQutwyngo
    /#23942269 / -4

    Не мой язык, но по описанию мне достаточно понятно. И почему я не удивлён? Вы даже не можете себе представить, сколько раз в своей практике мне приходилось сталкиваться с кусками кода, применяющими линейный поиск. Это же ужас какой-то! Такое впечатление, что программисты совсем обленились думать, и тупо решают задачи методом полного перебора, потому что на первом курсе, когда учат циклам, специально дают np-полные задачи. Но потом, почему-то, не учат разработке алгоритмов сортировки и поиска и ухода от поиска вообще, чтобы доступ происходил за константное время.

    Вопрос к вашему "патчу": почему нельзя было сделать хэш-таблицу и поддерживать её актуальной? Почему нельзя добавить методам в название порядковый идентификатор и получать метод по нему за константное время, т.е. обращением по идентификатору как индексу массива (разумеется, массив хранить и пополнять по необходимости вне вызова MethodByName)? В языке вообще есть специальные структуры, обеспечивающие функциональность поиска? Именно в языке, а не библиотеках: реализация на более низком уровне обеспечивает существенно бОльшую производительность. Кроме того, в языке есть собственно функциональность поиска методов, как, например, в Perl для классов?

    В конце концов, можно сделать конечный автомат (КА), выходом которого будет либо метод, либо null. При этом таблица переходов будет реализоваться массивом, в качестве индекса которого будет символ, допустимый в имени метода. Это будет быстрее, чем бинарный поиск, т.к. на каждом шаге используется не два индекса "меньше"/"больше", а множество индексов равномощное множеству символов. Если ASCII покрывает множество символов, из которых составляется имя метода, тогда всего 256 индексов на каждом уровне потребуется. Конечно, построить такой КА – отдельная, но стандартная задача. Выигрыш КА даёт только если минимизирован. Минимизация КА – классическая задача в теории КА (реализовывал её на JavaScript, C++ и Delphi). Недостаток – необходимость обновлять КА при добавлении/удалении методов. Но для этого есть частные эффективные решения, не требующие полной перестройки КА.

    • quasilyte
      /#23942281 / +2

      MethodByName -- не супер важная операция. Если пишется высокопроизводительный (performance-sensitive) код, этот метод использовать нельзя. Если какие-то приложения написаны с его использованием, это обидно, но это не повод писать новые приложения в таком же стиле. (Ниже будет пример, как можно уйти от MethodByName.)

      Вопрос к вашему "патчу": зачем при каждом вызове MethodByName делать сортировку, а затем поиск?

      Там нет сортировки как таковой. sort.Search() делает поиск по отсортированным данным. По факту, просто вызывается callback с определённым индексом i. Данные уже отсортированы.

      Почему нельзя было сразу сделать сортированный список методов, положить его, куда следует и поддерживать?

      Так оно и работает. Слайс всегда отсортирован.

      Либо хэш-таблицу? Почему нельзя добавлять метод в сортированный список, индекс или хэш-таблицу при его появлении?

      Сейчас в rtype нет хэш-таблицы, но есть отсортированный массив (слайс). Если добавлять мапу, то только если лениво инициализированную, потому что есть шанс, что "метод по имени" не понадобится никогда, а память эта мапа кушать будет. А если делать ленивую инициализацию, то усложнится код, всё равно лишняя память на дополнительный указатель и... да ну, имхо, это не оправдано в данном случае, хотя если бы MethodByName было важной операцией, может и было бы оправдано.

      Доступ по индексу к методу уже есть в API. Например, есть возможность самому в мапе хранить маппинг name=>index и потом по индексу получать метод.

      Как-то так:

      m := make(map[string]int)
      for i := 0; i < v.Type().NumMethods(); i++ {
        m[name] = i
      }
      
      // Далее:
      method := v.Type().Method(m["methodName"])

      Надеюсь, ответил на ваши вопросы хотя бы частично. Большая часть ваших вопросов из-за того, что вы под капот не смотрели, а у меня не получится в формате комментариев всё в деталях описать.

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

      • quasilyte
        /#23942361 / +2

        Теперь мне не даёт покоя некорректный код выше.

        Вот исправленная версия: https://go.dev/play/p/S-2VASgk1kT

        package main
        
        import (
        	"fmt"
        	"reflect"
        )
        
        type Example struct{}
        
        func (Example) Method1() {}
        func (Example) Method2() {}
        
        func main() {
        	typ := reflect.TypeOf(Example{})
        	methods := make(map[string]int)
        	for i := 0; i < typ.NumMethod(); i++ {
        		methods[typ.Method(i).Name] = i
        	}
        
        	fmt.Println(typ.Method(methods["Method1"]))
        }

        При этом не обязательно хранить индекс, наверное можно сразу методы, возвращаемые Method(i), сохранять в мапе.

        Так или иначе, есть альтернативы MethodByName() которые будут работать гораздо лучше.

      • DabjeilQutwyngo
        /#23944549

        Справедливости ради, фразы "зачем при каждом вызове MethodByName делать сортировку, а затем поиск?" в итоговой версии моего коментария нет.

        • Deosis
          /#23951047

          А где вы увидели сортировку?

    • Sly_tom_cat
      /#23943637

      Весь reflect - это по сути вытаскивание компиряции в рантайм, т.е. по сути переход к интерпритации... в компилируемом языке - такое себе.

      И именно по этому reflect и HL - вещи несовместимые. И это не только мое мнение - вон тот же easyjson - посути выпиливание рефлекта из стандартной реализации пакета json.

      Собствено профайлинг в go тем и хорош, что буквално в пару команд позволяет понять где проблема. А дальше вот именно такие оптимизации как в статье приводят к оптимизациям когда (из моего опыта) потребление по памяти с сотен мегабайт падает до единиц, с обратно-пропорциональном ростом производительности.

  3. domix32
    /#23945229 / -1

    cum cum%

    Лол, интересно конечно они там сокращают слова. А что за гачи инструмент которым вы все мерили?

    • quasilyte
      /#23945387 / +5

      Я, конечно, понимаю, что вы просто хотели пошутить, но может кому-то реально будет понятнее с пояснениями.

      А что за гачи инструмент которым вы все мерили?

      В статье упоминается pprof несколько раз. Он встроен в тулинг Go. Но им я не измерял, а просматривал CPU профиль.

      cum cum%

      cumulative - суммарное время (англ. - совокупное, накопительное), с учётом вызываемых внутри функции других функций. Flat при этом показывает "собственное" время функции.

      Каждый семпл в profile.proto обычно имеет стектрейс. Первый элемент из него -- текущая функция, которая исполняется сейчас. Если мы считаем flat, то в статистику добавляется только это значение. Остальные элементы -- функции выше по стеку. Если мы считаем sum, то эти значения тоже учитываются. Подробнее можно посмотреть в самих исходниках pprof.

      Возвращаясь к гачи-теме, как вам такой сниппет для pprof (100% рабочий):

      $ (pprof) top 10 -cum