[Перевод] Что ученые должны знать о железе для написания быстрого кода24.11.2020 11:32

owrgyindxe__kjjlebcgqxcadce.jpeg
источник изображения

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

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


Это не руководство по языку программирования Julia

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


Это не объяснение конкретных структур данных или алгоритмов

Помимо знания вашего языка, вы также должны понимать свой собственный код, чтобы сделать его быстрым. Вы должны понять идею, лежащую в основе нотации big-O, почему некоторые алгоритмы работают быстрее других, и как различные структуры данных работают внутри. Не зная, что такое «массив», как можно оптимизировать код, использующий массивы?

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


  • Как двоичное целое число представляется в памяти
  • Как число с плавающей запятой представлено в памяти (изучение этого также необходимо для понимания вычислительных ошибок от операций с плавающей запятой, что является обязательным при выполнении научного программирования)
  • Расположение в памяти «строк», включая кодировку ASCII и UTF-8
  • Основы того, как структурирован «массив», и в чем разница между плотным массивом, например, целых чисел и массивом ссылок на объекты
  • Принципы, лежащие в основе того, как работают Dict (т. е. хэш-таблица) и Set

Кроме того, я бы также рекомендовал ознакомиться с такими штуками как:


  • Кучи
  • Двусторонние очереди
  • Кортежи


Это не учебник по бенчмаркингу вашего кода

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


Содержание

Прежде чем начать, следует установить пакеты: 

# using Pkg
# Pkg.add("BenchmarkTools")
# Pkg.add("StaticArrays")

using StaticArrays
using BenchmarkTools

# Print median elapsed time of benchmark
function print_median(trial)
    println("Median time: ", BenchmarkTools.prettytime(median(trial).time))
end;


Базовая структура компьютерного оборудования

Начнем с упрощенной ментальной модели компьютера. Далее, будем добавлять детали к нашей модели по мере необходимости.

$ [CPU] \leftrightarrow [RAM] \leftrightarrow [DISK] $

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


  • Центральный процессор (CPU) представляет собой чип размером со штамп. Именно здесь на самом деле происходят все вычисления — в мозгу компьютера.
  • Оперативная память (Random access memory, ОЗУ, или просто «память») — это кратковременная память компьютера. Для поддержания этой памяти требуется электроэнергия, и она теряется при выключении компьютера. Оперативная память служит временным хранилищем данных между диском и процессором. Большая часть времени, затрачиваемого на «загрузку» различных приложений и операционных систем, фактически тратится на перемещение данных с диска в оперативную память и распаковку их там. Типичный потребительский ноутбук имеет около $10^{11}$ бит оперативной памяти.
  • Диск является элементом хранения данных. Данные на диске сохраняются после отключения питания, поэтому диск содержит долговременную память компьютера. Он также намного дешевле в пересчете на гигабайт, чем оперативная память. Потребительский ПК имеет около $10^{13}$ бит дискового пространства.


Minimize disk writes

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

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

Следующий пример служит для иллюстрации разницы в скорости: Первая функция открывает файл, получает доступ к одному байту из файла и снова закрывает его. Вторая функция случайным образом получает доступ к 1 000 000 целых чисел из оперативной памяти.

# Open a file
function test_file(path)
    open(path) do file
        # Go to 1000'th byte of file and read it
        seek(file, 1000)
        read(file, UInt8)
    end
end
@time test_file("README.md")

# Randomly access data N times
function random_access(data::Vector{UInt}, N::Integer)
    n = rand(UInt)
    mask = length(data) - 1
    @inbounds for i in 1:N
        n = (n >>> 7) ⊻ data[n & mask + 1]
    end
    return n
end

data = rand(UInt, 2^24)
@time random_access(data, 1000000);

# 0.000781 seconds (15 allocations: 992 bytes)
# 0.095022 seconds

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

$ [CPU] \leftrightarrow [RAM] \leftrightarrow [DISK\,CACHE] \leftrightarrow [DISK] $

На моем компьютере поиск одного байта в файле (включая открытие и закрытие файла) занимает около 781 мкс, а доступ к 1 000 000 целых чисел из памяти занимает 95 миллисекунд. Таким образом, оперативная память работает примерно в 8000 раз быстрее, чем диск.

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

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


CPU cache

