Скорость выполнения программы C
Различие может быть проиллюстрировано следующим:
std::cout << std::endl;
эквивалентно [1 114]
std::cout << '\n' << std::flush;
Так,
- Использование
std::endl, Если Вы хотите вызвать непосредственный сброс к выводу. - Использование
\n, если Вы волнуетесь по поводу производительности (который является, вероятно, не случаем, если Вы используете<<оператор).
я использую \n на большинстве строк.
Тогда использование std::endl в конце абзаца (но это - просто привычка и не обычно необходимое).
Вопреки другим требованиям, \n символ отображается на корректном конце платформы последовательности строки, только если поток идет в файл (std::cin и std::cout являющийся особенным, но все еще файлы (или подобный файлу)).
5 ответов
Старший порядок строк в сравнении с порядком старшего столбца.
Прежде всего напомним, что все многомерные массивы представлены в памяти как непрерывный блок памяти. Таким образом, многомерный массив A (m, n) может быть представлен в памяти как
a00 a01 a02 ... a0n a10 a11 a12 ... a1n a20 ... amn
В первом цикле вы проходите через блок памяти последовательно. Таким образом, вы проходите через массив, обходя элементы в следующем порядке
a00 a01 a02 ... a0n a10 a11 a12 ... a1n a20 ... amn
1 2 3 n n+1 n+2 n+3 ... 2n 2n+1 mn
Во втором цикле вы пропускаете память и проходите через массив, обходя элементы в следующем порядке
a00 a10 a20 ... am0 a01 a11 a21 ... am1 a02 ... amn
или, возможно, более ясно,
a00 a01 a02 ... a10 a11 a12 ... a20 ... amn
1 m+1 2m+1 2 m+2 2m+2 3 mn
] Все эти пропуски действительно причиняют вам боль, потому что вы не получаете преимуществ от кэширования. При последовательном прохождении массива соседние элементы загружаются в кеш. Когда вы пропускаете массив,
Из-за оптимизации архитектуры аппаратного обеспечения. Часть A выполняет операции с последовательными адресами памяти, что позволяет аппаратному обеспечению существенно ускорить обработку вычислений. Часть B, по сути, постоянно перескакивает в памяти, что сводит на нет многие аппаратные оптимизации.
Ключевой концепцией для этого конкретного случая является кэш процессора .
Это связано с тем, как распределяется память массива и как она загружается в кеш и к ней осуществляется доступ: в версии A при доступе к ячейке массива соседи загружаются с он помещается в кеш, а затем код немедленно обращается к этим соседям. В версии B осуществляется доступ к одной ячейке (и ее соседи загружаются в кеш), но следующий доступ находится далеко, в следующей строке, поэтому была загружена вся строка кеша, но использовалось только одно значение, а другая строка кеша должна заполняться для каждого доступа. Отсюда разница в скорости.
Проблема заключается в том, как ваш массив размещен в памяти.
В памяти компьютера обычно выделяются массивы, например, сначала все столбцы первой строки объединяются, затем второй строки и т. д.
Память вашего компьютера лучше всего рассматривать как длинную полосу байтов - это одномерный массив памяти, а не двухмерный, поэтому многомерные массивы должны быть размещены в описанный способ.
Теперь возникает еще одна проблема: современные процессоры имеют кеши. У них есть несколько кешей, и у них есть так называемые «строки кэша» для кеша первого уровня. Что это значит. Доступ к памяти быстрый, но недостаточно быстрый. Современные процессоры намного быстрее. Таким образом, у них есть встроенные кеши, которые ускоряют работу. Также они больше не обращаются к отдельным ячейкам памяти, но они заполняют одну полную строку кэша за одну выборку. Это тоже для производительности. Но такое поведение дает все преимущества операций, которые обрабатывают данные линейно. Когда вы сначала получаете доступ ко всем столбцам в строке, затем к следующей строке и так далее - вы фактически работаете линейно. Когда вы впервые обрабатываете все первые столбцы всех строк, вы «прыгаете» в памяти. Таким образом, вы всегда принудительно заполняете новую строку кэша, может быть обработано всего несколько байтов, тогда строка кэша, возможно, станет недействительной при следующем переходе ....
Таким образом, основной порядок столбцов плох для современных процессоров. , так как это не работает линейно.
Объявляемый массив размещается в памяти построчно. В основном у вас есть большой блок целых чисел M × N, и C делает небольшую хитрость, чтобы заставить вас поверить, что он прямоугольный. Но на самом деле он плоский.
Поэтому, когда вы выполняете итерацию по строкам (с M в качестве переменной внешнего цикла), вы действительно проходите через память линейно. То, что кеш ЦП обрабатывает очень хорошо.
Однако, когда вы выполняете итерацию с N во внешнем цикле, вы всегда делаете более или менее случайные переходы в памяти (по крайней мере, для оборудования это выглядит так). Вы обращаетесь к первой ячейке, затем перемещаете M целых чисел дальше и делаете то же самое и т. Д. Поскольку ваши страницы в памяти обычно имеют размер около 4 КиБ, это вызывает доступ к другой странице для каждой итерации внутреннего петля.