Почему так?
От: TailWind  
Дата: 12.09.21 18:35
Оценка:
Читаю файл
Последовательно
Для каждого чтения выделяю буфер размера Buf_Size с помощью vector<UCHAR> vbuf(Buf_Size);

Закомментировал чтение файла
Оставил только выделение памяти

И удивился что, при размере буфера 0x80000 стало дольше работать
Почему?

Если заменяю vector на:
void *buf = malloc(Buf_Size); free(buf);
работает моментально
Почему?

vector каждый UCHAR прописывает нулём в цикле?


File_Size 0x450000000

Buf_Size 0x8000      Time: 5969 ms
Buf_Size 0x10000     Time: 5937 ms
Buf_Size 0x20000     Time: 5907 ms
Buf_Size 0x40000     Time: 5890 ms

Buf_Size 0x80000     Time: 8766 ms <<<<<<<<<<
Buf_Size 0x100000    Time: 8703 ms
Buf_Size 0x200000    Time: 8578 ms
Buf_Size 0x400000    Time: 8594 ms
Buf_Size 0x800000    Time: 8609 ms
Buf_Size 0x1000000   Time: 8672 ms
Buf_Size 0x2000000   Time: 8672 ms
Buf_Size 0x4000000   Time: 8656 ms
Buf_Size 0x8000000   Time: 8641 ms
Buf_Size 0x10000000  Time: 8593 ms
Buf_Size 0x20000000  Time: 8688 ms
Buf_Size 0x40000000  Time: 8906 ms


Код:

INT64 File_Size = 0x450000000;
//
Log->printf(L"File_Size 0x%I64x\n\n", File_Size);
//
for (ULONG Buf_Size = 0x8000; ; Buf_Size*=2)
{
  Log->printf(L"Buf_Size 0x%-8x  ", Buf_Size);
  //
  TMFS_Win32_Timer Timer;
  //
  for (INT64 p=0; p<File_Size; p+=Buf_Size)
  {
    vector<UCHAR> vbuf(Buf_Size);
    //
    //void *buf = malloc(Buf_Size);  if (buf == NULL) throw TMFS_Exception(L"malloc fail");  free(buf);
    //
    //fr->Read(&vbuf[0], Buf_Size);
  }
  //
  Timer.Report(Log);
}
Re: Почему так?
От: Homunculus Удмуртия  
Дата: 12.09.21 18:46
Оценка:
Здравствуйте, TailWind, Вы писали:

А почему аллоцируешь во внутреннем цикле? Можно ж в один буфер много раз читать. Зачем заново аллоцировать каждый раз?
Re[2]: Почему так?
От: TailWind  
Дата: 12.09.21 19:02
Оценка:
H>А почему аллоцируешь во внутреннем цикле? Можно ж в один буфер много раз читать. Зачем заново аллоцировать каждый раз?

Это упрощение более сложной программы для тестов
Отредактировано 13.09.2021 4:37 TailWind . Предыдущая версия . Еще …
Отредактировано 12.09.2021 21:22 TailWind . Предыдущая версия .
Re: Почему так?
От: Videoman Россия https://hts.tv/
Дата: 12.09.21 21:46
Оценка:
Здравствуйте, TailWind, Вы писали:

TW>vector каждый UCHAR прописывает нулём в цикле?


Да, зануляет каждый элемент. Т.е. вектор это не только malloc.
http://www.gravatar.com/avatar/60560936caa07b944d4c3cecf1c06cc5?s=80&d=identicon
Re: Почему так?
От: watchmaker  
Дата: 12.09.21 23:11
Оценка: 20 (3)
Здравствуйте, TailWind, Вы писали:

TW>Для каждого чтения выделяю буфер размера Buf_Size с помощью vector<UCHAR> vbuf(Buf_Size);

TW>И удивился что, при размере буфера 0x80000 стало дольше работать
TW>Почему?

Для больших размеров буфера может меняется поведение в двух местах:
* OC может по разному читать файл (изменить политику read-ahead, например);
* Аллокатор может перестать управлять памятью самостоятельно, а просто передавать запросы ОС (вызывая mmap напрямую с требуемым размером).

Первое не про память, а вот второе напрямую влияет на скорость выделения и освобождения памяти. Если раньше аллокатор просто менял бит занятости у какого-то элемента в списке блоков да поддерживал какую-то простую (или не очень) структуру для поиска этих блоков, то теперь это честный поход в ядро ОС.
И так делают все популярные аллокаторы (кстати, с каким ты тестируешь?). Ибо выигрыша от собственного управления большими блоками не выходит: короткоживущие большие блоки не считаются типичным сценарием — в хорошей программе их либо мало, либо живут они долго. Но это же значит, что выделение и освобождение большого блока в цикле для аллокаторов всегда будет идти по дорогой ветке.


TW>Если заменяю vector на:

TW>void *buf = malloc(Buf_Size); free(buf);
TW>работает моментально
TW>Почему?

Вообще говоря, функции выделения и освобождения памяти не считаются в стандарте как имеющие непосредственно наблюдаемое поведение. Хотя все знают, что они под капотом вызывают системные вызовы (вроде mmap), которые, если вызывать их напрямую, однозначно имеют наблюдаемое поведение.
Но это сделано специально и означает, что компилятор вправе изменять место выделение памяти или вообще убирать его, если это не изменит наблюдаемое поведение другого кода.

Что компиляторы постоянно и делают: https://godbolt.org/z/9jse3Era3
Как видно, пару free(malloc(...)) компилятор тут же удаляет целиком. Отсюда и быстрая работа.
Неиспользуемый std::vector<char>(n, '\0') или занулённый результат malloc компилятор также может удалить (оставив бросание исключения, в случае недопустимого размера, например).
Но это получается у него не всегда: обычно у него не получается разглядеть через шаблоны замысел кода (что это всего-лишь временный буфер, к которому нет обращений из других мест или потоков), либо для этого нужно либо выкручивать уровень оптимизации. (но иногда получается: https://godbolt.org/z/7cxe6zYob)




TW>vector каждый UCHAR прописывает нулём в цикле?


Да.
Поэтому в популярных реализациях STL (и в стороннем коде, реализующем всякие string-like или vector-like структуры данных) есть различные расширения для сценария, когда нужно выделить память в контейнере, в которую дальше будет идти запись, и которую поэтому можно предварительно не занулять (примеры libc++,catboost,abseil,protobuf).

Вероятно, в каком-то виде их даже узаконят в стандарте языка: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1072r5.html Но, как видно, многие не ждут и пользуются этими расширениями уже сейчас.
Отредактировано 13.09.2021 9:14 watchmaker . Предыдущая версия .
Re[2]: Почему так?
От: TailWind  
Дата: 13.09.21 17:06
Оценка:
W>И так делают все популярные аллокаторы (кстати, с каким ты тестируешь?)
Я его специально не указывал
Значит тот что по умолчнию в STL

Сейчас вынес выделение памяти из цикла
Оставил только чтение

Тестирую на Window 7
На заднем плане запущен Хром, смотрю Youtube

Так вот при втором проходе видео останавливается. Хром зависает. Диски начинают бешено шуршать головками

Не знаете почему так?

Не важно какой размер буфера 0x4000 или 0x100000
Размер файла 16 ГБ

Причём если тесты запускать не из одного exe
А для каждого теста запускать exe заново, то такой проблемы нет (вроде)
Отредактировано 13.09.2021 21:24 TailWind . Предыдущая версия . Еще …
Отредактировано 13.09.2021 17:15 TailWind . Предыдущая версия .
Отредактировано 13.09.2021 17:07 TailWind . Предыдущая версия .
Re[3]: Почему так?
От: watchmaker  
Дата: 13.09.21 17:38
Оценка:
Здравствуйте, TailWind, Вы писали:

W>>И так делают все популярные аллокаторы (кстати, с каким ты тестируешь?)

TW>Я его специально не указывал
TW>Значит тот что по умолчнию в STL

Эти аллокаторы — не часть STL или С++. Но, конечно, C++ использует их для выделения и освобождения памяти. Именно они в конечном итоге делают реальную работу, когда выделяется память через malloc или new[]. И да, в разных сценариях они имеют существенно разную эффективность.
Re[2]: Почему так?
От: TailWind  
Дата: 13.09.21 17:59
Оценка:
W>* OC может по разному читать файл (изменить политику read-ahead, например);

Я до этого на Win_XP тестировал

И там чтение с буфером 0x4000 занимало 156 секунд
Чтение с буфером 0x100000 занимало 474 секунды (в 3 раза дольше)

Что вводит меня в полное недоумение
Я всегда считал, что чтение более большим буфером должно быть быстрее

Оказалось что если в CreateFile добавить флаг FILE_FLAG_RANDOM_ACCESS, с любым размером буфера работает одинаково (156с)
Re[2]: Почему так?
От: Mr.Delphist  
Дата: 14.09.21 09:23
Оценка:
Здравствуйте, watchmaker, Вы писали:

W>Но это получается у него не всегда: обычно у него не получается разглядеть через шаблоны замысел кода (что это всего-лишь временный буфер, к которому нет обращений из других мест или потоков), либо для этого нужно либо выкручивать уровень оптимизации. (но иногда получается: https://godbolt.org/z/7cxe6zYob)


Кстати, интересный момент. Я как-то верил в propagation силами компилятора — а оно вон как, Михалыч.
Re: Почему так?
От: Maniacal Россия  
Дата: 16.09.21 08:58
Оценка: 1 (1)
Здравствуйте, TailWind, Вы писали:

TW>
TW>File_Size 0x450000000

TW>Buf_Size 0x8000      Time: 5969 ms
TW>Buf_Size 0x10000     Time: 5937 ms
TW>Buf_Size 0x20000     Time: 5907 ms
TW>Buf_Size 0x40000     Time: 5890 ms

TW>Buf_Size 0x80000     Time: 8766 ms <<<<<<<<<<
TW>Buf_Size 0x100000    Time: 8703 ms
TW>Buf_Size 0x200000    Time: 8578 ms
TW>Buf_Size 0x400000    Time: 8594 ms
TW>Buf_Size 0x800000    Time: 8609 ms
TW>Buf_Size 0x1000000   Time: 8672 ms
TW>Buf_Size 0x2000000   Time: 8672 ms
TW>Buf_Size 0x4000000   Time: 8656 ms
TW>Buf_Size 0x8000000   Time: 8641 ms
TW>Buf_Size 0x10000000  Time: 8593 ms
TW>Buf_Size 0x20000000  Time: 8688 ms
TW>Buf_Size 0x40000000  Time: 8906 ms
TW>


Если поставить более короткий шаг и начать с меньшего размера буфера, то ещё интереснее результат.
Buf_Size 0x200       Time: 2110ms
Buf_Size 0x400       Time: 1140ms
Buf_Size 0x800       Time: 625ms
Buf_Size 0x1000      Time: 360ms
Buf_Size 0x2000      Time: 250ms
Buf_Size 0x4000      Time: 234ms
Buf_Size 0x8000      Time: 266ms
Buf_Size 0x10000     Time: 203ms
Buf_Size 0x20000     Time: 187ms
Buf_Size 0x40000     Time: 203ms
Buf_Size 0x80000     Time: 188ms
Buf_Size 0x100000    Time: 2406ms
Buf_Size 0x200000    Time: 2468ms
Buf_Size 0x400000    Time: 2375ms
Buf_Size 0x800000    Time: 2328ms
Buf_Size 0x1000000   Time: 2266ms
Buf_Size 0x2000000   Time: 2234ms
Buf_Size 0x4000000   Time: 2219ms
Buf_Size 0x8000000   Time: 2187ms
Buf_Size 0x10000000  Time: 2219ms
Buf_Size 0x20000000  Time: 2265ms
Buf_Size 0x40000000  Time: 2344ms
Buf_Size 0x80000000  Time: 2375ms


Думаю, прямая зависимость от размера кэша процессора. Вот у меня томозить начало с 0x100000, а не с 0x80000.



Посмотрел майкрософтовскую реализацию std::vector, интересная, конечно. Даже под пустой вектор выделяется буфер 16 байт (на это я уже натыкался, когда нечаянно прочитал *begin() из пустого вектора и не получил access violation). При выделении любого буфера дополнительно к его размеру прибавляется (2 * sizeof(void*) + 31) (31 это размер внутреннего выравнивания — 1, судя по названию _BIG_ALLOCATION_ALIGNMENT). Указатель для пользовательского буфера смещается на этот размер, в пользовательский указатель -1 записывается указатель на начало выделенного буфера, в пользовательский указатель -2 записывается число 0xFAFAFAFAFAFAFAFA, потом в деструкторе в дебажном коде проверяется на то, не удаляем ли мы выравненный кусок памяти на невыравненно выделенном. И для блоков больше 4Кб (размер страницы памяти, как я понимаю) применяется другой алгоритм аллокации, гораздо сложнее. В суть алгоритма не стал вникать. Потому в эксперименте с размера ~0x1000 всё ускоряется.

Кстати, с malloc + free эффект такой же (сначала тормозит, потом ускоряется).
Re[2]: Почему так?
От: TailWind  
Дата: 16.09.21 17:03
Оценка:
Здравствуйте, Maniacal

Тоже стало интересно

Сделал в цикле чтение файла всегда по адресу 0
Чтобы он закешировался и не вносил погрешность измерений
Но тоже самое количество раз, как если бы читал файл целиком
Теперь у меня malloc компилятор не убирает, и можно сделать замеры

Получается vector проигрывает malloc

vector снаружи цикла:

Buf_Size 0x200     Time: 5656 ms
Buf_Size 0x400     Time: 2907 ms
Buf_Size 0x800     Time: 1484 ms
Buf_Size 0x1000    Time: 781 ms
Buf_Size 0x2000    Time: 453 ms
Buf_Size 0x4000    Time: 297 ms
Buf_Size 0x8000    Time: 313 ms
Buf_Size 0x10000   Time: 250 ms
Buf_Size 0x20000   Time: 250 ms
Buf_Size 0x40000   Time: 234 ms
Buf_Size 0x80000   Time: 203 ms
Buf_Size 0x100000  Time: 219 ms
Buf_Size 0x200000  Time: 219 ms
Buf_Size 0x400000  Time: 265 ms
Buf_Size 0x800000  Time: 500 ms
Buf_Size 0x1000000  Time: 672 ms
Buf_Size 0x2000000  Time: 703 ms
Buf_Size 0x4000000  Time: 719 ms
Buf_Size 0x8000000  Time: 766 ms

malloc внутри цикла:

Buf_Size 0x200     Time: 6109 ms
Buf_Size 0x400     Time: 3281 ms
Buf_Size 0x800     Time: 1688 ms
Buf_Size 0x1000    Time: 890 ms
Buf_Size 0x2000    Time: 500 ms
Buf_Size 0x4000    Time: 328 ms
Buf_Size 0x8000    Time: 329 ms
Buf_Size 0x10000   Time: 265 ms
Buf_Size 0x20000   Time: 235 ms
Buf_Size 0x40000   Time: 250 ms
Buf_Size 0x80000   Time: 1078 ms
Buf_Size 0x100000  Time: 1047 ms
Buf_Size 0x200000  Time: 1093 ms
Buf_Size 0x400000  Time: 1157 ms
Buf_Size 0x800000  Time: 1390 ms
Buf_Size 0x1000000  Time: 1531 ms
Buf_Size 0x2000000  Time: 1563 ms
Buf_Size 0x4000000  Time: 1547 ms
Buf_Size 0x8000000  Time: 1531 ms

vector внутри цикла:

Buf_Size 0x200     Time: 8234 ms
Buf_Size 0x400     Time: 5188 ms
Buf_Size 0x800     Time: 3391 ms
Buf_Size 0x1000    Time: 2500 ms
Buf_Size 0x2000    Time: 2078 ms
Buf_Size 0x4000    Time: 1875 ms
Buf_Size 0x8000    Time: 1875 ms
Buf_Size 0x10000   Time: 1828 ms
Buf_Size 0x20000   Time: 1781 ms
Buf_Size 0x40000   Time: 1859 ms
Buf_Size 0x80000   Time: 2500 ms
Buf_Size 0x100000  Time: 2516 ms
Buf_Size 0x200000  Time: 2516 ms
Buf_Size 0x400000  Time: 2781 ms
Buf_Size 0x800000  Time: 3000 ms
Buf_Size 0x1000000  Time: 3094 ms
Buf_Size 0x2000000  Time: 3062 ms
Buf_Size 0x4000000  Time: 3000 ms
Buf_Size 0x8000000  Time: 2969 ms
Отредактировано 16.09.2021 17:06 TailWind . Предыдущая версия . Еще …
Отредактировано 16.09.2021 17:05 TailWind . Предыдущая версия .
Re[3]: Почему так?
От: Maniacal Россия  
Дата: 16.09.21 19:43
Оценка:
Здравствуйте, TailWind, Вы писали:

TW>Здравствуйте, Maniacal


TW>Тоже стало интересно


TW>Теперь у меня malloc компилятор не убирает, и можно сделать замеры

Главное free не забывать.

TW>Получается vector проигрывает malloc


Конечно, вектор проигрывает malloc. Вектор это обёртка над new, которая обёртка над malloc. Я лишь писал, что тенденция тормозить и ускоряться в зависимости от размера выделяемого блока в конкретном примере тесно коррелирует между ними. Оба сначала тормозят, потом разгоняются, а потом снова резко останавливаются и уже по плавно убывающей.
В дебаге, если поставить совсем маленький шаг (даже не умножение, а сложение), то видно, как скорость скачет в зависимости от того, произошла аллокация очередной страницы памяти или нескольких за шаг или нет.
Re[4]: Почему так?
От: TailWind  
Дата: 16.09.21 23:15
Оценка:
M>Конечно, вектор проигрывает malloc

В 5 раз?

Я всегда использовал vector, для выделения блока памяти, чтобы не париться
А тут вот оно как

Странно, что в STL нет объектов для этого
Отредактировано 16.09.2021 23:17 TailWind . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.