Бенмарки и недоязычки. Часть 1

Почему

В связи с нехваткой времени - решил завести какой-то лайт-контент. Уже давно хотел этим заняться, но тема достаточно сложная и многогранная. Именно поэтому её нужно отложить её на пост-времянку, но увидев на лоре опять вскукареки - решил начать сейчас. Опять же, это просто затравка, но от этого она не менее интересна.

Предыстория

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

Бенчмарки говна. Они ничего не бенчат.

• Фейковое зерно. Бенмарк по природе своей должен отражать реальную задачу, брать из неё суть и получать новую задачу лишённую всякого мусора, но решение которой автоматом решает начальную задачу. Мусор убирается для того, чтобы сосредоточиться на главном. Но - эти бенчмарки говна не имеют этого зерна. Они имеют фейковое зерно.
  
  Фейковое зерно это то, что авторы этого мусора пытаются выдать за зерно. Как это происходит. В задачу примешивается всякий мусор, который никак не следует из условий. Это просто прихоть идиотов. Если мы хотим сделать быстро - будем ли мы изначально выбирать тупиковые форматы, подходы и прочее? Нет. Весь этот мусор должен отсеяться ещё на первой итерации, вернее на нулевой итерации. Я покажу это в разбираемом бенчмарке ниже.


• Бенчмарк языка должен прежде всего бенчить язык, но прежде всего он должен бенчить возможность адепта.
  
  Что же происходить здесь? Раст-отребье(и прочие) ворует код, ворует рантайм. Что мы хотим узнать? Мы хотим узнать - что сможет родить раст-отребье, если его предоставить самому себе и его недоязычку. Это как посадить за лабу дошколёнка и дать ему возможность воровать готовые решения. Что мы этим узнаем? Может ли дошколёнок воровать? Воровать может любой. И это крайне важно, ведь если завтра вам нужно будет взять этих рабов и дать им задачу, то никакого готового уже не будет. И чего мы этим добились? А ничего.
  
  Тоже самое касается и недоязычка. Если мы хотим доказать состоятельность недоязычка - мы должны им полностью заменить то, за замену чего пропаганда это говно выдаёт. И пропаганда постоянно впаривает, что “мы же не можем заменить всё”, мы не заменяем потому, что “это не имеет смысла, а не мы не можем”. Ну во-первых смысл это имеет. Это пруф. Ты должен как адепт доказать всем, и по крайней мере себе, что ты можешь что-то заменить.
  
  Во-вторых, в этих всех бенчмарках никакое “сложно” не работает. Здесь сотни строк кода - нет никакой проблемы их написать. Но отребье не может даже этого.


• Измерения. Крайне важно выполнять измерения правильно, но это бездарное говно не способно на это. Допустим, раст-отребье любит использовать следующую схему. Оно бежит за последней версией своего огрызка фронта ворованного компилятора и сравнивает это с gcc5. Я видел это сотни раз, но и не только я, очевидно.
  
  Это значит то, что все измерения должны поддерживаться в актуальном состоянии. Никакого сравнения результатов сделанных 5 лет назад и сейчас - быть не может. Тоже самое касается окружения. Окружение должно быть идентично и актуально. Тоже самое касается железа. Результаты должно отражать реальность. Отражать то, что вы получите запустив это у себя. Но эти бездарности бенчат всё это на мусоре. Мало того, что этого мусора в принципе ни у кого нет - оно не имеет смысла.
  
  Причины просты. Я уже не раз про это рассказывал и недавно на лоре опять на это вышли, в очередных бенчмарках(говна). Поэтому нужно чётко помнить. core2 - это мусор. Результаты на этом говне никак не соотносятся с реальностью. Даже нехалем это мусор, Это нулевая итерация интела в современные реалии. Она была крайне слаба. Всё, что до нехалема(включительно) не является тем, на чём можно получить адекватные результаты. Это аксиома.

Пример

Я взял revcomp как типичный пример шизофрении. Он прекрасен всем.

Конечно же формат дерьма. Очевидно, что любой текст - мусор для идиотов. Любая стркутура в данных - мусор для идиотов. Подобный мусор никогда не будет работать быстро. Как я уже говорил - нулевая итерации оптимизации - безжалостный выпил всего плебейского мусора. А занятие оптимизацией этого мусора - это то самое фейковое зерно.

