Дело было вечером, делать было нечего.
Наткнулся на компилятор восток, работал в убунте
стало интересно, взял https://github.com/Vostok-space/vostok/blob/master/example/BubbleSort.mod
сбинарил. размер массива 100К.
потом стараясь максимально идентично сделал в NET8 последней, собрал релиз.
восток выполняется меньше 3 сек.
дотнет более 10. ну я бы понял, если бы 1-2 сек. но в 3 раза!
Даже zig в режиме fast оказался чуточку медленнее(а в нем даже сборщика мусора нет).
Вообщем, я озадачен. Есть предположения почему так?
Здравствуйте, Разраб, Вы писали:
Р>Дело было вечером, делать было нечего. Р>Наткнулся на компилятор восток, работал в убунте Р>стало интересно, взял https://github.com/Vostok-space/vostok/blob/master/example/BubbleSort.mod Р>сбинарил. размер массива 100К. Р>потом стараясь максимально идентично сделал в NET8 последней, собрал релиз.
Собрал Native AOT?
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, rudzuk, Вы писали:
R>Здравствуйте, Разраб, Вы писали:
Р>> сбинарил. размер массива 100К. R>... Р>> Вообщем, я озадачен. Есть предположения почему так?
R>А массив как инициализируется?
MODULE Hello;
IMPORT
Out,
BubbleSort;
CONST
hello = "HELLO";
m = 100000;
VAR
a : ARRAY m OF REAL;
i : INTEGER;
e : REAL;
BEGIN
e := FLT(m);
FOR i:=0 TO m - 1 DO
a [ m - i - 1 ] := e;
e := e - 1.0;
END;
BubbleSort.Sort(a);
Out.String(hello);
Out.Ln;
END Hello.
var m = 100_000;
var a = new double[m];
var s = (double)m;
for (var i = 0; i < m; i++)
{
a[i] = s;
s = s - 1;
}
Sort(a);
Console.WriteLine("HeLLO");
static void Sort(double[] a)
{
var Swap = (ref double x, ref double y) =>
{
var t = x;
x = y;
y = t;
};
for (var i = 0; i < a.Length; i++)
for (var j = 0; j < a.Length - 1 - i; j++)
if (a[j + 1] < a[j])
Swap(ref a[j + 1], ref a[j]);
}
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, Разраб, Вы писали:
Р>>Дело было вечером, делать было нечего. Р>>Наткнулся на компилятор восток, работал в убунте Р>>стало интересно, взял https://github.com/Vostok-space/vostok/blob/master/example/BubbleSort.mod Р>>сбинарил. размер массива 100К. Р>>потом стараясь максимально идентично сделал в NET8 последней, собрал релиз.
S> Собрал Native AOT?
перепроверил, под аот стабильно на 3,5 сек медленнее. еще страньше
Здравствуйте, Darky Darkov, Вы писали:
DD>Здравствуйте, Разраб, Вы писали:
Р>>потом стараясь максимально идентично сделал в NET8 последней, собрал релиз. DD>А покажите исходники
чуть выше шарп, а еще попробовал на F#, вот он вообще не завершается. тут вообще чертовщина))
let len = Array.length
let swap<'a> (arr: array<'a>, i, j) =
let t = arr[i]
arr[i] <- arr[j]
arr[j] <- t
let sort arr =
let ln = len(arr)
for i = 0 to ln - 1 do
for j = 0 to ln - 2 - i do
if arr[j + 1] < arr[j] then
swap (arr, j + 1, j)
let max = 100_000
let value = float(max)
let arr = Array.init max (fun i -> value - float (i))
sort arr
printfn "HELLO"
Р>var m = 100_000;
Р>var a = new double[m];
Р>var s = (double)m;
Р>for (var i = 0; i < m; i++)
Р>{
Р> a[i] = s;
Р> s = s - 1;
Р>}
[cs]
for (var i = 0; i < a.Length; i++)
и солнце б утром не вставало, когда бы не было меня
Ну неплохо было бы код метода BubbleSort.Sort(a) посмотреть и убедиться что они таки идентичны.
По реализации C#: насколько помню, в классическом пузырьке нужно во внешнем цикле постоянно чекать что ни одного swap не произошло и тогда завершаться.
Ну т.е. у пузырька худший случай O(N^2), а если повезет, то выпадет O(N). Ваш же код гарантированно N^2 молотит.
Р>Вообщем, я озадачен. Есть предположения почему так?
не вижу в коде замера времени. ты вместе с запуском и завершением процесса мерил, что ли?
замерь строго вызов метода Sort(), причем как минимум второго вызова (при первом может работать JIT) и надежнее несколько замеров в цикле сделать
Здравствуйте, syrompe, Вы писали:
S>Ну неплохо было бы код метода BubbleSort.Sort(a) посмотреть и убедиться что они таки идентичны.
S>По реализации C#: насколько помню, в классическом пузырьке нужно во внешнем цикле постоянно чекать что ни одного swap не произошло и тогда завершаться.
S>Ну т.е. у пузырька худший случай O(N^2), а если повезет, то выпадет O(N). Ваш же код гарантированно N^2 молотит.
Здравствуйте, gandjustas, Вы писали:
G>Здравствуйте, Разраб, Вы писали:
Р>>Вообщем, я озадачен. Есть предположения почему так?
G>Неправильно мерил?
/bin/time app
Здравствуйте, rudzuk, Вы писали:
R>Здравствуйте, Разраб, Вы писали:
Р>> Дело было вечером, делать было нечего. Р>> Наткнулся на компилятор восток, работал в убунте
R>Это же не компилятор, а транслятор
Р>> стало интересно, взял https://github.com/Vostok-space/vostok/blob/master/example/BubbleSort.mod Р>> сбинарил.
R>В какой язык транслировал и какой код получился на выходе? Чем компилировал? Просто интересно.
ставил из снап компилил опцией to-bin думаю clang
Здравствуйте, L_G, Вы писали:
Р>>Вообщем, я озадачен. Есть предположения почему так?
L_G>не вижу в коде замера времени. ты вместе с запуском и завершением процесса мерил, что ли? L_G>замерь строго вызов метода Sort(), причем как минимум второго вызова (при первом может работать JIT) и надежнее несколько замеров в цикле сделать
Здравствуйте, _FRED_, Вы писали:
FRE> Р>/bin/time app
FRE> То есть вы и время инициализации данных заодно и замерили? В дотнете воспользуйтесь стопвотчем и выведите на консоль результат.
Р>static void Sort(double[] a) Р>{ Р> var Swap = (ref double x, ref double y) => Р> { Р> var t = x; Р> x = y; Р> y = t; Р> };
Р> for (var i = 0; i < a.Length; i++) Р> for (var j = 0; j < a.Length — 1 — i; j++) Р> if (a[j + 1] < a[j]) Р> Swap(ref a[j + 1], ref a[j]); Р>} Р>[/cs]
Ух ты еще и делегат пришпандорил!
Попробуй
static void Sort(double[] a)
{
for (var i = 0; i < a.Length; i++)
for (var j = 0; j < a.Length - 1 - i; j++)
if (a[j + 1] < a[j])
Swap(ref a[j + 1], ref a[j]);
//[MethodImpl(MethodImplOptions.AggressiveInlining)] можно попробовать. Хотя и так должен быть инлайнингvoid Swap(ref double x, ref double y)
{
var t = x;
x = y;
y = t;
}
}
Здравствуйте, Serginio1, Вы писали:
S>Ух ты еще и делегат пришпандорил!
S> Swap(ref a[j + 1], ref a[j]);
S>//[MethodImpl(MethodImplOptions.AggressiveInlining)] можно попробовать. Хотя и так должен быть инлайнинг
S> void Swap(ref double x, ref double y)
Это не делегат, а обычная локальная функция.
Help will always be given at Hogwarts to those who ask for it.
S>> Swap(ref a[j + 1], ref a[j]);
S>>//[MethodImpl(MethodImplOptions.AggressiveInlining)] можно попробовать. Хотя и так должен быть инлайнинг
S>> void Swap(ref double x, ref double y)
_FR>
_FR>Это не делегат, а обычная локальная функция.
То что выше это локальная функция, которую я предложил вместо.
static void Sort(double[] a)
{
var Swap = (ref double x, ref double y) =>
{
var t = x;
x = y;
y = t;
};
for (var i = 0; i < a.Length; i++)
for (var j = 0; j < a.Length - 1 - i; j++)
if (a[j + 1] < a[j])
Swap(ref a[j + 1], ref a[j]);
}
Окей, принимается. В исходном варианте такой же N^2.
Запустил ваш код и дело таки похоже в делегате. Ну скорее всего в лишнем копировании данных для его вызова.
Вот такой код работает на 12 секунд быстрее вашего (21с против 33с) на моей машине:
using System.Diagnostics;
var m = 100_000;
var a = new double[m];
var s = (double)m;
for (var i = 0; i < m; i++)
{
a[i] = s;
s = s - 1;
}
var sw = new Stopwatch();
sw.Start();
Sort(a);
Console.WriteLine("HeLLO");
Console.WriteLine(sw.Elapsed);
static void Sort(double[] a)
{
for (var i = 0; i < a.Length; i++)
for (var j = 0; j < a.Length - 1 - i; j++)
if (a[j + 1] < a[j])
{
var t = a[j+1];
a[j + 1] = a[j];
a[j] = t;
}
}
S>Попробуй S>[cs] S>static void Sort(double[] a) S>{
Исходный вариант автора в релизе — 9с, в дебаге — 30с
Ваш вариант: в релизе — 5,5с, в дебаге 26с
Вариант совсем без отдельного метода Swap: в релизе — 5,5с, в дебаге 21.5
Здравствуйте, Serginio1, Вы писали:
S>Ух ты еще и делегат пришпандорил!
S>Попробуй
Тоже самое, была мысль что раз после сортировки нигде не пользуется массив, то и сортировки нет,
заменил вывод "hello" на a[0]. не помогло.
Мерял под виндой
(Measure-Command { dotnet run -c release | Out-Default }).ToString()
Здравствуйте, Разраб, Вы писали:
S>>Ух ты еще и делегат пришпандорил!
S>>Попробуй Р>Тоже самое, была мысль что раз после сортировки нигде не пользуется массив, то и сортировки нет, Р>заменил вывод "hello" на a[0]. не помогло. Р>Мерял под виндой Р>
Р>(Measure-Command { dotnet run -c release | Out-Default }).ToString()
Р>
Исходный вариант автора в релизе — 9с, в дебаге — 30с
Ваш вариант: в релизе — 5,5с, в дебаге 26с
Вариант совсем без отдельного метода Swap: в релизе — 5,5с, в дебаге 21.5
То есть Swap как локальная функция инлайнится
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Разраб, Вы писали:
Р>чуть выше шарп, а еще попробовал на F#, вот он вообще не завершается. тут вообще чертовщина)) Р>
Р>let sort arr =
Р>
Оказалось, всего-навсего надо было:
let sort (arr: float array) = ()
Теперь F# всего на 1 секунду медленней C#
не так уж и плохо, странно, что вывод типа, получился неверный, даже если вызвать как arr |> sort,
такая запись обычно помогает с выводом типа. Возможно пофиксять в 9ке. Запостил на форуме сообщества.
Я однажды писал на С++ прогу, в которой использовал стандартный дек.
Пишу, никого не трогаю, примуса починяю: сначала в Студии, потом в Кодеблоксе на винде.
Стандартный С++.
Оптимизация, все дела.
И тут выясняется, что прога из-под mingw работает в 5 (ПЯТЬ) раз быстрее из-под-студийной.
В релизе!
Что за хрень?!
Всегда было не более 10-12-15%!
А тут в 5 раз!
Я в конце-концов задал вопрос на РСДН
Один перец, имевший аналогичный опыт ответил, что дек в STL из-под Студии реализован через задницу.
Типа используй вектор.
Я, конечно так и поступил
И получил свои стандартные 10-12-15%.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, Serginio1, Вы писали:
S>>>Ух ты еще и делегат пришпандорил! _FR>>Это не делегат, а обычная локальная функция. S>То что выше это локальная функция, которую я предложил вместо.
Точно, виноват, у топикстартера действительно делегат вместо функции.
Help will always be given at Hogwarts to those who ask for it.
специально замерил сегодня под виндой
локальную функцию
делегат
без фукции(с аот и без)
по среднему никакой разницы между 1 и 2, небольшое ускорение во 3 но без заметной разницы с аот.
инициализация порядка 0,010-0,020 мс
т.е. все время уходит на сортировку.
S>>говорит, что разница есть
Р>специально замерил сегодня под виндой Р>локальную функцию Р>делегат Р>без фукции(с аот и без) Р>по среднему никакой разницы между 1 и 2, небольшое ускорение во 3 но без заметной разницы с аот. Р>инициализация порядка 0,010-0,020 мс Р>т.е. все время уходит на сортировку.
Странно, что разное время у тебя и syrompe разные результаты.
Такое возможно если данные упорядоченные изначально.
А они в твоем тесте упорядочены, но обратную сторону, то есть должна постоянно вызываться Swap
Странно, что нет разницы между делегатом и локальной функцией. То есть основное время уходит на сравнение.
А твой REAL точно соответствует double?
А атрибут не влияет?
[MethodImpl(MethodImplOptions.AggressiveInlining)]// можно попробовать. Хотя и так должен быть инлайнингvoid Swap(ref double x, ref double y)
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Разраб, Вы писали:
Р> т.е. все время уходит на сортировку.
Покажи, как ты вообще этот обероновский код собрал. Я поставил восток, но при попытке собрать получаю ошибку в первой же строке. Видимо делаю что-то не так.
Здравствуйте, rudzuk, Вы писали:
R>Здравствуйте, Разраб, Вы писали:
Р>> т.е. все время уходит на сортировку.
R>Покажи, как ты вообще этот обероновский код собрал. Я поставил восток, но при попытке собрать получаю ошибку в первой же строке. Видимо делаю что-то не так.
из рабочего каталога(где лежит модуль)
vostok to-bin <Имя главного модуля> . -m .
(-m — это где искать модули, первая точка куда бинарь положить)
Что еще удивительно, так это то что сам алгоритм на обероне
выглядит наиболее просто и вызывает меньше всего сомнений
особенно если сравнивать с зиг который позиционирует себя как дзен.
Отсутствие в нем for i to m заставило меня совершить ошибку при работе со счетчиком вложенного цикла.
ближе всего синтаксически оказался F#
хотя и он неожиданно сломался на выводе типов(obj вместо double) ))
В защиту dotnet могу сказать, что питон оказался невероятно медленным в этой задаче
Здравствуйте, Serginio1, Вы писали:
S> А твой REAL точно соответствует double?
оттранслировал в си. да. S> А атрибут не влияет?
заметной нет. Я тестил только релизы и только в консоли.
Енесколько раз запускал, т.к. все время что-то параллельно мешает.
Но среднее все время стабильно.
Здравствуйте, Разраб, Вы писали:
S>> А твой REAL точно соответствует double? Р>оттранслировал в си. да. S>> А атрибут не влияет? Р>заметной нет. Я тестил только релизы и только в консоли. Р>Енесколько раз запускал, т.к. все время что-то параллельно мешает. Р>Но среднее все время стабильно.
Вот интересно тогда ассемблерный код сравнить AOT и сишный
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, rudzuk, Вы писали:
R>Здравствуйте, Разраб, Вы писали:
Р>> из рабочего каталога(где лежит модуль) Р>> vostok to-bin <Имя главного модуля> . -m .
R>Все так и делал, получаю (исходник — твой Hello.mod; vostok --version: ost 0.0.10.dev): R>
0) Expected statement 1 : 1
Скачал последний релиз 9-10(исходники)
собрал бутстрап(init)
потом Build
в папке vostok создал папке bb(положил в нее Hello.mod, BubblSort.mod)
из родительской
result/ost run to-bin Hello bb/hello -infr . -m bb
xubuntu lts последняя
Здравствуйте, Serginio1, Вы писали:
S> Вот интересно тогда ассемблерный код сравнить AOT и сишный
хотел, но sharplab.io заругался да и не силен я в асм
S>> Вот интересно тогда ассемблерный код сравнить AOT и сишный Р>хотел, но sharplab.io заругался да и не силен я в асм
Не там надо дисассемблировать. А народ здесь поможет! «Хакер»: Учимся анализировать программы для x86 с нуля
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Разраб, Вы писали: Р> Скачал последний релиз 9-10(исходники) Р> собрал бутстрап(init) Р> потом Build Р> в папке vostok создал папке bb(положил в нее Hello.mod, BubblSort.mod) Р> из родительской Р> result/ost run to-bin Hello bb/hello -infr . -m bb Р> xubuntu lts последняя
У меня Ubuntu 22.04. vostok ставил из снапа. В результате, удалось запустить опустив параметр to-bin: vostok ./Hello.mod . -m . Он создает папку в tmp, куда складывает сгенерированный си-код, собранный бин и запускает его. Результаты у меня такие: