Невероятно быстрый подсчёт байтов

[sergio_nsk]

В итоге x500 прирост за счёт того, что std::cin заменил на mmap и x1,1 за счёт остального. Причём и первая замена несправедлива: в файле текст 122 127 89 ..., а в решении двоичный файл с байтами. Для справедливости переводчик мог бы показать прирост скорости только от замены std::cin с текстовым файлом на mmap с двоичным файлом

[sena]

оптимизированное решение работает со стандартным вводом

[mOlind]

Вы можете посмотреть условие и проверить свое решение на https://highload.fun/tasks/5 . там бинарные данные идут на вход. Замена std::cin на mmap дает x250 ускорение. А дальше волшебство и танцы с бубном, чтобы приблизиться к лидеру.

[NickDoom]

Мдас… чтобы ассемблер уверенно обходил все эти «умные компиляции», в наше время надо прямо уже конкретно жестить :)

С другой стороны — такого внимания требует 1% кода (но рискующий сожрать 99% времени выполнения). Тут можно и расщедриться. В этом плане ничего не изменилось :)

[sena]

Решение, которое мы представим, работает в 550 раз быстрее следующей тривиальной программы.

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

Если использовать обыкновенный read, то наивная реализация работает всего лишь в 5 раз медленнее оптимизированной. И это, конечно, тоже очень неплохо, но сенсации уже не получится.

#include <unistd.h>
#include <iostream>

int main(int argc, char **argv)
{

uint64_t count = 0;
size_t bufsize = 1024*4*256;
uint8_t buf[bufsize];
while(true) {
  ssize_t nread = read(0, buf, bufsize);
  if(nread <= 0) break;
  for(unsigned ii = 0; ii < nread; ++ii) {
    if (buf[ii] == 127) {
        ++count;
    }
  }
}
std::cout << count << std::endl;
return 0;
}

$ g++   -mavx2 -O3 simddumb.cc -o simddumb
$ time ./simddumb < testf.bin 
53616490

real	0m3,660s
user	0m2,474s
sys	0m1,185s

$ time ./simd < testf.bin 
53616490

real	0m2,150s
user	0m0,500s
sys	0m1,650s

Размер testf.bin 13GB

mmap это конечно уже не совсем наивная реализация, но надо для начала испытать с mmap и прочими оптимизациями, перед нырянием в ассемблер

[WASD1]

Там с подсчётом довольно странная ситуация.

Лучшее решение - 13к "попугаев".

1. Ваше решение - 155к (в 12 раз хуже)
2. То же с mmap - 79к (в 6 раз хуже)
3. Mmap + массив счётчиков + full unroll внутреннего цикла - 58к (в 4.5 раза хуже)
// решение с многопоточностью - предсказуемо ничего не даёт (1CPU в условии).

Надо заметить, что на моём 7800x3d (c AVX2) - последнее решение почти догнало asm-код.

Я подозреваю, что там какие-то артефакты измерений и лучшие решения это абузят (например(не обязательно это) меряют system-time + user-time -- тогда абузом будет: и prefetrch + nanosleep, т.к. nanosleep не попадёт в user/system time и по-сути подкачку данных из памяти в кэш мы не подсчитаем)

[Tsimur_S]

Похоже на челендж highload fizzbuzz с кодгольфа.

[Zara6502]

Зарегистрировался на сервисе, написал "свой" вариант на C#

int count = 0;
using (var stdin = Console.OpenStandardInput())
{
  byte[] buffer = new byte[32768];
  while (stdin.Read(buffer, 0, buffer.Length) > 0)
  {
     for(int c = 0; c < buffer.Length; c++)
         if (buffer[c] == 127) count++;
  }
}
Console.WriteLine(count);

и получил ошибку

Немного поизменял код, позапускал еще три раза и всегда ожидаемое и полученное значения различаются то на 4 то на 65 то на 74 байта.

и как узнать почему насчиталось не столько сколько они ожидают? исходный файл для подсчёта у них, как я понял, всегда разный (что странно) и скачать его нельзя.

у меня локально всё считает верно.

[Deosis]

При последнем чтении буфер может заполниться не до конца, и часть байтов с прошлой итерации будут обработаны ещё раз.

[Zara6502]

ну я балда конечно

int count = 0;
using (var stdin = Console.OpenStandardInput())
{
  byte[] buffer = new byte[32768];
  int bytes = 0;
  while ((bytes = stdin.Read(buffer, 0, buffer.Length)) > 0)
  {
     for(int c = 0; c < bytes; c++)
         if (buffer[c] == 127) count++;
  }
}
Console.WriteLine(count);

всё получилось!

Кстати пообщался с разработчиками в телеге, весьма дружелюбно и позитивно, интересный сайт.

Кстати по решению задачи:

Best score: 13 260 (на C++)

Моё очевидное из текста выше: 204 614 (на C#)

Базовый пример на C++: 8 922 064

То есть добавление буфера для чтения ускорило всё в 43.6 раза.

[voldemar_d]

В ней используется только AVX2, а AVX512 не используется.

А если использовать AVX512, то ещё в разы быстрее станет?

[POPSuL]

Спасибо за интересную ссылочку... Пошевелил мозгами чутка, занял 7е место в лидерборде по гошечке :)