Очевидно, что это не имеет смысла и бесполезно. Это сродни задаче оптимального забивания гвоздей, но при помощи микроскопа. Где вся задача будет сведена не к реальной эффективности, а к эффективности использования непредназначенного для данной задачи инструмента. Вот мы и будем изучать устройство микроскопа и заниматься тем, чтобы найти оптимальное место, котором можно бить как можно сильнее не разрушая микроскоп. Правда в ситуации с молотком - это “задачи” попросту не стоит.

Разберём портянку, я буду писать что является проявлением реальной задачи, а что является мусором.

  fs::path path{"/dev/stdin"};
  auto size = fs::file_size(path);
  auto data = (const char *)mmap(nullptr, size + 4096, PROT_READ, MAP_PRIVATE|MAP_POPULATE, STDIN_FILENO, 0);
  sv file{data, size};

Очевидно, что чтение файла - часть реальной задачи. 4 строчки.

  auto next = [=, prev = 0ul]() mutable -> std::pair<sv, sv> {
    auto arrow_pos = file.find_first_of('>', prev);
    auto begin_pos = file.find_first_of('\n', arrow_pos);
    if(begin_pos == sv::npos) return {};
    prev = file.find_first_of('>', begin_pos);
    return {file.substr(arrow_pos, begin_pos - arrow_pos + 1), file.substr(begin_pos + 1, prev - begin_pos - 1)};
  };

  auto index = view::generate(next) | view::take_while(_ != std::pair<sv, sv>{});

Далее, здесь я строю индекс. Это первая проблема форматов дерьма от идиотов для идиотов. Индекс за ноль может построить генератор, а далее мы можем его прочитать. Но что в случае с дерьмом? Правильно, нам нужно прочитать весь файл и найти в нём начало/конец нужным нам кусков.

  for(auto [name, data]: index) {
    write(STDOUT_FILENO, std::data(name), std::size(name));
    replace(data);
  };

Здесь просто обход индекса, печать заголовка последовательности. И запуск реплейса.

void replace(sv data) {
  auto op = select_replace60(data);
  constexpr size_t line_size = 61;
  constexpr size_t buff_size = line_size * 1024;
  char buff[buff_size] = {};
  auto n = size(data) / line_size;
  auto tail = size(data) - (n * line_size);

  auto it = end(data) - 1;
  auto buff_it = std::begin(buff);

  while(n--) {
    op(it, buff_it);
    buff_it += line_size;
    it -= line_size;
    if(buff_it == (std::end(buff) - line_size)) {
      write(STDOUT_FILENO, buff, buff_size - line_size);
      buff_it = buff;
    }
  }
  if(tail) {
    while(tail--) {
      if(*(--it) == '\n') continue;
      *buff_it++ = map256[*it];
    }
    *buff_it++ = '\n';
  }
  write(STDOUT_FILENO, buff, buff_it - std::begin(buff));
}

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

Но, это не всё. Можно заметить: auto op = select_replace60(data); Это одно проявление бездарности задачи.

auto select_replace60 = [](std::string_view in) {
  constexpr static auto replace60_map = ([] {
    std::array<decltype(replace60<0>) *, 60> map{};
    (60_c).times.with_index([&](auto index) {
      map[index()] = replace60<index()>;
    });
    return map;
  })();

  auto first_pos = size(in) - 1;
  assert(in.at(first_pos) == '\n');

  auto diff = first_pos - in.find_last_of('\n', first_pos - 1);
  assert(in.at(size(in) - diff - 1) == '\n');

  return replace60_map.at(61 - diff);
};

Вот оно. Здесь генерируется 61 функция для разных длин хвоста(условно), а далее определяется эта длинна и селектится по этой длиннее нужная функция.

template<size_t noffset> void replace60(const char * in, char * out) {
  constexpr auto offset = hana::llong_c<noffset>;

  auto op = [&] {
    *(uint16_t *)out = map[*(const uint16_t *)(in -= 2)];
    out += 2;
  };

  auto tail_size = ((60_c - offset) / 2_c);
  tail_size.times(op);

  if constexpr(offset % 2_c) {
//     край выглядит так, нужно скипнуть
//   ...1\n  
//   0...  
    *out++ = map256[*(--in)];
    --in;
//     assert(*in == '\n');
    *out++ = map256[*(--in)];
    (29_c - tail_size).times(op);
  } else {// even
//     здесь же края нет, нужно просто скипнуть '\n'
//   ...\n  
//   ...  
    in -= 1;
//     assert(*in == '\n');
    (30_c - tail_size).times(op);//здесь будет на один шаг больше
  }
  *(out++) = '\n';
}

