Русский
Русский
English
Статистика
Реклама

Chapel

Перевод Смотрим на Chapel, D, Julia на задаче вычисления ядра матрицы

24.06.2020 14:16:49 | Автор: admin

Введение


Кажется, стоит вам отвернуться, и появляется новый язык программирования, нацеленный на решение некоторого специфического набора задач. Увеличение количества языков программирования и данных глубоко взаимосвязано, и растущий спрос на вычисления в области Data Science является связанным феноменом. В области научных вычислений языки программирования Chapel, D и Julia являются весьма релевантными. Они возникли в связи с различными потребностями и ориентированы на различные группы проблем: Chapel фокусируется на параллелизме данных на отдельных многоядерных машинах и больших кластерах; D изначально разрабатывался как более продуктивная и безопасная альтернатива C++; Julia разрабатывалась для технических и научных вычислений и была нацелена на освоение преимуществ обоих миров высокой производительности и безопасности статических языков программирования и гибкости динамических языков программирования. Тем не менее, все они подчеркивают производительность как отличительную особенность. В этой статье мы рассмотрим, как различается их производительность при вычислении ядра матрицы, и представим подходы к оптимизации производительности и другие особенности языков, связанные с удобством использования.

Вычисление ядра матрицы формирует основу методов в приложениях машинного обучения. Задача достаточно плохо масштабируется -O(m n^2), где n количество векторов, а m количество элементов в каждом векторе. В наших упражнениях m будет постоянным и мы будем смотреть на время выполнения в каждой реализации по мере увеличения n. Здесь m = 784 и n = 1k, 5k, 10k, 20k, 30k, каждое вычисление выполняется три раза и берется среднее значение. Мы запрещаем любое использование BLAS и допускаем использование только пакетов или модулей из стандартной библиотеки каждого языка, хотя в случае D эталон еще сравнивается с вычислениями, использующими Mir, библиотеку для работы с многомерными массивами, чтобы убедиться, что моя реализация матрицы отражает истинную производительность D. Подробности вычисления ядра матрицы и основных функций приведены здесь.

При подготовке кода для этой статьи сообщества Chapel, D и Julia были очень полезны и терпеливы в отношении всех моих обращений, чему я признателен.

С точки зрения предвзятости, в начале работы, я был гораздо лучше знаком с D и Julia, чем с Chapel. Тем не менее, для получения наилучшей производительности от каждого языка требовалось взаимодействие с сообществами каждого языка, и я делал всё возможное, чтобы осознавать мои предубеждения и исправлять их там, где это было необходимо.

Бенчмарки языков программирования на задаче вычисления ядра матрицы


Приведенная выше диаграмма (сгенерированная с помощью ggplot2 на R с помощью скрипта) показывает время выполнения для количества элементов n для Chapel, D, и Julia, для девяти вычислений ядра. D лучше всего работает в пяти из девяти случаев, Julia лучше в двух из девяти, а в двух задачах (Dot и Gaussian) картинка смешанная. Chapel был самым медленным для всех рассмотренных задач.
Стоит отметить, что математические функции, используемые в D, были взяты из math API языка C, доступного в D через core.stdc.math, так как математические функции в стандартной библиотеке std.math языка D бывают достаточно медленными. Использованные математические функции приведены здесь. Для сравнения рассмотрим скрипт mathdemo.d, сравнивающий C-функцию логарифма с D-функцией из std.math:
$ ldc2 -O --boundscheck=off --ffast-math --mcpu=native --boundscheck=off mathdemo.d && ./mathdemoTime taken for c log: 0.324789 seconds.Time taken for d log: 2.30737 seconds.

Объект Matrix, используемый в бенчмарке D, был реализован специально из-за запрета на использование модулей вне стандартных языковых библиотек. Чтобы удостовериться, что эта реализация конкурентоспособна, т.е. не представляет собой плохую реализацию на D, я ее сравниваю с библиотекой Mir's ndslice, тоже написанной на D. На диаграмме ниже показано время вычисления матрицы минус время реализации ndslice; отрицательное значение означает, что ndslice работает медленнее, что указывает на то, что используемая здесь реализация не представляет собой негативную оценку производительности D.


Условия тестирования