Оперативная память быстрее диска, а процессор, в свою очередь, быстрее оперативной памяти. Процессор тикает, как часы, со скоростью около 3 ГГц, то есть 3 миллиарда тиков в секунду. Один «тик» этих часов называется тактовым циклом. Хотя это не совсем так, вы можете себе представить, что каждый цикл процессор выполняет одну простую команду, называемую инструкцией процессора, которая выполняет одну операцию над небольшим фрагментом данных. Тогда тактовая частота может служить ориентиром для других таймингов в компьютере. Стоит понимать, что за один такт фотон пройдет только около 10 см, и это ставит барьер тому, насколько быстро может работать память (которая расположена на некотором расстоянии от процессора). На самом деле, современные компьютеры настолько быстры, что существенным узким местом в их скорости является задержка, вызванная временем, необходимым для движения электричества по проводам внутри компьютера.

В этом масштабе чтение из оперативной памяти занимает около 100 тактов. Аналогично тому, как медлительность дисков может быть уменьшена путем копирования данных в более быструю оперативную память, данные из оперативной памяти копируются в меньший чип памяти непосредственно на процессоре, называемый кэш. Кэш быстрее, потому что он физически находится на чипе процессора (уменьшая путевые задержки), а также потому, что он использует более быстрый тип оперативной памяти, статическую оперативную память, вместо более медленной (но более дешевой в производстве) динамической оперативной памяти. Поскольку он должен быть размещен на процессоре, ограничивается его размер, и поскольку он более дорог в производстве, типичный кэш процессора содержит только около $10^8$ бит, примерно в 1000 раз меньше, чем оперативная память. На самом деле существует несколько уровней кэша процессора, но здесь мы упрощаем его и просто называем «кэш» как одну единственную вещь:

$ [CPU] \leftrightarrow [CPU\,CACHE] \leftrightarrow [RAM] \leftrightarrow [DISK\,CACHE] \leftrightarrow [DISK] $

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

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

Эффективное использование кэша сводится к локальности, временной и пространственной:


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

Из этой информации можно вывести ряд простых трюков для повышения производительности:


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


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


Чтобы проиллюстрировать это, давайте сравним время, затраченное на функцию random_access приведенную выше, с новой функцией linear_access. Эта функция выполняет те же вычисления, что и random_access, но использует i вместо n для доступа к массиву, поэтому она обращается к данным линейным способом. Следовательно, единственное различие — это шаблон доступа к памяти.

Обратите внимание на большое расхождение во времени.

function linear_access(data::Vector{UInt}, N::Integer)
    n = rand(UInt)
    mask = length(data) - 1
    for i in 1:N
        n = (n >>> 7) ⊻ data[i & mask + 1]
    end
    return n
end

print_median(@benchmark random_access(data, 4096))
print_median(@benchmark linear_access(data, 4096))

# Median time: 408.149 μs
# Median time: 1.864 μs

Это также имеет последствия для ваших структур данных. Хэш-таблицы, такие как Dict и Set, по своей сути неэффективны в кэше и почти всегда вызывают промахи кэша, в то время как массивы — нет.

Многие из оптимизаций в этом документе косвенно влияют на использование кэша, поэтому это важно иметь в виду.


Alignment

Как уже упоминалось, ваш процессор будет перемещать 512 последовательных бит (64 байта) в основную оперативную память и из нее в кэш одновременно. Эти 64 байта называются строкой кэша. Вся ваша основная память сегментирована на строки кэша. Например, адреса памяти от 0 до 63 — это одна строка кэша, адреса от 64 до 127-следующая, от 128 до 191-следующая и так далее. Ваш процессор может запрашивать только одну из этих строк из памяти, а не, например, 64 байта с адреса 30 до 93.

Это означает, что некоторые структуры данных могут пересекать границы между строками кэша. Если я запрошу 64-битное (8 байтовое) целое число по адресу 60, процессор должен сгенерировать два запроса памяти (а именно, чтобы получить строки кэша 0–63 и 64–127), а затем получить целое число из обеих строк кэша, теряя время.

Время, потраченное впустую, может быть значительным. В ситуации, когда доступ к кэш-памяти оказывается узким местом, замедление может приблизиться к двукратному. В следующем примере я использую указатель для повторного доступа к массиву с заданным смещением от границы строки кэша. Если смещение находится в диапазоне 0:56, то все целые числа помещаются в одну строку кэша, и функция работает быстро. Если смещение находится в 57:63, то все целые числа будут располагаться между строками кэша.

