Копирование файлов

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

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

Речь тут идет об использовании каких-либо приложений, поддерживающих постановку задач копирования файлов в очередь. Я пользуюсь Total Commander.

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

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

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

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

Издержки же на файловый кэш не очень значительны. Во-первых, это память. Но при нынешних ценах на ОЗУ в компьютерах её обычно с избытком, так что это не проблема.
Во-вторых, двойные пересылки память-память. Первый раз при чтении с устройства в буфер системы кэширования, затем второй раз при копировании из кэша в буфер приложения.
При записи те же два этапа сохраняются, только идут в обратной последовательности.
Так как современное ОЗУ весьма производительно, то пересылки память-память не сильно снижают производительность.

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

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

А для самого приложения решил реализовать следующую идею: есть набор потоков-"читателей", по одному на каждое физическое устройство хранения данных, и симметричный набор потоков-"писателей". Еще есть управляющий поток, который формирует задание "читателям", "читатели" в свою очередь читают данные из файла в буфер, это буфер передают соответствующим "писателям".
Идея здесь в том, что пока одно физическое устройство ждет завершения операции ввода/вывода, другое может в параллель тоже что-нибудь прочитать/записать.

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

Как ни обидно, особого выигрыша по сравнению с несколькими копиями copy/xcopy достичь не удалось. 😂 Как, впрочем и проигрыша. У xcopy, кстати, тоже есть опция копирования без кэширования, как раз для больших файлов.
Есть подозрение, что причиной всему небольшие задержки в переключении потоков между "читателям" и "писателями".

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

Ryzen 7 5800X

Походу, это последний американский процессор 😟, что мне удалось оттестировать. В системе 32 ГиБ ОЗУ DDR4 3200 МГц.

Сейчас пойдут графики, а потом кратенький анализ.

 

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

Средняя производительность за 7 лет увеличилась в четыре с лишним раза (от архитектуры PileDriver в 2013 году до Zen3 в 2020).
Однопоточная производительность выросла более чем в два раза на скалярных операциях и в 3.5 раза на векторных. Очень неплохо!

 

Немного скромнее обстоит дело с целочисленными скалярными операциями. Среднее ускорение всего лишь в 3.4 раза.

Однопоточное – "всего лишь" в 1.72 раза. При этом ускорение операции деления более значительно – в 1.81 раза, а вот более простые операции типа сложения и побитовых, ускоряются гораздо хуже – в 1.66 раза. Видимо, эти операции и ранее были оптимизированы неплохо.

Видно, что и многопоточность реализована в новом процессоре более эффективно. Правда, есть странный провал на решении систем из 12 уравнений на типе double, где Ryzen 7 поколения Zen3 сливает Ryzen 5 поколения Zen2. Честно говоря, не знаю даже, как его можно объяснить

Ryzen 7 5700U

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

Процессор относится к энергоэффективным процессорам второго поколения (Zen 2) для мобильных устройств, то бишь ноутбуков, с достаточно скромным теплопакетом в 25 Вт максимум. Кэша третьего уровня немного, всего 8 МиБ.
На борту 16 ГиБ памяти DDR4-3200.

А сейчас результаты тестов. За точку отчета (т. е. за единицу) взята производительность AMD FX-4350.

Сначала посмотрим на производительность операций с плавающей точкой.

 

В принципе, вроде достойно выглядит на фоне десктопного пятого Ryzen'а. Но с учетом чуть более быстрой памяти в ноутбуке я б ожидал большего.
Конечно, он быстрей стареньких Intel'ов, но они с более медленной памятью не сильно от него отстают. Видимо, более новые будут быстрее этого процессора от AMD, но не стоит забывать про ограниченный теплопакет. Процессоры от Intel гораздо более горячие, чем тестируемый, ну или могут быть (наверное?) такие же холодные, но и более медленные. Как-то так.

А вот во многопоточном режиме процессор особо не блещет. У него 8 ядер с поддержкой Hyper-Threading, но при этом он проигрывает десктопному варианту с 6  ядрами!
Видимо, тут сказываются ограничения теплопакета.
Процессоры Intel предыдущих поколений он, конечно, значительно опережает... Но у тех-то по четыре ядра в основном и память более медленная.

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