Код был выполнен на компьютере с операционной системой Ubuntu 20.04, 32 ГБ памяти и процессором Intel Core i9-8950HK @ 2.90GHz с 6-ю ядрами и 12-ю потоками.
$ julia --versionjulia version 1.4.1$ dmd --versionDMD64 D Compiler v2.090.1$ ldc2 --versionLDC - the LLVM D compiler (1.18.0):  based on DMD v2.088.1 and LLVM 9.0.0$ chpl --versionchpl version 1.22.0

Компиляция


Chapel:
chpl script.chpl kernelmatrix.chpl --fast && ./script

D:
ldc2 script.d kernelmatrix.d arrays.d -O5 --boundscheck=off --ffast-math -mcpu=native && ./script

Julia (компиляция не требуется, но может быть запущена из командной строки):
julia script.jl


Реализации


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

Chapel


Chapel использует цикл forall для распараллеливания по потокам. Также используется C-указатели на каждый элемент, а не стандартное обращение к массивам, и применяется guided итерация по индексам:
proc calculateKernelMatrix(K, data: [?D] ?T){  var n = D.dim(0).last;  var p = D.dim(1).last;  var E: domain(2) = {D.dim(0), D.dim(0)};  var mat: [E] T;  var rowPointers: [1..n] c_ptr(T) =    forall i in 1..n do c_ptrTo(data[i, 1]);  forall j in guided(1..n by -1) {    for i in j..n {      mat[i, j] = K.kernel(rowPointers[i], rowPointers[j], p);      mat[j, i] = mat[i, j];    }  }  return mat;}
Код на Chapel был самым трудным для оптимизации по производительности и потребовал наибольшего количества изменений кода.

D


Для распараллеливания кода D используется taskPool потоков из пакета std.parallel. Код на D претерпел наименьшее количество изменений для оптимизации производительности большая польза от использования специфического компилятора и выбранных ключей компиляции (обсуждается далее). Моя реализация Matrix позволяет отобрать столбцы по ссылке с помощью refColumnSelect.
auto calculateKernelMatrix(alias K, T)(K!(T) kernel, Matrix!(T) data){  long n = data.ncol;  auto mat = Matrix!(T)(n, n);  foreach(j; taskPool.parallel(iota(n)))  {    auto arrj = data.refColumnSelect(j).array;    foreach(long i; j..n)    {      mat[i, j] = kernel(data.refColumnSelect(i).array, arrj);      mat[j, i] = mat[i, j];    }  }  return mat;}

Julia


Код Julia использует макрос threads для распараллеливания кода и макрос views для ссылок на массивы. Единственное, что сбивает с толку с массивами в Julia это их ссылочный статус. Иногда, как и в этом случае, массивы будут вести себя как объекты-значения, и на них нужно ссылаться с помощью макроса views, иначе они будут генерировать копии. В других случаях они ведут себя как ссылочные объекты, например, при передаче их в функцию. С этим может быть немного сложно разобраться, потому что вы не всегда знаете, какой набор операций сгенерирует копию, но там, где это происходит, views обеспечивает хорошее решение.
Тип Symmetric позволяет сэкономить немного дополнительной работы, необходимой для отражения в матрице.
function calculateKernelMatrix(Kernel::K, data::Array{T}) where {K <: AbstractKernel,T <: AbstractFloat}  n = size(data)[2]  mat = zeros(T, n, n)  @threads for j in 1:n      @views for i in j:n          mat[i,j] = kernel(Kernel, data[:, i], data[:, j])      end  end  return Symmetric(mat, :L)end
Макросы @ bounds и @ simd в основных функциях использовались для отключения проверки границ и применения оптимизации SIMD к вычислениям:
struct DotProduct <: AbstractKernel end@inline function kernel(K::DotProduct, x::AbstractArray{T, N}, y::AbstractArray{T, N}) where {T,N}  ret = zero(T)  m = length(x)  @inbounds @simd for k in 1:m      ret += x[k] * y[k]  end  return retend
Эти оптимизации достаточно заметны, но очень просты в применении.

Использование памяти


Суммарное время для каждого бенчмарка и общая используемая память была собрана с помощью команды /usr/bin/time -v. Вывод для каждого из языков приведен ниже.