function alignment_test(data::Vector{UInt}, offset::Integer)
    # Jump randomly around the memory.
    n = rand(UInt)
    mask = (length(data) - 9) ⊻ 7
    GC.@preserve data begin # protect the array from moving in memory
        ptr = pointer(data)
        iszero(UInt(ptr) & 63) || error("Array not aligned")
        ptr += (offset & 63)
        for i in 1:4096
            n = (n >>> 7) ⊻ unsafe_load(ptr, (n & mask + 1) % Int)
        end
    end
    return n
end
data = rand(UInt, 256 + 8);

print_median(@benchmark alignment_test(data, 0))
print_median(@benchmark alignment_test(data, 60))

# Median time: 6.707 μs
# Median time: 12.680 μs

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

data = rand(UInt, 1 << 24 + 8)
print_median(@benchmark alignment_test(data, 10))
print_median(@benchmark alignment_test(data, 60))

# Median time: 404.351 μs
# Median time: 484.438 μs

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

memory_address = reinterpret(UInt, pointer(data))
@assert iszero(memory_address % 64)

Обратите внимание, что если начало массива выровнено, то для 1-, 2-, 4- или 8-байтовых объектов невозможно пересечь границы строк кэша, и все будет выровнено.

По-прежнему было бы возможно, например, чтобы 7-байтовый объект был смещен в массиве. В массиве 7-байтовых объектов 10-й объект будет помещен со смещением байта $7 \times (10-1) = 63$, и объект перешагнет строку кэша. Однако компилятор обычно не допускает структуру с нестандартным размером. Определим 7-байтовую структуру: 

struct AlignmentTest
    a::UInt32 # 4 bytes +
    b::UInt16 # 2 bytes +
    c::UInt8  # 1 byte = 7 bytes?
end

Затем мы можем использовать интроспекцию Джулии, чтобы получить относительное положение каждого из трех целых чисел в объекте AlignmentTest в памяти: 

function get_mem_layout(T)
    for fieldno in 1:fieldcount(T)
        println("Name: ", fieldname(T, fieldno), "\t",
                "Size: ", sizeof(fieldtype(T, fieldno)), " bytes\t",
                "Offset: ", fieldoffset(T, fieldno), " bytes.")
    end
end

println("Size of AlignmentTest: ", sizeof(AlignmentTest), " bytes.")
get_mem_layout(AlignmentTest)

# Size of AlignmentTest: 8 bytes.
# Name: a   Size: 4 bytes   Offset: 0 bytes.
# Name: b   Size: 2 bytes   Offset: 4 bytes.
# Name: c   Size: 1 bytes   Offset: 6 bytes.

Можно заметить, что, несмотря на то, что AlignmentTest имеет только 4 + 2 + 1 = 7 байт фактических данных, он занимает 8 байт памяти, и доступ к объекту AlignmentTest из массива всегда будет выровнен.

Есть только несколько ситуаций, в которых вы можете столкнуться с проблемами выравнивания, как программист. Я могу придумать два варианта:


  1. Если вы вручную создаете объект со странным размером, например, обращаясь к плотному целочисленному массиву с указателями. Это может сэкономить память, но будет времязатратно. Моя реализация фильтра кукушки делает так для экономии места.
  2. Во время матричных операций. Если у вас есть матрица, то столбцы иногда не выровнены, потому что она плотно хранится в памяти. например, в матрице 15×15 Float32 выровнен только первый столбец, а все остальные — нет. Это может иметь серьезные последствия при выполнении матричных операций: Я видел бенчмарки где умножение матрицы/вектора 80×80 происходит в 2 раза быстрее, чем умножение матрицы/вектора 79×79 из-за проблем с выравниванием.


Inspect generated assembly

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

Просмотр низкоуровнего кода будет полезен для понимания некоторых из следующих разделов, которые относятся к инструкциям процессора.

В Julia мы можем легко проверить скомпилированный ассемблерный код с помощью функции code_native или эквивалентного макроса @code_native. Проделаем это для простой функции: 

# View assembly code generated from this function call
function foo(x)
    s = zero(eltype(x))
    @inbounds for i in eachindex(x)
        s = x[i ⊻ s]
    end
    return s
end

# Actually running the function will immediately crash Julia, so don't.
@code_native foo(data)


