Начав изучение Scala, я сразу столкнулся с тем, что функциональная реализация простейшего алгоритма быстрой сортировки работает радикально медленней и потребляет существенно больше памяти, чем аналогичная императивная реализация. При этом никто не спорит, что функциональный код более краток, выразителен, и устойчив к ошибкам. Переписав оба примера на Rust, я обнаружил несколько важных вещей, которыми и хочу поделиться. Подробности под катом, а здесь приведу лишь краткие выводы:
- Для императивной реализации — выигрыш от Rust получился всего 20 %. Это означает, что JVM вплотную приблизилась к нативной производительности, и тут уже нечего улучшать.
- Для функциональной реализации — Rust оказался быстрее в 4.5 раза, потребление памяти снизилось в 5.5 раза, а отсутствие сборщика мусора сделало программу более стабильной (меньше разброс показателей). Это интересно для тех, кто хочет писать быстрые функциональные программы.
- Концепция единственного владельца данных (и единственной мутабельной ссылки), принятая в Rust, очень близка концепции иммутабельности, в результате чего функциональные алгоритмы, основанные на неизменяемости, рекурсии и копировании, легко ложатся на Rust практически без переписывания, тогда как императивные алгоритмы заставляют редизайнить код, учитывать мутабельность ссылок, времена жизни, и т.д.
Вывод — Rust как будто специально создан для ФП, хотя возможности его синтаксиса пока не дотягивают до Scala.
Итак, начнем со Scala и реализуем быструю сортировку в 2-х стилях:
Императивно — используем один и тот же массив, переставляя в нем элементы с помощью рекурсивной процедуры. Мы видим многословный код, потенциально уязвимый для опечаток, но оптимально использующий память, и максимально быстрый.
def sort_imp(arr: Array[Double]) {
def swap(i: Int, j: Int) {
val t = arr(i)
arr(i) = arr(j)
arr(j) = t
}
def sort1(l: Int, r: Int) {
val pivot = arr((l + r) / 2)
var i = l
var j = r
while (i <= j) {
while (arr(i) < pivot) i += 1
while (arr(j) > pivot) j -= 1
if (i <= j) {
swap(i, j)
i += 1
j -= 1
}
}
if (l < j) sort1(l, j)
if (i < r) sort1(i, r)
}
if (arr.length > 1)
sort1(0, arr.length - 1)
}Функционально — используем рекурсивную функцию, которая создает три новых массива, и затем возвращает их объединение. Очень компактный и красивый код, практически негде ошибиться, но очень медленный и прожорливый (бедный, бедный GC).
def sort_fun(arr: Array[Double]): Array[Double] = {
if (arr.length <= 1)
arr
else {
val pivot = arr(arr.length / 2)
Array.concat(
sort_fun(arr filter (pivot > _)),
arr filter (pivot == _),
sort_fun(arr filter (pivot < _))
)
}
}Бенчмаркинг ($ sbt run) на массиве 10 млн. случайных чисел и моем дохлом ноутбуке:
- императивно — 2.5 секунды
- функционально — 40 секунд
Как правильно считать память приложения я не знаю, но сам процесс java занял 3.6 Гб.
UPD
Скомпилировал в нативный код через LLVM с опцией nativeMode := «release» и сборщиком мусора «immix gc», результат получился еще хуже:
- императивно — 2.3 секунды
- функционально — 63 секунды
Перепишем то же самое на Rust:
Императивно — алгоритм не изменился, единственная проблема в том, что внутрь функций пришлось явно передавать мутабельную ссылку на исходный массив, так как замыкания для внутренних функций не работают, а использование специального синтаксиса замыканий, создает проблемы при рекурсии. Если наш алгоритм будет сложнее, мы можем столкнуться с ограничениями borrow-checker.
fn sort_imp(arr: &mut Vec<f64>) {
fn swap(arr: &mut Vec<f64>, i: usize, j: usize) {
let t = arr[i];
arr[i] = arr[j];
arr[j] = t;
};
fn sort1(arr: &mut Vec<f64>, l: usize, r: usize) {
let pivot = arr[(l + r) / 2];
let mut i = l;
let mut j = r;
while i <= j {
while arr[i] < pivot { i += 1; }
while arr[j] > pivot { j -= 1; }
if i <= j {
swap(arr, i, j);
i += 1;
j -= 1;
}
}
if l < j { sort1(arr, l, j); }
if i < r { sort1(arr, i, r); }
};
if arr.len() > 1 {
sort1(arr, 0, arr.len() - 1);
}
}Функционально — мы видим, что алгоритм идентичен, однако синтаксис Rust хуже приспособлен для функциональщины, пришлось объявлять промежуточный вектор.
Последовательное применение iter() и filter() к элементам массива приводит к тому, что параметр замыкания x получает тип &&f64, и двойную ссылку приходится разыменовывать **. Нужно явно клонировать отфильтрованные значения. Сигнатура функции append() требует именно мутабельную ссылку, а не сам вектор, что также увеличивает количество букв.
fn sort_fun(arr: Vec<f64>) -> Vec<f64> {
if arr.len() <= 1 {
arr
} else {
let pivot = arr[arr.len() / 2];
let mut a = Vec::<f64>::with_capacity(arr.len());
a.append(&mut sort_fun(arr.iter().filter(|x| pivot > **x).cloned().collect()));
a.append(&mut arr.iter().filter(|x| pivot == **x).cloned().collect());
a.append(&mut sort_fun(arr.iter().filter(|x| pivot < **x).cloned().collect()));
a
}
}UPD
Более красивый вариант:
fn sort_fun(arr: Vec<f64>) -> Vec<f64> {
if arr.len() <= 1 {
arr
} else {
let pivot = arr[arr.len() / 2];
[
sort_fun(arr.iter().filter(|&&x| pivot > x).cloned().collect()),
arr.iter().filter(|&&x| pivot == x).cloned().collect(),
sort_fun(arr.iter().filter(|&&x| pivot < x).cloned().collect()),
]
.concat()
}
}Можно было бы попытаться сделать код еще красивее, применив вместо объединения массивов — объединение итераторов iter().filter(...).chain(...). Это был бы полный zero-cost, но в итераторе мы не можем определить количество элементов, значит не можем поделить его пополам, а значит — реализовать алгоритм. Но в других случаях ленивые итераторы это красиво, экономно и быстро.
Обратите внимание — в императивный алгоритм я передаю мутабельную ссылку на массив, а в функциональный — сам массив, который автоматически уничтожается при выходе из функции (также уничтожаются все временные массивы на каждом шаге рекурсии).
Бенчмаркинг ($ cargo build --release):
- императивно — 2 секунды
- функционально — 9 секунд
Максимальное потребление памяти — 650 Мб.
В сухом остатке:
Если писать императивно, с использованием общего изменяемого состояния — прикладному программисту нет смысла переходить с управляемых языков на компилируемые, так как выигрыш в производительности не компенсирует сложности программирования и многословности исходных текстов. Однако, если писать функционально — пожалуй, я рассмотрю возможность использовать Rust в энтерпрайз-приложениях, так как всего лишь небольшое увеличение количества букв в исходном коде приводит к радикальному ускорению и экономии памяти, отсутствие сборщика мусора делает функциональные программы на Rust более стабильными, а безопасная работа с памятью не позволит выстрелить в ногу (да, null в нем тоже нет).
В мире есть много быстрых и выразительных ООП-языков, а по настоящему быстрых zero-cost функциональных языков — не очень. И если Rust будет двигаться в этом направлении — возможно ФП-подход найдет больше сторонников. Тем более, что по итогам 2019 года и Scala и Rust показали существенный рост популярности на фоне спада мейнстримных языков.
Полный текст на Scala.
Полный текст на Rust.
Спасибо за внимание.
Комментарии (227)
nikbond
28.12.2019 16:35Когда речь началась о производительности, я почему-то подумал что будет разбор вопроса о том, почему ФП-стайл чейны на итераторах быстрее императивных циклов.
А тут что-то непонятное — в обоих случаях уяснили, что ФП вариант медленнее. И что из этого следует? Какой ответ на вопрос из заголовка?
balajahe Автор
28.12.2019 16:43почему ФП-стайл чейны на итераторах быстрее императивных циклов
А почему они должны быть быстрее, тут же очевидно не распараллелить.
Hirrolot
28.12.2019 17:11Потому что компилятор имеет больше контекста в случае с итераторами.
https://doc.rust-lang.org/stable/book/ch13-04-performance.html
yamlevekke
28.12.2019 16:41Очень компактный и красивый код, практически негде ошибиться, но очень медленный и прожорливый (бедный, бедный GC).
Действительно, очень красиво. Знаете ли вы другие языки, которые позволяют писать так же красиво? Не обязательно более эффективные.yamlevekke
28.12.2019 16:49Сам себе отвечу — один из таких языков.
technic93
28.12.2019 17:18чтобы было заметнее вставлю кодом с вашего позволения
vector<double> sort(vector<double> vec) { if(size(vec) <= 1) { return vec; } else { auto pivot = vec[size(vec) / 2]; return concat_view( sort(vec | filter(_ < pivot)), vec | filter(_ == pivot), sort(vec | filter(_ > pivot)) ); } }
PsyHaSTe
29.12.2019 13:57+1Как в хаскелле люди пишут код с
$,<$>,<*>,>>=и прочим все страшно пугаются и бегают кругами в панике.
Как в плюсах люди переопределяют|,&,<<,>>и прочее так все сразу радуются как красиво и компактно получается.
Вы уж определитесь)
yamlevekke
29.12.2019 14:41-4Как в хаскелле люди пишут код с $, <$>, <*>, >>= и прочим все страшно пугаются и бегают кругами в панике.
Это синтаксический мусор.
Как в плюсах люди переопределяют |, &, <<, >> и прочее так все сразу радуются как красиво и компактно получается.
В том и дело, что они переопределяют и выглядит это не как синтаксический мусор. И работает не как мусор. Пайп через | — выглядит нормально и привычно. Пайп через >>= — синтаксиеский мусор.
К тому же, дело не в самих символах, а в том как они используются и читаются.
Вы уж определитесь)
Уже давно всё определено. Смотри на этот код — он идеален. Смотрим на показанное ниже "хаскель" — он мусор.
Повторю причины. Семантически хаскель перегружен всяких бесполезным мусором, который везде торчит. Именно поэтому там так много всяких символов — это попытка адептов залатать эту дуры. Если дать каждому элементу название хоть в 5-6 символов — портянка разрастётся в 10 раз. От того этот мусор и существует — он скрывает под собою избыточность и убогость дизайна. Вернее его отсутствие.
PsyHaSTe
29.12.2019 14:44+4В том и дело, что они переопределяют и выглядит это не как синтаксический мусор. И работает не как мусор. Пайп через | — выглядит нормально и привычно. Пайп через >>= — синтаксиеский мусор.
Потому что? Потому что "никаквси"? Ну это аргумент, да.
Уже давно всё определено. Смотри на этот код — он идеален. Смотрим на показанное ниже "хаскель" — он мусор.
Очередня зарисовка "Идеальные плюсы, а все остальные языки — мусор".
Ага, спасибо. Пеши исчо.
0xd34df00d
29.12.2019 19:53Ага, спасибо. Пеши исчо.
Не надо, пожалуйста. У человека уже третий виртуал всё же.
TargetSan
29.12.2019 20:09Он тут раньше появлялся под другим виртуалом?
0xd34df00d
29.12.2019 20:22Да. Первые несколько комментариев пишет нормально, потом ломается и начинает про методички, лозунги, мусор, скриптуху, вот это вот всё.
PsyHaSTe
29.12.2019 20:27Если я правильно понимаю товарищ зядлый ЛОРовец. Со всем соответствующим.
codemax
30.12.2019 12:47Скорее даже заядлый поехавший. Пара нормальных ответов и затем скатывание в истерику и брызганье слюной. И не только слюной, да. Даже для заядлых ЛОРовцев это не нормально.
TheShock
30.12.2019 16:49Я не вчитывался там пораньше что было, но вы во вдвоём сейчас настолько впали в осуждение личности, что даже слегка неприятно это читать.
codemax
30.12.2019 18:34По одному комментарию с каждого — это насколько мы «впали в обсуждение»? И да, «обсуждалась» тут скорее не личность, а явление ;) Многим уже, к сожалению, знакомое. И здесь, и на том самом ЛОРе.
Cerberuser
29.12.2019 18:21+1Пайп через | — выглядит нормально и привычно. Пайп через >>= — синтаксиеский мусор.
Привычно кому? Тем, кто двадцать лет программирует на C++? Или это намёк на то, что любой нормальный программист должен уметь работать с консолью (в том числе и с тамошними пайплайнами)?
Siemargl
29.12.2019 22:22Привычно кому? Тем, кто двадцать лет программирует на C++? Или это намёк на то, что любой нормальный программист должен уметь работать с консолью (в том числе и с тамошними пайплайнами)?
Хм, в Юниксе и даже ДОСе было так, почему вдруг нет?TargetSan
29.12.2019 22:45+1Не сказал бы что шелл — хороший пример здесь. Слишком отличается по целой пачке параметров, в том числе и синтаксисом.
vt4a2h
28.12.2019 19:38Великолепно выглядит на самом деле!
Жаль, что пока мало где в продакшене можно так писать :(
balajahe Автор
29.12.2019 10:40пока мало где в продакшене можно так писать :(
Можете пояснить почему? Я не сишник.yamlevekke
29.12.2019 11:03Ну потому что на С++ много легаси. Много всяких мусорных платформ и компиляторов. Приходится страдать многим.
По той же причине и на скале мало кто пишет. Модный и обычный С++ можно воспринимать как два разных языка. Как за жаву и скалу. Тогда понятно будет.
А так же ещё одно. Нужно понимать, что хотя код на С++ выглядит итак же как на скале — он на порядок мощнее. В скале это обычные методы/голые массивы и сахар вида (_ > x). В С++ же это не сахар.
Допустим, фильтр ленивый как в расте. Преобразование ленивая последовательность -> массив — неявная. Но всё это описано. На самом деле в этом маленьком куске кода — сотня вызовов функций.
Всё это я к чему, а к тому, что необходимый бекграунд для продуктивного использования подобных фич упирается в бесконечность. Не забываем, что к С++-коду применяются куда как более жесткие критерии оценки.
Поэтому, даже если человек научится и сможет использовать это продуктивно — шансы на то, что в его команде/окружении научится кто-то ещё — примерно равны нулю. Шансы куда более низкие, нежели в ситуации со скалой. Т.к. скала несоизмеримо проще.
balajahe Автор
29.12.2019 11:51+1Спасибо. Вы интересно и содержательно пишете, но немного провокационно. Люди поэтому и переходят на новые модные языки, что не хотят тратить годы на изучение ньюансов старых, они хотят простоты и однозначности «здесь и сейчас» пусть даже ценой некоторого ухудшения характеристик. Я вот чисто прикладной программист, и чем меньше мне нужно знать деталей реализации, тем больше останется времени и сил на собственно работу.
yamlevekke
29.12.2019 12:19Люди поэтому и переходят на новые модные языки, что не хотят тратить годы на изучение ньюансов старых
Это большая ошибка, по крайней мере в ситуации с С++ и данной логикой. Это не нюансы старого языка и не нюансы С++. Это нюансы той системы и того подхода, которая даёт тот уровень возможностей.
И в С++ в данном случае всё сложно не потому, что язык такой. Это частый тезис, который вливают в сознание обывателей подлые сектанты. Но он ложный.
Суть тут в том, что из-за упрощения требований, уменьшения колва нюансов — новый язык позволяет изучать его проще. Но это неправильное сравнение. Его проще изучать потому, что в нём тупо меньше смысла — меньше семантики.
Там есть GC и семантика работы с памятью ушла, но ушла не только она. В С++ работа с памятью не отличается от работы с любым другим ресурсом. И даже если GC решает проблему с ресурсом "память" — остальные ресурсы никуда не исчезают.
Файлы нужно открывать и закрывать, сокеты тоже и прочие вещи. Поэтому всё это либо разруливается руками, либо создаются какие-то механизмы автоматизации. И вот уже сложности. Хотя ГЦ есть.
Есть, допустим, что-то типа раста. В раст пихают каждый день новый сахар, а в С++ сахара нет вообще. Но этот сахар никак ему не помогает. В языке тупо мало возможностей, мало семантики. Он слишком слаб. Намного слабее скалы.
В связи с этим он проще С++, намного. На это слабость вырождается в синтаксический мусор и неспособность реализовать даже 10% того, что можно реализовать на С++.
Таким образом вся сложность С++ обусловлена не тем, что язык старый. А тем, что он может быть таким же выразительным как самые лучшие, но при этом он быстрее всех и может больше всех.
Это то, чего нет нигде. И это то, что компенсирует всю сложность С++. И здесь так же есть манипуляции от адептов всяких фантазёров. Что они говорят? У нас есть С++ — он сложный и мощный. Но они утверждают, что сложный он потому, что "дизайн говно".
И это большая ошибка. Мир не знает чего-то настолько же мощного и менее сложного. И мы не знаем что это — мы не знаем можно ли сделать так же, но проще. Пытались многие — все поломались.
Да, возможно когда-нибудь мы это увидим. Но пока нету — все рассуждения об этом — инсинуации адептов всяких громких учений.
balajahe Автор
30.12.2019 00:48Там есть GC и семантика работы с памятью ушла, но ушла не только она. В С++ работа с памятью не отличается от работы с любым другим ресурсом. И даже если GC решает проблему с ресурсом «память» — остальные ресурсы никуда не исчезают. Файлы нужно открывать и закрывать, сокеты тоже и прочие вещи. Поэтому всё это либо разруливается руками, либо создаются какие-то механизмы автоматизации. И вот уже сложности. Хотя ГЦ есть.
Хорошая иллюстрация вашим словам — Golang. А вот в Rust файлы закрываются автоматически по выходу переменной из области видимости )
TargetSan
29.12.2019 11:30Несколько причин.
Во-первых, здесь используются ranges, которые только-только попали в стандарт. Т.е. это bleeding edge, не всякий прод готов переходить на него и ловить все грабли по дороге.
Во-вторых, у компиляторов до сих пор проблемы с оптимизацией ranges, особенно старых, где концепты реализованы через костыли.
В-третьих, те самые концепты, без которых эта красота при малейшей очепятке выплёвывает простыню плохо читаемых ошибок.balajahe Автор
29.12.2019 12:37Спасибо! Справедливости ради, все новые языки примерно в таком же положении )
TargetSan
29.12.2019 13:17Не совсем. Проблема конкретно С++ здесь в том, как он реализует обобщённое программирование.
Во-первых, утиная типизация шаблонов. Концепты добавили ad-hoc проверку на соответствие набору требований. Но насколько я помню, это работает только с вызывающей стороны. Стандарт не обязывает проверять соответствие концепту в теле функции.
Во-вторых, поддержка этой красоты требует нетривиальной шаблонной магии за кадром. Перегрузка pipe operator активируется через enable-if при наличии определённого условия у одного из аргументов. Как правило, тип трансформера должен наследоваться от типа-маркера. Если интересны детали — загляните в документацию boost.range, в раздел про реализацию своих range transformers/adaptors.
Вообще же, почти такой синтаксис был доступен ещё до С++11 — если взять boost. Но boost как минимум тогда применял целый ряд хаков, чтобы обеспечить максимальную поддержку в доступных тогда компиляторах. Как результат — шаблоны становились ещё сложнее, и не всякий компилятор мог переварить 100-200 уровней вложенности, возникавших при сколь-нибудь нетривиальном пайпе. Не говоря уж про те самые простыни ошибок при любой опечатке. А ещё веселее было если скрестить с эмуляцией лямбд.
Современные языки решают эту проблему, вводя поддержку требуемых концепций изначально. К примеру, traits как средство статической проверки в обобщённом коде. Либо использование interfaces для той же цели, как в Java или C#.
Короче — при всём моём уважении к С++, он слишком уж оброс фичами и костылями за последние 25 лет. И выбрасывать их никто не будет — обратная совместимость.yamlevekke
29.12.2019 15:38Не совсем. Проблема конкретно С++ здесь в том, как он реализует обобщённое программирование.
Полная и нелепая чушь.
Во-первых, утиная типизация шаблонов.
У шаблонов не может быть другой типизации. Опять кто-то где-то что-то слышал, но ничего более.
Концепты добавили ad-hoc проверку на соответствие набору требований.
Полная и нелепая чушь.
Но насколько я помню, это работает только с вызывающей стороны.
Такая же чушь.
Стандарт не обязывает проверять соответствие концепту в теле функции.
Ещё более нелепая чушь. Я даже не знаю как это херню комментировать, но если проще.
Во-первых все функции всегда проверяются. С самого зарождения плюсов. Во-вторых концепты нужны не для проверки, а для перегрузки. Ведь перегрузка, в отличии от проверки, в С++ работает только на уровне сигнатуры функции.
Во-вторых, поддержка этой красоты требует нетривиальной шаблонной магии за кадром. Перегрузка pipe operator активируется через enable-if при наличии определённого условия у одного из аргументов.
Ну и пошло поехало. То вдруг проверку добавили, то вдруг она есть без концептов. Нужно определиться с методичкой. При наличии концептов enable_if ненужен. Именно этот костыль и заменял концепты до концептов.
Как правило, тип трансформера должен наследоваться от типа-маркера.
Полная и нелепая чушь.
Если интересны детали — загляните в документацию boost.range, в раздел про реализацию своих range transformers/adaptors.
Опять попытка сувать свои скудные познания из левых либ в семантику языка. То, как что и где реализовано — ничего не значит.
Вообще же, почти такой синтаксис был доступен ещё до С++11 — если взять boost.
Синтаксис доступен потому, что язык может. А что реализует его — неважно. Очевидно, что всё это было ещё с зарождения языка с теми же >>.
Но boost как минимум тогда применял целый ряд хаков, чтобы обеспечить максимальную поддержку в доступных тогда компиляторах.
Это никого не интересует.
Как результат — шаблоны становились ещё сложнее, и не всякий компилятор мог переварить 100-200 уровней вложенности, возникавших при сколь-нибудь нетривиальном пайпе. Не говоря уж про те самые простыни ошибок при любой опечатке. А ещё веселее было если скрестить с эмуляцией лямбд.
Опять какие-то архенительные истории из помоек района нулевых.
Современные языки решают эту проблему, вводя поддержку требуемых концепций изначально.
Полная и нелепая чушь. Удачи собрать новую жаву старым компилятором. С чего вдруг адепты такие невменяемые? Когда речь заходит о С++ — нужны все компиляторы. Когда заходит ни о С++ — уже про компиляторы забывают
К примеру, traits как средство статической проверки в обобщённом коде.
Полная и нелепая чушь. traits — примитивная херня. К тому же, здесь адепт опять засыпался. Потому всякая скриптуха с трейтами не собирается старыми компиляторами. Поэтому эти мусорные лозунги можно выкидывать на помойку.
Либо использование interfaces для той же цели, как в Java или C#.
Полная и нелепая чушь. Интерфейсы ни в какой вселенной не могут заменить шаблоны.
Короче — при всём моём уважении к С++, он слишком уж оброс фичами и костылями за последние 25 лет. И выбрасывать их никто не будет — обратная совместимость.
Короче. Я ничего не знаю. Я пишу чушь. Где-то услышал какую-то херню — повторил. Я ничего не знаю про фичи, я засыпался в каждом тезисе, сравниваю жопу с пальцем. Но я крайне экспертный эксперт и знаю что нужно, а что нет.
0xd34df00d
29.12.2019 20:31У шаблонов не может быть другой типизации. Опять кто-то где-то что-то слышал, но ничего более.
System F, нормальный параметрический полиморфизм.
Полная и нелепая чушь.
Аргументированно.
Такая же чушь.
Снова аргументированно.
Нет, тело шаблонов не тайпчекается согласно объявленным концептам. Планы на это были в оригинальном пропозале на концепты в середине нулевых, но где тот пропозал, а где концепты из C++20.
Во-первых все функции всегда проверяются. С самого зарождения плюсов.
Только они проверяются после подстановки конкретных значений типов (то есть, в момент инстанциирования шаблона), а не до (то есть, не в момент написания шаблона).
Во-вторых концепты нужны не для проверки, а для перегрузки.
Концепты нужны и для того, и для другого.
Опять какие-то архенительные истории из помоек района нулевых.
Ну да, поэтому я смотрю на процесс компиляции одного файла в своем рабочем проекте минут 5, и компилятор при этом отжирает гигов 10 памяти (что означает, что я на 64-ядерной машине с 64 гигами памяти всё равно могу собирать код не более чем в 6-7 потоков).
Я ничего не знаю. Я пишу чушь.
А вот здесь я с вами согласен. Не делайте так больше.
yamlevekke
29.12.2019 21:06-7System F, нормальный параметрический полиморфизм.
Поиграем. Лозунги меня не интересуют, но меня интересует слив очередного эксперта. Норма — я жду альтернативы hana/ranges/spirit на этом говне, либо что-либо доказывающие его состоятельность. Либо какие-то адекватные сравнения. Если их не последует, а их не последует, я фиксирую балабольство.
Нет, тело шаблонов не тайпчекается согласно объявленным концептам. Планы на это были в оригинальном пропозале на концепты в середине нулевых, но где тот пропозал, а где концепты из C++20.
Опять какая-то чушь. Где цитата моя — что эта херня опровергает? Какого ещё тела и согласно каким концептам? В общем, цитату, обоснования этой херни нелепой — в студию.
Для тех кто не понимает насколько нелепую херню данный эксперт несёт. Если кратко — ключевое отличии крестовых шаблонов от всякого скриптуха-говна заключается в том, что передаваемый тип не стирается.
Таким образом внутри тела будет всегда тип переданного аргумента и он всегда будет прочекан. Этот тип никаким образом не зависит от концепта, потому как концепт на тип никак не влияет и влиять не может.
Таким образом тайпчекать на концепт попросту не имеет смысла, потому как тайпчекинг работает всегда на уровне настоящего типа.
В общем, в очередной раз очередной студент пытается кому-то что-то рассказывать. Кстати, что-то быстро он уехал с темы с темы С++ и сливает. Это всё нужно знать об этих экспертах. Если что я напомню ситуации. Как только данный эксперт покажет мне его С++-портянку он тут уйдёт из темы с позором. И он это знает.
Кстати, это норма для данного эксперта. Он там много заливал про хаскель, но так и не осилил многопоточную версию показать.
Только они проверяются после подстановки конкретных значений типов (то есть, в момент инстанциирования шаблона), а не до (то есть, не в момент написания шаблона).
А это очередная чушь небывалых масштабов. Я уже сообщил когда и что С++ проверяет. Данная чушь попросту не имеет смысла потому как никакой проверки без инстанцирования нет и быть не может, потому как никаких типов нет.
И никакие проверки ненужны, потому как проверка каждого инстанса уже является проверкой. Причём куда более полноценной.
Ну да, поэтому я смотрю на процесс компиляции одного файла в своем рабочем проекте минут 5, и компилятор при этом отжирает гигов 10 памяти (что означает, что я на 64-ядерной машине с 64 гигами памяти всё равно могу собирать код не более чем в 6-7 потоков).
К чему написана эта херня? Меня не волнует где и что там собирается. Куда методичка потекла то? Где же system F и прочая чушь?
Поэтому нести херню в интернете каждый эксперт смелый, а потом идёт и латает легаси-лапшу. А чего же так? Вперёд — берёшь то, что не собирается 5 минут и не собираешь 5 минут. Чего же не берётся? Опять методичка потекла? Ну бывает.
TargetSan
29.12.2019 21:58+4я жду альтернативы hana/ranges/spirit
Она творит конкретно вот это:
https://github.com/boostorg/hana/blob/master/include/boost/hana/functional/placeholder.hpp
Во-первых хана написана на древних крестах. Во-вторых там там реализовано пол сотни операторов. А то, что там их пол сотни ни о чём не говорит — просто в С++ множество операторов.
костылинг на 14 крестах
Это базовые вещи, которых нету в скриптухе
Никакого отношения эти перегрузки к операциям не имеютПоциэнт слился успешно
К слову, в других языках все эти вещи есть искаропки, а не реализуются недолиспом с вырвиглазным синтаксисом, коим являются крестовые шаблоны. Учи матчасть, малыш.
yamlevekke
29.12.2019 22:07-5Малыш, а чего ты сюда прибежал? А чего же ты обделался с совместимость, обделался с ханой? Где ответы в тех ветках? Ой, не смог? Беги, малыш, отвечать.
Ах да, малыш, меня не интересуют твои потуги нелепые про есть. Есть — показывай. Не показал — ничего нет. Поэтому, малыш, иди ищи что показать. Не можешь? Ничего не знаешь? В методичке код не пишут? Ну бывает.
Пыхти, малыш, оправдывайся.
Siemargl
29.12.2019 22:27-1Где есть икаропки, это обычно потому, что язык не тянет свободное программирование… И вкостыливают в синтаксис
TargetSan
29.12.2019 23:07+3Это по-моему уже немного уклон в философский вопрос — что должно быть частью языка, а что — реализовано в библиотеке.
Приведу немного провокационный пример — концепты. Они ведь, в принципе, реализовывались и до этого. Или те же лямбды, появившиеся в С++11. Был ведь до того boost::lambda.
Тут ведь вопрос в том, насколько легко и удобно будет использовать библиотечную фичу. И — что немаловажно — как трудно будет отлаживать ошибки при её использовании.
И если плейсхолдер из hana сравнительно прост сам по себе, прикиньте, насколько читабельным будет сообщение об ошибке в такой лямбде с хотя бы тремя операторами и участием каких-нибудь шаблонных типов. Вот где-то на этом месте свободное программирование начинает вылазить немного боком. Как экстремальный пример можно привести Perl. А лямбды в составе языка дадут вам при ошибке вменяемое сообщение.0xd34df00d
29.12.2019 23:12+2Из коробки должен быть нормальный метаязык и работа с AST. Хаскелевский TH или идрисовский elaborator reflection куда ближе к идеалу чем то, что есть в плюсах.
Siemargl
29.12.2019 23:16но бесконечно далеки от народа (с) =)
TargetSan
29.12.2019 23:21+1Я уже откровенно запутался, что мы тут обсуждаем.
Siemargl утверждает, что если в языке нельзя, грубо говоря, определить плейсхолдер средствами языка (как пример), то язык костыльный т.к. не умеет в "свободное программирование" (DSL?).
Я утверждаю, что такие вещи должны быть частью языка т.к. требуют хорошей эргономики, в т.ч. краткого и понятного описания ошибок компиляции. В шаблонах С++, к слову, с теми самыми ошибками всё плохо.
Вы говорите о прямой работе с AST, template haskell и других полноценных системах метапрограммирования.
Так о чём говорим дальше? Или где и что я перепутал?
0xd34df00d
29.12.2019 23:28+2Лично я говорю о том, что создатели языка не могут продумать все юзкейсы, поэтому лучше дать достаточный набор ручек, чтобы их можно было реализовать библиотечно. А там у вас будут и плейсхолдеры, и строковая интерполяция, и удобный вызов шелл-команд, и генерация дибас-сигнатур, и много чего ещё, включая совершенно безумные вещи типа инлайн-кода на R или C.
Да и эволюция и соревнование библиотек происходит куда более естественным образом. Тех же библиотек строковых интерполяций с десяток уже, наверное.
TargetSan
29.12.2019 23:58С одной стороны DSL и все подобные ништяки. С другой стороны тот самый ненавистный прод, на котором авторы некоторых библиотек с лицухами за 5-6 значную сумму не могут нормальную обработку ошибок даже для простого ООПшного АПИ. Не говоря уже о необходимости подсаживать на проект джунов.
Наверное я сейчас просто не готов вести аргументированный спор на эту тему, т.к. никакие статические мета-системы кроме шаблонов С++ нормально не щупал. И да, они мне таки напоминают кастрированный лисп с синтаксисом из злачных кварталов Амстердама.
technic93
29.12.2019 23:46+2Есть один момент, что отличает плюсовые темплейты от манипуляторов AST — это интеграция с constexpr значениями.
0xd34df00d
29.12.2019 23:51+1В каком смысле?
Я вот прям сейчас рефакторю код, который, в том числе, парсил HTML и генерировал по нему некие данные, в рантайме, а теперь это будет делать в компил-тайме.
Даже никакие constexpr расставлять не надо, я просто беру ту же функцию, и просто вызываю её в нужной монаде (
Q).technic93
30.12.2019 00:04Не знаю про Хаскель к сожалению, имел ввиду что можно делать
if constexprили какой-то другой условный переход для мета программирования, что отличается от макросов раста, в том числе процедурных.
TargetSan
30.12.2019 00:01Справедливости ради, constexpr появились только в 11м стандарте. Более-менее юзабельными они стали только в 14-м, когда разрешили constexpr функции не из одного выражения. Ещё какие-то не слишком приятные ограничения сняли вроде только в 17м, но подробностей уже не упомню.
Siemargl
29.12.2019 23:16Я не буду возражать.
Но это вопрос принципа — достаточно ли гибок и универсален язык для реализации фич?
Тут два варианта — язык позволяет (ну да, диагностика страдает как в случае с ++) или же извините — зашито в код.
Я таки за гибкость с пряморуким применением, чем за деревянные фичи.TargetSan
29.12.2019 23:28Это пока такой код не используют в проде хотя бы человек пять :) В этот момент очень хочется половину фич отключить на уровне компилятора :)
0xd34df00d
29.12.2019 23:02+3Лозунги меня не интересуют, но меня интересует слив очередного эксперта. Норма — я жду альтернативы hana/ranges/spirit на этом говне, либо что-либо доказывающие его состоятельность. Либо какие-то адекватные сравнения. Если их не последует, а их не последует, я фиксирую балабольство.
Ваш тезис — «по-другому нелзья». Я показал, как по-другому можно.
Причём тут хана или спирит, непонятно, какое-то совсем открытое переобувание на ходу.
Рейнджи — те же ленивые списки.
Хана — нахрена она нужна, когда есть нормальный метаязык типа template haskell/generics/etc?
Спирит — attoparsec/megaparsec/тысячи других парсеков.
Какого ещё тела и согласно каким концептам?
Тела функции или класса. Согласно концептам, которые эта функция или класс требует от шаблонных параметров.
Если по-простому, то компилятор не требует от вас навешивания концепта «T сравним» на функцию типа
std::min. Поэтому если типы несравнимы, то код сломается внутриstd::minв точке её вызова.
Таким образом тайпчекать на концепт попросту не имеет смысла, потому как тайпчекинг работает всегда на уровне настоящего типа.
И это проблема с точки зрения модульности, понятности сообщений об ошибках и прочих практик (нужных только в скриптухе, понятное дело).
И никакие проверки ненужны, потому как проверка каждого инстанса уже является проверкой. Причём куда более полноценной.
Да, зачем проверять код во время его написания, когда его можно проверять во время использования?
Может, вам на питоне каком писать лучше? Там вообще проверки полноценнее некуда с вашей точки зрения.
К чему написана эта херня? Меня не волнует где и что там собирается.
А, то есть, код вы не пишете? Это многое объясняет.
Поэтому нести херню в интернете каждый эксперт смелый, а потом идёт и латает легаси-лапшу.
Забавно, что код на плюсах вы заведомо признаёте легаси-лапшой.
vt4a2h
29.12.2019 18:24И я не сишник, я на плюсах в основном пишу :)
А если серьёзно, то тому есть несколько причин:
- Далеко не весь код разумно писать в функциональном стиле.
Пример выше иллюстрирует это. Такая сортировка да, выглядит красиво, но жутко не эффективна по памяти и по числу фактических проходов по последовательности (на каждой итерации их делается по факту три, а не один). Никогда бы такую не написал в продакшене. Я библиотеки разрабатываю. - С точки зрения бизнеса, затраты на переход на самые последние компиляторы и стандарты языка, не всегда выгодны.
Не стоит забывать, что за очень и очень небольшим академическим исключением, разработка ПО — обслуживающая отрасль (вроде, скажем, стрижки волос). Владелец финансовых активов и заказывает музыку. - Компиляторы не под все платформы поддерживают последние стандарты.
… или поддерживают, но не полностью. Допустим есть какая-нибудь коммерчески успешная железяка, вокруг которой построен бизнес, но вот нет компиляторов, с поддержкой последнего стандарта. Пока такие компиляторы не появятся, использование новых особенностей языка будет невозможным. - Не все программисты хотя учить и использовать новые стандарты и подходы.
… и это не означает, что они "плохие". У людей просто разные приоритеты и жизненные ценности. Вы удивитесь сколько людей ещё даже C++11 не используют (а ведь возможности есть уже почти 9 лет, если не больше). - Не всегда просто подключить сторонние библиотеки.
Серьёзно, даже если они просто из заголовочников. Этому может быть множество причин с точки зрения бизнеса.
- Далеко не весь код разумно писать в функциональном стиле.
isden
28.12.2019 16:50Раз говорим о ФП, то вот внезапно :)
yamlevekke
28.12.2019 16:58+1Слишком страшно, да и к тому же оно читерит и просто берёт нулевой элемент обходя проблему автора.
isden
28.12.2019 17:27> Слишком страшно
А на мой взгляд красиво и понятно О_о
> оно читерит и просто берёт нулевой элемент обходя проблему автора.
Вы про это?
quicksort [] = []
Если да — то это специфика рекурсивной реализации в хаскеле, а не чит.yamlevekke
28.12.2019 17:34А на мой взгляд красиво и понятно О_о
Слишком много синтаксического мусора для трюка на который язык заточен. Но чем дальше — тем хуже.
Если да — то это специфика рекурсивной реализации в хаскеле, а не чит.
Нет, я не про это. Я про выбор pivot. У автора возникла проблема — как получить середину ленивой последовательности? Здесь хаскель не решает эту проблему а просто берёт первый элемент из последовательности.
Посмотрите на картинку. Потом на код автора и его проблему.isden
28.12.2019 17:40> Слишком много синтаксического мусора для трюка на который язык заточен. Но чем дальше — тем хуже.
Смотрите мой коммент ниже. Так лучше? :)
> Нет, я не про это. Я про выбор pivot. У автора возникла проблема — как получить середину ленивой последовательности? Здесь хаскель не решает эту проблему а просто берёт первый элемент из последовательности.
А зачем решать эту проблему? Как я понимаю (а я не совсем настоящий сварщик пока), за счет именно ленивости в хаскеле мы и можем сделать такой вот трюк (и это нормально и так и нужно делать).TheShock
28.12.2019 17:48А зачем решать эту проблему? Как я понимаю (а я не совсем настоящий сварщик пока), за счет именно ленивости в хаскеле мы и можем сделать такой вот трюк.
Тем, что тогда отсортированный массив (самый частый случай) становится худшим случаем с O(n2). А ещё вариант на Хаскелле — неусточив, в то время, как у автора — устойчив.
Ещё одно не понял. Почему там написано «let smallerSorted = quicksort [a | a < — xs, a <= x] » (то есть меньше ИЛИ РАВНО) в функции-фильтре, но при этом не попадает само число, которое является pivot'ом?isden
28.12.2019 18:02+1> неусточив
Поясните плз, что это означает?
> Ещё одно не понял. Почему там написано «let smallerSorted = quicksort [a | a < — xs, a <= x] » (то есть меньше ИЛИ РАВНО) в функции-фильтре, но при этом не попадает само число, которое является pivot'ом?
xs — это часть массива без первого элемента. Т.е. на выходе у нас те элементы этого остатка, которые <= x.TheShock
28.12.2019 18:12Поясните плз, что это означает?
ru.wikipedia.org/wiki/Устойчивая_сортировка
xs — это часть массива без первого элемента. Т.е. на выходе у нас те элементы этого остатка, которые <= x.
Теперь понятно, спасибо.
Правда устойчивость сделать легко (хаскель не знаю, но как-то так):
quicksort [] = [] quicksort (x:xs) = quicksort [y | y <- xs, y < x] ++ filter(== x)[array] -- ?? ++ quicksort [y | y <- xs, y > x]
А вот с квадратом в почти отсортированном массиве — огромная проблема0xd34df00d
28.12.2019 18:30List concat (там, где плюсики) и так линейный, можете просто линейно брать средний элемент (или вообще считать медиану).
isden
28.12.2019 18:40> ru.wikipedia.org/wiki/Устойчивая_сортировка
Я не уверен что это вообще применимо в данном случае.
Насколько понимаю, порядок следования одинаковых элементов тут меняться не должен. Тут же рекурсивный вызов с остатком.
yamlevekke
28.12.2019 17:51Смотрите мой коммент ниже. Так лучше? :)
Лучше, но в основном лучше оно просто переносом влево.
А зачем решать эту проблему?
Затем, что первый элемент не обязательно лучший выбор. Эффективность этого алгоритма напрямую зависит от удачного выбора опорного элемент. Нулевой элемент — это даже, наверное, один из худших выборов. Потому как начало может быть частично сортировано, а новые элементы добавляются в массив в конец.
Как я понимаю (а я не совсем настоящий сварщик пока), за счет именно ленивости в хаскеле мы и можем сделать такой вот трюк.
Нет. Это не трюк — это самое простое решение. Оно не зависит от ленивости/не ленивости.
В расте мы без проблем можем взять первый элемент последовательности, да и в С++.isden
28.12.2019 18:06> Затем, что первый элемент не обязательно лучший выбор. Эффективность этого алгоритма напрямую зависит от удачного выбора опорного элемент. Нулевой элемент — это даже, наверное, один из худших выборов. Потому как начало может быть частично сортировано, а новые элементы добавляются в массив в конец.
Я про ленивость не зря написал. Как я понимаю, фиксированного опорного элемента у нас как такового нет.yamlevekke
28.12.2019 18:28Я про ленивость не зря написал. Как я понимаю, фиксированного опорного элемента у нас как такового нет.
Его итак нет. Он есть на каждом шаге. Свой. А то, что у вас этот шаг написан "лениво" — это ничего не меняет. Ему так же нужен опорный элемент.
К тому же и в С++ и в расте всё это так же лениво. Хаскель-ленивость это почти тоже самое, что и
range | filter | to<vector>() | allв C++.
Разница лишь в том, что итерации в ленивой последовательности записываются в список. А далее уже этот список передаётся(под видом последовательности). В расте/С++ последовательность нельзя никуда передать — там нету состояния.
Ну ещё разница в том, что в примере выше вычитается вся последовательность. Хаскель же может вычитывать последовательность частично. Правда в С++ это так же можно реализовать. А так же это делает хаскель невероятно тормозным. Сами списки убогие структуры с ТЗ производительности, а состояние нужно везде и всюду таскать и копировать.
Поэтому если в С++ можно написать зерокост-трансформацию, то в хаскеле нельзя.
isden
28.12.2019 17:31Код по ссылке, кстати, можно немного упростить примерно вот так:
quicksort [] = [] quicksort (x:xs) = quicksort [y | y <- xs, y<x ] ++ [x] ++ quicksort [y | y <- xs, y>=x]stan_volodarsky
29.12.2019 10:37У вас выходной массив длиннее стал.
TargetSan
29.12.2019 14:12+3А то, что творит boost.hana чтобы реализовать _ — не страшно? Ну ооок...
yamlevekke
29.12.2019 14:55-4Ничего она там не творит. Зачем вы ничего не зная постоянно несёте какую-то херню? Это попытки говорить с видом будто чего-то знаешь, но на самом нет.
вот что она творит — ахренеть как страшно. Очередной первокурсник зашёл в код, увидел там что-то(ничего не понял) и решил сорвать покровы? Нелепо.
TargetSan
29.12.2019 15:43+3Она творит конкретно вот это:
https://github.com/boostorg/hana/blob/master/include/boost/hana/functional/placeholder.hpp
А твой псевдокод ниочём никого не интересует.yamlevekke
29.12.2019 16:18-2Собственно как я и говорил. Студент взял и что-то там увидел. И пошёл нести херню.
Она творит конкретно вот это:
Твои потуги никого не интересуют.
А твой псевдокод ниочём никого не интересует.
Это не псевдокод, студент, а полноценная реализация. Зачем ты пытаешься строить из себя что-то отличное от нуля?Во-первых хана написана на древних крестах. Во-вторых там там реализовано пол сотни операторов. А то, что там их пол сотни ни о чём не говорит — просто в С++ множество операторов.
Ну и чтобы сразу определить клоунов. invoke — это реализация (), которая здесь не используется. К тому же это костылинг на 14 крестах, ненужный. subscript — это реализация [value], который здесь не используется.
Далее всё остальное — это просто комбинаторная сложность. Каждый оператор — это op x или x op или op .
op_name ## _right и op_name ## _left — это первый и второй случай. Третий проще.
Для каждого реализовано & | const | && перегрузка для this. Это базовые вещи, которых нету в скриптухе, да и о которых этот студент ничего не знает.
Никакого отношения эти перегрузки к операциям не имеют — это базовая семантика C++, которая реализуется для всего.
balajahe Автор
28.12.2019 17:02Хаскель красавчик, и по производительности, говорят, какие-то чудеса показывает.
yamlevekke
28.12.2019 17:17и по производительности, говорят, какие-то чудеса показывает.
Обманывают. Про читы я выше сказал. А по поводу самой ленивости — она там работает не так как в С++/расте. В С++/расте — она честная, т.е. она не хранит состояние. Хаскель же работает так как пример с преобразованием в массив в расте — поэтому он не может быть быстрым как раст/С++ в принципе.
У раста примерно та же проблема. Там слишком ограниченные итераторы. Поэтому раст так же не может быть таким же быстрым как С++.
Это был бы полный zero-cost, но в итераторе мы не можем определить количество элементов, значит не можем поделить его пополам, а значит — реализовать алгоритм.
В расте так будет всегда. В случае с С++ такая ситуация будет только в случая с filter(и прочими методами, которые не возвращают RA-итераторы).
Преобразование массива в итератор даёт RA итератор у которого есть длинна. И все трансформации элемент в элемент над такими итераторами так же возвращают RA итератор.
balajahe Автор
28.12.2019 17:22А почему в расте так будет всегда?
yamlevekke
28.12.2019 17:30Слабый дизайн. Слабая система типов. Общая слабость языка.
Возможно, с потерей типизации можно это как-то реализовать. А почему не реализовали? Не знаю. Делали как можно проще, не заморачивались. Помню как кто-то хвалился тем, что «вот в С++ какие идиоты — множество типов итераторов и всякие сложности» «у нас всё просто — next()».
Дизайн решений в С++ обусловлен потом и кровью десятков лет передовой разработки. Новые решения часто делают подобную ошибку — думая, что «глупые просто». Но оказалось, что не глупые.TargetSan
28.12.2019 18:06+1Нет. В С++ такой дизайн итераторов объясняется баальшим желанием мимикрировать под указатели. Потому что во времена становления stl они часто и были указателями т.к. компилятор был туповат и не мог оптимизировать. Теперь мы вынуждены жрать этот кактус, плюс в stl так и не завезли за 20 лет адаптеры, облегчающие жизнь. Нет там никакой гипер-идеи, только попавший в стандарт прототипный дизайн. Как с JavaScript.
yamlevekke
28.12.2019 18:16Нет. В С++ такой дизайн итераторов объясняется баальшим желанием мимикрировать под указатели.
Да. К тому же очень слабый довод, потому как указатель(который итератор) далеко не всегда RA семантически.
Потому что во времена становления stl они часто и были указателями т.к. компилятор был туповат и не мог оптимизировать.
Они и сейчас указатели там, где указатели могут быть и будут. А где не могут — там их нет. И так было всегда. Опять же — очень слабые доводы.
То, что в том же векторе итераторы — указатели — это просто потому, что он семантически кусок памяти + совместимость. Почти во всех остальных контейнерах итераторы не указатели и ваша теория рушится.
Теперь мы вынуждены жрать этот кактус, плюс в stl так и не завезли за 20 лет адаптеры, облегчающие жизнь. Нет там никакой гипер-идеи, только попавший в стандарт прототипный дизайн. Как с JavaScript.
Она именно есть. Идеи нету в банальной перепасти итераторов из жаваскрипта( как это сделано в расте), а здесь же идея есть и она очевидна.
Я даже не знаю какой смысл выдвигать такие глупости. Они ведь дырявые насквозь. Проблема в ваших рассуждениях в том, что вы на какую-то имеющую место базу напридумывали глупостей.
А на самом деле всё просто. Итераторы как указатели(на самом деле как указатель там только разыменование/арифметика) в С++/stl потому, что stl всегда было про обобщение. И именно поэтому базовый интерфейс как у указателей — для унификации.
Это никак не связано с компиляторами, оптимизациями, туповат и прочее.
TargetSan
28.12.2019 20:15Да. К тому же очень слабый довод, потому как указатель(который итератор) далеко не всегда RA семантически.
Вообще-то это как раз доказательство того, что итераторы эволюционно выросли из голых указателей — там, где по-хорошему требовалось придумать более адекватную абстракцию. Существует ЕМНИП шесть категорий итераторов. Перегрузка по ним сильно затруднена без недавно появившихся концептов. Только суперсет одного из них семантически полностью соответствует голому указателю. А именно — упомянутый вами random access не даёт гарантии непрерывности диапазона значений под ним. input/output итераторы требуют костылей при реализации чтобы правильно имитировать указатель. И тем не менее, они имитируют указатели.
Вы кстати в курсе что сам концепт итератора происходит из smalltalk? Но при адаптации Степанов сделал из одного итератора (по факту диапазона) два — итератор начала и конца. Знаете почему? Как раз чтобы натянуть концепт итератора на указатель.
Они и сейчас указатели там, где указатели могут быть и будут. А где не могут — там их нет. И так было всегда. Опять же — очень слабые доводы.
То, что в том же векторе итераторы — указатели — это просто потому, что он семантически кусок памяти + совместимость. Почти во всех остальных контейнерах итераторы не указатели и ваша теория рушится.Моя теория как раз в том и состоит, что это негодная абстракция, возникшая в силу обстоятельств.
Она именно есть. Идеи нету в банальной перепасти итераторов из жаваскрипта( как это сделано в расте), а здесь же идея есть и она очевидна.
Как вы думаете, где они возникли раньше? Почему только в С++ итераторы имитируют интерфейс указателя?
Яваскрипт же я упоминаю именно как пример прототипа с кучей проблем, ставшего стандартом де-факто и стандартизированного как есть.
Я даже не знаю какой смысл выдвигать такие глупости. Они ведь дырявые насквозь. Проблема в ваших рассуждениях в том, что вы на какую-то имеющую место базу напридумывали глупостей.
Глупость как раз получилась у вас.
Ещё раз. То, что итераторы имитируют указатели — не великий план и не супер-дизайн. Это следствие костылей и ad-hoc решений, возникших на заре становления. Так же, как most vexing parse rule и другие подобные артефакты.
А на самом деле всё просто. Итераторы как указатели(на самом деле как указатель там только разыменование/арифметика) в С++/stl потому, что stl всегда было про обобщение. И именно поэтому базовый интерфейс как у указателей — для унификации.
Это никак не связано с компиляторами, оптимизациями, туповат и прочее.Где вы увидели в этом унификацию? Указатели и итераторы — семантически разные вещи. По вашему такое натягивание совы на глобус — это хорошо?
Признаю и понимаю ли я текущее положение вещей? Да, т.к. других вариантов особо нет. Считаю ли я такой дизайн хорошим? Однозначно нет.
yamlevekke
28.12.2019 20:52-2В общем, зачем мне повторять одни и те же глупости, ссылаться на "а вот оттуда бралось" без каких-либо пруфов.
Я привёл два базовых контр-тезиса. Первое — итераторы не пытаются быть каким-то там там имитаторами указателей — они их обобщали. Итераторы семантически никак вообще не завязаны на указатель. Указатель — просто вид итераторов.
Второе — если итераторы пытались быть указателями, то почему концепция итераторов куда шире указателей? Как так вышло.
Так же, я не вижу ответов за предыдущие глупости вида "компиляторы слабые — были указатели вместо итераторов"? Зачем вбрасывать, а потом игнорировать?
Так же эти заходы и попытка закидывать лозунгами вида "костыли". Показывайте не костыли, показывайте более мощные/не костыльные концепции итераторов?
Так же заходы вида "концепты появились" — такая же глупость. Во-первых потому, что существует множество техник диспатча по типу итератора(и чего угодно). Во-вторых — никакого аналога концептов нигде нету. Как и нету никаких аналогов даже старых костыльных методик. Толку об этом рассуждать?
Есть что показать — показывайте. Берёте любые итераторы и показываете RA. Не можете — все ваши рассуждения стоят ноль. Потому как попросту нету смысла ругать что-то уникальное.
Так же заходы вида "сову на глобус" — в каком месте сова? Обоснования. А нету их и не будет. Это просто религиозные триггеры из мира жаваскрипта/раста. Где функциональности подобной нету, но похаять нужно. Хаять могут те, кто сделал лучше. А не те, что не сделал.
Интерфейс итератора удобен и именно такой по нескольких основным причинам. 1) у С++ достаточные синтаксические возможности для обеспечения подобных возможностей. 2) Интерфейс указателей выбран для унификации с ними. И потому, что он удобный и выразительный.
От того, что кто-то не осилил перегрузку и прочее — обмазался синтаксическим мусором вида .next()/.iter() и пытается это как-то оправдать — этому ничего не значит.
В целом меня не перестают удивлять подобные срачи. Люди нахватаются каких-то базвордов и бегут срывать покровы. Но зачем? Можешь показать лучше — показывай. Не можешь показать — зачем заниматься этим срачем?
Я утверждаю, что С++ выразительный и мощный. Я иду и показываю это. Зачем делать что-то иное?
IkaR49
30.12.2019 08:00Я долго и упорно вникал в суть вашей дискуссии, обдумывал аргументы обеих сторон, но после фразы:
Указатель — просто вид итераторов.
понял, что мне надо выйти покурить. Это слишком для меня с утра.
Siemargl
30.12.2019 10:12Понимать это надо так: «итераторы могут быть реализованы и с помощью указателей» =)
0xd34df00d
28.12.2019 18:25+1Дизайн решений в С++ обусловлен потом и кровью десятков лет передовой разработки.
Возможно, вы имели в виду «десятков лет продакшн разработки». От ресерча в плюсах очень мало, а от совместимости с С и с решениями двадцатилетней давности — много.
yamlevekke
28.12.2019 18:32От ресерча в плюсах очень мало
Очень много. Просто вы говорите об академическом ресёрче — его в С++ действительно мало. Но ему это и ненужно. Академический ресёрч очень слаб и именно поэтому никто и нигде оптимальней дизайн не родил.
а от совместимости с С и с решениями двадцатилетней давности — много.
В С++ нет совместимости с си — С++ и есть си. Ошибочных решений там очень мало, а вот недоработок много. Но за его пределами недоработок ещё больше.
TargetSan
28.12.2019 20:27+1Таки нет. Не всякая валидная программа на С является валидной программой на С++.
yamlevekke
28.12.2019 20:32-4Не всякая валидная программа на С является валидной программой на С++.
С чему это написано? Это нелепая глупость, которая ретранслируется везде всюду. Зачем?
Не всякая валидная программа на си является валидной программой на си. Не каждая валидная программа на С++ является валидной программой на С++.
Ну, дальше что? Не каждая валидная программа на пхп является валидной программой на пхп. Продолжать? Или очевидна вся нелепость этого тезиса?
TargetSan
28.12.2019 20:47+2С чему это написано? Это нелепая глупость, которая ретранслируется везде всюду. Зачем?
То, что вы, не имея опыта программирования на означенных языках, не знаете об этих особенностях, не значит, что их нет.
Быстрый гуглёж даёт:
- Compatibility of C and C++, 2й абзац и далее по статье
- What can be done in c but not c++?
Не всякая валидная программа на си является валидной программой на си. Не каждая валидная программа на С++ является валидной программой на С++.
Ну, дальше что? Не каждая валидная программа на пхп является валидной программой на пхп. Продолжать? Или очевидна вся нелепость этого тезиса?Нет аргументов по существу — лучше не пишите, не путайте новичков вашими личными измышлениями. Тем более неверными.
yamlevekke
28.12.2019 21:00-3То, что вы, не имея опыта программирования на означенных языках, не знаете об этих особенностях, не значит, что их нет.
Повторю, меня не перестаёт удивлять то, как очередной зелёный срыватель покровов, услышав что-то в интернете, начинает со мною спорить. Да ещё и обвиняет меня в чём-то.
Повторю ещё раз — это полная чушь. Не нужно пытаться в споре со мною повторять херню из интернета. Это обречено на провал, всегда.
Быстрый гуглёж даёт:
Вместо гуглежа и наброса херни — лучше бы имели состоятельность.
В общем, если кому будет интересно я проясню тему. Смысл в том, что я сообщил о том, что "С++ и есть си". Далее какой-то эксперт услышав где-то то, что си не полностью совместим с С++ решил меня разоблачить.
Его рассуждения это чушь. И я сообщил выше почему, но эксперт не осилил понять. Если проще — с99 не совместим с с89, а с11 с с99. Следует ли из этого что-то? Нет, это полная чушь.
Тоже самое касательно и С++. C++20 не совместим с С++17. Но следует ли из этого то, что первый, либо второй не С++? Нет.
Т.е. эта херня про "валюдную программу" — это студенческая херня, который ничего не значит. То, что в новой итерации языка что-то поменялось и она не совместима со старой — не следует то, что это новый язык.
Думаю, что этого должно быть достаточно.
TargetSan
28.12.2019 21:23+1Его рассуждения это чушь.
Я хотя бы привёл ссылки с подтверждениями, что это два разных языка, пусть и с общими корнями. У вас я пока наблюдаю только переход на личности.
с99 не совместим с с89, а с11 с с99
C++20 не совместим с С++17.Не потрудитесь ли привести ссылки на указания, где более новые стандарты нарушают старые? Т.е. где они ломают обратную совместимость? Или вы не понимаете разницы между версиями стандарта и двумя языками с общими корнями?
Т.е. эта херня про "валюдную программу"
Т.е. термины well-formed и ill-formed для вас "херня"? Ну-ну.
Думаю, что этого должно быть достаточно.
Вот тут согласен. Дальнейший спор считаю бесперспективным.
yamlevekke
28.12.2019 21:38-4Я хотя бы привёл ссылки с подтверждениями, что это два разных языка, пусть и с общими корнями.
Каким образом эта чушь относится к моим тезисам?
У вас я пока наблюдаю только переход на личности.
Обоснования
Не потрудитесь ли привести ссылки на указания, где более новые стандарты нарушают старые?
Во-первых с чего вдруг продолжаешь этот поток чуши, на каком основании игнорируется несовместимость сверху вниз? Во-вторых — тысячи их.
Даже не знаю зачем я с экспертами-первокурсниками спорю. Надеюсь кто-то посмотрит на результат этой клоунады в следующий раз зелёные эксперты услышавшие пару базвордов не будет бежать и срывать покровы.
TargetSan
28.12.2019 23:14Каким образом эта чушь относится к моим тезисам?
Тем, что твои тезисы не тезисы, а какой-то бред.
Обоснования
Кол-во "чушь", "херня" на единицу текста. А вообще перечитай свои же комменты, хе-хе.
Во-первых с чего вдруг продолжаешь этот поток чуши, на каком основании игнорируется несовместимость сверху вниз? Во-вторых — тысячи их.
Т.е. ты всерьёз считаешь крутым язык с примерно десятью несовместимыми (по твоим же словам) друг с другом стандартами? Ну ооок, job safety driven development detected.
А ты в курсе, что без так пугающих тебя несовместимых изменений у тебя бы никогда не было твоих любимых итераторов? Ты в курсе, с чего начинался С++? Слышал про CFront?
Siemargl
28.12.2019 23:19О чем спорим?
Ну есть несовместимости С и С++. Они штучные, понятные и легко исправляемые.
История длинная, и пока показывает только то, что мир построен на С/С++. Остальное тлен либо надувание щекTargetSan
28.12.2019 23:25Да ни о чём мы особо не спорим. У гражданина полыхнуло когда я сказал, что фича С++, довольно спорная по дизайну в ряде мест, была не результатом гранд дизайна, а эволюцией портирования решения из другого языка. И тут всё заверте…
Было бы даже интересно если бы он привёл хоть какие-то аргументы, а не кидался какахами.Siemargl
28.12.2019 23:37портирования итераторов откуда, простите?
TargetSan
29.12.2019 00:03Насколько я помню, как минимум концепция итераторов в STL была взята Степановым из Smalltalk. С поправкой что итератор там был один и определял всю последовательность. Очень грубо — как нынешние ranges.
Вторая (или первая) часть яблока раздора — откуда пошла идея мимикрировать итераторы под указатели и насколько она удачная.
yamlevekke
29.12.2019 16:23Т.е. ты всерьёз считаешь крутым язык с примерно десятью несовместимыми (по твоим же словам) друг с другом стандартами? Ну ооок, job safety driven development detected.
Ты писал херню:
Не потрудитесь ли привести ссылки на указания, где более новые стандарты нарушают старые?
Тебе привели примеры. Я не вижу оправданий. Где оправдания? Меня не интересуют очередные рассуждения студентоты, которая где-то что-то слышала.
Получается ты сел в лужу. Ты болтал, что примеры несовместимости говорят о том, что С++ не си. Тебе я привёл примеры такой же несовместимости. Таким образом у тебя варианта два. Либо С++ не С++, либо С++ си.
Оправдания твои нелепые мимо темы меня не волнуют. Оправдывайся лучше.
MooNDeaR
28.12.2019 21:25https://habr.com/ru/post/482318/#comment_21072868
Ну, это я так, если вдруг что. Ни одна версия С++ не скомпилирует код, который я написал.
И если надо я еще вспомню парочку вещей в Си, которые тупо не скомпилируются)
Вместо того, чтобы перестать хвалить С++, какой он распрекрасный, попробуйте посмотреть на мир вокруг)) Я вот за уже 6 лет писанины на С++ могу столько дерьмовых и костыльных решений в нем припомнить, не говоря уже о просто аццком синтаксисе (вспомните нашумевную статью о пифагоровом треугольнике), полнейшую убогость работы под дебагом и миллионы UB.
Я правда люблю С++, но объективных недостатков у него уже очень много, синтаксис уже раздут до предела, что в момент, когда я попробовал Rust, я прям ощутил радость жизни)
MooNDeaR
28.12.2019 21:18+1С чему это написано? Это нелепая глупость, которая ретранслируется везде всюду. Зачем?
Нуууээээ… напишите-ка мне на С++ вот так:
// // Lib.h // enum FileActionType { ACTION_READ, ACTION_WRITE, ACTION_OPEN, ACTION_CLOSE, //.. other actions ACTION_ENUM_SIZE }; typedef void(*FileActionHandler)(void*); typedef FileActionHandler FileActionHandlerTable[ACTION_ENUM_SIZE]; void RegisterHandlers(const FileActionHandlerTable* table) { //do something } // // Main.c // void HandleFileWrite(void* info) { //do something } void HandleFileOpen(void* info) { //do something } int main() { FileActionHandlerTable table = { [ACTION_OPEN] = HandleFileOpen, [ACTION_WRITE] = HandleFileWrite }; RegisterHandlers(&table); return 0; }
UPD:
Аргументы что "так ни один здоровый человек писать не будет" — не принимаются. Это противоречит "С++ и есть Си". Ни одни стандарт, ни текущий, ни будущий, это не скомпилирует.yamlevekke
28.12.2019 21:46-4Не понимаю — зачем вы пытаетесь со мною спорить?
Нуууээээ… напишите-ка мне на С++ вот так:
Каким образом эта чушь связана с моими тезисами? Я не понимаю ещё одного — зачем вы выдаёте свои фантазии за мои тезисы? Неужели вы считаете, что эта нелепая примитивная херня новость для меня и что оно что-то значит? Нет, ничего она не значит. Но я помогу вам, ведь иначе вам слишком сложно.
Это нелепая глупость, которая ретранслируется везде всюду. Зачем?
Это означает не то, что между С и С++ нету разницы. И не то, что си с чего-то там вдруг совместим с С++ и прочая чушь.
Это значит лишь то, что вся эта херня про совместимость никак не определяет то, чем является, а чем не является язык. То, что следующая итерация в чём-то не совместима с предыдущей — не означает, что следующая итерация новый язык, либо не является старым языком.
MooNDeaR
28.12.2019 22:29Я ещё раз повторюсь, никакая итерация С++ никогда не скопилирует этот код, т.к. он конфликтует с синтаксисом лямбд. Соответственно:
В С++ нет совместимости с си — С++ и есть си.
Полная чушь. С любой точки зрения, что бы вы не имели ввиду под
Это значит лишь то, что вся эта херня про совместимость никак не определяет то, чем является, а чем не является язык
Что касательно:
Каким образом эта чушь связана с моими тезисами?
Что ж, пройдемся по тэзисам:
(про Rust) Слабый дизайн. Слабая система типов. Общая слабость языка.
Вы хоть раз на расте писали? Прекрасная система типов + удобный паттерн матчинг+ много статических гарантий + отличный дизайн контейнеров с возможнотью без проблем менять реализацию на мутабельную/персистентную не изменив не строчки кода. А всё за счёт move-семантики из коробки) Не стоит уж вспоминать про плюсовые проблемы из-за неявных конвертаций типов, перегрузок функций, поведения дефолтных параметров в виртуальных функций и прочего и прочего)
Дизайн решений в С++ обусловлен потом и кровью десятков лет передовой разработки
Дизайн решений в современном С++ обусловлен лишь одним — обратной совместимостью. Всё остальное — вторично. Дизайн старых решений в С++ обсуждать не хочется, ибо там дыра на дыре и дырой погоняет. Я уверен, что в мире нет ни одной программы на С++ без UB :)
Показывайте не костыли, показывайте более мощные/не костыльные концепции итераторов?
Растовые итераторы чем плохи? Итераторы там делают именно то, что должны — проходят по коллекции. Если вам нужно что-то большее — вам не нужны итераторы.
Я утверждаю, что С++ выразительный и мощный.
Но какой ценой? Порог входа в С++ сейчас просто космический) Нужна ли эта вся мощь? А если нужна, то кому?
Не понимаю — зачем вы пытаетесь со мною спорить?
Основная причина в том, что мне нравится, что у вас бомбит :) Ну, или вы делаете вид, что бомбит, но в целом одинаково забавно. А еще вы просто неправы в своих попытках идеализировать С++, но это уже второстеменно. С++ хорош и аналогов пока нет, но это не значит, что он идеален) Дырищ и неудобных решений в нём просто сотни)
Siemargl
28.12.2019 23:06Определись, либо нет совместимости С с С++ либо же
Дизайн решений в современном С++ обусловлен лишь одним — обратной совместимостью.
0xd34df00d
28.12.2019 23:12Её пытались сохранить, но полной совместимости нет. Для любого стандарта C существует программа, которая не соберётся ни одним стандартом C++.
Siemargl
28.12.2019 23:36Ну а проблема то в чем? Просто поспорить???
0xd34df00d
29.12.2019 00:55Проблемы две: во-первых, куча решений обусловлена соображениями минимизации числа несовместимостей. Во-вторых, при этом полной совместимости нет.
0xd34df00d
28.12.2019 21:43Академический ресёрч очень слаб и именно поэтому никто и нигде оптимальней дизайн не родил.
Оптимальней по каким критериям? По количеству UB на строку в минуту?
В С++ нет совместимости с си — С++ и есть си.
Ни одно из них не является подмножеством другого.
yamlevekke
28.12.2019 21:52-1Оптимальней по каким критериям?
По любым прикладным. Начнём с производительности, универсальности, применимости и результативности.
По количеству UB на строку в минуту?
Вброс полная чушь, потому как не имеет смысла пока вы не показали альтернативу тех строк, но без UB. Пока что никто не показал.
Ни одно из них не является подмножеством другого.
Это базворды ничего не значат и никак мой тезис не опровергают.
0xd34df00d
28.12.2019 21:58результативности
Куча задач на ряде других языков решается быстрее.
Вброс полная чушь, потому как не имеет смысла пока вы не показали альтернативу тех строк, но без UB.
Я не о тех языках говорю, а о самой неотъемлемой сущности языка.
Это базворды ничего не значат и никак мой тезис не опровергают.
Формальная логика, видимо, настолько же слаба, насколько академический ресерч. Ну ок.
yamlevekke
28.12.2019 22:12Куча задач на ряде других языков решается быстрее.
На каком основании проигнорированы все остальные критерии и в качестве ответа дан лозунг? Причём лозунг несостоятельный.
На ряде других языков задачи решаются быстрее не из-за языков а из-за более низких требований к ним. Это типичная подмена понятий.
Я не о тех языках говорю, а о самой неотъемлемой сущности языка.
Опять подмена понятий. Это не сущность языка — это сущность языка соответствующего требованиям предъявляемым С++. Пока вы не покажете то, что требования соответствует, но свойствами "UB" не обладает — рассуждения не имеют смысла.
Формальная логика, видимо, настолько же слаба, насколько академический ресерч. Ну ок.
Это не формальная логика, а попытка выдать какой-то глупый лозунг под неё. Смысла он не имеет и ничего не значит. Именно поэтому его вы не показали и логически с моим тезисом не связали.
Суть фокуса прост. Берётся базворд где-то услышанный про подмножества. Очевидно, что это полная чушь. Я уже говорил об этом выше. Любой язык в процессе своей эволюции перестаёт быть надмножеством себя прошлого просто в силу отсутствия совместимости снизу вверх.
И задача решается просто. Существует некий набор семантических/синтаксических/etc и даже идеологических правил/подходов. Именно это база определяет язык. И то, что в каких-то вариациях где-то куда-то что-то добавили/убавили — ни на что не влияет.
База осталась той же. Она не претерпела достаточно изменений для того чтоба называться новым языком.
0xd34df00d
28.12.2019 22:18+1Вы очень мдурёными путями занимаетесь софистикой, доказывая тавтологию «C++ — единственный язык, являющийся C++». Значимость его характерных особенностей при этом, по-видимому, постулируется и не показывается никак.
Ну, опять же, ок.
technic93
28.12.2019 17:46А как будет работать RA итератор поверх отфильтрованного вектора? Хранить где-то индексы или фильтровать каждый раз заново?
yamlevekke
28.12.2019 18:07После фильтра нету RA-итератора. Я выше об этом писал. RA итератор из RA итератора возвращают только трансформации из элемента в элемент.
А как будет работать RA итератор поверх отфильтрованного вектора?
Если захочется реализовать RA — его можно реализовать без проблем. Самый простой случай — это
to<vector>(). Преобразовать в любой контейнер, который поддерживает RA.
Если хочется оптимизации — можно создать буфер как вью, который будет читать последовательность и записывать её в себя. Но буфер этот, в отличии от конвертации в контейнер — можно переиспользовать.
0xd34df00d
28.12.2019 18:24Обманывают.
В моих личных бенчмарках он обычно идёт за плюсами, иногда — вровень, изредка — быстрее.
Хаскель же работает так как пример с преобразованием в массив в расте — поэтому он не может быть быстрым как раст/С++ в принципе.
Можете развернуть эту мысль? Я не понял ни логический переход, ни предпосылку, на самом деле.
yamlevekke
28.12.2019 18:41В моих личных бенчмарках он обычно идёт за плюсами, иногда — вровень, изредка — быстрее.
Зачастую они специально подобранные, а реализации С++ слабые. Да и от хаскеля там ничего не остаётся(массивы, unsafe и прочие прелести. А не нативная ленивость и нативные последовательности). Ни разу не видел адекватного сравнения — покажите, посмотрю.
Можете развернуть эту мысль? Я не понял ни логический переход, ни предпосылку, на самом деле.
Всё просто. В С++/раст честная ленивость, который не хранит состояние. И если бы вы цитировали честно — вы бы это увидели. Но вы пожелали процитировать кусок, что очень похоже на манипуляцию.
Если взять последовательность и умножить её на два — хаскель создаст новую последовательность, храня её состояние на каждой итерации.
Единственный вариант сделать на хаскеле зерокост(ну уровня хаскеля, разумеется) — это просто собрать мега-калбек и обойти им последовательность, либо просто применить перед передачей элемента.
Но это далеко от того, что умеют итераторы даже в расте. Конечно — можно начать игнорировать удобства написания кода, его выразительность и прочие свойства. Но эта неправильный подход.
0xd34df00d
28.12.2019 21:56Зачастую они специально подобранные, а реализации С++ слабые.
Да нет, почему, не так давно реализовал алгоритм Левенштейна, линейный по памяти — даже придумывать ничего не пришлось, плюсы на моей машине стабильно на 20-30% сливают.
массивы
Чем это плохо?
unsafe
Только если
unsafeIndexи тому подобные вещи. Ну так сорян, когда вы на плюсах дёргаетеoperator[]у вектора, там точно такой жеunsafeIndex. И усилением системы типов хаскеля это починить получится (см. завтипы), а плюсов — нет.
А не нативная ленивость и нативные последовательности
Ленивость не является необходимым атрибутом кода на хаскеле. Она там по умолчанию, не более.
Нативность последовательностей… Ну, список не более нативен, чем
STUArray.
Если взять последовательность и умножить её на два — хаскель создаст новую последовательность, храня её состояние на каждой итерации.
Щито? Вы это вот имели в виду?
Prelude> ls1 = [1..] Prelude> ls2 = (2 *) <$> ls1
Если да, то о каком состоянии вы говорите?
yamlevekke
29.12.2019 10:18-1Да нет, почему, не так давно реализовал алгоритм Левенштейна, линейный по памяти — даже придумывать ничего не пришлось, плюсы на моей машине стабильно на 20-30% сливают.
Ещё раз, вы игнорируете часть моего тезиса. Кресты сливают потому, что ваша реализация слаба. Методика ваша проста. Вы поддерживаете своими лозунгами миф о том, что существуют какие-то быстрые языки. И что типа код на С++ — быстрый код и прочая чушь.
В реальности же производительность напрямую зависит от того, кто код написал. А язык лишь предоставляет возможности человеку. И разница между С++ и скриптухой в том, что возможностей в С++ на порядок больше. А значит человек, который сможет их раскрыть — получит лучший результат.
Очевидно, что если код пишет тот, кто не может и не умеет — разницы не будет никакой. Потому как абсолютно неважно то — какие возможности даёт язык. Человек(говнодел) их попросту не использует. И разница вся будет обусловлена качеством рантайма.
Чем это плохо?
Тем, что это нарушение базовых принципов ФП.
Только если unsafeIndex и тому подобные вещи.
Все вещи о которых вы что-то знаете. К этому нужно добавить те вещи, которые реализовали за вас другие срыватели покровов.
Ну так сорян, когда вы на плюсах дёргаете operator[] у вектора, там точно такой же unsafeIndex.
Не, это не прокатит. У С++ нету фп-методички и прочей чуши про безопасность, отсутствие состояний, мутаций и прочее. Конечно, когда вам нужно что-то доказать в интернете — вы тут же забываете про все эти методички и бежите делать "как там".
В это и разница. Вы делаете как там, когда хотите показать "быстро", но призываете делать "как тут", когда дело касается сравнений языков.
И усилением системы типов хаскеля это починить получится (см. завтипы)
Это мантра и не более того.
а плюсов — нет.
А это полная чушь — система типов в С++ сильнее хаскеля.
Ленивость не является необходимым атрибутом кода на хаскеле. Она там по умолчанию, не более.
Это дыра в логике. В конечном итоге в ситуации, когда человек в тупике — у него всё не является необходимым атрибутом. Очевидно, что у вас просто проблемы и вам выгодно отказываться от всего. В конечном итоге это дойдёт до того, что "фп ненужно", "типизация ненужна" и прочее. Что вы и делали и будите делать.
Нативность последовательностей… Ну, список не более нативен, чем STUArray.
Очевидно, что в скриптухи нативного ничего нет. И очевидно, что это враньё. Списки есть на уровне базовых синтаксических конструкций — их подразумевает семантика. Массив это просто левая либа, которая в принципе противоречит почти всем вашим догматам.
Если да, то о каком состоянии вы говорите?
Да, о каком состоянии — очевидно. Зачем включать "я ничего не понял", когда возникают идеологические проблемы? Абсолютно неважно то, считает ли ваша догматика это состоянием или нет — это состояние. А ваша догматика интересна лишь её адептам.
Я показал это на примере ниже. Там можно посмотреть.
0xd34df00d
29.12.2019 22:38+4Кресты сливают потому, что ваша реализация слаба.
size_t lev_dist(const std::string& s1, const std::string& s2) { const auto m = s1.size(); const auto n = s2.size(); std::vector<int64_t> v0; v0.resize(n + 1); std::iota(v0.begin(), v0.end(), 0); auto v1 = v0; for (size_t i = 0; i < m; ++i) { v1[0] = i + 1; for (size_t j = 0; j < n; ++j) { auto delCost = v0[j + 1] + 1; auto insCost = v1[j] + 1; auto substCost = s1[i] == s2[j] ? v0[j] : (v0[j] + 1); v1[j + 1] = std::min({ delCost, insCost, substCost }); } std::swap(v0, v1); } return v0[n]; }
Ждём продвинутую версию.
И разница между С++ и скриптухой в том, что возможностей в С++ на порядок больше.
Возможностей для чего?
Почему-то так получилось, что в C++ эти возможности сопряжены с выстреливанием себе в ногу. Я бы хотел, чтобы такие возможности были изолированы и явно помечены, а не допустимы в каждом месте кодовой базы.
Тем, что это нарушение базовых принципов ФП.
В каком месте ST — нарушение базовых принципов ФП?
Все вещи о которых вы что-то знаете. К этому нужно добавить те вещи, которые реализовали за вас другие срыватели покровов.
Они уже реализованы в компиляторе, компилятор про них знает и может о них рассуждать. В случае FFI компилятор ни о чём рассуждать не может.
Кроме того, операционных систем на чистом современном C++ не видно (да и не современном тоже не особо), так что что ж получается, что C++ — скриптуха?
Это мантра и не более того.
Ну да, возможность статически доказать, что индекс не выйдет за пределы массива — мантра. Как там в 50-х?
А это полная чушь — система типов в С++ сильнее хаскеля.
Лол.
Ну на плюсах-то это сделать, очевидно, тривиально, и можно уже давно, не так ли?
Это дыра в логике. В конечном итоге в ситуации, когда человек в тупике — у него всё не является необходимым атрибутом. Очевидно, что у вас просто проблемы и вам выгодно отказываться от всего. В конечном итоге это дойдёт до того, что "фп ненужно", "типизация ненужна" и прочее. Что вы и делали и будите делать.
Какой-то набор слов.
{-# LANGUAGE Strict #-}, Bang patterns? Не, не слышали.
Очевидно, что в скриптухи нативного ничего нет.
Прям как в плюсах (см. выше).
Списки есть на уровне базовых синтаксических конструкций — их подразумевает семантика.
Которые, тем не менее, компилируются в нативный код, точно так же использующий распределение памяти от ОС или внутреннюю мутабельность, если компилятор выведет, что это можно сделать.
Массив это просто левая либа, которая в принципе противоречит почти всем вашим догматам.
Изолированная мутабельность. Сделали,
runSTей, rank-2-полиморфизм убедился, что мутабельность не убежала, и всё.
Посмотрел бы я на такое в плюсах.
Да, о каком состоянии — очевидно. Зачем включать "я ничего не понял", когда возникают идеологические проблемы? Абсолютно неважно то, считает ли ваша догматика это состоянием или нет — это состояние. А ваша догматика интересна лишь её адептам.
Опять какие-то догматики у вас и ничего по существу. Скучно :(
yamlevekke
29.12.2019 23:08-5Ждём продвинутую версию.
Не, эти потуги меня не интересуют. Конкретно — бенчмарки и говно на скриптухе. Где оно — я не вижу? Что-то было быстрее — пруфы где?
Сначала пруфы того, что это говно сливает. Потом я уже покажу как нужно писать.
Почему-то так получилось, что в C++ эти возможности сопряжены с выстреливанием себе в ногу. Я бы хотел, чтобы такие возможности были изолированы и явно помечены, а не допустимы в каждом месте кодовой базы.
Эти потуги меня так же не интересует. Либо показываете где не сопряжены, либо это сектантские мантры.
В каком месте ST — нарушение базовых принципов ФП?
Таким. За примерами далеко ходить ненужно. Именно поэтому все ваши массивы — это левые либы, прикрученные сбоку.
В целом хорошо, что адепт секты начинает отказываться от методичке, когда она течёт. Я жду декларации тезисов "состояние — хорошо. Иммутабельность — плохо. Чистота — говно".
Они уже реализованы в компиляторе, компилятор про них знает и может о них рассуждать. В случае FFI компилятор ни о чём рассуждать не может.
Очередная нелепая чушь. О чём он там знает — пруфы.
Кроме того, операционных систем на чистом современном C++ не видно (да и не современном тоже не особо), так что что ж получается, что C++ — скриптуха?
Опять какая-то методичка дырявая. Особенно в ситуации со мною. Срочно чинить. С++ — си. На си ОС есть, все. Методичка поломалась.
Ну да, возможность статически доказать, что индекс не выйдет за пределы массива — мантра. Как там в 50-х?Очередные сектантские завывания. Я жду пример хелоуворда в котором это доказано статически. Я не буду говорить о чём-то больше — просто хотя бы это.
Ну на плюсах-то это сделать, очевидно, тривиально, и можно уже давно, не так ли?
Опять чушь. Каким образом эта херня связана с мои тезисом, а так же пример того, что на мусорной скриптухи можно сделать, а на С++ нет.
Какой-то набор слов.
Обоснования этой нелепой херне.
Прям как в плюсах (см. выше).
Обоснования этой нелепой херни. Ну и оправдания за то, что гений наш пыхтит над легаси говном на С++ вместо срывов покровов на скриптухи? Чего же так? Как там собеседования? Перепастилось с СО? Пыхтел месяц? Ну ничего — аудитория тут высокого уровня — гении быстро начинают забывать кто они и что они.
Которые, тем не менее, компилируются в нативный код, точно так же использующий распределение памяти от ОС или внутреннюю мутабельность, если компилятор выведет, что это можно сделать.Полная чушь. Именно поэтому наш гений бежит перепащивать крестовое говно на ансейфам и массивах. А чего же так? Чего не ваяется на нативном то коде? Нативный же?
Ой, а в любой скриптухе jit и там тоже всё нативное. Ой, да наш гений опять запытался. Методичка устарела лет на 20? Ну ничего. Бывает.
Изолированная мутабельность. Сделали, runST ей, rank-2-полиморфизм убедился, что мутабельность не убежала, и всё.
Как там, много наизолировалось? А пока кто-то изолирует — кто-то пыхтит над легаси говном и месяц пыхтит над пастой с СО. Бывает.
Посмотрел бы я на такое в плюсах.
Что посмотреть? Как лабу сбацать? Здесь таким не занимаются.
Опять какие-то догматики у вас и ничего по существу. Скучно :(
Да, ответ достойный адепта. "Я не я, я ничего не понял". "сольюсь по быстрому".
0xd34df00d
29.12.2019 23:24+2Не, эти потуги меня не интересуют.
Понятно. Ваши аргументы не аргументы.
Сначала пруфы того, что это говно сливает.
А это не интересует уже меня. Давайте вы напишете настоящую правильную эффективную версию, а не тот говнокод, что у меня получился.
Эти потуги меня так же не интересует. Либо показываете где не сопряжены, либо это сектантские мантры.
В том, что весь C++ — это один большой unsafe.
Таким.
Аргумент.
В целом хорошо, что адепт секты начинает отказываться от методичке, когда она течёт. Я жду декларации тезисов "состояние — хорошо. Иммутабельность — плохо. Чистота — говно".
Возможность иметь верифицированно локальное состояние — хорошо. Возможность иметь локально ограниченную мутабельность — хорошо.
Возможность иметь гранулированный контроль за эффектами — хорошо.
Не иметь этого везде и всегда — плохо.
Очередные сектантские завывания. Я жду пример хелоуворда в котором это доказано статически. Я не буду говорить о чём-то больше — просто хотя бы это.
В хаскель завтипы ещё не завезли. Посмотрите на языки, куда завезли.
Именно поэтому наш гений бежит перепащивать крестовое говно на ансейфам и массивах.
Вы не слышали, что структуры данных нужно подбирать под задачу?
Как там, много наизолировалось?
Да, нормалёк. Соответствующая библиотека в итоге выдаёт совершенно чистый API без грязных хаков типа
unsafePerformIO.
Что посмотреть? Как лабу сбацать? Здесь таким не занимаются.
Что, даже лабы не смогли?
Да, ответ достойный адепта. "Я не я, я ничего не понял". "сольюсь по быстрому".
Беру пример с лучших.
yamlevekke
30.12.2019 00:25-5А это не интересует уже меня. Давайте вы напишете настоящую правильную эффективную версию, а не тот говнокод, что у меня получился.
Ну т.е. я могу фиксировать балабольство?
Не иметь этого везде и всегда — плохо.
Враньё. Почему тогда все эти нелепые хеллоуворлды на скриптухи состоят из этого на 99%. Опять потекла методичка — срочно нужно латать.
В хаскель завтипы ещё не завезли. Посмотрите на языки, куда завезли.
Нет, опять методичка потекла. Разговор был о хаскеле. К тому же, зачем мне смотреть на говно? Да и чего-то я не вижу реализаций хелоуворлда выше на этом говне? Опять методичка течёт? Ну бывает.
Вы не слышали, что структуры данных нужно подбирать под задачу?
Опять методичка потекла. С вас просили основания, а не очередную херню. Где основание предыдущим тезисам, где ответ на мой вопрос? Опять несмоглось?
Да, нормалёк. Соответствующая библиотека в итоге выдаёт совершенно чистый API без грязных хаков типа unsafePerformIO.
Опять сектантские завывания. Он не может быть чистым по определению. К тому же, api этим можно только подтереться.
Что, даже лабы не смогли?
Да, я же не клоун из интернета чтобы заниматься подобной хернёй. Для этого существуют специальные адепты, отборные.
Беру пример с лучших.Я не сомневаюсь. Какие же вы тут все слабые. Хотя сомнительно, что я встречу когда-то сильного сектанта.
0xd34df00d
30.12.2019 01:17+5Ну т.е. я могу фиксировать балабольство?
Ну раз не хотите показывать правильную версию, то да, видимо, придётся фиксировать.
Почему тогда все эти нелепые хеллоуворлды на скриптухи состоят из этого на 99%.
Из чего — этого? Вы уж определились бы.
Разговор был о хаскеле.
Я сразу написал: «И усилением системы типов хаскеля это починить получится (см. завтипы), а плюсов — нет.» То естЬ, сейчас там этого нет. Куда стремиться — понятно. Работа идёт, пропозалы пишутся и принимаются.
Опять методичка течёт?
Опять методичка потекла.Тяжко, наверное, жить в мире, где для борьбы со священными плюсами аж методички пишут.
Он не может быть чистым по определению.
По какому такому определению?
К тому же, api этим можно только подтереться.
Не знаю, у меня и использовать его вполне получалось.
yamlevekke
30.12.2019 01:39-6Ну раз не хотите показывать правильную версию, то да, видимо, придётся фиксировать.
Опять балабольство, фиксируем начальное балабольство:
Да нет, почему, не так давно реализовал алгоритм Левенштейна, линейный по памяти — даже придумывать ничего не пришлось, плюсы на моей машине стабильно на 20-30% сливают.
Цитируем мой ответ(его часть):
Ещё раз, вы игнорируете часть моего тезиса. Кресты сливают потому, что ваша реализация слаба. Методика ваша проста.
Т.е. здесь упоминается "сливает", т.е. оно должно сливать. И контекст заключается в этом. Вам нужно отвечать на это и за это. Где доказательства слива? Где бенчмарки?
Из чего — этого? Вы уж определились бы.
Ну всё, адепт скриптухи совсем поплыл — это конечная.
Цитирую базовое балабольство:
Не иметь этого везде и всегда — плохо.
Здесь данный адепт почему-то знал что такое "это" и именно под этой цитатой написан мой ответ.Теперь же, когда адепт в лужу то сел — начались манёвры вида "я ничего не знаю". Типичная клоуна достойная адепта скриптухи все тезисы которого — враньё и херня.
Я сразу написал: «И усилением системы типов хаскеля это починить получится (см. завтипы), а плюсов — нет.» То естЬ, сейчас там этого нет. Куда стремиться — понятно. Работа идёт, пропозалы пишутся и принимаются.
Меня не интересуют эти потуги. Меня интересует то на каком основании адепт подменил контекст и начал вещать о каких-то там других языках.
К тому же, адепт так и не обосновал балабольство на тему "плюсов — нет". Что и требовалось доказать.
Тяжко, наверное, жить в мире, где для борьбы со священными плюсами аж методички пишут.
Да нет, плюсы тут не причём. Просто адепты настолько слабые, что все их тезисы — это методичка из интернета и пару трюков. Что мы и наблюдаем. А ну и табун сектантов, которые минусуют.
По какому такому определению?
По моему. И по любому другом за пределами секты. api никак на чистоту не влияет и не может "грязное" сделать чистым.
Именно на этом плывут все сектанты, которые считают, что раз их методичка говорит "чистое" — значит чистое. Хотя очевидно, что методичка сектантов будет говорить то, что выгодно сектантам.
Не знаю, у меня и использовать его вполне получалось.
Чёт методичка опять потекла. То "уже не нужен", то "получается". К тому же, здесь опять типичные сектантские завывания. Использовать можно любое api и факт его использования никак и ни о чём не говорит.
St_one
28.12.2019 23:30Что значит "в c++ честная ленивость". По какой классификации вы делите ленивость, и как определить честную/нечестную? Насколько я знаю в c++ вообще нет ленивости на уровне языка(или в новых версиях появилась?).
А хаскель, насколько я знаю, ничего с последовательностью умноженной на 2 делать не будет, пока не понадобится результат.isden
28.12.2019 23:56> А хаскель, насколько я знаю, ничего с последовательностью умноженной на 2 делать не будет, пока не понадобится результат.
Все так, и поэтому можно делать штуки вроде вот таких:
Prelude> fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ] Prelude> take 10 fib [1,1,2,3,5,8,13,21,34,55] Prelude> one = 1 : one Prelude> take 5 one [1,1,1,1,1]
Т.е. из бесконечного списка берется и вычисляется только нужное количество элементов.yamlevekke
29.12.2019 10:46-1Все так, и поэтому можно делать штуки вроде вот таких:
Ахренеть какие штуки. Всем штукам штуки. В целом я понимаю почему всё происходит так как происходит. Люди слишком наивные и такая херня у них вызывает удивление. Тем и пользуются всякие пропагандисты, которые вливают им в уши "это хаскель — это круто. Никто не может. Тут всё ахренеть как сложно" и прочее.
В реальности же — это примитивная херня. Её нигде нет не потому, что она такая крутая — нет. Она имеет множество ограничений и множество проблем.
Поэтому опять пришли адекватные люди и показали то как нужно делать.
yamlevekke
29.12.2019 10:05-1Что значит "в c++ честная ленивость".
То и значит. Выше уже обсуждали про RA для последовательностей.
По какой классификации вы делите ленивость, и как определить честную/нечестную?
По простой. Честная может больше.
Насколько я знаю в c++ вообще нет ленивости на уровне языка(или в новых версиях появилась?).
С++ это не мусорая скриптуха — ей там и ненужно быть на уровне языка(да и каким образом она может быть на уровне языка?).
А хаскель, насколько я знаю, ничего с последовательностью умноженной на 2 делать не будет, пока не понадобится результат.
Будет.
Последовательности в хаскеле работают как генераторы. И они работают только в том случае, когда последовательность читается последовательно. Когда же нужно RA — её пихают в список.
int main() { auto gen = std::mt19937{}; auto ints = iota(0ul);// 0 ... inf auto rands = generate(gen); auto take10 = take(10); //это достаточно очевидно, так работает хаскель print(ints | take10); print(rands | take10); // но вот то о чём я говорю. Разница в дизайне // мы имеем RA к бесконечной последовательности. // На хаскеле этого не сделать - нужно менять семантику // т.е. реализовать это таким образом, что-бы не использовать RA // Что-бы реализовать семантический эквивалент - нужно написать [0..] со всеми вытекающими. print(rands | transform(at(ints)) | take10); //можно проводить какие угодно трасформаци 1 к 1 auto ints2 = ints | transform(_ / 2); print(ints2 | take10); print(rands | transform(at(ints2)) | take10); //проблему можно увидеть здесь // rands[100];// семантика как в хаскеле // print(at(rands | transform(at(ints2)))(100500));// аналогично //и как и в хаскеле решается она просто: // (rands | to<std::vector>())[10];//это отвалится с OoM, в хаскеле нет print((rands | take10 | to<std::vector>())[9]);//так работает, как и в хаскеле !! 9 // чуть изменим код выше // ints = 0 : [ a + 1 | a <- ints ] // ints !! 100000000000 // пошло жрать память бесконечно // в примере выше такой проблемы нет, потому как на уровне генераторов существует RA print(ints[100000000000]); }
St_one
29.12.2019 11:11Нет, вы не правы. Хаскель ничего не будет делать со списком, пока не потребуется результат. RA никакого отношения к ленивости не имеет.
О какой семантике речь, если в хаскеле [a] это явное описание связанного списка. У вас в С++ есть RA по связанному списку? Нет.
Т.е у вас нет никакой классификации и вы сравниваете мягкое и теплое.yamlevekke
29.12.2019 11:59Нет, вы не правы.
Я прав.
Хаскель ничего не будет делать со списком, пока не потребуется результат
Чушь нелепая. Здесь чётко описан кейс, где результат требуется. Зачем писать херню? Дан пример — где код, который работает с данной семантикой? Кода нет — трёп есть.
RA никакого отношения к ленивости не имеет.
Имеет, прямое. То, что хаскель так не может — это не значит, что эта скриптуха имеет монополию на понятие ленивости. Здесь видно типичную сектантскую защиту — "у меня нет — отношения не имеет".
О какой семантике речь, если в хаскеле [a] это явное описание связанного списка. У вас в С++ есть RA по связанному списку? Нет.О такой. что список в хаскеле взялся только от того, что никак иначе это не реализовать с той же семантикой. Поэтому хаскель кастует последовательность к списку, когда нужно взять по индексы.
Т.е. кстати, ваша методичка потекла. Потому как если бы доступ по индексу к последовательностям был бы ненужен, то такого функционала попросту не было бы.
У вас в С++ есть RA по связанному списку? Нет.
Он и ненужен, потому как С++ для этого случая связный список ненужен. Связный список — это проблемы вашей скриптухи, которая обусловлена проблемой в дизайне скриптухи.
Т.е у вас нет никакой классификации и вы сравниваете мягкое и теплое.
Есть.
St_one
29.12.2019 12:18Скриптуха это как-раз плюсы, с его темплейтами и инклудами. Вы не понимаете что пишите просто. Ничего никуда не кастуется, вы явно описываете связанный список и хотите от него рандомного доступа. Это глупость, видно что вы просто не знаете как работают алгоритмы в принципе, не только в хс или плюсах. Зато орете громче всех.
yamlevekke
29.12.2019 12:29Ну всё, адепт поплыл. Пошли обвинения и прочая чушь, но ответа нет.
Сразу опишу методичку данного адепта. Схема простая. Я выкатываю тезис "для решения задачи в хаскель-скриптухе я обязан использовать список, а он говно". Далее адепт данной секты начинает нести херню вида "да ты сам написал список, да это базовая семантика списка" и прочую чушь.
Но это чушь потому, что проблема не в том, что список говно. И я не говорю, что в С++ он будет не говно(хотя таким говном как в этой скриптухи он не будет никогда, очевидно). Я говорю о том, что С++ не требует списка, в отличии от хаскель скриптухи.
Т.е. проблема заключается не списке как данный адепт секты святой скриптухи пытается вам сообщить. Проблема в его наличии. В том, что данная скриптуха заставляет использовать список. Либо переписывать алгоритм таким образом, чтобы убрать RA.
Но я не хочу убирать RA там, где оно есть. Я не хочу во имя веры писать говно и страдать.
Ничего никуда не кастуется, вы явно описываете связанный список и хотите от него рандомного доступа.
Я не описываю связный список. Адепт врёт. То, что здесь связный список — это проблема хаскеля. В хаскеле иначе не сделать.В общем, "зато орёте" мы поступим просто. "орёте" пойдёт и реализует RA для ints, т.е. реализует семантику массива.
St_one
29.12.2019 12:33-1Адепт здесь только один, и это не я. То что вам чего-то от меня хочется — не мои проблемы. Я просто показываю что вы не знаете о чем говорите. И вы уже сто раз расписались в своем невежестве, товарищ Скриптуха Адептуха
0xd34df00d
29.12.2019 23:11+2О такой. что список в хаскеле взялся только от того, что никак иначе это не реализовать с той же семантикой. Поэтому хаскель кастует последовательность к списку, когда нужно взять по индексы.
Хаскель ничего никуда не кастует.
Потому как если бы доступ по индексу к последовательностям был бы ненужен, то такого функционала попросту не было бы.
!!очень сильно не рекомендуется использовать. Если вам нужен доступ по индексу — используйтеData.Vectorс константным доступом, илиData.Sequenceс логарифмическим (вообще отличная структура данных, если вам нужна именно структура данных, а не гибрид итератора с траверсалом).
billyevans
30.12.2019 08:59Там слишком ограниченные итераторы. Поэтому раст так же не может быть таким же быстрым как С++.
А почему тогда у реализации stl С++ rb-дерева есть указатель на предка?
FForth
28.12.2019 17:10Quick-Sort на Rust (и других языках, в том числе и функциональных близких к ним, например Factor)
rosettacode.org/wiki/Sorting_algorithms/Quicksort#Rust
P.S. Вот бы сравнение в статье было по разным реализациям одного и того же на разных языках. :)
technic93
28.12.2019 17:16на раст можно было так
fn sort_fun(arr: Vec<f64>) -> Vec<f64> { if arr.len() <= 1 { arr } else { let pivot = arr[arr.len() / 2]; [ sort_fun(arr.iter().filter(|&&x| pivot > x).cloned().collect()), arr.iter().filter(|&&x| pivot == x).cloned().collect(), sort_fun(arr.iter().filter(|&&x| pivot < x).cloned().collect()), ] .concat() } }
freecoder_xx
28.12.2019 21:55+1fn sort(arr: Vec<f64>) -> Vec<f64> { if arr.len() <= 1 { arr } else { let pivot = arr[arr.len() / 2]; let (a, b): (_, Vec<_>) = arr.into_iter().partition(|&x| pivot > x); let (b, c) = b.into_iter().partition(|&x| pivot == x); [sort(a), b, sort(c)].concat() } }lgorSL
29.12.2019 17:21Кстати, в скале такая замена фильтрации на partition заметно ускорила код. У меня получилось 15 секунд вместо 20.
def sort_fun_2(arr: Array[Double]): Array[Double] = { if (arr.length <= 1) arr else { val pivot = arr(arr.length / 2) val (b, le) = arr partition (pivot < _) val (l, e) = le partition (pivot > _) Array.concat(sort_fun_2(l), e, sort_fun_2(b)) } }
P.S. Я ещё попробовал вариант с
groupBy(d => if (d > pivot) 1 else if (d < pivot) -1 else 0), время около 18 секунд.
MooNDeaR
28.12.2019 16:49выигрыш от Rust получился всего 20 %.
"Всего"? :) Да 20% — это довольно много так-то, в такой тупой задаче, которую JVM совершенно нормально может оптимизировать.
Вся скорость Rust (да соббсно и С++) основывается на аццком инлайнинге за счёт "мономорфизации" (читай шаблонов). На такой задаче результат этих оптимизаций не раскрыть.
Да и вообще, если уж на то пошло, Rust уже позиционирует себя как язык с функциональной парадигмой, да все его API стандартной библиотеки насквозь ФП-шные. От этого не понимаю смысла заголовка.
balajahe Автор
28.12.2019 17:07Просто для меня ФП-шность Rust-а стала определенным открытием, становятся ненужны всякие лайфтаймы, за которые Rust и недолюбливают.
MooNDeaR
28.12.2019 17:16+1Лайфтаймы — это ключевая фишка Rust) За счёт них получается обеспечить memory safety на этапе компиляции, что как бы очень круто, но объяснять эту крутость мне оч лень :)
В конце концов, если вам так уж плохо от лайфтаймов, оборачивайте все в
std::rc::Rc(или жеstd::sybc::Arc) и живите счастливо (нет) используя interior mutability :) Вы получите ровно то, что хотите в рантайме, но тогда зачем вам Rust?
А конце концов Rust позиционируется как замена Си (и иногда Си++), т.е. замена системным языкам. Для написания ОС вот уже точно ФП не подходит от со+ва совсем)
balajahe Автор
28.12.2019 17:28Это да. Мне просто до системщины далеко, а хочется быстрый прикладной код. Ковырял Go но это как-то совсем грустно, счетчик ссылок Rc — это еще медленней чем GC, достаточно посмотреть на Swift, который чудес производительности не показывает. Получается, что для моей прикладухи — ФП с обильным копированием данных — лучший выход.
freecoder_xx
28.12.2019 22:02В Swift вроде не посто Rc, а Arc (если проводить аналогию с Rust).
balajahe Автор
28.12.2019 22:06Ну да, конечно. В последнее время мне кажется что дешевле кусок данных скопировать чем заморачиваться со ссылками, счетчиками, временами жизни, отсюда и интерес к ФП )
0xd34df00d
28.12.2019 22:06Ещё интереснее статически доказывать, что ничего никуда копировать, считать, и так далее, не надо. Region inference, все дела.
balajahe Автор
28.12.2019 22:14Вообще, это такая бомба под JVM, которой либо придется уступить место компилируемым языкам, либо стать операционной системой.
0xd34df00d
28.12.2019 18:27Я был бы очень рад видеть в хаскеле аффинные типы, и я очень рад в идрисе 2 видеть quantitative type theory, что настолько близко к лайфтаймам раста, насколько ФП может быть к ним близко.
yamlevekke
28.12.2019 18:48что настолько близко к лайфтаймам раста
А зачем быть к ним близко? Они достаточно слабы и ограничены. Вся stdlib обмазана unsafe-хаками. Система типов должна быть управляема с уровня языка. Чтобы условный итератор был реализован через unsafe-хак, который никак и ничем не верифицируется, кроме общения разработчиков.
0xd34df00d
28.12.2019 22:00Система типов должна быть управляема с уровня языка.
Чтобы на каждый чих доказывать progress + preservation (что часто сделать изнутри языка нельзя, потому что Гёдель, мать его)? Спасибо, но нет.
Чтобы условный итератор был реализован через unsafe-хак, который никак и ничем не верифицируется, кроме общения разработчиков.
Зачем явно хотеть этого, если можно реализовывать формально верифицированные итераторы?
NeoCode
28.12.2019 18:14А есть еще «объектно-ориентированный» (или «модульный»?) подход, когда просто берется готовая и многократно проверенная реализация сортировки из библиотеки:)
На самом деле я не против функциональных подходов, более того — те же лямбда-функции для меня были одной из самых ожидаемых фич С++. Функции как объекты первого класса это очень круто и удобно.
Но вот жертвовать производительностью и пересоздавать массивы каждый раз… ну не знаю, я на такое не готов.balajahe Автор
28.12.2019 19:43Классика жеж. И потом, если копирование дешевое — почему бы не скопировать. Просто надо выбрать меньшее зло — лишние аллокации памяти или GC — для разных задач будет разный ответ.
Siemargl
28.12.2019 20:56Копирование дешевое — это когда памяти хватает.
У вас для сортировки 80МБ данных используется 650Мб o_O
Ну и сравнение разных алгоритмов, в т.ч разных rand — та еще профанация.
Код на С с розетты требует 80Мб (и, что уже смешно, выполняется на дохлом хостинге за 1,03с, что позволяет не считаться с 20% в сравнении LOL)balajahe Автор
28.12.2019 21:10Про rand не понял, сравнивалась только сортировка, уже после инициализации массива. Императивщина не расходует память — хоть на С хоть на Rust будет 80Мб, только на расте еще бинарь 2.7Мб.
Функциональщина расходует память, так как рекурсия нехвостовая. И на C будет расходовать.
Я в целом не спорю что императивщина практичнее, просто когда у вас кластер, тот же SPARK например, как вы расшарите мутабельный стейт между нодами? Поэтому и передают через сеть большие куски данных (копируют то есть), а в алгоритмах функциональщина рулит, тот же спарк на скале написан.Siemargl
28.12.2019 23:12Про rand не понял, сравнивалась только сортировка, уже после инициализации массива.
из исходников этого не следует.
Докажите
Я бы предложил взять «плохую» С-реализацию за базу и с ней сравнивать.
PS.rand() — дорогая функция, сильно зависит от реализации, в бенчах ее надо исключать.balajahe Автор
28.12.2019 23:38Я с вами согласен, у меня не было особой цели бенчить, был смысл показать скорость ФП на Rust. И совершенно не спорю, что C/++ быстрее, но меня Rust интересует исключительно как прикладной язык для бигдаты, потому что на нем можно не заморачиваться знаниями о стеке, куче, указателях и деструкторах, достаточно выучить понятие ссылка )
Siemargl
29.12.2019 00:16для бигдаты проблема временной памяти для обработки стоит особенно остро.
так что лишнее копирование пары ТБ из-за синтаксиса загонит вас в тупикbalajahe Автор
29.12.2019 00:26Ну, в классическом map/reduce ничего не копируется, все однопроходно и примитивно, итераторы обычно zero-cost, а если алгоритм сложнее и нужно часть данных в памяти хранить — вот тут и важно чтобы язык делал это максимально компактно. Я пока не понял, нужно мне чистое ФП или не нужно.
svr_91
30.12.2019 14:14> Про rand не понял
Кстати, нельзя бенчмаркать «быстрые» функции, выполняющиеся после медленных. rand — медленная. Советую сгенерировать массив rand-ом и скопировать его целиком в исходникbalajahe Автор
30.12.2019 14:39В смысле, не понял, 80 Мб жеж.
fn main() { const COU :usize = 10000000; use rand::Rng; let mut rng = rand::thread_rng(); let mut arr = Vec::<f64>::with_capacity(COU); for _ in 1..COU { arr.push(rng.gen::<f64>()); } let tbegin = std::time::SystemTime::now(); //sort_imp(&mut arr); arr = sort_fun1(arr); println!("{:?}", tbegin.elapsed().unwrap()); }svr_91
30.12.2019 14:53+1Вроде я когдато видел такой тест, что
slow_func()
tBegin =
fast_func()
tEnd =
Давало результат в худшую сторону, чем просто
tBegin =
fast_func()
tEnd =
Притом что slow_func и fast_func могуть быть как связаны друг с другом, а могут и не связаны.
Возможно это как-то связано с тем, что процессор после медленной функции начинает троттлить или что-то еще.
Сейчас сходу набросал пример, но не получилось такого поведения поймать. Но ситуация имеет место бытьbalajahe Автор
30.12.2019 15:08При активном выделении / освобождении памяти может ОС залипать, или GC. Но в Rust нет никакого рантайма, всю память под вектор я выделил заранее, так что бенч будет точным.
PsyHaSTe
30.12.2019 15:34+1Но частично советом можно воспользоваться. Я всегда в тестах предпочитаю задавать сид, чего и вам желаю. А то потом "счастливой отладки" и пытайся понять, почему вдруг поведение поломалось.
stilic
28.12.2019 18:44Для императивной реализации — выигрыш от Rust получился всего 20 %. Это означает, что JVM вплотную приблизилась к нативной производительности, и тут уже нечего улучшать.
Не всего 20%, а аж целых 20% разницы.
Быстрота JVM не будет удивлять вас, если вы вспомните о JIT.
Вывод — Rust как будто специально создан для ФП, хотя возможности его синтаксиса пока не дотягивают до Scala.
Зачем тянуть в один язык возможности языка другого? Только потому, что к возможностям Scala вы привычны?
Создайте новый. LLVM сейчас позволяет это делать вполне себе полноценно и в одного.yamlevekke
28.12.2019 18:52Зачем тянуть в один язык возможности языка другого? Только потому, что к возможностям Scala вы привычны?
Почему в С++ скала воспроизводится 1в1, а в расте нет? Проблема тут не в том, что автор привык и что это какие-то там возможности. Это выразительность языка и его возможности, которые позволяют создавать выразительные надёжные интерфейсы.
В данном случае(да и во многих других) раст попросту слаб чтобы воспроизвести выразительность. И нужно развивать язык стремясь к "красиво и удобно", а не закрываться "уродливо — это наша фишка". Это не фишка — это недоработка.
balajahe Автор
28.12.2019 19:37Обновил статью — скомпилировал в Scala Native, функциональная реализация — 63 секунды, то есть еще хуже, значит LLVM не панацея, сборщик мусора все равно нужно линковать, да и не предназначены эти JVM-языки для нативной компиляции, хотя и могут.
PsyHaSTe
29.12.2019 14:21Джит сильно ограничен бюджетом времени. Раст/сишную программу компилить час на сервере спокойно можно, а вот попросить юзера подождать — не выйдет.
Потому кстати в андроидах аоты и стали популярны.
stilic
28.12.2019 23:18+1Если писать императивно, с использованием общего изменяемого состояния — прикладному программисту нет смысла переходить с управляемых языков на компилируемые
Гы.
1) Scala компилируемый.
2) Вы проверили только 2 языка по 2 ситуации — и уже делаете далеко идущие выводы.
Может оно и так.
А может и не так.
Вашего одиночного эксперимента недостаточно.balajahe Автор
28.12.2019 23:27-1В статье приведены замеры в т.ч. и для Scala Native. В целом согласен что все выводы лишь частный случай.
Keynessian
29.12.2019 07:31-1Rust должен стать функциональным языком программирования
Чтобы Rust жрал даже в простеньких приложениях память как в не себя из-за иммутабельности?
Keynessian
29.12.2019 11:56Никому из минуснувших не кажется, что это УБЬЁТ те преимущества которые имеет Rust?
Mingun
29.12.2019 12:15Почему? Иммутабельность только в концепции, при компиляции будет вполне себе мутабельное состояние. Именно потому, что компилятор знает, что если мы делаем "копию" иммутабельного объекта и более этот иммутабельный объект не используется, то никакой реальной копии делать не нужно. О том, что объект более не используется, компилятору расскажет borrow checker. А ему в свою очередь — сюрприз — программист, который правильно определит в коде, где использовать ссылки, а где передачу владения. И в нужных местах расставит метки, сколько живет тот или иной объект по отношению к другим объектам (но обычно это не нужно, компилятор способен сам это вывести во многих случаях).
0xd34df00d
29.12.2019 23:43+2но обычно это не нужно, компилятор способен сам это вывести во многих случаях
Это на самом деле одна из причин, почему линейные типы так долго едут в хаскель — по мнению экспертов по ghc, в подавляющем большинстве случаев компилятор может и сам вывести нужные аннотации (хотя я в это не верю, но нутрянка ghc для меня — тёмный лес), а с точки зрения корректности профит не столь оправдан, особенно учитывая, что есть прочие способы достигнуть похожих эффектов.
mayorovp
29.12.2019 12:31На картинке изображены проблемы сборки мусора и проблемы раздутых страниц, а вовсе не проблемы иммутабельности.
TargetSan
29.12.2019 12:36Для начала, Rust уже поддерживает функциональную парадигму. Просто функциональное программирование прежде всего про композицию функций, а уж потом про иммутабельность. Так что вам никто не мешает в ржавчине иметь мутабельное состояние — но там, где явно попросите. И нормальный квиксорт там пишется не сложнее чем на других императивных языках.
Хром, к слову, написан на том самом С++. И жрёт память из-за агрессивного кеширования, а также прожорливости JS в целом.
vintage
29.12.2019 12:28if (i <= j) swap(i, j)
Как-то странно вы реализовали алгоритм Хоара.
Правильно было бы как-то так:
auto quickSort( Item )( Item[] items ) { if( items.length < 2 ) return items; auto pivot = items[ $ / 2 ]; size_t left = 0; size_t right = items.length - 1; while( left < right ) { while( items[left] < pivot ) ++left; while( items[right] > pivot ) --right; if( left >= right ) break; swap( items[left++] , items[right--] ); } items[ 0 .. left ].quickSort; items[ left .. $ ].quickSort; return items; }
При этом в императивной форме алгоритм простой, понятный и гарантированно быстрый. А что там наоптимизирует компилятор в функциональной форме — одному рандому известно.
Boomburum у вас на больших страницах адски грузит процессор яндекс-метрика:
balajahe Автор
29.12.2019 14:37Спасибо за уточнение. Я просто пытаюсь понять границы применимости функциональщины. Индустрия разработки UI похоже достигла консенсуса, и например Flutter насквозь функциональный, стейт вынесен в отдельные классы, остальное иммутабельное. И несмотря на необходимость уборки мусора — иммутабельные виджеты кэшируют по параметрам конструктора, и в целом получается хорошая скорость. А вот применима ли функциональщина в бекэнде — для меня вопрос открытый.
PsyHaSTe
29.12.2019 13:43Вот не зря я статью писал, но никто её не читает...
Вот вам на хаскелле пример, чистый ФП язык
{-# LANGUAGE BangPatterns #-} import qualified Data.Vector.Generic as V import qualified Data.Vector.Generic.Mutable as M import qualified Data.Vector.Unboxed as U import System.CPUTime import Text.Printf qsort :: (V.Vector v a, Ord a) => v a -> v a qsort = V.modify go where go xs | M.length xs < 2 = return () | otherwise = do p <- M.read xs (M.length xs `div` 2) j <- M.unstablePartition (< p) xs let (l, pr) = M.splitAt j xs k <- M.unstablePartition (== p) pr go l; go $ M.drop k pr main :: IO () main = do let input = reverse [1..1000000] :: [Int] start <- getCPUTime let !result = qsort $ V.fromList input :: U.Vector Int end <- getCPUTime print result let diff = (fromIntegral (end - start)) / (10^12) printf "Computation time: %0.9f sec\n" (diff :: Double) return ()
На моей машине миллион интов сортируются за 0.09375 sec.
Хотел сравнить с вашим вариантом:
fn main() { let mut input: Vec<_> = (1..1000000).rev().collect(); let result = { sort_imp(&mut input); input }; println!("{:?}", result); } fn sort_imp<T: Ord + Copy>(arr: &mut Vec<T>) { fn swap<T: Ord + Copy>(arr: &mut Vec<T>, i: usize, j: usize) { let t = arr[i]; arr[i] = arr[j]; arr[j] = t; } fn sort1<T: Ord + Copy>(arr: &mut Vec<T>, l: usize, r: usize) { let pivot = arr[(l + r) / 2]; let mut i = l; let mut j = r; while i <= j { while arr[i] < pivot { i += 1; } while arr[j] > pivot { j -= 1; } if i <= j { swap(arr, i, j); i += 1; j -= 1; } } if l < j { sort1(arr, l, j); } if j < r { sort1(arr, i, r); } } sort1(arr, 0, arr.len() - 1); }
Но к сожалению он паникует в рантайме. У вас где-то отрицательный usize получается.
Какие выводы тут можно сделать? Ну, например такой, что на ФП вполне можно забить на неизменяемость в угоду производительности (не устану это повторять из раза в раз).
Во-вторых раст вряд ли вообще выйдет назвать ФП языком. Тут и факт того, что боксы дорогие, да и эргономика языка: с точки зрения любого фп Fn/FnMut/FnOnce это одно и то же, в расте — совершенно разные типы, от которых невозможно абстрагироваться (привет HKT/GAT). Чтобы было понятно, как влияют разные трейдофы на язык, сравние вот такую вот стейт монаду написанную на скале (раз уж у нас в статье примеры на ней):
def stateMonad[S]: Monad[State[S, ?]] = { type StateS[T] = State[S, T] new Monad[StateS] { override def mreturn[A](a: => A): StateS[A] = State(s => (a, s)) override def bind[A, B](f: StateS[A])(g: A => StateS[B]): StateS[B] = State[S, B]( s1 => { val (a, s2) = f.run(s1) g(a).run(s2) } ) } }
И вот такой вот простейший читаемый раст:
use std::marker::PhantomData; struct StateM<F, S, A>(F, PhantomData<S>) where F: FnOnce(S) -> (A, S); fn mreturn<A, S>(a: A) -> StateM<impl FnOnce(S) -> (A, S), S, A> { StateM(move |s| (a, s), PhantomData) } fn bind<F, S, A, B, U, R>(m: StateM<F, S, A>, f: U) -> StateM<impl FnOnce(S) -> (B, S), S, B> where F: FnOnce(S) -> (A, S), U: FnOnce(A) -> StateM<R, S, B>, R: FnOnce(S) -> (B, S), { StateM(move |s| { let (a, s) = (m.0)(s); (f(a).0)(s) }, PhantomData) }
с 6(!!) генерик параметрами вместо двух. А там где в ФП их будет 3-4 в расте будет под два десятка.
Ну и в-третьих сама кор тима не склонна такие вещи внедрять.
mayorovp
29.12.2019 14:47с точки зрения любого фп Fn/FnMut/FnOnce это одно и то же
Ну не совсем. Если
Fn(X) -> Y— это в ФПX -> Y, тоFnMut(X) -> Y— это скорееX -> State s Y, ну аFnOnce(X) -> Y— это какlinear (X -> Y).PsyHaSTe
29.12.2019 14:49Ок, про FnMut понятно, его просто нет. А про linear, большинство ЯП не выносят это в типы.
Всё же есть некоторый трейдоф между выразительностью системы типов и продуктивностью. Boring Haskell, все дела. Они конечно топят за странные (плохие) вещи, но сама поднятая ими проблема — реально существует, и требует адресации.
balajahe Автор
29.12.2019 18:20паникует в рантайме
Каюсь, взял из мануала не проверив, он нестабильный, иногда падает, исправлю.
По поводу ФП с мутабельностью — я в курсе вашей позиции и статью читал :), этот подход точно не добавит популярности Rust, и вообще непонятно — а зачем нам такое ФП? Основная плюшка ФП как я ее понимаю — простой наглядный код + возможность надежно протестировать. Если обвешаться боксами, селлами, лайфтаймами, и при этом потерять тестируемость — такое ФП точно никому не нужно. Моя идея была как раз обратной — мы сознательно приносим в жертву производительность и расход памяти, понимаем что данные будут многократно копироваться, но мы берем такой ЯП, в котором это копирование делается дешево, а синтаксис более-ли-менее читабельный. Поскольку JVM безбожно сливает рекурсию (надо бы на котлине и чистой джаве проверить), остается C++ ну и Rust. Интересно было бы проверить на хаскеле рекурсивный вариант без стейта, потому что со стейтом даже JS научился работать быстро.PsyHaSTe
29.12.2019 20:39+1По поводу ФП с мутабельностью — я в курсе вашей позиции и статью читал :), этот подход точно не добавит популярности Rust, и вообще непонятно — а зачем нам такое ФП? Основная плюшка ФП как я ее понимаю — простой наглядный код + возможность надежно протестировать. Если обвешаться боксами, селлами, лайфтаймами, и при этом потерять тестируемость — такое ФП точно никому не нужно.
А где тут боксы, селлы и лайтаймы? В коде на хаскелле 8 строчек кода которые производят сортировку. Чуть-чуть сложнее варианта на С, но тем не менее довольно читаемо.
Написал я их как иллюстрацию того, что выжимать перфоманс можно — раз. Что мутабельный/иммутабельный — вопрос предпочтений, и ФП стиль не заставлят всё писать иммутабельно — два. Натягивать сову лишний раз смысла нет, лучше делать так, как делать лучше. "Такое ФП" нужно если вам нужно выжать производительность. По тем же причинам, почему люди выбирают С/Раст.
Но правда в том, что ФП языки дают перфоманс сравнимый с растом. Преимущество раста скорее в нестандартных таргетах, низкоуровневом доступе к железу и памяти. Если брать перфоманс, то хаскель не более чем в 2-3 раза проигрывает, причем это при идеоматичном иммутабельно-ленивом стиле, без особого упарывания инплейс мутабельностью. А вот по памяти проигрывает 1-2 порядка (хотя всё еще лучше на порядок чем жвм).
Отсюда вывод, что если вам не жалко докупить плашек памяти, то хаскель вам вполне подойдет даже под нагрузкой.
Моя идея была как раз обратной — мы сознательно приносим в жертву производительность и расход памяти, понимаем что данные будут многократно копироваться, но мы берем такой ЯП, в котором это копирование делается дешево, а синтаксис более-ли-менее читабельный.
Только вы не всегда приносите производительность в жертву. Как уже говорилось, абстракции часто дают производительность, а не забирают. Например, в расточате был пример где человек обмазался боксами и получил производительность в несколько раз ниже чем в наивном хаскелле. Хотя казалось бы взял раст. А хаскельский гц спокойно переварил сколько-то там гигабайт в мусора в секунду за 0 CPU.
Интересно было бы проверить на хаскеле рекурсивный вариант без стейта, потому что со стейтом даже JS научился работать быстро.
Не понял, что имеется ввиду. В наивной версии быстрой сортировки нет хвостовой рекурсии. А не-хвостовая рекурсия быстрой не бывает, и очень быстро передает привет стеку.
0xd34df00d
29.12.2019 23:49+2По поводу ФП с мутабельностью — я в курсе вашей позиции и статью читал :), этот подход точно не добавит популярности Rust, и вообще непонятно — а зачем нам такое ФП? Основная плюшка ФП как я ее понимаю — простой наглядный код + возможность надежно протестировать.
Вот пример кода, упоминаемого выше, с локальной мутабельностью и вот этим всем (правда, оказалось, что расстояние Левенштейна мне в итоге не нужно, поэтому допиливать это и реализовывать более умные алгоритмы мне теперь чо-т лень).
Это настолько же тестируемый код, насколько иммутабельная версия. Собственно, вот тесты, для иммутабельной версии они были бы точно такие же. Вся мутабельность скрыта и надёжно защищена монадой
ST.
При этом я могу использовать этот код в другом месте, написанном в иммутабельном стиле, который занимает 1-5% от времени выполнения, а не 95%, как этот. Компилятор при этом может рассуждать об этом коде, не нужно никакого FFI, всё равно есть куча проверок от компилятора, и так далее.
Siemargl
29.12.2019 22:34-1Но к сожалению он паникует в рантайме. У вас где-то отрицательный usize получается.
Очень слабенькое обоснование для адепта супернадежного Раста. Кстати, код даже без ансейфов.
Интересно будет услышать поиск ошибки и обоснование внезапного UB (ну или как оно тут).
Да, это trial!mayorovp
29.12.2019 22:41Ну так UB-то тут и нет, паника возникает гарантированная (в дебаге) и так же гарантированно не возникает (в релизе).
balajahe Автор
29.12.2019 22:50Оно не падает, а паникует на проверке границ массива. Панику можно перехватить, в отличие от NPE. Так что все надежно, контролируемо, и даже хорошо что паникует, сразу видны достоинства Rust, теперь вот специально не буду исправлять опечатку :)
PsyHaSTe
29.12.2019 23:01+2Очень слабенькое обоснование для адепта супернадежного Раста. Кстати, код даже без ансейфов.
Да, в этом плане раст очень плох. Например, вот этот код не ловится ни одним анализатором!
fn main() { panic!(); }Siemargl
29.12.2019 23:11-2Уже 3й раз от тебя съезд в демагогию. А ошибку найти слабо?
PsyHaSTe
29.12.2019 23:29А где предыдущие два? Я и так потратил полчаса чтобы на хаскелле версию забацать и забенчить (заодно разбирался как в стаке бенчмарк режим включается). Я считаю, что достаточно своего времени вложил.
Что касается кода выше, то он работает для ренжа
1..24574а для1..24575паникует. Проблема явно чуть сложнее тривиальной ошибки на единицу, дебажить её у меня никакого желания нет. Можешь, попробуешь сам?0xd34df00d
29.12.2019 23:52заодно разбирался как в стаке бенчмарк режим включается
stack bench+ нужная секция вpackage.yaml, чо там.
Вот критерион, конечно, чуть сложнее.
PsyHaSTe
29.12.2019 23:58ну сначала я не мог понять почему замер времени всегда дает 0. Потратил время чтобы понять, что это из-за ленивости и как бангом это починить. Потом разбирался с
myapp.cabalчтобы понять что там прописать чтобы оптимизации были (ghc-options), ну и прочие странные вещи вродеexitcode-stdio-1.0.
В общем, для начинающего хачкеллиста который код читает, но в разработку вне репла умеет не очень сильно, оказалось немного неочевидно и пришлось потратить немного времени чтобы разобраться.
Siemargl
30.12.2019 10:09-1Предыдущие — в предыдущих обсуждениях. Когда тебе нечего ответить, начинаешь съезжать на чушь.
Многовато ошибок нашлось в таком маленьком куске кода.
И кстати, ваша версия не собирается Rust 1.33 на ideone из-за заемщика. С — стабильность.
И это была не ошибка индексации, как balajahe нескромно предположил тут.
Результ исправленныйPsyHaSTe
30.12.2019 10:35+2Предыдущие — в предыдущих обсуждениях. Когда тебе нечего ответить, начинаешь съезжать на чушь.
Мне начинают надоедать голословные утверждения.
Многовато ошибок нашлось в таком маленьком куске кода.
Сколько конкретно?
И кстати, ваша версия не собирается Rust 1.33 на ideone из-за заемщика. С — стабильность.
Потому что код написан с использованием возможностей NLL. Пользоваться новыми языковыми возможностями — плохо?
Результ исправленный
А вот это хорошо, спасибо. Тогда вот такой замер:
fn main() { let mut input: Vec<_> = (1..1000000).rev().collect(); let now = Instant::now(); let result = { sort_imp(&mut input); input }; let time = now.elapsed(); println!("{:?}", result); println!("{}", time.as_secs_f64()); }
Выдает на моей машине 0.013585. Собирал с
[profile.release] lto = true codegen-units = 1
Кстати, в варианте на хаскелле я тупанул, он вычисление начального списка из миллиона элементов тоже считает. Вот в таком виде:
main :: IO () main = do let list = reverse [1..1000000] :: [Int] !input = V.fromList list :: U.Vector Int start <- getCPUTime let !result = qsort input end <- getCPUTime let !diff = (fromIntegral (end - start)) / (10^12) print result printf "Computation time: %0.9f sec\n" (diff :: Double) return ()
на моей машине выдает
0.015625000 secSiemargl
30.12.2019 11:25А у топика 10кк f64 + rand. Что сравниваем?
И вообще речь шла о том, что статья с бесполезным бенчмаркингом. И непонятными выводами из этого
Было 3 ошибкиPsyHaSTe
30.12.2019 11:52+2Ну я сравнивал миллион интов. Но 10кк флоатов тоже не проблема:
Haskell: Computation time: 0.281250000 sec
Rust: 0.1540258
technic93
30.12.2019 11:20+1Результ исправленный
Ваш код работает не правильно
Siemargl
30.12.2019 11:41Значит не все исправил =)
На каких данных не работает?technic93
30.12.2019 11:501) Если есть одинаковые елементы
2) [56., 15., 10., 77.1, 55., 21., 11., 52., 47., 5., 41., 92., 26., 83., 27., 43., 88., 45., 77.2, 36.] например такой рандомPsyHaSTe
30.12.2019 11:57+2А что во втором случае? у меня получилось:
[5.0, 10.0, 11.0, 15.0, 21.0, 26.0, 27.0, 36.0, 41.0, 43.0, 45.0, 47.0, 52.0, 55.0, 56.0, 77.01, 77.02, 83.0, 88.0, 92.0]
...
А да, действительно:
41.0, 45.0, 43.0
Я случайно инпут чуть-чуть поменял. Если ваш сделать то ошибка действительно есть.
potan
30.12.2019 08:33+2С синтаксисам в Rust, на мой взгляд, для ФП все хорошо. А вот HTK в системе типов очень не хватает.
vilinski
30.12.2019 10:02-3хачкель-мачкель. А вот окамл гораздо больше похож на rust и отродясь уже годен и к функциональному и императивному применению. Его беда лишь в том что он старше хачкеля и не хайпов как гошечка или скалка. Побечмаркайте! И кстати, если уж сравнивать самовары с помидорами, время компиляции тоже не сравнено! Тут окамл кмк в одном ряду с растом и го, если даже не рвет их обоих, как тузик тряпку. кгам короче
neplul
30.12.2019 11:37ну так первая версия Rust была написана на OCaml, и первоначальный Rust значительно отличался от текущей версии и был намного ближе к ML потомкам.
P.S И по-хорошему, в этом контексте надо вспоминать не про OCaml, Haskell и т.п, а Standard ML вот там было идеальное сочетание функционального и императивного программирования.
0xd34df00d
30.12.2019 20:00+1Окамл младше хаскеля, кстати.
А ещё очень прикольно смотреть, как окамлисты на модулях делают подобие тайпклассов. На прошлой работе на митапе хаскелистов окамлист читал доклад, как на модулях сделать иерархию Functor, Applicative и Monad. Когда я у него спросил, как сделать хотя бы аналог MonadReader какого-нибудь, он почему-то погрустнел.
orcy
30.12.2019 13:21+1Статья оставляет ощущение обескураженности. Так много логически нестыкуемых между собой утверждений.
Если писать императивно, с использованием общего изменяемого состояния — прикладному программисту нет смысла переходить с управляемых языков на компилируемые, так как выигрыш в производительности не компенсирует сложности программирования и многословности исходных текстов.
Вроде исходные тексты императивных исходников Scala и Rust выглядят одинаковыми, откуда возникает "сложность программирования" и "многословность исходных текстов"?
Как проверили что "выигрыш в производительности не компенсирует"? На основе реализации быстрой сортировки с ошибками?
На тему сортировки реализации быстрой сортировки имеет смысл глянуть доклад Александреску https://www.youtube.com/watch?v=FJJTYQYB1JQ, вот где хардкор.
balajahe Автор
30.12.2019 13:50Статья про неоптимальный функциональный код (без хвостовой рекурсии), который JVM слила, а Rust нет. Не всегда есть желание заморачиваться со стейт-монадами, иногда хочется просто вернуть копию данных, и чтоб работало. Понятно, что упремся в стек, но на Scala я уже не могу 100kk обработать, а на Rust еще могу. Вы правы, что в проде такой код будет выглядеть смешно, хотя всякое бывает.
orcy
30.12.2019 20:36Понятно. Я не силен в функциональном программировании, но моя бы мысль была в том что если хочется писать в функциональном стиле, то возможно есть что-то более удобнее чем Rust. С другой стороны и Rust или в C++ есть наработки по immutable data type которые предполагают что копирование будет относительно дешево.
balajahe Автор
30.12.2019 21:20В функциональщине интересна мемоизация, сейчас как раз пишу небольшой прототип на JS vs Rust, будет с чем сравнить. Собственно, в мемоизации все просто — взять хэш от параметров, и найти в мапе результат. И тут главное — производительность, потому что параметры могут быть объектами.
sshikov
Может мне кажется, но ваш второй алгоритм на скале просто не реализует быструю сортировку? Она ведь не предполагает создания новых массивов. Ну так и что в итоге сравнивали? Хоара с непонятно чем?
balajahe Автор
OK, я просто взял пример из учебника по Scala, можно взять любой другой с рекурсией, которая не раскладывается в цикл компилятором, а таких алгоритмов достаточно. Основная идея была — накладные расходы на сборщик мусора слишком велики, а Rust как раз очень подходит для функционального стиля, смотрите — в моем примере на Rust мы наблюдаем аж 2 дополнительных копирования данных — сначала клонируем каждый элемент итератора clone(), потом возвращаем вектор (не ссылку !) из функции — а это еще одно копирование, и все равно получается в разы быстрее, чем JVM, где, очевидно, массив аллоцируется в куче, и ничего лишний раз копировать не надо.
sshikov
Ну так я совершенно согласен с идеей в целом. Нужно по возможности избегать GC, если мы хотим высокую производительность. Но просто по этой реализации уж очень много вопросов. Начиная с того, что не стоило бы наверное называть это быстрой сортировкой.
>массив аллоцируется в куче, и ничего лишний раз копировать не надо.
А точно не надо? Array.concat разве не будет преаллоцировать новый массив, и копировать все три объединяемых?
balajahe Автор
Само собой, но в расте еще до этого две аллокации, возможно вторую (возврат из функции) они уже оптимизируют, но по документации, насколько я ее понимаю, это копирование. Я мог бы вернуть из функциии ссылку, но тогда нужно было бы определить время жизни самого вектора, и синтаксис получился бы жутковатый — с лайфтаймами, а зачем новичков распугивать :)
PS
Согласен, пример с числами не показателен, если б там лежали толстые объекты — бенчмаркинг мог быть совсем другим.