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

Векторизованные запросы

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

Вот определение вики, не связанное с развлечениями:

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

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

Проще говоря:

Оперируйте вектором (пакетом) записей с помощью одной инструкции.

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

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

Векторизация и столбчатые форматы

Для столбчатых форматов популярны методы векторизации. Столбчатые форматы обладают определенными преимуществами, которые способствуют повышению производительности векторизованных запросов:

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

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

Методы векторизации

Векторизация использует инструкции SIMD (Single Instruction Multiple Data), которые позволяют выполнять одну инструкцию для нескольких данных.

Одна инструкция SIMD может обрабатывать 16 целых чисел за раз, тем самым достигая параллелизма на уровне данных.

Развертывание цикла

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

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

Конвейерная обработка петли

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

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

Резюме

Векторизация - это выполнение инструкций для вектора (пакета) данных.

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

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

Векторизация использует инструкции SIMD (Single Instruction Multiple Data), которые позволяют выполнять одну инструкцию для нескольких данных.

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

Это все, а пока мы обсудим скомпилированные запросы в части 3.

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