код 
section __TEXT,__text,regular,pure_instructions
; ┌ @ In[13]:4 within 'foo'
; │┌ @ abstractarray.jl:212 within 'eachindex'
; ││┌ @ abstractarray.jl:95 within 'axes1'
; │││┌ @ abstractarray.jl:75 within 'axes'
; ││││┌ @ In[13]:3 within 'size'
    movq    24(%rdi), %rax
; ││││└
; ││││┌ @ tuple.jl:157 within 'map'
; │││││┌ @ range.jl:320 within 'OneTo' @ range.jl:311
; ││││││┌ @ promotion.jl:409 within 'max'
    testq   %rax, %rax
; │└└└└└└
    jle L75
    movq    %rax, %rcx
    sarq    $inlinе$63, %rcx
    andnq   %rax, %rcx, %rcx
    movq    (%rdi), %rdx
; │ @ In[13]:5 within 'foo'
; │┌ @ int.jl:860 within 'xor' @ int.jl:301
    negq    %rcx
    movl    $inlinе$1, %esi
    xorl    %eax, %eax
    nopw    %cs:(%rax,%rax)
    nopl    (%rax)
L48:
    xorq    %rsi, %rax
; │└
; │┌ @ multidimensional.jl:543 within 'getindex' @ array.jl:788
    movq    -8(%rdx,%rax,8), %rax
; │└
; │┌ @ range.jl:597 within 'iterate'
; ││┌ @ promotion.jl:398 within '=='
    leaq    (%rcx,%rsi), %rdi
    addq    $inlinе$1, %rdi
; ││└
    addq    $inlinе$1, %rsi
; ││┌ @ promotion.jl:398 within '=='
    cmpq    $inlinе$1, %rdi
; │└└
    jne L48
; │ @ In[13]:7 within 'foo'
    retq
L75:
    xorl    %eax, %eax
; │ @ In[13]:7 within 'foo'
    retq
    nop
; └

Разберемся с этим:

Строки, начинающиеся с ;, являются комментариями и объясняют, из какого раздела кода берутся следующие инструкции. Они показывают вложенные серии вызовов функций и то, где в исходном коде они находятся. Заметим, что eachindex, вызывает axes1, которая обращается к axes, которая вызывает size. Под строкой комментария, содержащей вызов size, мы видим первую инструкцию процессора. Название инструкции находится в крайнем левом углу, movq. Название состоит из двух частей: mov, типа инструкции (для перемещения содержимого в регистр или из него), и суффикса q, сокращенного от «quad», что означает 64-битное целое число. Существуют следующие суффиксы: b (байт, 8 бит), w (слово, 16 бит), l (длинный, 32 бит) и q (quad, 64 бит).

Следующие два столбца инструкции, 24(%rdi) и %rax, являются аргументами для movq. Это имена регистров (мы вернемся к ним позже), в которых хранятся данные для работы.

Вы также можете заметить (на увеличенном дисплее ассемблер-кода), что код сегментирован на разделы, начинающиеся с имени, с буквой «L», например, есть раздел L48. Переход между этими разделами происходит при использовании операторов if или ветвей. Здесь раздел L48 отмечает фактический цикл. Рассмотрим следующие две инструкции в разделе L48: 

; ││┌ @ promotion.jl:401 within '=='
     cmpq    $inlinе$1, %rdi
; │└└
     jne     L48

Первая инструкция cmpq (compare quad) сравнивает данные в реестре rdi, которые содержат данные о количестве оставшихся итераций (плюс одна), с числом 1 и устанавливает определенные флаги (провода) в процессоре на основе результата. Следующая команда jne (jump if not equal) совершает прыжок, если флаг «equal» не установлен в процессоре, что происходит, если остается одна или несколько итераций. Он переходит к «L48», что означает повторение этого раздела.


Быстрая инструкция, медленная инструкция

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

Инструкции процессоров обычно занимают несколько циклов процессора для завершения. Однако, если инструкция использует другую часть ЦП во время ее выполнения, ЦП обычно может запустить новую инструкцию до завершения старой: если какая-то операция X занимает, скажем, 4 такта, они могут поставить в очередь одну или даже две операции за такт, используя функцию, называемую конвейеризация инструкций. Следовательно, Инструкция X имеет задержку в 4 цикла, что означает, что для завершения инструкции требуется 4 цикла. Но если процессор может поставить в очередь новую инструкцию в каждый отдельный цикл, он может иметь взаимную пропускную способность 1 такт, что означает в среднем, что требуется только 1 цикл на операцию.

