Comments 11
Честно говоря, ни разу не очевидно, что MethodByName() имеет сложность O(N), и, видимо, для большинства других программистов на Go, даже для таких крупных проектов, как Hugo, тоже. Спасибо за статью и за патч! Поставил плюсик issue
Не мой язык, но по описанию мне достаточно понятно. И почему я не удивлён? Вы даже не можете себе представить, сколько раз в своей практике мне приходилось сталкиваться с кусками кода, применяющими линейный поиск. Это же ужас какой-то! Такое впечатление, что программисты совсем обленились думать, и тупо решают задачи методом полного перебора, потому что на первом курсе, когда учат циклам, специально дают np-полные задачи. Но потом, почему-то, не учат разработке алгоритмов сортировки и поиска и ухода от поиска вообще, чтобы доступ происходил за константное время.
Вопрос к вашему "патчу": почему нельзя было сделать хэш-таблицу и поддерживать её актуальной? Почему нельзя добавить методам в название порядковый идентификатор и получать метод по нему за константное время, т.е. обращением по идентификатору как индексу массива (разумеется, массив хранить и пополнять по необходимости вне вызова MethodByName)? В языке вообще есть специальные структуры, обеспечивающие функциональность поиска? Именно в языке, а не библиотеках: реализация на более низком уровне обеспечивает существенно бОльшую производительность. Кроме того, в языке есть собственно функциональность поиска методов, как, например, в Perl для классов?
В конце концов, можно сделать конечный автомат (КА), выходом которого будет либо метод, либо null. При этом таблица переходов будет реализоваться массивом, в качестве индекса которого будет символ, допустимый в имени метода. Это будет быстрее, чем бинарный поиск, т.к. на каждом шаге используется не два индекса "меньше"/"больше", а множество индексов равномощное множеству символов. Если ASCII покрывает множество символов, из которых составляется имя метода, тогда всего 256 индексов на каждом уровне потребуется. Конечно, построить такой КА – отдельная, но стандартная задача. Выигрыш КА даёт только если минимизирован. Минимизация КА – классическая задача в теории КА (реализовывал её на JavaScript, C++ и Delphi). Недостаток – необходимость обновлять КА при добавлении/удалении методов. Но для этого есть частные эффективные решения, не требующие полной перестройки КА.
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.
Теперь мне не даёт покоя некорректный код выше.
Вот исправленная версия: 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() которые будут работать гораздо лучше.
Справедливости ради, фразы "зачем при каждом вызове MethodByName делать сортировку, а затем поиск?" в итоговой версии моего коментария нет.
Весь reflect - это по сути вытаскивание компиряции в рантайм, т.е. по сути переход к интерпритации... в компилируемом языке - такое себе.
И именно по этому reflect и HL - вещи несовместимые. И это не только мое мнение - вон тот же easyjson - посути выпиливание рефлекта из стандартной реализации пакета json.
Собствено профайлинг в go тем и хорош, что буквално в пару команд позволяет понять где проблема. А дальше вот именно такие оптимизации как в статье приводят к оптимизациям когда (из моего опыта) потребление по памяти с сотен мегабайт падает до единиц, с обратно-пропорциональном ростом производительности.
Это не совсем так. В Go reflect в таком виде (я имею ввиду настолько полную и достатоно неплохую реализацию) сделан по причине того, что в Go очень слабая система типов если ее сравнивать с C++/Rust etc, но при этом хочется давать туже гибкость в плане интерфейсов реализации. Можно посмотреть на `database/sql` который может принимать на вход в методах любые аргументы. И вот тут в Go без reflection никак, даже дженерики в которые сейчас будут не в состоянии решить ряд проблем. Поэтому в Go так и распространена кодогенерация, которая, от части, и решает проблему с типами которые компилятор не может вывести и для этого и используется reflection и выноситься многое на уровень с компиляции в рантайм. И easyjson не исключение, он не reflection выпиливает, а по типу генерит реализацию маршалинга и анмаршалинга под него в настоящий код, который проверяется при компиляции. Ровно как и говорить о том, что reflect и HL вещи несовместимые некорректно, да, там достаточно большой оверхед, но тоже смотря с чем сравнивать и это часть языка и хочешь или нет, но если нужно, то других вариантов бывает что и нет
Хочу ещё дополнить тем, что в пакете reflect некоторые операции относительно быстрые и совместимые с высокой производительностью, если понимать некоторые нюансы.
Например, если значение уже выделено в куче, то какой-нибудь reflect.ValueOf(x).IsNil() может быть эффективнее, чем крупный type switch по типам и сравнение с nil, потому что reflect сделает почти чёрную магию с распаковкой интерфейса и проверкой его data поля (напрямую через unsafe будет ещё быстрее, но unsafe не всегда оправдан).
А вот вещи типа MethodByName даже линковщик могут смутить и сделать его более консервативным при удалении мёртвого кода (ведь какой-то метод могут внезапно вызвать по имени через строку, чьё значение статически неизвестно).
Хотя если хочется контроля и стабильности, наверное лучше не использовать reflect вовсе (когнитивно так проще, чем пытаться быть экспертом и следить за изменениями в разных версиях Go). И те же fmt пакеты туда же. Справедливости ради, на практике мало кому нужно настолько контролировать производительность, но всякие zerolog и zap не просто так появились. :)
cum cum%
Лол, интересно конечно они там сокращают слова. А что за гачи инструмент которым вы все мерили?
Я, конечно, понимаю, что вы просто хотели пошутить, но может кому-то реально будет понятнее с пояснениями.
А что за гачи инструмент которым вы все мерили?
В статье упоминается pprof несколько раз. Он встроен в тулинг Go. Но им я не измерял, а просматривал CPU профиль.
cum cum%
cumulative - суммарное время (англ. - совокупное, накопительное), с учётом вызываемых внутри функции других функций. Flat при этом показывает "собственное" время функции.
Каждый семпл в profile.proto обычно имеет стектрейс. Первый элемент из него -- текущая функция, которая исполняется сейчас. Если мы считаем flat, то в статистику добавляется только это значение. Остальные элементы -- функции выше по стеку. Если мы считаем sum, то эти значения тоже учитываются. Подробнее можно посмотреть в самих исходниках pprof.
Возвращаясь к гачи-теме, как вам такой сниппет для pprof (100% рабочий):
$ (pprof) top 10 -cum
Ускоряем hugo на 20% простым изменением в пакете reflect