Chapel занял наибольшее общее время, но использовал наименьший объем памяти (почти 6 Гб оперативной памяти):
Command being timed: "./script"User time (seconds): 113190.32System time (seconds): 6.57Percent of CPU this job got: 1196%Elapsed (wall clock) time (h:mm:ss or m:ss): 2:37:39Average shared text size (kbytes): 0Average unshared data size (kbytes): 0Average stack size (kbytes): 0Average total size (kbytes): 0Maximum resident set size (kbytes): 5761116Average resident set size (kbytes): 0Major (requiring I/O) page faults: 0Minor (reclaiming a frame) page faults: 1439306Voluntary context switches: 653Involuntary context switches: 1374820Swaps: 0File system inputs: 0File system outputs: 8Socket messages sent: 0Socket messages received: 0Signals delivered: 0Page size (bytes): 4096Exit status: 0

D расходует наибольший объем памяти (около 20 ГБ оперативной памяти на пике), но занимает меньше общего времени, чем Chapel для выполнения:
Command being timed: "./script"User time (seconds): 106065.71System time (seconds): 58.56Percent of CPU this job got: 1191%Elapsed (wall clock) time (h:mm:ss or m:ss): 2:28:29Average shared text size (kbytes): 0Average unshared data size (kbytes): 0Average stack size (kbytes): 0Average total size (kbytes): 0Maximum resident set size (kbytes): 20578840Average resident set size (kbytes): 0Major (requiring I/O) page faults: 0Minor (reclaiming a frame) page faults: 18249033Voluntary context switches: 3833Involuntary context switches: 1782832Swaps: 0File system inputs: 0File system outputs: 8Socket messages sent: 0Socket messages received: 0Signals delivered: 0Page size (bytes): 4096Exit status: 0

Julia потратила умеренный объем памяти (около 7,5 Гб пиковой памяти), но выполнялась быстрее всех, вероятно, потому что ее генератор случайных чисел является самым быстрым:
Command being timed: "julia script.jl"User time (seconds): 49794.85System time (seconds): 30.58Percent of CPU this job got: 726%Elapsed (wall clock) time (h:mm:ss or m:ss): 1:54:18Average shared text size (kbytes): 0Average unshared data size (kbytes): 0Average stack size (kbytes): 0Average total size (kbytes): 0Maximum resident set size (kbytes): 7496184Average resident set size (kbytes): 0Major (requiring I/O) page faults: 794Minor (reclaiming a frame) page faults: 38019472Voluntary context switches: 2629Involuntary context switches: 523063Swaps: 0File system inputs: 368360File system outputs: 8Socket messages sent: 0Socket messages received: 0Signals delivered: 0Page size (bytes): 4096Exit status: 0

Оптимизация производительности


Процесс оптимизации производительности на всех трех языках был очень разным, и все три сообщества были очень полезны в этом процессе. Но были и общие моменты.
  • Статическая диспетчеризация функций ядра вместо использования полиморфизма. Это означает, что при передаче функции ядра используется параметрический (времени компиляции) полиморфизм, а не динамический (времени исполнения), при котором диспетчеризация с виртуальными функциями влечет за собой накладные расходы.
  • Использование представлений/ссылок, вместо копирования данных в многопоточном режиме, имеет большое значение.
  • Распараллеливание вычислений имеет огромное значение.
  • Знание того, что массив является основным для строки/столбца, и использование этого в вычислениях имеет огромное значение.
  • Проверки границ и оптимизации компилятора дают огромную разницу, особенно в Chapel и D.
  • Включение SIMD в D и Julia внесло свой вклад в производительность. В D это было сделано с помощью флага -mcpu=native, а в Julia это было сделано с помощью макроса @ simd.

С точки зрения специфики языка, наиболее сложным был переход к производительному коду в Chapel, и код в Chapel больше всего изменился: от простых для чтения операций с массивами до использования указателей и управляемых итераций. Но со стороны компилятора было относительно легко добавить --fast и получить большой прирост производительности.

Код на D изменился очень мало, и большая часть производительности была получена за счет выбора компилятора и его флагов оптимизации. Компилятор LDC богат возможностями оптимизации производительности. Он имеет 8 -O уровней оптимизации, но некоторые из них повторяются. Например, -O, -O3 и -O5 идентичны, а других флагов, влияющих на производительность, бесчисленное множество. В данном случае использовались флаги -O5 --boundscheck=off -ffast-math, представляющие собой агрессивные оптимизации компилятора, проверку границ, и LLVM's fast-math, и -mcpu=native для включения инструкций векторизации.

