Комментарии 415
Кроме того C# используют безопасное обращение к массиву.
У меня, к сожалению, .NET Core под линуксом не завелось — требовало чуть больше усилий на установку и настройку окружения, чем я был готов потратить.
Я C# не знаю, так что если вы дадите вариант с ансейф-доступом, то я с радостью его прогоню на той же машине под Mono. Ну и да, в Java-то обращения тоже безопасные, насколько я могу судить.
Убрал преобразование строки в массив байт.
using System;
using System.Diagnostics;
using System.Linq;
public class Program
{
public static Int32 LevDist(string s1, string s2)
{
var m = s1.Length;
var n = s2.Length;
// Edge cases.
if (m == 0)
{
return n;
}
if (n == 0)
{
return m;
}
var v0 = Enumerable.Range(0, n + 1).ToArray();
var v1 = new int[n + 1];
v0.CopyTo(v1, 0);
for (var i = 0; i < s1.Length; ++i)
{
v1[0] = i + 1;
for (var j = 0; j < s2.Length; ++j)
{
var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
var delCost = v0[j + 1] + 1;
var insCost = v1[j] + 1;
v1[j + 1] = Math.Min(substCost, delCost);
if (insCost < v1[j + 1])
{
v1[j + 1] = insCost;
}
}
var temp = v0;
v0 = v1;
v1 = temp;
}
return v0[n];
}
public static void Main()
{
var s1 = new String('a', 15000);
var s2 = new String('a', 15000);
var s3 = new String('b', 15000);
for (var i = 0; i < 5; i++)
{
Stopwatch execTimer = new Stopwatch();
execTimer.Start();
Console.WriteLine(LevDist(s1, s2));
Console.WriteLine(LevDist(s1, s3));
execTimer.Stop();
var execTime = execTimer.ElapsedMilliseconds / 1000.0;
Console.WriteLine($"Finished in {execTime:0.000}s");
}
}
}Unsafe версию не выкладываю — она работает примерно так же. Видимо из-за необходимости пинить указатель, или ещё какие-то накладные расходы вылазят.
пс. кстати у вас в описании теста указан размер строки 20000, а в бенчах везде 15000. Это так задумано?
что как бы намекает.
На то, что мне надо было сделать в тексте пожирнее соответствующее замечание:
Код для всех примеров сравнивает строки длиной 15 тысяч символов, а не 20, однако числа перенормированы для длины в 20 тысяч символов.
std::string s1(20000, 'a');
std::string s2(20000, 'a');
std::string s3(20000, 'b');
std::vector<int64_t> v0;
v0.resize(n + 1);
std::iota(v0.begin(), v0.end(), 0);
а в коде С ты выдялешь 15000
const int len = 15000;
int i;
char s1[15001], *s2 = s1, s3[15001];причем создаешь как ты говоришь на СТЕК, а не на динамической памяти как в С++.
Это вообще буквально до замера всё делается.
Не влияет ну совсем.
Да. У C голый результат с 15 тыщами символов получится в районе 0.5-0.6 секунд (на память). После нормировки на разные длины получится то, что приведено в таблице.
Собственно, сишная реализация была одной из тех, корректность переномировки которых я проверил отдельно.
А размеры…
Код для всех примеров сравнивает строки длиной 15 тысяч символов, а не 20, однако числа перенормированы для длины в 20 тысяч символов.
ну запусти сам и проверь разницу 15 и 20 тыс.
Если хочешь, вот что я сравнивал (15 000):
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
static long
lev_dist (const char *s1,
const char *s2)
{
unsigned long m, n;
unsigned long i, j;
long *v0, *v1;
long ret, *temp;
m = strlen (s1);
n = strlen (s2);
/* Edge cases. */
if (m == 0) {
return n;
} else if (n == 0) {
return m;
}
v0 = malloc (sizeof (long) * (n + 1));
v1 = malloc (sizeof (long) * (n + 1));
if (v0 == NULL || v1 == NULL) {
fprintf (stderr, "failed to allocate memory\n");
exit (-1);
}
for (i = 0; i <= n; ++i) {
v0[i] = i;
}
memcpy (v1, v0, n + 1);
for (i = 0; i < m; ++i) {
v1[0] = i + 1;
for (j = 0; j < n; ++j) {
const long subst_cost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
const long del_cost = v0[j + 1] + 1;
const long ins_cost = v1[j] + 1;
#if !defined(__GNUC__) || defined(__llvm__)
if (subst_cost < del_cost) {
v1[j + 1] = subst_cost;
} else {
v1[j + 1] = del_cost;
}
#else
v1[j + 1] = (subst_cost < del_cost) ? subst_cost : del_cost;
#endif
if (ins_cost < v1[j + 1]) {
v1[j + 1] = ins_cost;
}
}
temp = v0;
v0 = v1;
v1 = temp;
}
ret = v0[n];
free (v0);
free (v1);
return ret;
}
int
main ()
{
const int len = 15000;
int i;
char s1[15001], *s2 = s1, s3[15001];
clock_t start_time, exec_time;
for (i = 0; i < len; ++i) {
s1[i] = 'a';
s3[i] = 'b';
}
s1[len] = s3[len] = '\0';
start_time = clock ();
printf ("%ld\n", lev_dist (s1, s2));
printf ("%ld\n", lev_dist (s1, s3));
exec_time = clock () - start_time;
fprintf (stderr,
"Finished in %.3fs\n",
((double) exec_time) / CLOCKS_PER_SEC);
return 0;
}#include <chrono>
#include <cstdio>
#include <numeric>
#include <string>
#include <vector>
static long
lev_dist(const std::string &s1,
const std::string &s2) noexcept
{
const auto m = s1.size();
const auto n = s2.size();
// Edge cases.
if (m == 0) {
return n;
} else if (n == 0) {
return m;
}
const auto ca1 = s1.c_str();
const auto ca2 = s2.c_str();
std::vector<long> v0(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) {
const auto subst_cost = (ca1[i] == ca2[j]) ? v0[j] : (v0[j] + 1);
const auto del_cost = v0[j + 1] + 1;
const auto ins_cost = v1[j] + 1;
// std::min({ subst_cost, del_cost, ins_cost }) is slow.
v1[j + 1] = std::min(subst_cost, del_cost);
if (ins_cost < v1[j + 1]) {
v1[j + 1] = ins_cost;
}
}
std::swap(v0, v1);
}
return v0[n];
}
int
main()
{
const auto s1 = std::string(15000, 'a');
const auto &s2 = s1;
const auto s3 = std::string(15000, 'b');
const auto start_time = std::chrono::steady_clock::now();
printf("%ld\n", lev_dist(s1, s2));
printf("%ld\n", lev_dist(s1, s3));
const auto end_time = std::chrono::steady_clock::now();
fprintf(stderr,
"Finished in %.3lfs\n",
std::chrono::duration<double>(end_time - start_time).count());
return 0;
}Получив:
- gcc 9.2: ~0.727с
- clang 9: ~0.775с
- g++ 9.2: ~0.869с
- clang++ 9: ~0.791с
Не влияет ну совсем.
Так-то стек лежит надёжно в L1-кэше процессора, а динамическая память — далеко-далеко и её кучу раз придётся доставать.
20000 символов
Про это я уже написал. Это написано в тексте поста, это написано в комментариях теперь уже раза три, так что я не понимаю, что вам тут не нравится.
4 раза
Технически — пять раз, там ещё копия этого v0 есть.
причем создаешь как ты говоришь на СТЕК, а не на динамической памяти как в С++.
Это происходит один раз за время жизни программы, которая работает порядка одной секунды. Вы действительно думаете, что выделение пары сотен килобайт пятью кусками займёт какое-то время, хотя бы даже сравнимое с погрешностью измерений, на этом фоне?
Уж лучше бы вы поинтересовались, был ли у меня отключен турбобуст и использовал ли я привязку к одному ядру CPU, ей-богу.
2. Количество памяти влияет на кеш, а он как известно очень мал
3 ????
4 выдляем 100500 нормируем и говорим что С++ медленный.
В обоих случаях данные не помещаются в L1. В обоих случаях данные целиком помещаются в L2.
Раз вы не верите, что нормировку я проверил, давайте я сделаю это при вас. Правда, на другой машине с другим процессором, к той у меня сейчас доступа нет.
Код прямо из поста, 15 тыщ символов, минимальное время из пяти запусков — 0.578 секунд, стандартное отклонение — 0.0026 секунды.
Поменял везде 15 тыщ на 20 тыщ, минимальное время — 1.031 секунд, стандартное отклонение — 0.0021 секунды.
Нормировка: 0.578 * (4 / 3) ** 2 даёт 1.028 секунд.
1.028 достаточно близко к 1.031? Особенно учитывая, что разница между ними примерно равна стандартному отклонению каждого из них?
Не могу воспроизвести, скорость ровно такой же получается.
Что, в принципе, ожидаемо, так как на цикл приходится, считайте, всё время работы программы, а strlen дёргается вне цикла.
В любом случае, strlen привносит излишнюю непредусмотренную тестом логику и работу в алгоритм. Ни один из других языков не выполняет подобного поиска среди элементов массива, поэтому правильнее было бы добавить параметры в вызов lev_dist
Разница перекрывается не "обычным разбросом значений", а двумя вложенными циклами.
Когда время выполнения имеет вид a N2 + b N + c, то для достаточно большого N на коэффициенты b и c просто пофигу.
Да, при особо неудачном раскладе вы можете из-за strlen получить время 101%. Но если там вышло 190% — дело точно не в strlen.
Должно быть
memcpy(v1, v0, sizeof (long) * (n + 1));но его же тоже можно прооптимайзить?
Да, и я на это потратил ровно столько же времени, сколько на оптимизацию кода на хаскеле. Другое дело, что потенциал для оптимизации кончился чуть раньше.
Массивы
Так там и так массив.
быстрый вывод
Он делается один раз за время жизни программы, в самом конце.
логика вычисления минимума сильно избыточная и лишние +1-ы, которые можно не делать 2 раза, а просто выбрать минимум и бахнуть ++
Про +1 хорошее замечание. Я переместил его внутрь, как в хаскеле — ничего не изменилось. Кроме того, я даже сделал GVN руками, сохраняя предыдущее значение на стеке для следующей переменной (как последняя оптимизация в хаскеле) — плюсам от нее ни холодно, ни жарко, видать, gcc 9.2 и clang 9 оба умеют ее делать (что не расходится с моими ожиданиями, я не так давно про нее где-то читал, в частности, что в них она реализована).
А дальше можно было бы выжать ещё производительности из обоих вариантов, в правильном порядке сравнивая значения… Но это как-то уже немножко другой сорт оптимизаций.
Строки — это не массивы. Это странная штука, которая заточена под быстрое-быстрое копирование всякого-разного из одного места в другое и редкие операции, собственно, с их элементами.МассивыТак там и так массив.
Ассимтотика там такая же как в массивах, но константа — заметно выше по скорости и заметно ниже по памяти.
Строки — это не массивы. Это странная штука, которая заточена под быстрое-быстрое копирование всякого-разного из одного места в другое и редкие операции, собственно, с их элементами.
Это в плюсах? На длинах порядка тысяч, когда SSO не играет?
Да, теоретически компилятор может эту проверку вытащить наружу и сделать 4 версии — но не факт, что он это делает. Проверять нужно.
А процессор, конечно, справится без вопросов — но всё давно ему эти инструкции нужно декодировать, как минимум…
Ну что ж, std::string не подходит для строк. Неприятное открытие для меня.
Надо мне уже завязывать с плюсами, что-то это все как-то...
Ну что ж, std::string не подходит для строк. Неприятное открытие для меня.Просто строки, в большинстве программ, это не то, что вы думаете. В Java отличие вообще явное: есть java.lang.String (где строка обычно воспринимается «как единое целое»), есть java.lang.StringBuilder.А в C++ всё можно сделать и прямо в
std::string, а можно — перебросив их в std::vector… но это имеет смысл делать только если строки большие.Если маленькие, в среднем меньше 20-30 символов — то затраты на переброску не окупят ускорение. А они, в реальных программах, как правило такие и есть.
Надо мне уже завязывать с плюсами, что-то это все как-то...Ну дык. Где вы ещё столько ногострелов найдёте в одном месте? Разве что в PHP и то не факт…
Просто строки, в большинстве программ, это не то, что вы думаете.
Ну так там уникод какой или ещё какая ерунда, что не даёт относиться к ним как к массиву байт. А тут, казалось бы...
Где вы ещё столько ногострелов найдёте в одном месте?
В моем личном зачёте после плюсов пока лидирует Coq. Но оно там несколько другого рода.
Ну так там уникод какой или ещё какая ерунда, что не даёт относиться к ним как к массиву байт.Именно.
А тут, казалось бы...Структура, разработанная для работы с объектами, которые почти никогда не обрабатываются как массив байт плохо справляется с этим?
Чего вас удивляет?
Ну это всё равно как если бы вы использовали для замера скорости движения автомобиля автокран, экскаватор или вообще шасси для запуска ракет С-400 и удивлялись — а чё они так медленно ездят-то?
А потому что они не для этого. Да, они, конечно, и автомобили тоже… но это — не их основное предназначение!
В моем личном зачёте после плюсов пока лидирует Coq.Ну вот… и тут C++ не лидер.
Структура, разработанная для работы с объектами, которые почти никогда не обрабатываются как массив байт плохо справляется с этим?
Ну, может, это я такой, но строки как массивы байт нужно довольно часто обрабатывать.
Другое дело, что нечасто это строки хотя бы в несколько килобайт.
Ну вот… и тут C++ не лидер.
Лидер-лидер, все остальное как раз следует за ним.
Другое дело, что нечасто это строки хотя бы в несколько килобайт.Ну вот тут и порылась собака: строки, в современном C++, заточены под выигрыш за счёт отказа (довольно частого) от
new/delete. Когда строк много, они, в среднем, короткие, копируют их часто (а внутрь смотрят мало) — получается очень хороший результат.А вот когда все строки длинные, копируют их мало, внутрь смотрят часто… тогда выигрыша от отказа от
new/delete — нет… а плата за него (хоть и небольшая) — есть…Так-то tradeoff неплохой: проигрыш — всегда не слишком большой (почти никогда не больше чем вдвое, обычно процентов 20-30, даже если специально делать плохие условия для них), а вот выигрыш — может быть очень и очень приличным… но вот как раз конкретно в вашем тесте проигрыш есть, выигрыша — нету.
Ну, может, это я такой, но строки как массивы байт нужно довольно часто обрабатывать.
Это вы такой. Прикладному программисту строки надо считывать, выводить, парсить, формировать через форматирование-интерполяцию или конкатенацию, в крайних случаях менять в них регистр или искать подстроки.
Для всего этого придумываются свои структуры данных, не являющиеся просто массивами байт (и std::string в текущих реализациях — далеко не самая сложная из них).
А в C++ всё можно сделать и прямо в std::string, а можно — перебросив их в std::vector… но это имеет смысл делать только если строки большие.
А в чём смысл перебрасывания, когда в std::string есть метод reserve(size_type)? Вполне аналог функций StringBuilder-а.
std::string дорогой operator[]. Примерно вдвое дороже, чем у std::vector.Да, это 3-4 операции вместо 1-2, но это всё равно разница вдвое.
Однако поскольку она мала в абсолютных величинах это не имеет смысла если вы применяете к строке «однопроходные» алгоритмы: времени на копирование туда и обратно будет потрачено столько, что операции сразу с
std::string будут быстрее.А вот если у вас алгоритм O(N²)… или даже если вы просто делаете 10 проходов при обработке вашей строки… это может иметь смысл.
Ну что ж, std::string не подходит для строк.
недавно ктото заявил что std::stream не подходит для юникода.
Вообще за 5 лет универа и 10 лет работы, всё еще понимаю что ничего не понимаю про строки (а ещё про даты и плавающую запятую, а ещё и про файловые системы) и чем дальше, тем больше накапливается разного непонимания.
Особенно те, где! американские_символы. Нам раньше каждую неделю присылали какой то иероглиф в тикет, который был должен отрисовываться как то не так. Например не справаналево, а снизувверх например.
Зато приятно общаться с учениками, горит огонь в глазах, и думают что уже всё знают :)
Особенно те, где! американские_символы. Нам раньше каждую неделю присылали какой то иероглиф в тикет, который был должен отрисовываться как то не так.
Не, ну я в своё время писал строки, которые адекватно поддерживают UTF-8 и умеют работать в терминах уникодовых символов (не глифов, нет, просто единичных символов, забыл, как они там на юникодовом называются) с O(1)-доступом к символу по индексу, и там как раз было предельно понятно, что std::string не подходит, но тут-то… массив байт...
кстати у вас в описании теста указан размер строки 20000, а в бенчах везде 15000. Это так задумано?
Да. C++-код и хаскель-код из первой «части» писался мной, и так как я работал над всего двумя языками, мне было не лень гонять их на чуть больших данных. Для остальных языков это куда больнее, особенно когда они работают в 100-300 раз дольше этих двух версий.
Так как сложность алгоритма — O(mn), т. е. квадратичная для строк одинаковой длины, можно просто умножить ваш результат на соотношение длин строк (т. е. на (4/3)²).
Проверка корректности этой нормировки для пары случайных реализаций показывает, что так можно делать.
Очень хорошо получилось и прекрасно показало что публика на Хабре вовсе не так продвинута, как она сама о себе думает…
Очень хорошо получилось и прекрасно показало что публика на Хабре вовсе не так продвинута, как она сама о себе думает…
Для меня куда более показательной является реакция на коммент о том, что список инициализации — это вектор, и что-то там в рантайме обязательно аллоцируется. Да, я согласен, можно обсуждать, что именно мы бенчмаркаем, когда сознательно выбираем оставить вариант со списком инициализации, но это вопрос немножко другого рода и ближе к философии, и до него как-то совсем не особо дошло.
Надо как-нибудь при случае проверить, что чем громче и с большим количеством обвинений вбрасывать какой-то тезис, при этом минимизируя конкретику и проверяемые цифры/эксперименты, тем лучше он будет воспринят.
Ну и для красоты, замените
var temp = v0;
v0 = v1;
v1 = temp;на
(v0, v1) = (v1, v0);Чем мы хуже гошников, в конце-то концов? :)
using System;
using System.Diagnostics;
using System.Linq;
using System.Text;
public class Program
{
public static Int32 LevDist(string s1, string s2)
{
if (s1.Length == 0)
{
return s2.Length;
}
else if (s2.Length == 0)
{
return s1.Length;
}
var v0 = new int[s2.Length + 1];
var v1 = new int[s2.Length + 1];
for (int i = 0; i < v0.Length; i++)
{
v0[i] = v1[0] = i;
}
for (var i = 0; i < s1.Length; i++)
{
v1[0] = i + 1;
for (var j = 0; j < s2.Length; j++)
{
var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
var delCost = v0[j + 1] + 1;
var insCost = v1[j] + 1;
v1[j + 1] = Math.Min(substCost, delCost);
if (insCost < v1[j + 1])
{
v1[j + 1] = insCost;
}
}
(v0, v1) = (v1, v0);
}
return v0[s2.Length];
}
public static void Main()
{
string s1 = new String('a', 15000);
string s2 = s1;
string s3 = new String('b', 15000);
for (var i = 0; i < 5; i++)
{
Stopwatch execTimer = new Stopwatch();
execTimer.Start();
Console.WriteLine(LevDist(s1, s2));
Console.WriteLine(LevDist(s1, s3));
execTimer.Stop();
double execTime = execTimer.ElapsedMilliseconds / 1000.0;
Console.WriteLine($"Finished in {execTime.ToString():0.000}s");
}
}
}
Тут Enumerable.Range(...) заменен на обычный масив и для красоты сделал (v0, v1) = (v1, v0). Выполняться стало за 0.55 вместо 0.65. Запускал на .NET Core SDK (3.1.100), следующим образом
dotnet run -c releaseНа той же машине раст отрабатывает за 0.490. Запускался через
cargo run --releaseЧто-то все эти изменения к mono (на которой я могу проверить) не очень дружественны. Эта версия выполняется ещё медленнее — 3.189 с минимальное время.
Пока там Mono — сказать, что Mono никому не нужен таки нельзя…
И есть даже возможность компиляции нативных бинарников (например CoreRT).
Mono разве что в Unitiy, и то со временем думаю перейдут на Core.
Просто, имхо, количестов C# кода в играх на unity(там логику можно писать не только на C#) мне кажется меньшим чем той же охапки бизнесс-логики написанных для ASP
Как минимум я считаю что он скорее приближаетсяпо сложности ASP.NET сейчас.
Да, возможно это просто моё субъективное восприятие, а реальное положение дел иное.
using System;
using System.Diagnostics;
using System.Linq;
using System.Text;
public class Program
{
public static Int32 LevDist(string s1, string s2)
{
if (s1.Length == 0)
{
return s2.Length;
}
else if (s2.Length == 0)
{
return s1.Length;
}
var v0 = new int[s2.Length + 1];
var v1 = new int[s2.Length + 1];
for (int i = 0; i < v0.Length; i++)
{
v0[i] = v1[0] = i;
}
for (var i = 0; i < s1.Length; i++)
{
v1[0] = i + 1;
for (var j = 0; j < s2.Length; j++)
{
var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
var delCost = v0[j + 1] + 1;
var insCost = v1[j] + 1;
v1[j + 1] = Math.Min(Math.Min(substCost, delCost), insCost);
}
(v0, v1) = (v1, v0);
}
return v0[s2.Length];
}
public static void Main()
{
string s1 = new String('a', 15000);
string s2 = s1;
string s3 = new String('b', 15000);
for (var i = 0; i < 5; i++)
{
Stopwatch execTimer = new Stopwatch();
execTimer.Start();
var levDist1 = LevDist(s1, s2);
var levDist2 = LevDist(s1, s3);
execTimer.Stop();
Console.WriteLine(levDist1);
Console.WriteLine(levDist2);
double execTime = execTimer.ElapsedMilliseconds / 1000.0;
Console.WriteLine($"Finished in {execTime.ToString():0.000}s");
}
}
}
У меня на mono 6.6.0 стало чуть медленнее: 3.052 с против предыдущих 2.967 с.
С небольшими оптимизациями — 560 ms:
public class LevensteinDistance
{
[Params(15_000, 20_000)]
public int Size;
private string _s1;
private string _s2;
private string _s3;
[GlobalSetup]
public void Setup()
{
_s1 = new string('a', Size);
_s2 = new string('a', Size);
_s3 = new string('b', Size);
}
[Benchmark(Baseline = true)]
public int Levenstein_Orig()
{
return LevDist_Orig(_s1, _s2) + LevDist_Orig(_s1, _s3);
}
public int LevDist_Orig(string s1, string s2)
{
var ca1 = Encoding.UTF8.GetBytes(s1);
var ca2 = Encoding.UTF8.GetBytes(s2);
return LevDist_Orig(ca1, ca2);
}
public int LevDist_Orig(byte[] s1, byte[] s2)
{
var m = s1.Length;
var n = s2.Length;
// Edge cases.
if (m == 0)
{
return n;
}
else if (n == 0)
{
return m;
}
Int32[] v0 = Enumerable.Range(0, n + 1).ToArray();
var v1 = new Int32[n + 1];
v0.CopyTo(v1, 0);
for (var i = 0; i < m; ++i)
{
v1[0] = i + 1;
for (var j = 0; j < n; ++j)
{
var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
var delCost = v0[j + 1] + 1;
var insCost = v1[j] + 1;
v1[j + 1] = Math.Min(substCost, delCost);
if (insCost < v1[j + 1])
{
v1[j + 1] = insCost;
}
}
var temp = v0;
v0 = v1;
v1 = temp;
}
return v0[n];
}
[Benchmark]
public int Levenstein_Opt()
{
return LevDist_Opt(_s1, _s2) + LevDist_Opt(_s1, _s3);
}
public int LevDist_Opt(string s1, string s2)
{
if (s1.Length == 0)
{
return s2.Length;
}
else if (s2.Length == 0)
{
return s1.Length;
}
var v0 = Enumerable.Range(0, Size + 1).ToArray();
var v1 = new int[Size + 1];
v0.CopyTo(v1, 0);
for (var i = 0; i < s1.Length; i++)
{
v1[0] = i + 1;
for (var j = 0; j < s2.Length; j++)
{
var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
var delCost = v0[j + 1] + 1;
var insCost = v1[j] + 1;
v1[j + 1] = Math.Min(Math.Min(substCost, delCost), insCost);
}
(v0, v1) = (v1, v0);
}
return v0[s2.Length];
}
}
Убрал вывод через консоль, преобразование строк в массив байтов, в условиях циклов заменил переменные на s.Length, вычисление минимального из трех через два метода Math.Min.
Только не используйте Range в высокопроизводительном коде:
var v0 = Enumerable.Range(0, Size + 1).ToArray();Попробуем сравнить версию с Range и обычным циклом с спомощью SharpLab. Вызов Range никак не инлайнится в релизе, поэтому лезем за ним в документацию на referencesource, копируем код, избавляемся от мусора и получаем такое. Как видим, метод крайне не оптимален: используется yield внутри, который генерирует кучу лишнего кода для такой простой операции, как инициализация массива последовательными значениями.
Дело в том, что метод в Enumerable.Range в Core оптимизирован так, что работает в ~10 раз быстрее, чем в Framework и по времени выполнения почти не отличается от ручного заполнения массива через цикл.
Мои тесты:
[Params(15_000)]
public int Size;
[Benchmark]
public int Range()
{
int[] arr = Enumerable.Range(0, Size + 1).ToArray();
return arr[0];
}
[Benchmark]
public int Loop()
{
var arr = new int[Size + 1];
for (var i = 0; i < Size; i++)
arr[i] = i;
return arr[0];
}Плюс Enumerable.Range выполняется всего один раз в коде автора, так что его влияние на общий результат минимально.
Но в целом вы правы: если бы, скажем, этот метод выполнялся в цикле или размер массива был побольше (500к+) или мы бы взяли Framework вместо Core, тогда да — лучше было бы использовать ручное заполнение.
using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
public class Program
{
[MethodImpl(MethodImplOptions.AggressiveOptimization)]
public static unsafe Int32 LevDist(char[] s1, char[] s2)
{
var m = s1.Length;
var n = s2.Length;
// Edge cases.
if (m == 0)
return n;
if (n == 0)
return m;
var n1 = n + 1;
var v0Ptr = Marshal.AllocHGlobal(n1 * sizeof(int));
var v1Ptr = Marshal.AllocHGlobal(n1 * sizeof(int));
var v0 = (int*) v0Ptr;
var v1 = (int*) v1Ptr;
for (var i = 0; i < n1; i++)
{
v0[i] = i;
v1[i] = i;
}
for (var i = 0; i < m; ++i)
{
v1[0] = i + 1;
for (var j = 0; j < n; ++j)
{
var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
var delCost = v0[j + 1] + 1;
var insCost = v1[j] + 1;
v1[j + 1] = Math.Min(Math.Min(substCost, delCost), insCost);
}
var temp = v0;
v0 = v1;
v1 = temp;
}
var result = v0[n];
Marshal.FreeHGlobal(v0Ptr);
Marshal.FreeHGlobal(v1Ptr);
return result;
}
public static void Main()
{
var s1 = new char[15000];
for (var i = 0; i < s1.Length; i++)
s1[i] = 'a';
var s2 = s1;
var s3 = new char[15000];
for (var i = 0; i < s3.Length; i++)
s3[i] = 'b';
for (var i = 0; i < 5; ++i)
{
var execTimer = new Stopwatch();
execTimer.Start();
Console.WriteLine(LevDist(s1, s2));
Console.WriteLine(LevDist(s1, s3));
execTimer.Stop();
Console.WriteLine($"Finished 2 in {(execTimer.ElapsedMilliseconds / 1000.0):0.000}s");
}
}
}go: 0.491s
.net: 0.699s
C# .NET Core 3.1
Это unsafe реализация, у меня она медленее на 0.11 с обычной реализации на строках на R7 2700X.
using System;
using System.Diagnostics;
public class Program
{
public static unsafe int LevDist(char* s1, int m, char* s2, int n)
{
// Edge cases.
if (m == 0)
{
return n;
}
else if (n == 0)
{
return m;
}
var v0 = new int[n + 1];
var v1 = new int[n + 1];
for (var i = 0; i < m; ++i)
{
v1[0] = i + 1;
for (var j = 0; j < n; ++j)
{
var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
var delCost = v0[j + 1] + 1;
var insCost = v1[j] + 1;
v1[j + 1] = Math.Min(substCost, delCost);
if (insCost < v1[j + 1])
{
v1[j + 1] = insCost;
}
}
var temp = v0;
v0 = v1;
v1 = temp;
}
return v0[n];
}
public static int Main()
{
var s1 = new string('a', 15000);
var s2 = s1;
var s3 = new string('b', 15000);
var execTimer = new Stopwatch();
execTimer.Start();
int res1, res2;
unsafe
{
fixed (char* c1 = s1)
fixed (char* c2 = s2)
fixed (char* c3 = s3)
{
res1 = LevDist(c1, s1.Length, c2, s2.Length);
res2 = LevDist(c1, s1.Length, c3, s3.Length);
}
}
execTimer.Stop();
Console.WriteLine(res1);
Console.WriteLine(res2);
var execTime = execTimer.ElapsedMilliseconds / 1000.0;
Console.WriteLine($"Finished in {execTime:0.000}s");
return 0;
}
}Однако, если в данной реализации вывод положить внутрь unsafe блока и убрать переменные, то результаты уравниваются с результатом стандартной реализации, но с отдельными переменными и отдельным выводом (с unsafe всё наоборот).
using System;
using System.Diagnostics;
public class Program
{
public static unsafe int LevDist(char* s1, int m, char* s2, int n)
{
// Edge cases.
if (m == 0)
{
return n;
}
else if (n == 0)
{
return m;
}
var v0 = new int[n + 1];
var v1 = new int[n + 1];
for (var i = 0; i < m; ++i)
{
v1[0] = i + 1;
for (var j = 0; j < n; ++j)
{
var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
var delCost = v0[j + 1] + 1;
var insCost = v1[j] + 1;
v1[j + 1] = Math.Min(substCost, delCost);
if (insCost < v1[j + 1])
{
v1[j + 1] = insCost;
}
}
var temp = v0;
v0 = v1;
v1 = temp;
}
return v0[n];
}
public static int Main()
{
var s1 = new string('a', 15000);
var s2 = s1;
var s3 = new string('b', 15000);
var execTimer = new Stopwatch();
execTimer.Start();
unsafe
{
fixed (char* c1 = s1)
fixed (char* c2 = s2)
fixed (char* c3 = s3)
{
Console.WriteLine(LevDist(c1, s1.Length, c2, s2.Length));
Console.WriteLine(LevDist(c1, s1.Length, c3, s3.Length));
}
}
execTimer.Stop();
var execTime = execTimer.ElapsedMilliseconds / 1000.0;
Console.WriteLine($"Finished in {execTime:0.000}s");
return 0;
}
}Стандартная safe реализация.
using System;
using System.Diagnostics;
public class Program
{
public static int LevDist(string s1, string s2)
{
var m = s1.Length;
var n = s2.Length;
// Edge cases.
if (m == 0)
{
return n;
}
else if (n == 0)
{
return m;
}
var v0 = new int[n + 1];
var v1 = new int[n + 1];
for (var i = 0; i < m; ++i)
{
v1[0] = i + 1;
for (var j = 0; j < n; ++j)
{
var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
var delCost = v0[j + 1] + 1;
var insCost = v1[j] + 1;
v1[j + 1] = Math.Min(substCost, delCost);
if (insCost < v1[j + 1])
{
v1[j + 1] = insCost;
}
}
var temp = v0;
v0 = v1;
v1 = temp;
}
return v0[n];
}
public static int Main()
{
var s1 = new string('a', 15000);
var s2 = s1;
var s3 = new string('b', 15000);
var execTimer = new Stopwatch();
execTimer.Start();
var res1 = LevDist(s1, s2);
var res2 = LevDist(s1, s3);
execTimer.Stop();
Console.WriteLine(res1);
Console.WriteLine(res2);
var execTime = execTimer.ElapsedMilliseconds / 1000.0;
Console.WriteLine($"Finished in {execTime:0.000}s");
return 0;
}
}Если вывод в последнем примере положить внутрь блока замера времени и избавиться от переменных, то получаем замедление, в принципе логично. Но Unsafe реализация работает зеркально наоборот, думаю там можно ещё что-то улучшить, но надо копать глубже.
using System;
using System.Diagnostics;
public class Program
{
public static int LevDist(string s1, string s2)
{
var m = s1.Length;
var n = s2.Length;
// Edge cases.
if (m == 0)
{
return n;
}
else if (n == 0)
{
return m;
}
var v0 = new int[n + 1];
var v1 = new int[n + 1];
for (var i = 0; i < m; ++i)
{
v1[0] = i + 1;
for (var j = 0; j < n; ++j)
{
var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
var delCost = v0[j + 1] + 1;
var insCost = v1[j] + 1;
v1[j + 1] = Math.Min(substCost, delCost);
if (insCost < v1[j + 1])
{
v1[j + 1] = insCost;
}
}
var temp = v0;
v0 = v1;
v1 = temp;
}
return v0[n];
}
public static int Main()
{
var s1 = new string('a', 15000);
var s2 = s1;
var s3 = new string('b', 15000);
var execTimer = new Stopwatch();
execTimer.Start();
Console.WriteLine(LevDist(s1, s2));
Console.WriteLine(LevDist(s1, s3));
execTimer.Stop();
var execTime = execTimer.ElapsedMilliseconds / 1000.0;
Console.WriteLine($"Finished in {execTime:0.000}s");
return 0;
}
}Кроме того C# используют безопасное обращение к массиву.
Его можно обойти, если использовать контрукцию вида:
for (var i = 0; i < array.Length; i++)
{
var item = array[i];
}
Копиляров в состоянии понять что i ограничено по array.Length и переполнения быть не может.
В моём случае оригинальная версия работает 0,84с, версия с a.Length работает 0,68с, а unsafe версия работает 0.63с.
Я и не думал об этом, хотя всегда использую именно a.Length, но не для скорости, а чтоб не накосячить.
Самое удивительное, что раньше, когда компьютеры были большими, наоборот, учили сохранять длину во временную переменную перед циклом.
Или если использовать foreach.
public static Int32 LevDist(string s1, string s2)
{
return LevDist(s1.ToCharArray(), s2.ToCharArray());
}
public static Int32 LevDist(char[] s1, char[] s2)
{
var m = s1.Length;
var n = s2.Length;
// Edge cases.
if (m == 0)
{
return n;
}
else if (n == 0)
{
return m;
}
var v0 = new int[n+1];
var v1 = new int[n+1];
for(var i = 0; i < n; i++)
v0[i] = v1[i] = i;
for (var i = 0; i < m; i++)
{
v1[0] = i + 1;
for (var j = 0; j < n; j++)
{
var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
var delCost = v0[j + 1] + 1;
var insCost = v1[j] + 1;
v1[j + 1] = Math.Min(Math.Min(substCost, delCost), insCost);
}
var temp = v0;
v0 = v1;
v1 = temp;
}
return v0[n];
}
public static void Main()
{
string s1 = new String('a', 15000);
string s2 = s1;
string s3 = new String('b', 15000);
Stopwatch execTimer = new Stopwatch();
execTimer.Start();
Console.WriteLine(LevDist(s1, s2));
Console.WriteLine(LevDist(s1, s3));
execTimer.Stop();
double execTime = execTimer.ElapsedMilliseconds / 1000.0;
Console.WriteLine($"Finished in {execTime:0.000}s");
}
Со включенной оптимизацией на моей машине дает 0.77с против 5.6c в оригинальной версии.
На удивление, использование
ReadOnlySpan дает худшие результаты по сравнению с копированием массива в char[].На удивление, использование ReadOnlySpan дает худшие результаты по сравнению с копированием массива в char[].
Не могли бы показать вариант с ReadOnlySpan? Интересно посмотреть почему так происходит, какая версия .Net Core?
Просто засунуть тело функции LevDist(char[] s1, char[] s2) в LevDist(string s1, string s2) и все будет работать еще быстрее.
Относительное влияние останется тем же самым, так как тело-то тоже будет выполняться тысячи раз.
Нет, чаще — в десятки тысяч символов. Я эту ерунду на исходный код натравливаю.
Знаю про древний стандарт в 80 символов, у редакторов даже подсветка раньше была, когда выходишь дальше.
Интересно было-бы найти статистику гитхаба, сколько там средняя длинна строки в исходниках.
Впрочем, не особо важно. Если подумать, копирование в массивы в данном случае будет не дольше чем заполнение двух массивов int дальше по коду и уж явно сильно быстрее, чем вложенный цикл m*n. Так что на производительность слабо влияет. Просто в нем нет никакого смысла, почему-бы и не убрать.
Там строка — это весь файл целиком, без разбития по привычным человеку строкам по \n.
Ну не знаю, лично у меня замена в сишарпе Enumerable.Range на ручной цикл дала порядка 10% прироста производительности.
adamsitnik.com/Span/#span-vs-array
А когда взял кто-то, кто видит C# не в первый раз, то и вуаля — Java уже медленее.
А что в том коде на сишарпе не так? Ну да, пара моментов неоптимально написана (типа кэширования m и n), но в остльном нормальный такой код.
Как челоек получил 5.6с для меня — загадка. У меня код выше отрабатывает примерно за 0.63 секунды, чуть-чуть быстрее чем оригинальный.
Запустите код со строками в 20 тыщ символов.
Ну и, может, там прогревать надо или ещё что как-то особо. numba питоновая вон в первый запуск тоже раза в полтора-два медленнее у меня.
Сори, тупанул.
С 20к символов у меня сишарп выдает 1.18с. Раст — 0.8с.
На .net 472 — 0.935c. Это объясняется тем, что в неткоре джит делает ставку на быстрый запуск и хуже оптимизирует. Недавно ввели tieredJIT которы до старого уровня иногда догоняет во время работы, когда какой-то код горячим получается, но очевидно на задачке выполняемой секунду он не успевает ничего сделать.
У меня получилось так:
NET Core 3.1 — 0.9 s
NET Framework 4.7.2 — 1.2 s
Mono 6.6.0 — 1.8 s
v1[j + 1] = std::min({delCost, insCost, substCost});на
v1[j + 1] = std::min(std::min(delCost, insCost), substCost);и о чудо, не нужно список(вектор) из трех переменных инициализировать (выделять память) и удалять ее. На моей машине ускорение в 3 раза.
P. S. Ох уж эти истории про медленный C и C++
А там и не выделяется ничего — initializer_list должен разворачиваться в компилтайме, это таки не лист и не вектор. И да, в одном из заключений про это написано.
А ещё производительность зависит от того, в каком порядке вы выполняете сравнения.
И про это в заключении тоже написано. Вот, процитирую себя же на всякий:
При некоторых из этих порядков мне таки удалось воспроизвести ускорение в случае C++. Так, если вместо std::min({ delCost, insCost, substCost }) написать std::min(substCost, std::min(delCost, insCost)), то время работы под gcc увеличивается до 1.440 секунд, а под clang — уменьшается до 0.840 секунд (ура, быстрее всех остальных вариантов и почти хаскель). Похоже, clang не любит initializer lists и не может их заинлайнить, а gcc шедулит операции и регистры так, что, по крайней мере, на этих конкретных данных результат проигрывает.
Но ещё раз отмечу, что оптимизацией порядка в случае хаскеля я не занимался, и заниматься этим в рамках этого бенчмарка не рекомендую в любом языке.
Кроме того, это значит, что нельзя рассчитывать на компилятор даже в таком языке, как C++, где в компиляторы влиты десятки тысяч человеколет.
initializer_list и, соотвественно, «недооптимизированных» обращениях в память.Это проблема QoI.
И gcc тому же с ручной развёрткой становится хуже, а не лучше.
И gcc тому же с ручной развёрткой становится хуже, а не лучше.Пожимает плечами. Это уже совсем другая история.
GCC, в последнее время, очень сильно сдал. Google оттуда всех разработчиков снял и куча народу из «академиев» тоже на Clang переключились.
Кое-где, иногда, он ещё может «показть класс» (всё-таки в него много тысяч человеко-лет вбухано тоже), но объективно — он таки от Clang отстаёт.
Как несложно догадаться раньше Google содержал сколько-то контрибуторов в GCC, сейчас — часть переключилась на Clang, часть уволилась…
А там и не выделяется ничего — initializer_list должен разворачиваться в компилтайме, это таки не лист и не вектор.initializer_list — это, увы, именно-таки массив. И обрабатывается как массив и косяки у него, как при работе с массивом.И да — из-за проблем с алиасингом подобные вещи компилятору «тяжело» обрабатывать. Я внизу приводил вообще патологический пример.
Это одно из мест, где разработчики языка придумали очередную подлянку, которую должны уметь «изводить» разработчики компиляторов — а они, увы, не всегда справляются.
initializer_list — это, увы, именно-таки массив
Но не вектор. Динамических аллокаций там нет (то есть, компилятор, наверное, имеет право реализовывать их с аллокациями, но зачем ненавидеть своих пользователей?).
Кроме того, предельный случай без всех этих листов и шаблонных minов тоже приведен — это вариант на С. И он не оказывается существенно быстрее.
Динамических аллокаций там нет (то есть, компилятор, наверное, имеет право реализовывать их с аллокациями, но зачем ненавидеть своих пользователей?).Динамических аллокаций нет, а проблемы алиасинга — есть.
Для оптимизации C++ они — вообще больное место.
Кроме того, предельный случай без всех этих листов и шаблонных minов тоже приведен — это вариант на С. И он не оказывается существенно быстрее.А что-нибудь вообще — оказывается «существенно быстрее»? Не так, что вы, в версии на C (и исправленной версии на C++) уже добрались до пределов того, что можно сделать без векторизации?
Автовекторизация в C++ сейчас — это скорее игрушки (типа
inline в прошлом веке) — мы вообще пока не в курсе чего там можно автоматически сделать. Обрабатываются только кой-какие самые очевидные циклы.Динамических аллокаций нет, а проблемы алиасинга — есть.
Именно! Значит, по крайней мере, писать идиоматичный код надо с оглядкой на ассемблер. Ну, как вы и говорите.
И, значит, идиоматичный код почти наверное не будет в топе производительности, хотя казалось бы — zero-overhead abstractions и прочие красивые слова.
Впрочем, ваши ссылки ниже я ещё не смотрел внимательно — с мобильника по пути на работу это не очень, чуть позже гляну.
А что-нибудь вообще — оказывается «существенно быстрее»? Не так, что вы, в версии на C (и исправленной версии на C++) уже добрались до пределов того, что можно сделать без векторизации?
Есть асимптотически более эффективные алгоритмы для этой задачи, но они чуть менее тривиальны. Собственно, моя реализация с мутабельностью и этим всем подчистую сливает чистой реализации с теми, более эффективными алгоритмами. Но это именно алгоритмические улучшения.
И, значит, идиоматичный код почти наверное не будет в топе производительности, хотя казалось бы — zero-overhead abstractions и прочие красивые слова.Ну — слова-то красивые, а на практике — надо в ассемблер смотреть. Когда я в школе учился я вообще был большим скептиком по отношению к C++: что толку от абстракций, которые «могли бы быть zero-overhead», если на практике — там «overhead» нифига даже не «zero»?
Сейчас компиляторы умеют уже убирать 99% этих абстракций, но иногда… вот это вот что такое? Какая абстракция и куда протекла, что компилятор вдруг решил в оптимизированном «до упора» коде оставить
test cl, cl — притом, что в cl, в этот момент, будет нуль!Но это именно алгоритмические улучшения.На это вроде C++ компиляторы не пытаются замахиваться, всё-таки. Да и никакие другие промышленные (не зная что нам «на переднем крае науки, впрочем).
Я бы удивился, если бы они хотя бы заметили, что там можно обойтись одной строкой, а не двумя.
Собственно, если вдруг интересно, вот этот папир с более эффективной реализацией.
tl;dr там два улучшения — можно сравнивать не посимвольно, а сразу 8 (или сколько байт в вашем слове) символов через хитрые наблюдения и немного препроцессинга (что теоретически даёт улучшение константы в 8 раз), плюс не обязательно смотреть на всю матрицу, а можно идти вдоль диагонали, отступая не сильно далеко от неё, особенно если вы удовлетворитесь ответом вида «расстояние больше N» для некоторого наперёд заданного N.
Увы, я в своей задаче понял, что расстояние Левенштейна — не лучшая метрика, и мне резко стало лень реализовывать более эффективные варианты.
Я сравниваю расстояние между исходными кодами, отформатированными согласно разным стилям. Соответственно, лучше рассматривать пару из (d1, d2), где d1 — модуль разности гистограмм непробельных символов, d2 — сколько пробельных символов надо удалить или добавить, чтобы выровнять две строки. Соответственно, сравнение тогда лексикографическое.
Ну или в коде.
ты слово Array видишь, а метод size? и что это не вектор по твоему?
P. S. Ох уж эти истории про медленный C и C++А они всегда про это: компилятор, вроде бы, должен лишнее удалять… но не всегда ему это удаётся. И это — после тысяч человеко-лет, в это вбуханных.
std::initializer_list был разработан как раз для таких случаев. И его использование у 0xd34df00d — как раз вполне идеоматично.А что у компилятора при этом ролики за шарики заезжают — так это как раз вечная беда C++: теоретически на нём можно писать не глядя в ассемблерный выхлоп, практически — регулярно вот подобные косяки и вылезают.
Про ваши трюки компилятор в курсе и вполне способен их применять — тут не в них дело.
Сам пишу на Java и вижу, что неправильно написать гораздо сложнее, чем упомнить и внимательно прочитать все детали конструкторов, const* указателей, ссылок и shared_ptr, а разница между ними иногда кратная. Еще и новые стандарты добавляют и добавляют синтаксического мусора…
Разницы нету, смотри тут https://godbolt.org/z/E5WRNT
В более общем случае может быть разница из-за порядка сравнений когда переменные приходят из разных мест но к "выделять память" отношения не имеет.
Разработчики про это знают, так что, похоже, вы очень вовремя написали статью…
Clang++ даёт хорошие результаты, если использовать range-based for или если вместо std::string сравнивать прямо элементы C-массива (.c_str()).
Не знаю, насколько это близко к описанной проблеме, но что-то явно очень медленно при использовании оператора [] у std::string.
Не знаю, насколько это близко к описанной проблеме, но что-то явно очень медленно при использовании оператораУ[]уstd::string.
std::string очень сложный operator[]. Теоретически «общую» часть компилятор должен бы вынести… но, похоже, в данном случае — не выходит.Может быть тоже проблемы aliasing'а легко…
Про алиасинг таки интересно. Там же нигде нет записи по char* или unsigned char* — с чего бы компилятору его опасаться?
char* или unsigned char* может меняться (с точки зрения указателя) при записи в любую переменную адрес которой мог утечь куда-то.В результате некоторые алгоритмы могут резко усколяться если вместо
char использовать что-то типа: struct __attribute__((packed)) FastChar {
long long value:8;
};Об этом я не подумал, да. Вы правы. Правда, здесь-то я пишу в локальные для функции вектора, на которые даже адрес или ссылка ни разу не берётся (если не считать локальный же std::swap), и компилятору должно бы хватить мозгов это увидеть.
С другой стороны, LICM-вынос чтения символа из строки s1 на уровень внешнего цикла производительность (для gcc, по крайней мере) не меняет вообще никак.
Так что, как я уже сказал, это может влиять только на некоторые алгоритмы, далеко не на все.
У меня в соседнем коде был шанс алиасинга, и я уже подумывал заменить std::string на std::vector<CharWrapper>, где struct CharWrapper { char ch; }; — по идее этого достаточно, чтобы алиасинга не было, потому что больше нет указателей на char. У вас там, однако, обёртка выглядит по-другому. Что я теряю от такого, более простого варианта?
То есть мне было бы, в принципе, интересно увидеть пример кода, где ваш
CharWrapper может хоть на что нибудь повлиять…Доступ к элементу структуры может же алиаситься с доступом ко всем, с чем алиасится соответствующий тип поля структуры.
ЕМНИП, в случае с char там алиасинг может быть только однонаправленный — char* может указывать на кусок int, а вот int* на char указывать не может никогда. Ну, это если я правильно понял что означает термин glvalue (придумали, блин, терминологию, и всё лишь бы не рассуждать о языке в терминах самого языка!)
ЕМНИП, в случае с char там алиасинг может быть только однонаправленный —Да, но для создания проблем этого же достаточно. Если вы имеете строку — то вы работает с её содержимым через указатели, а раз так, что алиасинг, с точки зрения компилятора, возможен.char*может указывать на кусокint, а вотint*наcharуказывать не может никогда.
Тут фишка в том, что да, вы, формально, не имеете права взять указатель на
CharWrapper, прератить в указатель на int — и использовать. Всё так.Но если указатель на
CharWrapper приходит откуда-то снаружи, то у компилятора нет никой возможности узнать — это таки настоящий CharWrapper или кусок int (см. пример ниже)… и, соответственно, ему приходится «закладываться на подставу».
ЕМНИП, в случае с char там алиасинг может быть только однонаправленный — char* может указывать на кусок int, а вот int* на char указывать не может никогда.Либо диапазоны могут пересекаться, и тогда int* и char* потенциально указывают на одну память (алиасятся), либо не пересекаются (и мы, возможно, исходим из этого предположения). Никакой однонаправленности в алиасинге нет
Я получаю отсутствие объектов типа char*. Соответственно, я не пишу по таким указателям и не читаю, а это значит, что про алиасинг, по идее, можно не думать.
void foo(int);
int bar(CharWrapper* x, CharWrapper* y, int *z) {
foo(*z);
*x = {1};
*y = {32};
return *z;
}
Здесь ведь никаких UB нету с вашим подходом — и компилятору придётся это учитывать. А с моим — есть… и он может немного своевольничать.
Можете запустить и убедиться что ваша версия выдаёт 8234, а моя — 298…
Потому что в вашем случае всё равно доступ к данным идёт через glvalue типа
char, а моём случае — через long long. Да, это небольшой такой long long, размером в один байт… но это всё равно long long!А у вас там слева разве нет UB? Ну, где вы пишете в один член юниона, а потом читаете из другого?
Как иначе сделать так, чтобы ссылка на char внутри структуры указывала куда-то ещё, я не знаю.
Ну, где вы пишете в один член юниона, а потом читаете из другого?Нет. Ну во всяком случае так считают разработчики компиляторов. Тут всё упирается в то, что все эти автогенерённые
CharWrapper() и operator= автогенерируются компилятором — но остаются законными даже если указатель на CharWrapper() был порождён из указателя на другой тип…If a program attempts to access the stored value of an object through a glvalue of other than one of the following types the behavior is undefined:То есть в C++ вообще никого не волнует указатель какого типа вы используете… только к объекту какого типа вы пытаетесь «достучаться».
…
—(11.8) a char, unsigned char, or std::byte type
Как иначе сделать так, чтобы ссылка на char внутри структуры указывала куда-то ещё, я не знаю.Через
reinterpret_cast самое простое.Нет.
Почему? Всю жизнь же было (ну и всю жизнь компиляторы это разрешали, да, но это другой разговор).
Ну и тут явно 6.7.3.1/5.
То есть в C++ вообще никого не волнует указатель какого типа вы используете… только к объекту какого типа вы пытаетесь «достучаться».
Я бы ожидал, что компилятор увидит, что я пытаюсь обратиться к char.
Через reinterpret_cast самое простое.
Но кастить вы будете к типу структуры, а он ничего не алиасит.
Ну и тут явно 6.7.3.1/5.С какого перепугу? У нас по-прежнему всё время всё тот же
int, с которого мы начинали… только доступ к нему — через объект типа char… что явно разрешено…Я бы ожидал, что компилятор увидит, что я пытаюсь обратиться к char.Как он это увидит, извините? Если ему явно разрешено обращаться к объекту типа int через glvalue типа char?Но кастить вы будете к типу структуры, а он ничего не алиасит.Алиасит-алиасит! В том-то и дело, что алиасит. В этом-то и беда. C (а за ним и C++) так устроен.
То есть если вы имеете что-нибудь типа
struct Point {
int lattitude;
int longitude;
};
struct 3DPoint {
int x,y,z;
};
z у чего-то, что было рождено как Point, конечно, нельзя). Это очень активно применяется программистами на C, потому и появляются все эти чудесные pointer interconvertible типы.И, соотвественно, можно заворачивать
char в «обёртки» из struct, union или std::array сколько угодно — он всё равно останется charом и ему будет разрешего алиаситься с чем угодно.Это вам, извините, не
Rust и не Haskell. Ушки-то от C всё равно торчат…С какого перепугу?
Потому что я зареюзил сторедж, записав в член-массив. Все, инт, как тривиальный объект тривиального типа без деструктора, сдох в этот момент, лайфтайм у него кончился.
Как он это увидит, извините? Если ему явно разрешено обращаться к объекту типа int через glvalue типа char?
Потому что все способы сделать так, чтобы этот char указывал не на char, нелегальны, насколько я понимаю. Ну а что компиляторы по рукам вас не бьют за игры с юнионами — вопросы к компиляторам.
Алиасит-алиасит!
Не согласен:
то Point и 3DPoint можно безболезненно кастить друг к другу (обращаться к z у чего-то, что было рождено как Point, конечно, нельзя)
На эту тему я сходу так не уверен, но к nested object, сиречь к char, можно кастить, да. Но это именно что голый чар, он не был получен как указатель на что-то, и компилятор вполне имеет право считать, что он не алиасит.
Либо алиасит настолько же, насколько любой другой тип, могущий быть common subobject или как оно там называется. То есть, почти любой тип.
Потому что я зареюзил сторедж, записав в член-массив.С чего вдруг? Вы модицицировали имеющееся там значение типа
int используя данный вам char. Там по прежнему остался int.Вы не туда смотрите — тут мой
union вообще непричём, я мог бы и reinterpret_cast сделать.Потому что все способы сделать так, чтобы этотНаоборот! Почти что любой способ будет корректным! Проблемы тут в том, что структураcharуказывал не наchar, нелегальны, насколько я понимаю.
pointer-interconvertible со своим первым членом, а указатель на char должен алиасится с любым типом (иначе вообще никак нельзя написать memcpy или memmove).Но это именно что голый чар, он не был получен как указатель на что-то, и компилятор вполне имеет право считать, что он не алиасит.Почитайте ещё раз про pointer interconvertible типы внимательно. Обратите внимание на последний случай — мы имеем возможность придумать себе объект, которого не существует, но который поможет нам перейти от одного объекта к другому через воображаемые структуры и объединения!
А иначе как бы непонятно вы вообще могли использовать штуки типа offsetof.
Либо алиасит настолько же, насколько любой другой тип, могущий быть common subobject или как оно там называется. То есть, почти любой тип.Вы тут мешаете в кучу два процесса:
1. Возможность преобразования типов указателей на объекты.
2. Возможность модификации самих объектов, на которые эти указатели указывают.
Так вот первое — можно делать почти всегда. Вы можете преобразовать указатель на
int в указатель на float, char, CharWrapper или вообще почти что угодно (с функциями и, особенно, указателями на члены класса есть ограничения).Однако это не значит, что вы можете, используя этот указатель, безопасно обращаться к значениям, которые там находятся!
Ментальная модель такая: разные типы обрабатываются разными устройствами. Неважно — у вас там 8087 (почитайте о том, как 8087 обращается в память — это весьма нетривиально) или Weitek — в любом случае «главный» CPU может обратиться за результами тогда, когда они ещё не готовы. Синхронизация, в общем, небесплатна — и осущствляется тогда, когда вы используете указатели на
char.Вот это — ментальная модель, описанная в документации на C++: возможность преобразовать один указатель в другой — не даёт вам, автоматически, права этот указатель использовать!
У вас же, похоже, ментальная модель какая-то совсем другая, потому что я даже следов её не вижу! Законно ли, скажем, преобразовать указатель на
int в указатель на short, а потом сдвинуть его на пару элементов? Да не вопрос! А вот можно ли потом обращаться к этому shortу? Ну… если у вас там изначально была структура из intа и shortа… то да — законно и беспроблемно. А вот если там был, изначально, массив intов… тогда нет.А вот
char — он особое исключение. Он всегда может использоваться — независимо от того, с какого типа вы изначально начали и, что важно, тип результата тоже может быть каким угодно. Через него можно прямо добраться до байтов из которых состоит объект — без ограничений (и да, в стандарте есть места, где он говорит о «байтах из которых состоит объект»).Да, во многих других языках типы — куда более «серьёзная» конструкция (не только Haskell, но даже и Pascal какой-нибудь). А в C++ — это тооооненькая-тооооненькая прослоечка над байтами.
А ограничения алиасинга, которые используют компиляторщики — они изначально для совсем-совсем другого был придуманы… Условно — для связки 8086+8087 (и других подобных).
Такие дела…
С чего вдруг? Вы модицицировали имеющееся там значение типа int используя данный вам char. Там по прежнему остался int.
Записав в другой объект с тем же стореджем.
Вы не туда смотрите — тут мой union вообще непричём, я мог бы и reinterpret_cast сделать.
К чему, к char*?
Почитайте ещё раз про pointer interconvertible типы внимательно. Обратите внимание на последний случай — мы имеем возможность придумать себе объект, которого не существует, но который поможет нам перейти от одного объекта к другому через воображаемые структуры и объединения!
Да, это значит, что вы можете привести указатель на CharWrapper к указателю на char.
Но это не значит, что glvalue, соответствующая CharWrapper'овскому char, может указывать на произвольный объект. Вы же её можете получить только от этого CharWrapper!
А иначе как бы непонятно вы вообще могли использовать штуки типа offsetof.
А я их не использую Что там компилятор делает и какую магию в своей нутрянке он предоставляет — не моё дело. Это его магия, семантика которой ему известна.
Ментальная модель такая: разные типы обрабатываются разными устройствами.
Моя ментальная модель предельно проста — для работы с объектом я могу использовать только указатель на него либо указатель на char/uchar/std::byte. Всё.
Законно ли, скажем, преобразовать указатель на int в указатель на short, а потом сдвинуть его на пару элементов?
Да, конечно.
Ну… если у вас там изначально была структура из intа и shortа… то да — законно и беспроблемно.
Не уверен. А вдруг у вас там компилятор паддинг вставит?
Более того, не уверен даже в случаях отсутствия паддинга (и с кем-то про это несколько лет назад даже спорил, но лень и на эту тему по стандарту бегать).
Но в любом случае это всё неважно. Да, если у вас есть указатель на CharWrapper, то вы можете из него сделать указатель на char. Но что это ломает? Вы, в конце концов, из любого объекта можете сделать указатель на char.
Вопрос в другом: можете ли вы сделать указатель на CharWrapper из указателя на char, который изначально не указывал на CharWrapper или на char? Я утверждаю, что нет, поэтому алиасинга быть не может.
Есть дыра, связанная с тем, что CharWrapper является pointer-interconvertible c любым другим типом, имеющим char первым членом, но это выполняется и для предложенного вами типа.
Записав в другой объект с тем же стореджем.Ну уж нет. Читаем:
In simple assignment (=), the object referred to by the left operand is modified ([defns.access]) by replacing its value with the result of the right operand.
Простое присваивание не создаёт нового объекта — оно модифицирует существующий.
Отсюда, собственно, вся разница между конструктором и оператором присваивания.
КВы не туда смотрите — тут мой union вообще непричём, я мог бы и reinterpret_cast сделать.К чему, к char*?
char*, double*, CharWrapper*… да вообще указатель на один тип можно в указатель на почти любой другой тип в C++ безопасно кастить через reinterepret_cast. Вот использовать полученный указатель — да, можно только с ограничениями… Да, это значит, что вы можете привести указатель на CharWrapper к указателю на char.
Но это не значит, что glvalue, соответствующая CharWrapper'овскому char, может указывать на произвольный объект. Вы же её можете получить только от этого CharWrapper!Почему это? Я могу стартовать с указтеля на целое число, пробразовать его в указатель на
char (нет ограничений), могу его потом и подвигать (кто запретит?), потом преобразовать в CharWrapper*.Нигде на этом пути никаких запретов нет…
Причём тут «нутрянка»? Если у вас standard-layout-тип то вы имеете в вашей программе всеми этими удобствами пользоваться безусловно… а начиная с C++17 — разработчики компилятора могуть разрешить вам пользоваться всеми этими чудесами и в других случаях (но не обязаны).А я их не используюЧто там компилятор делает и какую магию в своей нутрянке он предоставляет — не моё дело. Это его магия, семантика которой ему известна.
Впрочем вам
CharWrapper — он, конечно, standard-layout… что сразу закрывает тему.Для того, чтобы написать
offsetof — нужна магия, выходящая за рамки стандарта, да… но чтобы использовать — магии не нужно… а с вашим подходом она таки была бы нужна.Моя ментальная модель предельно проста — для работы с объектом я могу использовать только указатель на него либо указатель на char/uchar/std::byte. Всё.Это отличная ментальная модель, но разрабочики компилятров должны поддерживать не только такие вещи, а всё, что разрешает стандарт… а разрешает он весьма много чего…
Не уверен. А вдруг у вас там компилятор паддинг вставит?Дык и размером
int может оказаться не в два shortа. Для проверки подобных вещей как раз offsetof и sizeof и нужны.Вопрос в другом: можете ли вы сделать указатель на CharWrapper из указателя на char, который изначально не указывал на CharWrapper или на char? Я утверждаю, что нет, поэтому алиасинга быть не может.На основании чего вы это утверждаете? Кто вам это запретит? В каком именно месте возникнет UB? Pointer-interconvertible типы потому так и называются, что их можно конвертировать в любом направлении…
Есть дыра, связанная с тем, что CharWrapper является pointer-interconvertible c любым другим типом, имеющим char первым членом, но это выполняется и для предложенного вами типа.Разумеется! Разница-то не в этом! Разница в том, что в моём типе никаких
charов нету. Там long long. Небольшой такой, однобайтовый. Он не может ни с чем алиаситься.Кстати я тут подумал и понял, что перемудрил. Ибо никакого «небольшого» long long, конечно не нужно. Достаточно небольшого однобайтового char… потому что у битовых полей же нельзя взять адрес — то есть тип битового поля не совпадает с объявленным типом этого поля… это отдельный тип… хотя выглядит, конечно, как «масло масляное»… но работает… но сносит крышу ICC… прекрасно, просто прекрасно…
Люблю C++: где ещё можно выстрелить себе в ногу столькими разными способами?
Простое присваивание не создаёт нового объекта — оно модифицирует существующий.
У юнионов создаёт. То есть, там написано не совсем это, и вы теоретически могли бы взять указатель на этот член (как вы и делаете), скастануть в char и что-то туда присвоить, но я, опять же, не уверен, что это легально. Получается какой-то уж больно очевидный хак и дыра.
Вот использовать полученный указатель — да, можно только с ограничениями…
Естественно, и мы же обсуждаем вопрос использования.
Я могу стартовать с указтеля на целое число, пробразовать его в указатель на char (нет ограничений), могут его потом подвигать (кто запретит?), потом преобразовать в CharWrapper*.
Прекрасно. И где у вас здесь возник алиасинг? Откуда у вас возможность через указатель на CharWrapper писать куда-то ещё?
На основании чего вы это утверждаете? Кто вам это запретит?
Если быть совсем формальным (один фиг не агду ковыряю), то сделать указатель можете. Разыменовать вы его потом не можете.
В каком именно месте возникнет UB?
В том, где вы попытаетесь работать с объектом с типом, отличающимся от CharWrapper, через указатель на CharWrapper.
То есть, конечно, вы его можете преобразовать обратно в char* и творить стандартную вакханалию, но вы её будете творить через указатель на char*. Нет указателя на char* — нет проблем, а я в сухости и безопасности.
Кстати я тут подумал и понял, что я перемудрил. Ибо никакого «небольшого» long long, конечно не нужно. Достаточно небольшого однобайтового char… потому что у битовых полей же нельзя взять адрес — то есть тип битового поля не совпадает с объявленным типом этого поля… это отдельный тип…
Я битовые поля не люблю, enum class meh : char в рамках вашего подхода хватит? Или даже signed char?
То есть, там написано не совсем это, и вы теоретически могли бы взять указатель на этот член (как вы и делаете), скастануть в char и что-то туда присвоить, но я, опять же, не уверен, что это легально.Легально-легально. Вы вообще подумайте: кому и зачем могла бы быть нужно разрешение на получение доступа к объектам произвольного типа через glvalue типа
char, unsigned char или std::byte, если бы на самом деле ограничения касались бы именно указателей?Получается какой-то уж больно очевидный хак и дыра.Никаких хаков и никакой дыры: вы можете записывать в
char независимо откуда вы его взяли и через какие тернии этот char при этом прошёл. По крайней мере если мы не выходим за рамки standard-layout типов…Естественно, и мы же обсуждаем вопрос использования.А тут тоже всё просто: если это указатель на
char и он указывает на какой-то объект… то обращаться к нему легально. Мы могли его лаже в чиселко превратить и куда-нибудь в SQL базу положить, а потом забрать… без разницы (впрочем это возможно только если в реализации существует intptr_t).Откуда у вас возможность через указатель на CharWrapper писать куда-то ещё?Ну тут-то как раз всё просто: если вы явно преобразуете этот указать обратно указатель на
char — то всё будет точно законно. А вот должен ли автоматически сгенерированный оператор присваивания допускать то, что изначально указатель мог быть рождён из указателя на другой тип… хороший вопрос — не знаю, следует ли это откуда-нибудь.То есть может быть с точки зрения стандарта вы, может быть, и правы. А вот с точки зрения GCC — точно нет. А поскольку ошибка консервативная (код корректный, хотя возможно не оптимальный) то вряд ли её кто-то будет править, пока не появятся реальные программы, где это важно…
Нет указателя на char* — нет проблем, а я в сухости и безопасности.Этого недостаточно: тут же как раз всё наоборот — вы же хотите убедить компилятор, что ему разрешено чуть больше, чем с указателями на char*. Если компилятор вообще все указатели будет трактовать как указатели на char — всё же корректно будет (собственно для этого даже опция есть -fno-strict-aliasing).
Или даже signed char?Signed char ничем не отличается… а вот enum — да, работает… похоже это самый лучший и переносимый вариант. Он и ICC не пугает…
Вы вообще подумайте: кому и зачем могла бы быть нужно разрешение на получение доступа к объектам произвольного типа через glvalue типа char, unsigned char или std::byte, если бы на самом деле ограничения касались бы именно указателей?
Я уже давно перестал думать о «зачем» в контексте стандарта. По крайней мере, в таких местах, где куча разных разделов играет друг с другом в каких-то нетривиальных комбинациях.
Никаких хаков и никакой дыры: вы можете записывать в char независимо откуда вы его взяли и через какие тернии этот char при этом прошёл. По крайней мере если мы не выходим за рамки standard-layout типов…
Я о другом.
Пусть у вас
union
{
int a;
float b;
};Тогда если вы сделаете
auto ptr = &b;
*ptr = 20;
a = 10;
return *ptr;то это просто обязано быть невалидным.
А тут тоже всё просто: если это указатель на char и он указывает на какой-то объект… то обращаться к нему легально.
Но наличие отдельного типа CharWrapper именно что позволяет избегать наличия указателя на char в коде в явном виде!
Ну тут-то как раз всё просто: если вы явно преобразуете этот указать обратно указатель на char — то всё будет точно законно.
Полностью согласен. Но для этого мне надо получить указатель на char. И это работает для абсолютно любого типа: вы можете указатель на него превратить в указатель на char и писать куда угодно.
То есть может быть с точки зрения стандарта вы, может быть, и правы. А вот с точки зрения GCC — точно нет.
Вы меня уже убедили, что мой исходный вариант, вероятно, работает не очень, и надёжнее делать по-другому. Но я всё ещё не могу понять, где моя брешь в понимании алиасинга.
А поскольку ошибка консервативная (код корректный, хотя возможно не оптимальный) то вряд ли её кто-то будет править, пока не появятся реальные программы, где это важно…
Когда-то и сравнение this с нулём не выбрасывалось, а LLVM вроде как в 9-й версии это стал оптимизировать.
Этого недостаточно: тут же как раз всё наоборот — вы же хотите убедить компилятор, что ему разрешено чуть больше, чем с указателями на char*.
Именно! Поэтому у меня нет указателей на char.
Тогда если вы сделаетеНу тут у вас никаких
auto ptr = &b; *ptr = 20; a = 10; return *ptr;
то это просто обязано быть невалидным.
chat нету и типы не similar, так что да — тут это невалидно.Я уже давно перестал думать о «зачем» в контексте стандарта.Тем не менее разработчики стандартна об этом думают (работа у них такая). В частности есть прекрасный пример, который разработчики компиляторов считают невалидным, хотя стандарт, вроде бы, его допускает.
union DeathToHumans {
float f;
int i;
};
void foo(int* pi,
float* pf,
DeathToHumans* switcher) {
switcher.f = 1.0;
*pf = 2.0;
switcher.i = 42;
*pi = 57;
}
...
DeathToHumans x;
foo(&x.i, &x.f, &x);
...
Однако пока никто не предложил хорошего решения (в смысле: изменения текста стандарта).
Но наличие отдельного типа CharWrapper именно что позволяет избегать наличия указателя на char в коде в явном виде!Но речь же идёт не об указателе типа
char, а о glvalue типа char!У вас-то нет… а вот в автоматически сгенерированной функцииЭтого недостаточно: тут же как раз всё наоборот — вы же хотите убедить компилятор, что ему разрешено чуть больше, чем с указателями на char*.Именно! Поэтому у меня нет указателей на char.
CharWrapper::operator=(const CharWrapper&) — они есть (вернее там есть glvalue типа char — но в нужном месте стандарта речь как раз о glvalue, не об указателях). И компилятор считает, что они могут обращаться к другому типу… хотя следует ли это из стандарта — я сказать и не могу…Ну тут у вас никаких chat нету и типы не similar, так что да — тут это невалидно.
Так там у вас тоже char нету, есть только CharWrapper. Вы можете получить указатель на char, но для этого придётся сделать явный каст, и у вас будет указатель на char.
Причём даже разработчики стандарта, в принципе, признали, что то, что стандарт это допускает — «не есть хорошо»… потому что если такое признать допустимым, то получится что указатели на что угодно могут алиаситься, если между ними вызывается функция, кода которой мы не видим…
Это как раз ближе к тому, что я там в конце пытаюсь придумать — что с похожей логикой каждый указатель может алиаситься с каждым.
Но речь же идёт не об указателе типа char, а о glvalue типа char!
Мой поинт в том, что код заш… может, начинает алиасить тогда и только тогда, когда у вас в том или ином виде вылезает явный указатель на char. Скастуете CharWrapper к нему — будет боль и алиасинг. Нет каста — нет проблем.
И компилятор считает, что они могут обращаться к другому типу…
Вот мое впечатление — что компилятору здесь силёнок не хватает.
Впрочем, если сделать шаг назад, ситуация, когда два вроде как неглупых разработчика, более-менее знающих C++, обсуждают, как же на этом языке сделать строки, и уже почти сутки не могут придти к консенсусу — это прикольно. Хороший язык.
оставлю тут https://lkml.org/lkml/2018/6/5/769. тоже пытался понять после вашей дискуссии с "царём" в соседнем топике но ни**а не понял.
Увидел, от кого письмо — сразу понял, что в письме будет «в гцц работает, значит, всё в порядке».
Прям синдром Линуса в поле from.
Так наоборот, gcc позволяет программисту больше, давая себе меньше простора для оптимизаций.
А в других языках просто нет таких юнионов (или вообще указателей).
Впрочем, если сделать шаг назад, ситуация, когда два вроде как неглупых разработчика, более-менее знающих C++, обсуждают, как же на этом языке сделать строки, и уже почти сутки не могут придти к консенсусу — это прикольно.Почему не могут? Могут. Уже пришли к консенсусу: "
enum FastChar : char {};" — это точно рабочий вариант.А дальнейшее — это уже попытка придумать можно ли обойтись структурой…
Хороший язык.Отличный просто. Никогда ни в чём нельзя быть уверенным.
mov byte ptr [rsp - 16], 0
......
mov rcx, qword ptr [rsp - 16]
mov qword ptr [rsp - 16], rcx
......
test cl, clОбъяснение по ссылке выглядит убедительным (хотя для меня не очень понятным, ну да ладно), однако вообще это выглядит как, скажем так, некий приговор, если не языку, то использованным идиомам. Меньше кортежей, меньше…
Просто не только у ФП-шников компиляторы ещё не достаточно умные.
C++20 «zero-cost» за счёт встраивания короутины в объемлющую процедуру.Там до обещанного «zero-cost» ещё копать и копать — компиляторы ломаются в самых простейших случаях…
за счёт встраивания короутины в объемлющую процедуру
Хочется верить, что это встраивание не будет носить массовый характер, кмк в большинстве случаев все-таки корутине следует быть отдельной сопрограммой.
Но пока это происходит как и с
initializer_list: встраивается-то оно встраивается, но ошмётки во все стороны торчат.Ситуация с initializer_list выглядит грустной еще и потому, что описание std::min с таким параметром не гласит о том, что при таком вызове раскручивается маховик
Я их оба не знаю :)
Если кинете более эффективный вариант, то я его с радостью проверю сегодня вечером.
<…>
let ca1: Vec<u8> = s1.bytes().collect();
let ca2: Vec<u8> = s2.bytes().collect();
let mut v0: Vec<i32> = (0..).take(n + 1).collect();
let mut v1 = v0.to_vec();
for (i, c1) in ca1.iter().enumerate() {
unsafe {
*v1.get_unchecked_mut(0) = i as i32 + 1;
for (j, c2) in ca2.iter().enumerate() {
<…>Действительно, так быстрее.
Отличная статья. Но я, признаться, недоумеваю, где же Idris с его завтипами? Интересно же.
Там с массивами так себе, а на списках я это делать не буду, он не сможет их соптимизировать. Надо брать Idris 2, собирать его из гита… Тема для отдельной статьи, в общем.
С удовольствием бы почитал. Прогаю на плюсах, с интересом перенимаю ФП практики, но не достиг просветления для перехода на Haskell. Бегло читал, что Idris ещё круче, потому буду ждать (предвкушая детальный разбор, анализ оптимизаций и ассемблерные листинги) :)
Круче означает помимо всего прочего — сложнее. Поэтому прежде чем прыгать в самую гущу лучше с чего попроще начать. Новичкам на плюсах наверное самую темную темплейт магию сразу не показывают, сначала простенько, на массивчиках, в рантайме, и потом уже понемногу-понемногу дальше.
Как посмотреть.
ФП учить — ИМХО без разницы, базовая семантика что в хаскеле, что в идрисе одна и та же (с точностью до ленивость). Идрис даже, может, чуть лучше, там из коробки можно делать дырки и смотреть на типы.
Учиться писать продакшн-код — хаскель на голову выше, за счёт тулинга и библиотек в основном.
Учить всякую наркоманию в типах — идрис лучше, там все это адекватно, органично и из коробки. Как работают завтипы там, я плюс-минус понимаю. Как работает комбинация из полутора десятков расширений языка в случае хаскеля, которые пытаются это эмулировать — хорошей интуиции у меня нет, и проще в голове держать некий образец на идрисе, который потом транслировать в хаскель.
C
Windows 10, gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)
$ gcc ld.c -Ofast -fPIC -fPIE -static -flto -o ld.exe
$ ld.exe
0
15000
Finished in 0.934s
Python
Косметические изменения в коде:
import sys
import time
import numpy as np
from numba import jit
@jit
def lev_dist(s1: bytes, s2: bytes) -> int:
m = len(s1)
n = len(s2)
# Edge cases.
if m == 0:
return n
elif n == 0:
return m
v0 = np.arange(0, n + 1)
v1 = np.arange(0, n + 1)
for i, c1 in enumerate(s1):
v1[0] = i + 1
for j, c2 in enumerate(s2):
subst_cost = v0[j] if c1 == c2 else (v0[j] + 1)
del_cost = v0[j + 1] + 1
ins_cost = v1[j] + 1
# min(subst_cost, del_cost, ins_cost) is slow.
min_cost = subst_cost if subst_cost < del_cost else del_cost
if ins_cost < min_cost:
min_cost = ins_cost
v1[j + 1] = min_cost
v0, v1 = v1, v0
return v0[n]
Результаты на Windows 10, Python 3.7.5
$ python ld.py
0
15000
Finished in 0.968s
На долю процентов C быстрее, но скорости практически сравнимы.
Умножьте на (4/3)² — для этих данных время квадратично зависит от длины, а везде строки в 20 тыщ символов.
Ну и, кстати, сколько тогда работы выполняется в питоне, а сколько — в C?
Ну и, кстати, сколько тогда работы выполняется в питоне, а сколько — в C?Ну Python же это язык. У него может быть реализация как у интепретируемого языка, а может быть и jit компиляция.
А по факту я взял приведенный исходник на Python, практически добавил всего одну аннотацию, запустил в стандартной реализации CPython и получил практически скорость языка С. С точки зрения разработчика я нигде не вышел из окружения Python.
Ну Python же это язык. У него может быть реализация как у интепретируемого языка, а может быть и jit компиляция.
Безусловно (поэтому там есть сравнение с pypy). Но FFI в C — это ИМХО как-то не очень честно при бенчмаркинге реализаций, так как вы тогда сравниваете не эффективность реализаций, а эффективность FFI.
так numba это не ffi
Теперь-то обратил внимание на @jit. Прикольная штука, буду иметь в виду, если вдруг придётся столкнуться с питоном.
То есть если вы сами пишите код — в общем не проблема.
А вот взять чужой код и налепить на него jit — можно поиметь проблем.
Но учитывая ускорение в несколько раз — иногда можно поиграться…
На мой взгляд вполне честно все сравнивать с точки зрения разработчика. Есть код, есть плафторма, есть результат.
Да и чем, грубо говоря, декоратор "@jit" так уж сильно отличается от набора специальных флагов «gcc» с подсказками для оптимизаций?
Я в том комментарии был неправ, так как неправильно прочитал код.
Если я захочу прогнать ваш вариант на той же машине, где замерял все остальные реализации, что мне там надо поставить кроме самого питона?
$ pip3 install numpy
$ pip3 install numba
На всякий случай, вот полный код:
#!/usr/bin/env python3
import sys
import time
import numpy as np
from numba import jit
@jit
def lev_dist(s1: bytes, s2: bytes) -> int:
m = len(s1)
n = len(s2)
# Edge cases.
if m == 0:
return n
elif n == 0:
return m
v0 = np.arange(0, n + 1)
v1 = np.arange(0, n + 1)
for i, c1 in enumerate(s1):
v1[0] = i + 1
for j, c2 in enumerate(s2):
subst_cost = v0[j] if c1 == c2 else (v0[j] + 1)
del_cost = v0[j + 1] + 1
ins_cost = v1[j] + 1
# min(subst_cost, del_cost, ins_cost) is slow.
min_cost = subst_cost if subst_cost < del_cost else del_cost
if ins_cost < min_cost:
min_cost = ins_cost
v1[j + 1] = min_cost
v0, v1 = v1, v0
return v0[n]
if __name__ == "__main__":
s1 = b"a" * 15_000
s2 = s1
s3 = b"b" * 15_000
exec_time = -time.monotonic()
print(lev_dist(s1, s2))
print(lev_dist(s1, s3))
exec_time += time.monotonic()
print(f"Finished in {exec_time:.3f}s", file=sys.stderr)
for j, c2 in enumerate(s2):
v1[j+1] = min(v0[j] if c1 == c2 else (v0[j]+1), v0[j+1]+1, v1[j]+1)
Не понимаю, чем не понравился автору статьи min()?
Подобные "упрощения" не очень то и упрощают чтение кода. :)
P.S. В конце концов можно так сделать:
for j, c2 in enumerate(s2):
v1[j+1] = min(v0[j] if c1 == c2 else (v0[j]+1),
v0[j+1]+1,
v1[j]+1)
0.998 с (на 20 тыщах). Неплохо!
Python c JIT-компиляцией через Numba просто рвёт все остальные скриптовые языки.
Why is NumPy Fast?¶
Vectorization describes the absence of any explicit looping, indexing, etc., in the code - these things are taking place, of course, just “behind the scenes” in optimized, pre-compiled C code
Ну как-то так. Я бы непричислял это к заслугам питона.
Только вот серьезные проблемы с совместимостью с Python 3.10 :( См. https://github.com/numba/numba/issues/7562
на любом языке можно писать на фортране
Numba – это что-то невероятное…
У меня оно не получилось быстрее C, но оно справилось быстрее Julia.
Круто, что даже без использования numpy при помощи numba можно прилично ускорить работу программы.
Например, если на код автора просто навесить декоратор @jit — программа отработает за 2.528 на моем железе.
Если убрать isinstance — уже будет 1.7.
Что не может не радовать. :)
Все-таки, если уже считаем в Питоне, то берем для этого инструменты, которые для него придумали.
P.S. Забыл про главное, компилятор ldc2, а не референсный DMD.
Не хочу комментировать, что 0xd34df00d намерял с C++, но ведь с D именно так оно и есть уже.
Можно было бы ещё LDC приложить, ведь он быстрее DMD справился с сей задачей.
ldc у меня не собрался. Дашь бинарь?
Протестировал у себя, получил похожие цифры, а потом уже удвоился за счёт проверок границ. Даже не задумывался, что можно бенчмаркать DMD, на автомате взял ldc. Результаты у меня:
C gcc 8.3: Finished in 0.696s
D ldc2 1.10.0: Finished in 0.638s
Есть разброс, но в целом D версия чуть быстрее.
const levDist = (s1, s2) => {
const m = s1.length;
const n = s2.length;
// Edge cases.
if (m === 0) {
return n;
} else if (n === 0) {
return m;
}
let v0 = new Uint16Array(n + 1);
let v1 = new Uint16Array(n + 1);
for (let i = 0; i < m; ++i) {
v1[0] = i + 1;
for (let j = 0; j < n; ++j) {
v1[j + 1] = Math.min(
v0[j] + (s1[i] === s2[j] ? 0 : 1),
v0[j + 1] + 1,
v1[j] + 1
);
}
[v0, v1] = [v1, v0];
}
return v0[n];
};
const s1 = new Uint8Array(15000).fill('a'.charCodeAt(0));
const s2 = s1.slice();
const s3 = new Uint8Array(15000).fill('b'.charCodeAt(0));
console.time('Finished in');
console.log(levDist(s1, s2));
console.log(levDist(s1, s3));
console.timeEnd('Finished in');а зачем на с++ используется int64?
Для консистентности с хаскель-версией, там Int — знаковый и соответствующей машине битности. Впрочем, замена на uint64_t или на (u)int32_t вообще ничего не меняла на моей машине (что ожидаемо, работа с L2-кешем таки не оказывается боттлнеком, чтения/записи исключительно последовательные и хорошо предсказываются, векторизации здесь нет, а сравнения и сложения процессор выполняет, видимо, одинаково эффективно).
void calc_line(const char c1, const std::string &s2, const int64_t *__restrict v0, int64_t *__restrict v1, size_t n);
Сразу sse появляются и прочие удовольствия
интересно что у меня на clang++8 если ставить флаг -std=gun++2a вместо -std=gnu++17 есть прирост где-то на 8%.
К тому же еще странно как у вас шланг так сливает гцц, я вот захожу на годболт, и там шланг векторизирует а гцц нет, и у меня на машине шланг8 быстрее гцц9.1. Сейчас поставлю новые версии.
Еще расту тоже надо указывать -C "target-cpu=native для честности. Кстати хаскелю наверное тоже что то такое т.к. это флаг скорее всего для ллвм.
интересно что у меня на clang++8 если ставить флаг -std=gun++2a вместо -std=gnu++17 есть прирост где-то на 8%.
Вот это вот действительно интересно. Я сходу не могу придумать, за счёт чего оно бы так могло быть.
К тому же еще странно как у вас шланг так сливает гцц, я вот захожу на годболт, и там шланг векторизирует а гцц нет, и у меня на машине шланг8 быстрее гцц9.1.
Я, кстати, не знаю, как тут так просто бы векторизовать, так как у каждого следующего элемента массива есть неприятная зависимость по данным от всех предыдущих. Если он там действительно векторизует, а не просто использует векторные регистры и векторные мувы, чтобы сразу 8-16-32 инта получать, то это очень круто.
Ну и да, на одной из машин у меня был clang 8, и там он был быстрее gcc, так что, вероятно, это регрессия. Но полный набор тестов на той машине я провести не мог, а ставить clang 8 на ту, где мог, просто потому, что он тут быстрее — это какое-то читерство.
Кстати хаскелю наверное тоже что то такое т.к. это флаг скорее всего для ллвм.
Если вкратце, то у меня не получилось, а жаль. Могло бы быть ещё чуточку быстрее.
наверное про векторизацию я нагнал и это был код iota
У меня разница между шланг8 и шланг9 минимальна. 8-ой шланг действительно дает маленькую регрессию при с++17.
А я уже тестил с оптимизацией s1[i] за границей цикла. Иначе (на вашем оригинальном коде) в шланге9 дикая регрессия больше чем в два раза!
Было бы неплохо обновить статью новой табличкой результатов. И новыми выводами.
И еще статья дает больше информации не столько о скорости ЯП, сколько об их читаемости.
Как вечером доберусь до домашней машины — прогоню предложенные новые варианты и обновлю.
А выводы-то… Ну вот питон с numba приятно удивил, да. Другой вывод — похоже, я не умею передавать смысл того, что я делаю.
У меня вывод простой (из аналогичных тестов) — если язык компилируемый, то в большинстве случаев производительности достаточно, кроме разве что, специализированных задач.
И можно не пренебрегать безопасностью в угоду производительности.
Но в любом случае надо хорошо знать свой инструмент.
У меня вывод простой (из аналогичных тестов) — если язык компилируемый, то в большинстве случаев производительности достаточно, кроме разве что, специализированных задач.
С одной стороны — не только. Смотрите, как хорошо себя JS показывает на V8/SM.
С другой — не столько. Случаи, когда тот же хаскель был медленнее на несколько порядков, у меня тоже были. Правда, я тогда был сильно глупее и неопытнее. Думаю, на самом деле разница там уж не на порядки.
Проблема Хаскеля (ну и не только, например linq, sql), как я глупо думаю — что высокоуровневые абстракции скрывают реальные накладные расходы — и очень легко написать красивый код, получив ужасную практическую реализацию с квадратичными расходами.
А фиг его знает, в чём проблема.
Я на самом деле очень разочарован, что forM_ пришлось выкинуть и написать хвостовую рекурсию руками. Это плохо. Этого быть не должно. Я ожидаю, что компилятор это свернёт и сделает за меня.
А ведь это, ну, очень базовая во всех смыслах вещь. И функция в базовой библиотеке, и используется часто, и от этой мелкой оптимизации можно выиграть разы (как показывает данный пост).
Боюсь, её написание займёт больше виртуального лимита в час, который я себе отвёл, так что её время работы не определено.
И так для каждой микроархитектуры.
А если серьёзно, я смотрел на асм (но больше на хаскелевский — интересно было, чего там компилятор наворотил). В общем, мне пока хватит.
Что, если в хаскелевском коде 0.8с уходит на инициализацию некого рантайма, а остальные 0.01с на что-то вроде
.LC0:
.string "0"
main:
movl $.LC0, %edi
jmp puts? Я бы добавил зависимость от входных данных, чтобы быть уверенным, что результат считается не в compile-time.
Ну тут две вещи дают уверенность:
- Я добавлял
NOINLINE-прагму к определению функции (с очевидной семантикой) — ничего не изменилось вообще никак, а кроссмодульную оптимизацию в ghc не завезли. - Библиотека criterion специально сделана так, чтобы данные не протекали в функцию до начала бенчмарка, и результаты от этой библиотеки согласуются с результатами из табличек.
у меня уже есть ответ, впрочем
//$ca1 = $ca2 = [];
//for ($i = 0; $i < $m; ++$i) {
// $ca1[] = ord($s1[$i]);
//}
//for ($i = 0; $i < $n; ++$i) {
// $ca2[] = ord($s2[$i]);
//}
А соответствующие циклы заменить на:
for($i = 0; $i < $m; $i++) {
$v1[0] = $i + 1;
for($j = 0; $j < $n; $j++) {
$subst_cost = ($s1[$i] === $s2[j]) ? $v0[$j] : ($v0[$j] + 1);
$del_cost = $v0[$j + 1] + 1;
$ins_cost = $v1[$j] + 1;
// min($subst_cost, $del_cost, $ins_cost) is slow.
$min_cost = ($subst_cost < $del_cost) ? $subst_cost : $del_cost;
if ($ins_cost < $min_cost) {
$min_cost = $ins_cost;
}
$v1[$j + 1] = $min_cost;
}
[$v0, $v1] = [$v1, $v0];
}
Минус два цикла — должно дать существенный прирост производительности
Сравнение чисел просто немножко дешевле.
плюс строгое равенство при сравнении одиночных символов.
Зуб даю мой код быстрее и читабельнее. Не говоря уже про UTF-8
минус два цикла с вычислением ord()Вне цикла подобные манипуляции вообще ничего не значат на общем фоне. Так-то их можно вообще вынести наружу… только зачем?
плюс строгое равенство при сравнении одиночных символов
При сравнении строк иначе и нельзя. А вот при сравнении (гарантированных) чисел никакой разницы тут не будет.
Не говоря уже про UTF-8
Все версии сделаны именно так, чтобы сравнивались именно индивидуальные байты для однородности и простоты (ну, в большинстве случаев).
Но вообще, как ни иронично, именно вариант с конвертацией в массив чисел более юникододружелюбный, потому что с ним для UTF-8 нужно просто заменить ord на mb_ord, а иначе нужно использовать mb_substr; а это, сам понимаешь, уже целый вызов функции внутри цикла.
минус два цикла с вычислением ord()
Вне цикла подобные манипуляции вообще ничего не значат на общем фоне. Так-то их можно вообще вынести наружу… только зачем?
Я не понял что именно вы предлагаете «вынести наружу»?
Что-то я не понял мысль. Или мне кажется вы не поняли про какие два цикла я говорю.
Я предложил тупо убрать два вспомогательных цикла перед двумя вложенными друг в друга — потому что они ничего не добавляют важного и нужного. И если их цель преобразовать строки в числа — то мне кажется это немного высокая цена ради того чтобы позже выиграть на сравнении чисел вместо строк.
Но преобразование строк в числа — m + n операций (где это длины строк), а сравнений потом происходит в районе mn. 40 тысяч против 400 миллионов в этом случае.
И если их цель преобразовать строки в числа
Как бы, ord…
Неужели так сложно поверить, что числа сравнивать дешевле, чем целые строки, хоть и единичные %)?
это немного высокая цена
Два for на 40 000 циклов суммарно.
ради того чтобы позже выиграть на сравнении чисел вместо строк
А вот сравнение происходит 400 000 000 раз.
Не говоря уже про UTF-8
Предложенная функция всё равно остаётся метрикой (в математическом смысле), пусть и считает немного не то.
Но игнорирование уникода было одним из моих допустимых предположений, считать всё корректно для уникода (и особенно для UTF-8) чуть менее просто.
считать всё корректно для уникода (и особенно для UTF-8) чуть менее просто.
Тут зависит от реализации. Для раста можно заменить итератор по bytes на итератор по chars и получить всё то же самое и без особой просадки производительности.
А на php с кем-то предложенным тут mb_substr это будет уже O(n⁴), потому что для взятия каждого следующего символа надо будет пробежать по всей строке.
В коде на С++ внутри одного цикла идет std::swap длинных векторов, в коде на С — меняются указатели. До кучи внутри swap идет вызов new/delete, которые на Це эквиваленты дерагнью malloc/free, что само по себе плохо сказывается на производительности и зависит от того, как там heap устроен, плюс есть эффект на забивание кешей процессора
Там нет вызова new/delete. И быть его там не должно, если ваша реализация STL зачем-то там выделяет/освобождает память, то её лучше выкинуть.
В этом случае std::swap действительно делает чуть больше работы, чем обмен указателями (так как он обменивает ещё и длины, а они одинаковые), но я не думаю, что это принципиально что-то меняет.
Быстрее, чем C++; медленнее, чем PHP