Наши партнеры

UnixForum

Библиотека сайта rus-linux.net

Статический анализ (продолжение)

Оригинал: Static Analysis
Автор: Leah Hanson
Дата публикации: 22 сентября 2015
Перевод: Н.Ромоданов
Дата перевода: июль 2016 г.

Это продолжение статьи. Начало смотрите здесь

Проверка в циклах типов переменных

Как и в большинстве языков программирования, для написания на языке Julia очень быстрого кода требуется понимание того, как работает компьютер, и как работает язык Julia. Важной частью помощи компилятору создать для вас быстрый код — это написать код, который будет стабильным с точки зрения использования типов данных; это важно как в языке Julia, так и в языке JavaScript, а также принесет пользу в других языках, использующих динамическую компиляцию JIT. Если компилятор сможет определить, что переменная в некоторой части кода будет всегда иметь один тот же конкретный тип, то он сможет выполнить более глубокую оптимизацию, чем в тем случае, если он посчитает, (правильно или нет), что для некоторой переменной допустимы сразу несколько возможных типов. Более подробно о том, почему стабильность типов (также называемая "мономорфизмом") очень важна для языка JavaScript, вы можете прочитать по следующей ссылке.

Почему это важно

Давайте напишем функцию, которая принимает значение типа Int64 и увеличивает его на некоторую величину. Если число маленькое (меньше 10), давайте увеличим его на большее значение (на 50), но если оно большое, то давайте его увеличим на чуть-чуть (на 0,5).

function increment(x::Int64)
  if x < 10
    x = x + 50
  else
    x = x + 0.5
  end
  return x
end

Эта функция выглядит довольно просто, но тип у x является нестабильным. Я выбрала два числа: 50 типа Int64 и 0,5 типа Float64. В зависимости от величины x, может быть добавлено либо одно, либо другое. Если добавить значение, равное 22 и имеющее тип Int64, к 0.5, имеющему тип Float64, то вы получите тип Float64 (22,5). Поскольку тип переменной в функции (x) может меняться в зависимости от значения аргументов функции function (x), то этот метод increment и, в частности переменная x, имеют нестабильный тип.

Float64 это тип, который представляет значения с плавающей запятой, хранящиеся в 64 битах; в языке C он называется double. Это один из типов с плавающей точкой, которые понимают 64-разрядные процессоры.

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

Во-первых, давайте посмотрим на примере, что мы хотим обнаружить. Мы рассмотрим две функции. Каждая из них суммирует числа от 1 до 100, но, кроме суммирования чисел, они делят каждое число на 2 перед тем, как его добавить к сумме. Обе функции получают один и тот же ответ (2525.0); и возвращают один и тот же тип данных (Float64). Тем не менее, первая функция, unstable, имеет переменную с нестабильным типом данных, а во второй, stable, нестабильности по типам нет. 

function unstable()
  sum = 0
  for i=1:100
    sum += i/2
  end
  return sum
end
function stable()
  sum = 0.0
  for i=1:100
    sum += i/2
  end
  return sum
end

Единственное различие в тексте между этими двумя функциями состоит в инициализации суммы sum: sum = 0 и суммы sum = 0.0. В языке Julia 0 имеет тип Int64, а 0.0 имеет тип Float64. Сколь большие изменения могли произойти из-за этого небольшого различия?

Поскольку язык Julia компилируется в режиме Just-In-Time (JIT), то первый запуск функции будет выполняться дольше, чем последующие запуски. (При первом запуске затрачивается время, необходимое для компиляции функции для конкретных типов аргументов). Если мы измеряем производительность функции, то прежде, чем измерять затрачиваемое время, мы должны удостовериться, что она один раз уже выполнялась (или была предварительно откомпилирована).

julia> unstable()
2525.0

julia> stable()
2525.0

julia> @time unstable()
elapsed time: 9.517e-6 seconds (выделено 3248 байтов)
2525.0

julia> @time stable()
elapsed time: 2.285e-6 seconds (выделено 64 байта)
2525.0

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