Теперь оценим многопоточное ускорение на разных размерностях задачи.

Как видим, "загадочный" горб для мобильного процессора на графиках ускорения имеет более выраженный характер.
На текущий момент мне кажется, что фронт этого горба связан с сочетанием сразу двух факторов: недостаточное количество памяти для генерации такого количества систем, что бы можно было более-менее точно замерить производительность на малых размерах задачи. Плюс потоки часто мешают друг другу получать системы для их решения, простаивая в очереди ожидания.
А вот более короткая полка по сравнению с Ryzen 5 связана явно с более маленьким размером кэш-памяти 3-го уровня (8 МиБ против 32 МиБ).
Зато на графике для 32-битных данных хорошо заметно, что память у ноутбука чуть-чуть быстрее (3200 МГц против 3000).

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

 

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

Выводы

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

UInt128

Реализовал все методы для полноценной работы с беззнаковым целым длиной 128 бит (16 байт) на Pascal, реализация только для Delphi под X64, так как большая часть кода на ассемблере. Качайте UInt128.pas, кому надо.

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

Юнит-тесты прогнал, но вполне возможно, что где-то небольшие косяки остались. Если найдете – пишите.

Обратный элемент

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

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

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

Ax + By = R

Здесь A и B ‒ числа, для которых мы ищем частное решение (если R=0, то мы также можем найти наибольший общий делитель, который будет равен значению R с предыдущей итерации метода Евклида, если R=1, то мы находим как раз обратный элемент в кольце вычетов). А x и y ‒ это неизвестные целые коэффициенты, которые нужно найти, что бы выполнялось равенство.
В прошлых постах я несколько нестандартно трактовал их в обратном порядке, когда x и y были числами, а A и B ‒ коэффициентами. Впрочем, так как они вполне симметричны, то суть дела это не меняет.

Для поиска обратного элемента удобнее в качестве A взять модуль, а в качестве B ‒ число, для которого мы ищем обратный элемент.
Тогда после решения диофантова уравнения Ax + By = 1 y будет обратным элементом к B.
Не к каждому B в кольце вычетом по модулю A может быть найден элемент. Это возможно только когда A и B является взаимно простыми числами. В противном случае в результате работы расширенного алгоритма Евклида мы скорее всего получим решение Ax + By = 0, т. е. R с предыдущей итерации будет НОД(A, B), а By mod A  = 0.

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

Вариант для натуральных чисел отличается от целых лишь уравнением:

Ax - By = R

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

Ax₁ - By₁ = R₁,
где  x₁  = 1; y₁ = Q₁ = A div B; R₁ = A mod B,

То на второй

By₂ - Ax₂ = R₂,

где y₂ и x₂ считаются аналогично первой итерации.
Здесь тоже есть тонкость: так как на каждой нечетной итерации коэффициент при B берется со знаком "минус", то обратный элемент должен считаться так: A - y, в то время как на четных итерациях он точно равен y.
Для расчета обратного элемента коэффициент x нам не нужен, поэтому его и вовсе можно не считать.
А для y можно использовать следующую рекуррентную формулу:

Кстати, x считается точно по такой же формуле, но начальные значения поменяны местами.

В результате на чистом паскале получается так:

function getInvElNat(Module, El : UInt64) : UInt64;
var
  b : byte;
  Y1, Y0 : UInt64;
  D, A, R : UInt64;
begin
  A := Module;
  b := 0;
  Y1 := 0;
  Y0 := 1;
  while El > 1 do
  begin
    D := A div El;
    R := A - El*D;
    A := El;
    El := R;
    Result := Y0*D + Y1;
    b := not(b);
    Y1 := Y0;
    Y0 := Result;
  end;
  if b <> 0 then
    Result := Module-Result;
end; 

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

А вот так я переписал на ассемблере:

function getInvElNatASM(Module, El : UInt64) : UInt64;
// Module - RCX, El - RDX, Result - RAX
asm
  push RSI;
  mov RAX, Module;
  mov R8, El;
  mov R9, El;
  xor R10b, R10b; // b
  xor R11, R11; //Y0
  xor RSI, RSI; // Y1;
  inc R11;
  cmp R8, small 1;
  jbe @Finish;
@Loop:
  xor RDX, RDX;
  div R8;
  mov R9, R11;
  imul R9, RAX;
  add R9, RSI;
  not R10b;
  mov RAX, R8;
  mov R8, RDX;
  mov RSI, R11;
  mov R11, R9;
  cmp R8, small 1;
  ja @Loop;
@Finish:
  sub Module, R9;
  test R10b, R10b;
  cmovz RAX, R9;
  cmovnz RAX, Module;
  pop RSI;
end;

Получилось гораздо компактнее, чем целочисленный вариант с длинной арифметикой. Правда, производительность отличается не сильно:
‒ целочисленный вариант на asm ‒ 10.7 млн. оп./с;
‒ натуральный вариант на asm ‒ 11.4 млн. оп./с;
‒ натуральный вариант на Pascal ‒ 7.8 млн. оп./с.

MUL/IMUL

Итак, в прошлом посте я столкнулся с фактом, что полное 128-битное умножение примерно в 8 раз медленнее, чем 64-битное. Как-то медленновато будет!

В чем же дело? А дело, понятно, в коде. Вот в таком:

class operator UInt128.Multiply(Op1, Op2: UInt128): UInt128;
begin
  if Op1.HiPart = 0 then
    if Op2.HiPart = 0 then // малое умножение
      Result := SmallMultiply(Op1.LowPart, Op2.LowPart)
    else
      Result := Op2*Op1.LowPart
  else
    if Op2.HiPart = 0 then
      Result := Op1*Op2.LowPart
    else // большое умножение
      Result := LargeMultiply(Op1, Op2);
end;

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

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

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

Кстати, саму структуру этого оператора умножения я тоже не сам придумал, а подсмотрел у AMD в Software Optimization Guide.
У них есть пример 64-битного умножения в 32-битном режиме, собственно, его можно смело переносить в вариант 128-битного умножения на 64-битных регистрах. Естественно, с учетом того, что свободных регистров в 64-битном режиме поболе будет.
Естественно, в примере нет никаких вызовов вспомогательных процедур, просто переходы на разные участки кода, но смысл такой же.
Ну и надо сказать, что они там тоже активно IMUL используют для короткого умножения.

Тем не менее, я при переносе вышеприведенного кода на ассемблер пошел своим путем и использовал полную версию беззнакового умножения. Видимо, в силу упертого консерватизма.
И получил в результате примерно 151 млн. 128-битных умножений в секунду, ускорив исходный код в 1.7 раза. Неплохо!
Теперь 128-битное умножение всего лишь в 4.5 раза медленнее, чем 64-битное, что в принципе вполне приемлемо.

И вот я смотрю на код и вот не нравятся мне эти условные переходы. Думаю: "А что будет, если я вообще от них откажусь?"
Отказываюсь от проверок, тупо всегда умножая, как будто операнды полные , провожу несколько экспериментов с регистровой оптимизацией и еще немного ускоряю полное умножение!
В результате получаю 165 млн. оп./с или в 4.1 раза медленнее 64-битного умножения. Отлично!

Но, возможно, я вместе с водой выплеснул и ребенка? Ведь исходный пример от AMD не просто так был придуман и позволял снизить количество операций умножения, когда один или оба операнды имели данные меньше 64-бит длиной.
Поэтому тестирую вариант, когда один из операндов имеет 128-битные данные, а вот у второго данные помешаются в 64 бита.
С условными операторами это дает 159 млн. оп./с, что совсем не намного быстрее, чем когда оба оператора полноразрядные. А вот без условных операторов, когда всегда выполняется 128-битное умножение полностью, скорость возрастает до 168 млн. оп./с.
То есть полное умножение оказывается быстрее сокращенного!

