При написании сегодняшнего Codeforces Round #126 и решении задачи A столкнулся с несколько неожиданными поведением. А именно при использовании двумерных массивов размера 2048 x 2048 скорость доступа к данным оказалась на порядок хуже, чем скорость доступа в случае массивов 2048 x 2047 (или 2048 x 2049, или ещё какого-то другого размера) (см. посылки 1829297 и 1830397). Данное поведение оказалось для меня весьма неожиданным (казалось бы наоборот выравнивание данных должно было ускорить доступ). Посему возник вопрос, почему же оно медленее?
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
22:44:18
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
22:44:18
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 18:50:43 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
это кэш.
промахи кэша случаются гораздо чаще если разница между последовательными запросами кратна степени двойки.
где то была классная статья на эту тему... если найду — кину ссылку
upd. http://igoro.com/archive/gallery-of-processor-cache-effects/
Спасибо за ответ и ссылку. Буду знать в будущем про такую фишку.
Еще в Linux бывает какая-то лажа связанная со страницами памяти, если размеры массивов кратны их размеру. Тоже где-то писали по этому поводу ацмщики на русском.
А откуда вообще операционке знать про размер массивов?
Ну да, можно к словам придираться, а можно понять что в случае таких размеров массивов могут быть последовательные запросы к разным страницам виртуальной памяти, что может вызывать например частые страничные прерывания и их выгрузка/загрузка в своп и обратно. Не помню точно причину, но результат — плохое время работы, и связанно это с некими особенностями ядра Linux.
В том виде, в котором Вы сформулировали это утверждение, оно не может быть верно т.к. никто кроме Вашей программы не знает, какого размера массивы. В частности, массив длиной в одну страницу отличим даже на процессорном уровне фактически неотличим от массива чуть большей длины. У автора поста основная особенность — это доступы к адресам на расстоянии степеней двойки, а не массив длины степени двойки.
Да, я дурак. Зато Вы очень стройно, ясно и понятно выражаете свои мысли: "В частности, массив длиной в одну страницу отличим даже на процессорном уровне фактически неотличим от массива чуть большей длины".
Речь не о "размере массива", а о "размерах массива", в частности имеется в виду второе измерение кратное степени двойки, поэтому изменение первого индекса на один приводит к адресу отличающемуся на степень двойки.