Вот сама функция реплейса. Задача её - дать “оптимальную” функцию. Здесь можно посмотреть разницу между компиляторами. Шланг здесь сливает в 10 раз. И причина проста - он не сделай из этой функции то, что нужно мне. Хотя все вводные ему дали. Это и есть та фундаментальная разница между компилятором и огрызком. Для тех, кто захочет пожрать говна - нужно руками проставлять все индексы.
Очевидно, что всё это решение фейкового зерна. Это ненужно для решения реальной задачи. Даже двухбайтная таблица замены, которая здесь вызывает проблемы - не вызывает их в случае с нормальным форматом данных.

constexpr uint8_t swmap(uint8_t c) {
  switch(c) {
    case 'A': case 'a': return 'T';// 'A' | 'a' => 'T',
    case 'C': case 'c': return 'G';// 'C' | 'c' => 'G',
    case 'G': case 'g': return 'C';// 'G' | 'g' => 'C',
    case 'T': case 't': return 'A';// 'T' | 't' => 'A',
    case 'U': case 'u': return 'A';// 'U' | 'u' => 'A',
    case 'M': case 'm': return 'K';// 'M' | 'm' => 'K',
    case 'R': case 'r': return 'Y';// 'R' | 'r' => 'Y',
    case 'W': case 'w': return 'W';// 'W' | 'w' => 'W',
    case 'S': case 's': return 'S';// 'S' | 's' => 'S',
    case 'Y': case 'y': return 'R';// 'Y' | 'y' => 'R',
    case 'K': case 'k': return 'M';// 'K' | 'k' => 'M',
    case 'V': case 'v': return 'B';// 'V' | 'v' => 'B',
    case 'H': case 'h': return 'D';// 'H' | 'h' => 'D',
    case 'D': case 'd': return 'H';// 'D' | 'd' => 'H',
    case 'B': case 'b': return 'V';// 'B' | 'b' => 'V',
    case 'N': case 'n': return 'N';// 'N' | 'n' => 'N',
    default: return 0;
  }
}

constexpr auto map = ([] {
  constexpr auto max = std::numeric_limits<uint8_t>::max();
  std::array<uint16_t, max * max> map{};
  for(size_t it = 0; it < map.size(); ++it) {
    uint8_t hi = (it >> 8), lo = it;
    map[it] = (swmap(lo) << 8) | (swmap(hi));
  }
  return map;
})();

constexpr auto map256 = ([] {
  constexpr auto max = std::numeric_limits<uint8_t>::max();
  std::array<uint8_t, max> map{};
  for(size_t it = 0; it < max; ++it)
    map[it] = swmap(it);
  return map;
})();

Здесь ничего интересно - это одна и двух-байтная таблица замены.

GODBOLT

Следствия

• Первое. Я уже не раз говорил, что эти бенчмарки говно и результаты там мусор. Какое-то отребье в комментах мне кукарекало, что всё не так. Всё это неправда и решения там не говно. Это решение минимум в 2 раза быстрее, к тому же оно однопоточное. Но об этом позже.
• Второе. Многопоточность. Очевидно, что здесь можно увидеть то, как бездарное раст-отребье увидев новый трюк и либу - побежала везде пихать дерьмо. Но отребье всегда будет отребьем. В следующей части я запилю либо многопоточность, либо векторизацию. Но нужно понимать, что халявная многопоточность покупается за память. Нужно весь файл читать в память. Но интересней здесь лучше, а это время. Но всё это говно.
  Поэтому, скорее всего, вторая часть будет про то, как бы это выглядело в ситуации с нормальным форматом данных. И уже в рамках неё будет ясно - почему всё это мусор, который ничего не стоит. Матчасть разберу во второй части.

Ах да, C++ версия из топа - выдаёт неверные результаты в определённых кейсах. Я просрал время на поиски проблем у себя, которых не было.