Почему так? Видимо, из-за условных операторов и сброса конвейера. У меня есть предположение, что этот код из Optimization Guide кочует из одной версии руководства в другую, а написан он был давным-давно, в эпоху 386 или 486 процессоров.
Тогда операции умножения выполнялись гораздо дольше, (от 9 до 38 тактов на 486 процессоре), конвейер либо вообще отсутствовал, либо был очень короткий, а операции сравнения были почти такими же быстрыми, как и сейчас. Поэтому для такой архитектуры использование переходов в процедуре длинного умножения было вполне оправдано.
Но на современных процессорах команда умножения выполняется гораздо быстрее, а конвейер имеет значительную длину, так что его сброс стоит очень дорого. Так что, по всей видимости, для 128-разрядных умножений использовать условные переходы невыгодно.
За исключением, пожалуй, того случая, когда данные обеих операндов меньше 64 бит. К сожалению, оттестировать такой вариант очень сложно, так как результат умножения очень быстро растет.
Но, честно говоря, я не вижу смысла оптимизации именно для такого случая. Если данные столь короткие, то не проще ли для их обработки использовать 64-битный тип?
А если данные все же велики, то вероятность того, что оба операнда будут меньше 64 бит, мала и встречаться будет нечасто, так что потери производительности от такой ситуации будут крайне незначительны.

Ну и наконец про IMUL. Ну все же используют, а я чего-то не стал... Ну, попробую. Я, собственно, не ожидал какого-то увеличения производительности на моем PileDriver, исходя из производительности умножения (короткое и длинное умножение занимают одинаковое количество тактов на этой архитектуре). Да, получилось на одну команду меньше и регистры веселее использовались. Но вот скорость стабильно оказывалась на несколько процентов меньше, чем в случае полного умножения.
Не знаю, с чем это связано. Вообще даже идей нет. Допускаю, что на Intel и на AMD Ryzen с коротким умножением эта функция будет выполняться на те же несколько процентов быстрее. Но в целом это ничего не меняет, поэтому оставил в коде беззнаковую полную версию MUL.

Умножение UInt128

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

Тестирование проводил на нечетных числах, так как умножение на четные быстро обнуляет один из операндов на ограниченном по точности типе.
В результате Pascal в релизе показал 680 млн. 64-битных умножений в секунду, а мое умножение 128-битного на 64-битное - всего около 170 млн. Примерно в 4 раза медленнее. Хотя должно бы быть теоретически медленнее всего чуть больше двух раз. Такова плата за универсальность.

А вот умножение 128 на 128 бит дает 88 млн. умножений в секунду, что уже в 8 раз медленнее чисто 64-битного умножения, что странно. Ведь такая 128-битная операция требует лишь три 64-битных умножения и два сложения. Надо внимательнее посмотреть на свой код, видимо, там можно что-нибудь оптимизировать, я даже догадываюсь, что 😁.

Оценить, насколько хорошо работает PascalABC.NET с его BigInteger достаточно сложно. Дело в том, что он имеет "бесконечную" точность, рассчитывая полное произведение, в том время как мой тип старшую часть, выходящую за 128 бит, теряет. В результате множитель в процессе теста на BigInteger постоянно и очень быстро растет, а вместе с тем растет и вычислительная сложность каждого умножения.
В результате я замерял его производительность так: сначала замерил время выполнения N умножений, отбрасывая после каждого все то, что выходило за пределы 128 бит. с помощью побитового AND.
Затем замерил время N операций AND, и вычел одно время из другого.

В результате BigInteger показал 5.5 млн. умножений в секунду, или в 16 раз медленнее моего варианта 128 на 128 бит. Я считаю, что очень неплохо, с учетом того BigInteger считал полное умножение, получая 256 бит результата, что требует еще одного 64-битного умножения и кучи сложений.
Поначалу я предполагал, что в BigInteger используется универсальный алгоритм умножения, например, методом Фурье, но, судя по всему, там используют разные алгоритмы в зависимости от длины операндов. И на относительно коротких умножениях они используют обычный вариант длинного умножения.