В Julia макросы в рассмотренных ранее изменениях заметно улучшили производительность, но они не были слишком запутанными. Я попробовал изменить уровень оптимизации -O, но это не улучшило производительность.

Качество жизни


В этом разделе рассматриваются относительные плюсы и минусы, связанные с удобством и простотой использования каждого языка. Люди недооценивают усилия, затрачиваемые на повседневное использование языка; необходима значительная поддержка и инфраструктура, поэтому стоит сравнить различные аспекты каждого языка. Читателям, стремящимся избежать TLDR, следует прокрутить до конца данного раздела до таблицы, в которой сравниваются обсуждаемые здесь особенности языка. Было сделано все возможное, чтобы быть как можно более объективным, но сравнение языков программирования является сложным, предвзятым и спорным, поэтому читайте этот раздел с учетом этого. Некоторые рассматриваемые элементы, такие как массивы, рассматриваются с точки зрения Data Science/технических/научных вычислений, а другие являются более общими.

Интерактивность


Программистам нужен быстрый цикл кодирования/компиляции/результата во время разработки, чтобы быстро наблюдать за результатами и выводами для того, чтобы двигаться вперёд либо вносить необходимые изменения. Интерпретатор Julia самый лучший для этого и предлагает гладкую и многофункциональную разработку, а D близок к этому. Этот цикл кодирования/компиляции/результата может быть медленным даже при компиляции небольшого кода. В D есть три компилятора: стандартный компилятор DMD, LLVM-компилятор LDC и GCC-компилятор GDC. В этом процессе разработки использовались компиляторы DMD и LDC. DMD компилирует очень быстро, что очень удобно для разработки. А LDC отлично справляется с созданием быстрого кода. Компилятор Chapel очень медленный по сравнению с ним. В качестве примера запустим Linux time для компилятора DMD и для Chapel для нашего кода матрицы без оптимизаций. Это дает нам для D:
real0m0.545suser0m0.447ssys0m0.101s

Сравним с Chapel:
real0m5.980suser0m5.787ssys0m0.206s

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

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

Документация и примеры


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

Документация Julia наиболее близка по качеству к документации на Python и даёт пользователю очень плавный, детальный и относительно безболезненный переход на язык. Она также имеет богатую экосистему блогов, и темы по многим аспектам языка легкодоступны. Официальная документация D не так хороша и может быть сложной и разочаровывающей, однако существует очень хорошая бесплатная книга Программирование на D, которая является отличным введением в язык, но ни одна единичная книга не может охватить язык программирования целиком и не так много исходных текстов примеров для продвинутых тем. Документация Chapel достаточно хороша для того, чтобы сделать что-то, хотя представленные примеры различаются по наличию и качеству. Часто программисту требуется знать, где искать. Хорошая тема для сравнения библиотеки файлового ввода/вывода в Chapel, D и Julia. Библиотека ввода/вывода Chapel содержит слишком мало примеров, но относительно ясна и проста; ввод/вывод D распределён по нескольким модулям, и документации более сложно следовать; документация по вводу/выводу Julia содержит много примеров, и она ясна и проста для понимания.

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

Поддержка многомерных массивов


Массивы здесь относятся не к массивам в стиле С и С++, доступным в D, а к математическим массивам. Julia и Chapel поставляются с поддержкой массивов, а D нет, но у него есть библиотека Мир, которая содержит многомерные массивы (ndslice). В реализации расчета ядра матрицы я написал свой объект матрицы в D, что несложно, если понимать принцип, но это не то, что хочет делать пользователь. Тем не менее, в D есть линейная библиотека алгебры Lubeck, которая обладает впечатляющими характеристиками производительности и интерфейсами со всеми обычными реализациями BLAS. Массивы Julia, безусловно, самые простые и знакомые. Массивы Chapel сложнее для начального уровня, чем массивы Julia, но они спроектированы для запуска на одноядерных, многоядерных системах и компьютерных кластерах с использованием единого или очень похожего кода, что является хорошей уникальной точкой притяжения.

Мощность языка


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

D был задуман как замена C++ и взял очень много от C++ (а также заимствовал из Java), но делает шаблонное программирование и вычисления времени компиляции (CTFE) намного более удобными для пользователя, чем в C++. Это язык с одиночной диспетчеризацией (хотя есть пакет с мультиметодами). Вместо макросов в D есть mixin для строк и шаблонов, которые служат аналогичной цели.