Если мы хотим получить точные цифры для сравнения функций stable и unstable, то нам нужно более длительный цикл или мы должно много раз запускать это функции. Тем не менее, функция unstable будет вероятно, более медленной. Гораздо интереснее то, что мы можем обнаружить большое различие в количестве выделенной памяти, для функции unstable выделено около 3 Кб памяти, тогда как для функции stable используется 64 байта.

Поскольку функция unstable достаточно простая, то можно предположить, что выделение памяти происходит в цикле. Чтобы проверить это, мы можем сделать цикл длиннее и посмотреть, увеличится ли соответствующим образом количество выделяемой памяти. Давайте сделаем цикл от 1 и до 10000, что в 100 раз больше предыдущего; мы предполагаем, что количество выделяемых байтов также увеличится примерно в 100 раз, т. е. примерно до 300 КБ. 

function unstable()
  sum = 0
  for i=1:10000
    sum += i/2
  end
  return sum
end

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

julia> unstable()
2.50025e7

julia>@time unstable()
elapsed time: 0.000667613 seconds (выделено 320048 байтов)
2.50025e7

Для новой функции unstable выделено приблизительно около 320 Кбайтов памяти, т. е. именно то, что можно было ожидать в случае, если выделение памяти происходит в цикле. Чтобы объяснить, что в этом случае происходит, мы собираемся заглянуть «под капот» и посмотреть, как работает язык Julia.

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

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

Немутируемые типы, как правило, являются типами данных, которые представляют значения, а не коллекции значений. Например, большинство числовых типов, в том числе Int64 и Float64, являются немутируемыми. (Числовые типы в языке Julia являются обычными типами данных, в не специальными примитивными типами данных; вы можете определить новый тип данных MyInt64, который будет точно таким же, как один из уже имеющихся). Поскольку немутируемые типы данных не могут быть изменены, вы должны сделать новую копию значения каждый раз, когда вы хотите изменить данные. Например, для 4 + 6 следует создать новое значение Int64 для хранения результата. В противоположность этому, члены мутируемого типа могут быть обновлены сразу по месту; это означает, что вам не нужно создавать копию для того, чтобы сделать изменение.

Идея выделять память для операции x = x + 2, вероятно, звучит довольно странно; почему вы должны замедлять выполнение такой элементарной операции из-за того, что делаете значения Int64 немутируемыми? Это именно тот случай, где происходит оптимизация компиляции: использование немутируемых типов не (как правило) не замедляет скорость выполнения операции. Если переменная x имеет стабильный вполне конкретный тип (например, Int64), то компилятор волен выделять память для x в стеке и изменять x прямо на месте. Проблема возникает только тогда, когда переменная x имеет нестабильный тип (поэтому компилятор не знает, сколько памяти будет использовано или какой будет использован тип данных); после того, как для x будет выделена память и эта память будет размещена в куче, компилятор не может быть абсолютно уверенным в том, что некоторый другой кусок кода не использует это значение, и, следовательно, не может его редактировать.

Поскольку переменная sum в stable имеет конкретный тип (Float64), компилятор знает, что он может хранить ее локально в функции и мутировать его значение; sum не будет размещена в куче и, каждый раз, когда мы добавляем i/2. новые копии делать не нужно.

Поскольку переменная sum в unstable не имеет конкретный тип, компилятор выделяет для нее память в куче. Каждый раз, когда мы изменяем сумму, мы для нового значения выделяем место в куче. На размещение значения в куче (и извлечения его каждый раз, когда мы хотим прочитать значение переменной sum) затрачивается много времени.

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

Детали реализации

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

  • Как мы находим циклы?
  • Как мы находим переменные в циклах?
  • Как мы находим типы переменной?
  • Как мы печатаем результаты?
  • Как мы сообщим о том, что тип является нестабильным?

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

Типом переменной /code>sum в unstable является объединение Union(Float64,Int64). Это тип объединения UnionType, особый тип, что указывает на то, что переменная может содержать любое множество типов. Переменная типа Union(Float64,Int64) может содержать значения типа Int64 илиFloat64; значение может иметь только одного из этих типов. Тип UnionType объединяет любое количество типов (например, UnionType(Float64, Int64, Int32) объединяет три типа). И мы собираемся внутри циклов искать переменные типа UnionTyped.

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

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

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

Продолжение статьи смотрите здесь