В следующей таблице время измеряется в тактах:

Команда lea принимает три входа, A, B и C, где A должно быть 2, 4 или 8, и вычисляет AB + C. Мы вернемся к тому, что делают инструкции «вектор» позже.

Для сравнения мы можем также добавить некоторые очень грубые оценки других источников задержек:

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

divide_slow(x) = div(x, 8)
divide_fast(x) = x >>> 3;

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

# Calling it with debuginfo=:none removes the comments in the assembly code
code_native(divide_slow, (UInt,), debuginfo=:none)

        .section    __TEXT,__text,regular,pure_instructions
    movq    %rdi, %rax
    shrq    $inlinе$3, %rax
    retq
    nopl    (%rax,%rax)


Minimize allocations

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

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

В таких языках программирования, как Julia, Python, R и Java, освобождение производится автоматически с помощью программы, называемой сборщиком мусора (GC). Эта программа отслеживает, какие объекты оказываются недоступными программисту, и освобождает их. Например: 

thing = [1,2,3]
thing = nothing

Нет никакого способа вернуть исходный массив »[1,2,3] » обратно, он недостижим. Поэтому он просто тратит впустую оперативную память и ничего не делает. Это «мусор». Выделение и освобождение объектов иногда приводит к тому, что GC начинает сканирование всех объектов в памяти и освобождает недостижимые, что вызывает значительное отставание. Вы также можете запустить сборщик мусора вручную: 

GC.gc()

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


Код 
function increment(x::Vector{<:Integer})
    y = similar(x)
    @inbounds for i in eachindex(x)
        y[i] = x[i] + 1
    end
    return y
end

function increment!(x::Vector{<:Integer})
    @inbounds for i in eachindex(x)
        x[i] = x[i] + 1
    end
    return x
end

function print_mean(trial)
    println("Mean time: ", BenchmarkTools.prettytime(BenchmarkTools.mean(trial).time))
end

data = rand(UInt, 2^10);
# Запустите один раз, чтобы скомпилировать функцию - мы не хотим измерять компиляцию
increment(data); increment!(data)

print_mean(@benchmark increment(data));
print_mean(@benchmark increment!(data));

# Mean time: 1.799 μs
# Mean time: 81.788 ns

На моем компьютере функция выделяющая память в среднем работает более чем в 20 раз медленнее. Это связано с несколькими свойствами кода:


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

Обратите внимание, что я использовал среднее время вместо медианы, так как для этой функции GC запускает только приблизительно каждый 30-й вызов, но при этом потребляет 30–40 мкс. Все это означает, что производительный код должен сводить выделение ресурсов к минимуму. Обратите внимание, что макрос @btime печатает количество и размер выделений памяти. Эта информация дается потому, что предполагается, что любой программист, который заботится о тестировании своего кода, будет заинтересован в сокращении аллокаций.


Не на все объекты нужно выделять память

Внутри оперативной памяти данные хранятся либо в стеке, либо в куче. Стек — это простая структура данных с началом и концом, похожая на Vector в Julia. Стек может быть изменен только путем добавления или вычитания элементов из конца, аналогично Vector'у только с двумя мутирующими операциями push! и pop!. Эти операции в стеке выполняются очень быстро. Однако, когда мы говорим об аллокациях, мы говорим о данных в куче. В отличие от стека, куча имеет неограниченный размер (ну, она имеет размер оперативной памяти вашего компьютера) и может быть изменена произвольно, при удалении любых объектов.

Интуитивно может показаться очевидным, что все объекты будучи помещены в оперативную память, должны иметь возможность быть удаленными в любое время программой, и поэтому должны быть выделены в куче. И для некоторых языков, таких как Python, это верно. Однако это не относится к Джулии и другим эффективным компилируемым языкам. Целые числа, например, часто могут быть помещены в стек.

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


  • Объект имеет достаточно маленький размер и помещается в стек. Это необходимо по техническим причинам для работы стека.
  • Компилятор может точно предсказать, когда ему нужно добавить и уничтожить объект, просто открыв стек (аналогично вызову pop! на Vector). Обычно это относится к локальным переменным в компилируемых языках.

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


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

В Julia у нас есть понятие bitstype, которое представляет собой объект, который рекурсивно содержит объекты, выделяемые не кучей. Выделенные в куче объекты — это объекты типов String, Array, Symbol, изменяемые объекты или объекты, содержащие любой из предыдущих. Битовые типы более эффективны именно потому, что они неизменяемы, фиксированы по размеру и почти всегда могут быть оформлены как стек. Последний пункт также объясняет, почему объекты неизменяемы по умолчанию в Julia, и приводит к еще одному совету производительности: используйте неизменяемые объекты везде, где это возможно.

Что это означает на практике? В Julia это означает, что если вы хотите быстрые выделяемые как стек объекты, то:


  • Ваш объект должен быть создан, использован и уничтожен в полностью скомпилированной функции, чтобы компилятор точно знал, когда ему нужно создать, использовать и уничтожить объект. Если объект возвращается для последующего использования (а не сразу возвращается в другую, полностью скомпилированную функцию), мы говорим, что объект экранируется и должен быть выделен.
  • Тип вашего объекта должен быть битовым типом.
  • Ваш тип должен быть ограничен по размеру. Я точно не знаю, насколько большим он должен быть, но 100 байт — это нормально.
  • Точные требования к памяти вашего типа должно быть известно компилятору.
abstract type AllocatedInteger end

struct StackAllocated <: AllocatedInteger
    x::Int
end

mutable struct HeapAllocated <: AllocatedInteger
    x::Int
end

Сравним подноготную приведенных выше объектов: 

@code_native HeapAllocated(1)

    .section    __TEXT,__text,regular,pure_instructions
; ┌ @ In[20]:8 within 'HeapAllocated'
    pushq   %rbx
    movq    %rsi, %rbx
    movabsq $inlinе$jl_get_ptls_states_fast, %rax
    callq   *%rax
    movabsq $inlinе$jl_gc_pool_alloc, %rcx
    movq    %rax, %rdi
    movl    $inlinе$1400, %esi             ## imm = 0x578
    movl    $inlinе$16, %edx
    callq   *%rcx
    movabsq $inlinе$4470743600, %rcx       ## imm = 0x10A7A2230
    movq    %rcx, -8(%rax)
    movq    %rbx, (%rax)
    popq    %rbx
    retq
    nopl    (%rax)
; └

Обратите внимание на инструкции callq в HeapAllocated. Эта инструкция вызывает другие функции, а это означает, что на самом деле для создания объекта HeapAllocated, действительно требуется гораздо больше кода. В отличии от этого, в StackAllocated нужно всего несколько инструкций: 

@code_native StackAllocated(1)

    .section    __TEXT,__text,regular,pure_instructions
; ┌ @ In[20]:4 within 'StackAllocated'
    movq    %rsi, %rax
    retq
    nopw    %cs:(%rax,%rax)
    nop
; └

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

Base.:+(x::Int, y::AllocatedInteger) = x + y.x
Base.:+(x::AllocatedInteger, y::AllocatedInteger) = x.x + y.x

data_stack = [StackAllocated(i) for i in rand(UInt16, 1000000)]
data_heap = [HeapAllocated(i.x) for i in data_stack]

@btime sum(data_stack)
@btime sum(data_heap);

#   130.958 μs (1 allocation: 16 bytes)
#   951.989 μs (1 allocation: 16 bytes)

Мы можем удостовериться, что массив data_stack действительно хранит данные StackAllocated, тогда как data_heap содержит указатели (т. е. адреса памяти): 

println("First object of data_stack:         ", data_stack[1])
println("First data in data_stack array:     ", unsafe_load(pointer(data_stack)), '\n')

println("First object of data_heap:          ", data_heap[1])
first_data = unsafe_load(Ptr{UInt}(pointer(data_heap)))
println("First data in data_heap array:      ", repr(first_data))
println("Data at address ", repr(first_data), ": ",
        unsafe_load(Ptr{HeapAllocated}(first_data)))

#=
First object of data_stack:         StackAllocated(10099)
First data in data_stack array:     StackAllocated(10099)

First object of data_heap:          HeapAllocated(10099)
First data in data_heap array:      0x0000000139a7e570
Data at address 0x0000000139a7e570: HeapAllocated(10099)
=#


Exploit SIMD vectorization

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

© Habrahabr.ru