Как стать автором
Обновить
36
Карма
0
Рейтинг
Дмитрий @dmitryikh

Software Developer

  • Подписчики 6
  • Подписки

Rust vs. C++ на алгоритмических задачах

Наверное, вы не так поняли. Задача называется binary_search и состоит из ввода/вывода + сортировку массива A + поиск значений из массива B в массиве A. В таблице честно указана асимптотика задачи O(N logN).

Хотя нехорошо, что сортировка, занимающая O(N logN), может занимать больше времение, чем основная деятельность программы, описанная в ее названии (тут мы имеем O(M logN), где M — кол-во элементов в массиве B). Возможно, в следующей ревизии статьи и кода, я буду подавать на вход программы уже отсортированные данные.

Rust vs. C++ на алгоритмических задачах

Спасибо большое за замечания! Я исправлю код в репозитории и в статье.

Насчет возврата -1 из binary_search, как так получилось: изначально в задаче в онлайн курсе было такое требование (возвращать -1, индексация с 1), изначально я решал данную задачу на C++ и, недостаточно подумав, переписал так же на Rust. Действительно, лучше возвращать Option, а при записи результата делать unwrap_or(-1)

Rust vs. C++ на алгоритмических задачах

1. Согласен, как только доберусь до машинки, на которой проводил замеры, соберу данные по clang. Постараюсь взять clang такой версии, чтобы версия LLVM совпадала с Rust.
2. Я измеряю не время вызова функций — это действительно сложная история и есть много готовых решений. Я измеряю полное время выполнения программы. Я отказался от программы time, т.к. она под Mac os x не выдавала результат с нужной мне точностью. Программа measure, на которую вы указали, — это лишь попытка обойти это ограничение и иметь возможность проводить замеры на Linux & Mac os x.

Rust vs. C++ на алгоритмических задачах

Вы про UTF-8 строки? Если вы используете только ASCII символы, то вы не заметите разницы, и кол-во байт в строке будет равно кол-ву символов в строке.

Rust vs. C++ на алгоритмических задачах

Процитирую статью:
Делалось 10 прогонов каждой задачи на каждом наборе данных, далее результаты усреднялись


Можно было брать больше прогонов, но дисперсия времени выполнении была невелика.

Rust vs. C++ на алгоритмических задачах

Интуитивно — оптимизированные до упора программы должны дать примерно одинаковое быстродействие


Спасибо за эту мысль. Я ее не смог высказать в статье.

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

Мы ведь хотим писать быстро, и чтоб работало быстро, а не зависать над ассемблером и профилировщиком :)

Rust vs. C++ на алгоритмических задачах

Про -DNDEBUG спасибо! Я обязательно исправлю этот недочет. Возможно, цифры изменятся.

Код ужасно оптимизирован

Этот комментарий нам никак не поможет, напишите конкретное место и как его улучшить.

Rust vs. C++ на алгоритмических задачах

На всякий случай повторю, что цель статьи не в том, чтобы сказать, что Rust быстрее C++, а сказать, что Rust не медленней C++.

Код для C++ не представлен, чтобы не раздувать размер статьи. Код доступен на github, там же вы можете оценить корявость кода и флаги компиляции. Если у вас будут объективные замечания к коду — я обязательно их учту. Флаги:
g++ -std=c++11 -O2 -o main_cpp main.cpp
rustc -O --crate-name main_rust main.rs

Rust компилирует в LLVM код, как и clang, поэтому оптимизации, заложенные в LLVM, должны работать и там, и тут.

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

Информация

В рейтинге
Не участвует
Работает в
Зарегистрирован
Активность