История оптимизации: создание сканера кода для больших приложений Golang

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

Фон

Мы поддерживаем несколько интерфейсов для преобразования исходного кода и двоичных приложений в их соответствующее представление CPG. В частности, один интерфейс, называемый go2cpg для преобразования исходного кода Go, оказался несколько медленнее, чем ожидалось, в некоторых более крупных репозиториях.

Что мы сделали

Поскольку нам обычно приходится тестировать языковые интерфейсы на общедоступном коде, мы описываем здесь все шаги, основанные на репозитории open-policy-agent / opa, который достаточно велик, чтобы даже на мощной машине преобразование потребовалось несколько секунд (в данном случае все цифры, указанные ниже, для 8-ядерного / 16-поточного ЦП, с 64 ГБ оперативной памяти и довольно быстрым твердотельным накопителем M.2 NVMe.

Первоначальное состояние было следующим: выполнение команды go2cpg generate (которую вы обычно не увидите в таком виде, она заключена в наш инструмент командной строки, когда вы вызываете ее с помощью sl analyze --go ...) не так быстро, как мы надеялись:

go2cpg generate ./...

41.47s user 1.20s system 270% cpu 15.774 total
41.69s user 1.06s system 277% cpu 15.405 total
41.86s user 1.20s system 271% cpu 15.884 total
42.07s user 1.16s system 271% cpu 15.910 total
42.11s user 1.15s system 273% cpu 15.805 total

avg. 41.84s user 15.756s total

Эти измерения были выполнены вручную в целях иллюстрации, но для сравнительного анализа мы использовали hyperfine, который в нашем случае затем вызывается следующим образом:

hyperfine --warmup 3 "go2cpg generate -o /tmp/cpg.bin.zip ./..."

Обратите внимание, что здесь мы добавляем несколько прогонов, чтобы снизить вероятность кэширования диска или, возможно, даже некоторых операций цепочки инструментов Go, мешающих измерениям. Каталог /tmp также был установлен на RAM-диск - к сожалению, /dev/null не может быть использован из-за того, как записывается ZIP-архив.

Таким образом, наша базовая линия была около шестнадцати секунд.

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

Однако в качестве первого шага мы начали создавать и углублять профили ЦП и памяти.

Профилирование

В Go профилирование уже очень хорошо поддерживается стандартной библиотекой с использованием пакетов runtime/pprof и net/http/pprof. Первый позволяет нам создавать профили, а второй предоставляет удобный веб-интерфейс для анализа результатов после их создания.

Мы всегда собираем их, чтобы клиенты могли создавать, а затем отправлять нам данные профилирования:

SHIFTLEFT_CPUPROFILE=cpu \
  SHIFTLEFT_MEMPROFILE=mem go2cpg generate ...

У нас есть два файла, cpu и mem, и мы можем просмотреть их, используя:

go tool pprof -http=":8000" \
  <path to go2cpg binary> cpu # respectively "mem"

Общие шаги:

• загрузка исходного кода Go
• проверка типа
• создание блоков Protobuf (как для AST, так и для графа потока управления CFG)
• маршалинг их в необработанные байты
• запись их в ZIP-архив

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

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

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

Кроме того, оказалось, что есть еще несколько кусочков головоломки.

Мы видим, что одна область, сжатие ZIP, занимает довольно много времени.

Мы также можем выделить еще одну область для маршаллинга Protobuf, которая требует значительного количества времени.

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

Неочевидная стоимость карт

У нас был определенный шаблон для перечислений, который оказался гораздо более затратным, чем ожидалось: изначально мы определили операторы и несколько других перечислений с типом на основе int и константами, определенными через iota:

type Operator int
const (
    AssignmentOperator Operator = iota
    AssignmentPlusOperator
    AssignmentMinusOperator
    // ...
)

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

func (o Operator) String() string {
    s, ok := map[Operator]string{
        AssignmentOperator:      "<operator>.assignment",
        AssignmentPlusOperator:  "<operator>.assignmentPlus",
        AssignmentMinusOperator: "<operator>.assignmentMinus",
        // ...
    }[o]
    if !ok {
        panic(fmt.Sprintf("unknown operator %d", o))
    }
    return s
}

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

К счастью, изменение этого шаблона потребовало не так уж много работы, большая часть которой заключалась в механическом изменении определений и узлов вызова в некоторых местах, чтобы также избавиться от лишнего вызова метода String вместо простого string преобразования:

type Operator string
var AssignmentMinusOperator Operator = "<operator>.assignmentMinus"
var AssignmentMultiplicationOperator Operator = "<operator>.assignmentMultiplication"
var AssignmentDivisionOperator Operator = "<operator>.assignmentDivision"
// ...

В случаях, когда нам нужно несколько связанных значений, мы также просто изменили определения с int на struct { int; string } и т. Д. И вместо этого определили глобальные переменные (которые, конечно, следует рассматривать как константы, которыми они являются на самом деле).

Уровни сжатия

Интерфейс Go должен производить вывод, по крайней мере, во внутреннем формате обмена для CPG, по сути, это ZIP-контейнер двоичных объектов Protobuf.

Раньше мы использовали стандартные библиотечные подпрограммы ZIP, однако их замена на оптимизированную реализацию из klauspost/compress позволила нам сэкономить время, а также полностью отключить сжатие:

envMethod := os.Getenv("SHIFTLEFT_COMPRESSION_METHOD")
compressionMethod, err := strconv.ParseUint(envMethod, 10, 16)
if err != nil {
    compressionMethod = uint64(zip.Deflate)
}
g.flagCompressionMethod = cmd.Flags().Uint16(
	"compression-method",
	uint16(compressionMethod),
	"Specifies the compression level for ZIP archive output"
)

// ...

w, err := archive.CreateHeader(&zip.FileHeader{
    Name:   entry.Name,
    Method: compressionMethod,
})

Поскольку это в основном внутренний флаг (обычно мы не заставляем клиентов думать об этом вообще), мы не стали беспокоиться о дополнительных функциях, связанных с ним. По сути, всего два уровня (по сравнению, например, со стандартной zip утилитой в Linux): 0 для отсутствия сжатия и 8 для среднего сжатия Deflate.

Конечно, примечательно, что мы торгуем уменьшением времени работы с противоположным увеличением потребления дискового пространства. В нашем примере мы переходим от ZIP-файла размером 20 МБ к файлу размером 80 МБ. По всей видимости, это не будет проблемой (мы распаковываем эти файлы только один раз или, может быть, несколько раз), и поэтому этот флаг вполне может быть скоро включен во всем мире.

Протобуф Маршаллинг

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

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

К счастью, есть по крайней мере один улучшенный форк под названием gogo/protobuf, который позволяет нам использовать генерацию кода для всех соответствующих структур. Это изменение сводилось к замене части вызова protoc, который генерирует код Go из нашей схемы CPG, а затем к использованию новой версии этого кода. На самом деле нам нужны только процедуры маршалинга, демаршаллинг здесь не имеет значения, и мы могли бы уменьшить объем сгенерированного кода - хотя и небольшую оптимизацию.

Помимо этого изменения, фактически использовать библиотеку так же просто, как включить другую зависимость:

import (
    // ...
    _ "github.com/gogo/protobuf/proto"
    // ...
)

Это изменение также выявило небольшую ошибку либо в контракте интерфейса, либо в нашем коде: оказалось, что все сгенерированные фрагменты Protobuf совместно использовали некоторые из ранее сгенерированных фрагментов при использовании вновь сгенерированного кода:

func writeToProtobuf(w io.Writer,
                     cpg *cpg.CpgStruct,
                     pbuf *proto.Buffer) error {
    err := pbuf.Marshal(cpg)
    if err != nil {
        return err
    }
    _, err = w.Write(pbuf.Bytes())
    pbuf.Reset()
    return err
}

Эта функция повторно использует экземпляр proto.Buffer и отлично работает со стандартной библиотекой Protobuf. Для кода gogo/protobuf нам пришлось изменить это на:

func writeToProtobuf(w io.Writer,
                     cpg *cpg.CpgStruct,
                     buf []byte) error {
    size := cpg.Size()
    if cap(buf) < size {
        newSize := cap(buf)
        for newSize < size {
            newSize *= 2
        }
        buf = make([]byte, newSize)
    }
    n, err := cpg.MarshalToSizedBuffer(buf[:size])
    if err != nil {
        return err
    }
    _, err = w.Write(buf[:n])
    return err
}

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

Мелкие исправления

Мы также изменили некоторые конкатенации строк, чтобы использовать strings.Builder, в основном механическое изменение, которое компилятор действительно должен выполнить за нас, как это сделано в Java. Это изменение не окажет большого влияния, если оно не находится в очень горячем коде (как для нас). Кроме того, прохождение через этот экземпляр построителя ускорит работу вместо простого возврата строк из метода String и последующего добавления этих результатов в еще один построитель. Мы действительно хотим иметь здесь потоковый вывод, всегда добавляя к одному и тому же экземпляру построителя во всех возможных рекурсивных вызовах функций и только в конце вынимая сгенерированную строку.

Что касается кеширования, то теперь мы берем несколько наиболее часто генерируемых структур и сохраняем их в нескольких переменных. К счастью, код маршаллинга принимает только эти элементы и добавляет их в выходной буфер, не изменяя их. Это важно для того, чтобы мы могли совместно использовать эти объекты в памяти, и с ~ 500 тыс. Обращений к наиболее часто используемому объекту до 60 тыс. Для наименее часто используемого кэшированного объекта, мы удаляем довольно много выделений практически бесплатно. Единственная стоимость здесь - проверка одного перечисления и одного строкового значения на равенство - здесь компромисс все еще имеет смысл:

func initBuilders() {
	intValues = make([]cpg.PropertyValue, maxIntValues)
	for i := int32(0); i < maxIntValues; i++ {
		intValues[i] = cpg.PropertyValue{
			Value: &cpg.PropertyValue_IntValue{
				IntValue: i,
			},
		}
	}
	value := &cpg.PropertyValue{
		Value: &cpg.PropertyValue_StringValue{
			StringValue: NamespaceBlockNode.Name,
		},
	}
	astParentTypeNamespaceBlock = &cpg.CpgStruct_Node_Property{
		Name: cpg.NodePropertyName_AST_PARENT_TYPE,
		Value: value,
	}
	// ...
}

Это также показывает, как мы кэшируем некоторые из наиболее часто используемых целочисленных значений (например, аналогично тому, как, скажем, Python кэширует маленькие целые числа).

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

// AST_PARENT_TYPE/NAMESPACE_BLOCK 458373
// AST_PARENT_FULL_NAME/<global> 319088
// DISPATCH_TYPE/STATIC_DISPATCH 122132
// SIGNATURE/ 103669
// TYPE_FULL_NAME/void 62816
// we're caching the top five elements only
// for illustration, these are the next five elements in order:
// CODE/ 38819
// NAME/bool 36581
// FULL_NAME/bool 36552
// NAME/<operator>.assignment 33922
// METHOD_FULL_NAME/<operator>.assignment 33921

Некоторые другие значения также могут быть преобразованы в глобальные переменные, но фактически константы, например constant.MakeUnknown по крайней мере на момент написания всегда возвращает одну и ту же пустую структуру - поскольку все операции с ней не заботятся об идентичности, мы можем сделать этот вызов только один раз и повторно использовать результат.

У нас было несколько мест, где мы использовали паттерн Строитель для создания объектов. Это очень удобно для удобочитаемости и возможности повторного использования компоновщиков, но в некоторых местах без всякой причины добавляет накладные расходы. Таким образом, мы смогли вручную встроить определенные вызовы, например что-то вроде w.ComplexEdge(_type, src, dst).Build(), прежде чем выделить новый объект-конструктор в ComplexEdge и немедленно выбросить его в метод Build. Заметив, что мы даже не использовали функциональные возможности, которые иначе предлагались ComplexEdge (то есть, чтобы связать больше данных с ребром), мы заменяем эти вызовы прямым w.BuildSimpleEdge(_type, src, dst), удаляя выделения. Опять же, этот тип оптимизации будет иметь значение только в том случае, если будет вызван очень горячим путем. Но мы могли бы просто сделать это для ясности.

Влияние

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

Мы практически не видим каких-либо более конкретных областей, которые все еще выделяются - выделение памяти и сборщик мусора являются двумя самыми большими болевыми точками, и, как уже говорилось, мы можем сделать только так много для их уменьшения в средстве проверки типов, поскольку мы не (хотим ) контролировать этот фрагмент кода.

В цифрах время работы теперь тоже выглядит намного лучше:

SHIFTLEFT_COMPRESSION_METHOD=0 go2cpg generate ./...
14.23s user 1.03s system 250% cpu 6.091 total
14.94s user 0.97s system 253% cpu 6.280 total
14.49s user 0.86s system 243% cpu 6.299 total
14.54s user 0.99s system 251% cpu 6.180 total
13.71S user 1.06s system 250% cpu 5.906 total
avg. 14.382s user 6.151s total

Еще одна часть, в которой мы все еще знаем об относительно простых изменениях, - это переписывание AST, которое снова использует стандартные инструменты из go/ast/astutil, которые, к сожалению, также полагаются на отражение для некоторых довольно часто используемых итераций. Взяв этот библиотечный код и переписав его для повышения производительности, вы избавитесь от дорогостоящих вызовов отражения за счет дублирования кода (мы в основном копируем один и тот же общий алгоритм для нескольких типов, часть кода, которая, кстати, очень выиграет от универсальных шаблонов) .

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

Мы все еще изучаем более масштабные алгоритмические изменения, чтобы еще больше сократить объем работы. Это относится к области исключения кода, подлежащего анализу, настройки инструментов стандартной библиотеки и перемещения операций из внешнего интерфейса в нашу серверную часть (что, к сожалению, не приведет к сокращению общего времени выполнения).

Заключение

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

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

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