Chapel имеет поддержку дженериков и зарождающуюся поддержку для ООП с одиночной диспетчеризацией, в нем нет поддержки макросов, и в этих вопросах он ещё не так зрел, как D или Julia.

Конкурентность и параллельное программирование


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

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

Julia имеет хорошую поддержку как конкурентности, так и параллелизма.

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

Стандартная библиотека


Насколько хороша стандартная библиотека всех трех языков в целом? Какие задачи она позволяют пользователям легко выполнять? Это сложный вопрос, потому что при этом учитываются качество библиотеки и фактор документирования. Все три языка имеют очень хорошие стандартные библиотеки. В D самая полная стандартная библиотека, но Julia отличная вторая, потом Chapel, но все никогда не бывает так просто. Например, пользователь, желающий написать бинарный ввод/вывод, может найти Julia самой простой для начинающего; она имеет самый простой, понятный интерфейс и документацию, за ней следует Chapel, а затем D. Хотя в моей реализации программы для чтения IDX-файлов, ввод/вывод D был самым быстрым, но зато код Julia было легко написать для случаев, недоступных на двух других языках.

Менеджеры и экосистема пакетов


С точки зрения документации, использования и возможностей, менеджер пакетов D Dub является наиболее полным. D также имеет богатую экосистему пакетов на веб-сайте Dub, зато менеджер пакетов Julia тесно интегрирован с GitHub и является хорошей пакетной системой с хорошей документацией. У Chapel есть менеджер пакетов, но нет высокоразвитой экосистемы.

Интеграция с Cи


Cи- интероперабельность проста в использовании на всех трех языках; Chapel имеет хорошую документацию, но не так популярен, как другие. Документация на языке D лучше, а документация на языке Julia самая полная. Однако, как ни странно, ни в одной документации по языкам нет команд, необходимых для компиляции вашего собственного кода на C и его интеграции с языком, что является недосмотром, особенно когда дело касается новичков. Тем не менее, в D и Julia легко искать и найти примеры процесса компиляции.

Сообщество


Для всех трех языков есть удобные места, где пользователи могут задавать вопросы. Для Chapel, самое простое место это Gitter, для Julia это Discourse (хотя есть и Julia Gitter), а для D это официальный форум сайта. Julia сообщество является наиболее активным, а затем D, а затем Chapel. Я обнаружил, что вы получите хорошие ответы от всех трех сообществ, но вы, вероятно, получите более быстрые ответы по D и Julia.
Chapel D Julia
Компиляция/ Интерактивность Медленная Быстрая Лучшая
Документация & Примеры Детальные Лоскутные Лучшие
Многомерные массивы Да Только родные
(библиотека)
Да
Мощность языка Хорошая Отличная Лучшая
Конкурентность & Параллелизм Отличная Отличная Хорошая
Стандартная библиотека Хорошая Отличная Отличная
Пакетный менеджер & Экосистема Зарождающаяся Лучшая Отличная
Си -Интеграция Отличная Отличная Отличная
Сообщество Маленькое Энергичное Наибольшее
Таблица характеристик качества жизни для Chapel, D & Julia

Резюме


Если вы начинающий программист, пишущий числовые алгоритмы и выполняющий научные вычисления, и хотите быстрого и простого в использовании языка, Julia это ваш лучший выбор. Если вы опытный программист, работающий в той же области, Julia все еще является отличным вариантом. Если вы хотите более традиционный, промышленный, статически скомпилированный, высокопроизводительный язык со всеми свистоперделками, но хотите что-то более продуктивное, безопасное и менее болезненное, чем C++, то D это ваш лучший вариант. Вы можете написать что угодно в D и получить отличную производительность благодаря его компиляторам. Если вам нужно, чтобы вычисления массивов происходили на кластерах, то Chapel, наверное, самое удобное решение.

С точки зрения грубой производительности в этой задаче, D был победителем, явно демонстрируя лучшую производительность в 5 из 9 эталонных задач. Исследование показало, что ярлык Julia как высокопроизводительного языка это нечто большее, чем просто шумиха он обладает собственными достоинствами в сравнении с высококонкурентными языками. Было сложнее, чем ожидалось, получить конкурентоспособную производительность от Chapel команде Chapel потребовалось много исследований, чтобы придумать текущее решение. Тем не менее, по мере того, как язык Chapel взрослеет, мы сможем увидеть дальнейшее улучшение.
Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru