LINUX.ORG.RU

не пойму, что делает код

 , ,


1

1
int *p = (int*)malloc(MAX_BLOCK_SIZE);
int tmp = 0;
for (int b = MIN_BLOCK_SIZE; b < MAX_BLOCK_SIZE; b += STEP) {
    for (int c = 0; c <= b; c += sizeof(int)) {
        tmp += *(int*)((int)p + c);
        *(int*)((int)p + c) = tmp;
    }
}

Да, я пришел на лор со своими лабами. Нет, я не хочу, чтоб анонимус, который всем говорит, что им не быть программистами, делал мои лабы за меня. Я хочу разобраться.

MAX/MIN block size и step - это предполагаемые «размеры блока» кэша L1. Это как бы пример кода из руководства от лабы. Там написано «Для выполнения лабораторной работы вам нужно время выполнения одной итерации внутреннего цикла в зависимости от размера блока, который обрабатывается».

То есть что я получаю? На k-й итерации: размер блока min+((k-1)*step), я произвожу соответствующее количество операций записи и чтения (дальше - допустим, только записи), получаю какой-то набор чисел.

К сожалению, я не понимаю, зачем это делается. Задание такое: «исследовать скорость обработки элементов блока памяти при выполнении операций записи». При проходе во внутреннем цикле я почему-то заполняю какой-то кусок массива с каким-то шагом какими-то числами, а во внешнем цикле - просто увеличивается обрабатываемый кусок массива. Как это может продемонстрировать производительность кэша?

★★★★

На определённом размере массива он перестанет помещаться в кеш?

PolarFox ★★★★★ ()

Длинный и развёрнутый ответ можно получить в книге «What every programmer should know about memory».

Короткий ответ: пока все твои данные влезают в кэш проца циклы будут быстро крутиться. А вот если ты вылазишь за пределы кэша то процу придётся за данными лезть в оперативу что убъёт всю производительность. Там, правда, там куча нюансов.

PS код смотрел одним глазом, может что не распарсил

true_admin ★★★★★ ()

*(int*)((int)p + c);

А почему не

*(p+c)
?

И что с этим кодом будет на x86-64?

i-rinat ★★★★★ ()
Ответ на: комментарий от i-rinat

хз, я переписываю его слега по-своему, и все эти вещи автоматическ заменяю. еще использую uint8_t, чтоб писать чаще, это на что-то влияет?

cdshines ★★★★ ()
Ответ на: комментарий от cdshines

это на что-то влияет?

Если ты про uint8_t, то отличий на x86 быть не должно. Если ты про 64-битный код, то в таких прямых преобразованиях баг, ибо указатель 64 бита, а int — 32. Некоторые аллокаторы на x86-64 любят выделять кучу вверху, и такое приведение типов приведёт к записи мимо выделенного массива.

i-rinat ★★★★★ ()
Ответ на: комментарий от true_admin

Так весь массив имеет размер, равный размеру кэша. То есть, у меня, в том, что я пишу?

define L1_DATA_SIZE      (32 * 1024)
//...
uint8_t *array = (uint8_t*) malloc(L1_DATA_SIZE);
Может ли весь массив попасть в кэш?

И да, у меня

cdshines@v3700:~|⇒  cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64
Это размер блока?

cdshines ★★★★ ()
Ответ на: комментарий от cdshines

А как лучше?

*(p+c) или p[c]

Если к указателю прибавить число n, то получится указатель на n-й элемент типа указателя. То есть если p — указатель на int (и sizeof(int) == 4) и p == 0x1000, то p+1 == 0x1004, а p+2 == 0x1008.

Ещё в цикле нужно будет увеличивать c на единицу, а не на sizeof(int).

i-rinat ★★★★★ ()
Ответ на: комментарий от cdshines

Может ли весь массив попасть в кэш?

Может. А может и не попасть. У кэша есть ещё параметр «ассоциативность». И связанный с этим эффект алиасинга. Вернее, ассоциативность — это попытка снизить влияние алиасинга.

i-rinat ★★★★★ ()
Ответ на: комментарий от i-rinat

*(p+c) или p[c]

В коде вроде бы це это смещение в байтах, так что неплохо бы привести пэ хотя бы к void *.

anonymous ()
Ответ на: комментарий от anonymous

В коде вроде бы це это смещение в байтах

Я последним предложением это пояснил: «нужно будет увеличивать c на единицу, а не на sizeof(int).»

так что неплохо бы привести пэ хотя бы к void *.

Плохой совет, я считаю. Разве это не ошибка — пытаться индексировать указатель типа void* ?

i-rinat ★★★★★ ()

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

anonymous ()
Ответ на: комментарий от cdshines

А если объявить массив uint64_t* ?

Зачем? Не понимаю, чего ты пытаешься этим добиться.

i-rinat ★★★★★ ()
Ответ на: комментарий от i-rinat

нужно будет увеличивать c на единицу, а не на sizeof(int)

Если я ничо не путаю, то нужно будет увеличивать це на четверть (восьмую), что проблематично сделать в системе с целочисленными указателями.

Пэ можно привести к char *, если религия не позволяет прибавлять к void *.

anonymous ()
Ответ на: комментарий от i-rinat

Оё, прости, и правда там +=sizeof(int) же.

anonymous ()
Ответ на: комментарий от i-rinat

Я сделал, в общем, и так и вышло. Если брать uint8_t* (мне так проще считать) при моем кэше 32КБ, т.е. выделять (uint8_t*)malloc(32 * 1024* 2) - в 2 раза больше, и брать с интервалом по 10% от 10% до 200% (20 грубых замеров), то выходит, что в первых десяти среднее арифметическое времени доступа в ~2 раза ниже. (странно, я ожидал, что из-за того, что время доступа к памяти на порядки больше, там будут бОльшие числа).

Попутный вопрос: вот такое: http://ideone.com/zQ6hvW, как видно, работает нормально, а у меня - сегфолт. От чего может зависеть?

cdshines ★★★★ ()
Ответ на: комментарий от cdshines

32 кБайт это кеш первого уровня? А кеш второго уровня есть?

mky ★★★★★ ()
Ответ на: комментарий от mky
cdshines@v3700:~|⇒  lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
Thread(s) per core:    2
Core(s) per socket:    2
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 37
Stepping:              5
CPU MHz:               1197.000
BogoMIPS:              4787.62
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              3072K
NUMA node0 CPU(s):     0-3

АПВС?

cdshines ★★★★ ()
Ответ на: комментарий от i-rinat

А почему не

Скорее всего это фрагмент функции, где аргумент void * p.

Я вообще подозреваю что это код для микро (стиль похож).

cdshines Ну и да - похоже на вычисление «контрольной суммы» блока для тех, кто понимает это буквально

ziemin ★★ ()
Ответ на: комментарий от cdshines

АПВС

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

Код по ссылке мне не понятен, может в C++11 malloc() выделяет память как-то по другому, а в обычном Cи malloc выделит ″1024 * 1024″ байта, а обращение к ″lp[s-1]″ подразумевает, что нужно выделять ″s * sizeof(uint64_t)″.

mky ★★★★★ ()
Ответ на: комментарий от cdshines

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

Чего-то я пивандрия перебрал и до этого не дочитал. Смысл кэша в том, что 1) он принимает запись от процессора, но физически пишет при простоях или переполнении; 2) при чтении (например слова) он читает не только то, что нужно, а целый блок - следующие обращения обслужатся из кэша. В твоём примере и чтение и запись. Где-то должен быть замер времени. Ты его делишь на кол-во элементов вычисляя среднее время.

ИМХО.

ziemin ★★ ()
Ответ на: комментарий от cdshines

Попутный вопрос: вот такое: http://ideone.com/zQ6hvW, как видно, работает нормально, а у меня - сегфолт. От чего может зависеть?

Я сюда код скопирую:

#include <iostream>
#include <cstddef>
int main() {
  unsigned long long s = 1024 * 1024;
  uint8_t *p = (uint8_t*)malloc(s);
  p[s-1] = 100;
  std::cout << (int)p[s-1] << std::endl;
  uint64_t *lp = (uint64_t*)malloc(s);
  lp[s-1] = 100;
  std::cout << lp[s-1] << std::endl;
  return 0;
}

uint64_t *lp = (uint64_t*)malloc(s);

Тут ты выделяешь блок памяти длиной в 1024*1024 байт

lp[s-1] = 100;

А тут пишешь в 8242879-й байт. Очевидно, выход за границы массива.

i-rinat ★★★★★ ()
Ответ на: комментарий от ziemin

Какое у тебя задание? Глянул на первое - там только про чтение. Следовательно присвоение тебе нужно исключить (типа на сообразительность )

ziemin ★★ ()

i-rinat, mky, true_admin Я тут практически случайно запустил еще раз этот код и, что странно, в отличии от разультатов, которые были раньше, теперь время доступа постоянно как для кэша 2 уровня. Вот код:

http://ideone.com/uAyGrE

На ideone чуднЫе часы, поэтому попробуйте у себя. У меня получаются нормальные числа на ноуте, но все равно. Раньше среднее арифметическок было ~3 ДО тех пор, пока все влазило в Л1-кэш, и ~6 ПОСЛЕ, а теперь - и до, и после - примерно одинаковые числа.

От чего может быть такое изменение? Код тот же самый. Ядро, правда, новое, но это же не могло так повлиять? Пробовал каждый раз выделять заново массив переменного размера - результат тот же.

И да, иногда вообще время в последней четверти замеров опускается до 2-3, но это совсем редко.

Я опять где-то сделал глупую ошибку?

true_admin, отдельное спасибо за «What every programmer should know about memory», полезно, хоть и чрезвычайно дотошно, по-моему :)

cdshines ★★★★ ()
Ответ на: комментарий от cdshines

Не могу сказать, по какой причине у вас изменились результаты, может быть ядро переключило режим работы кеша L1 с write-back на write-through, если это возможно. Я плохо представляю особенности L1 кеша современных интеловских процессоров. Может вам лучше изучать соотношения скорости для L2/L3 или L3/память.

С точки зрения изучения производительности кеша ваш код неудачен.

Во-первых, вы работаете байтами. При промахе в кеш загружается/выгружается целая строка (не скажу сколько), но точно не один байт. В результате, после одного промаха у вас идёт серия удачных операций с кешем. Поэтому правильнее использовать 64-битное число.

Во-вторых, в момент начала цикла ″p[c] = c″ выделенной malloc() области памяти не будет в L1-кеше и, скорее всего, не будет в L2-кеше, так как до этого был вызов ″chrono::high_resolution_clock″, который обрашался к ядру — чтение-запись различных областей памяти чистит кеш. Я бы рекомендовал делать цикл ″p[c] = c″ 10 раз — обернуть его его другим циклом.

Ещё можно попробовать использовать счётчик тактов (ассемблерная команда rdtsc), а не ″chrono::high_resolution_clock″, чтобы точнее измерять длительность цикла.

И попробуйте перевести ваши результаты в привычные МБайт/с, чтобы можно было посмотрев различные тесты в интернете близких процессоров и сравнить. Возможно, что у вас компилятор создаёт такой код, который всё время работает мимо кеша.

mky ★★★★★ ()
Ответ на: комментарий от cdshines

mky дело говорит.

Я запустил, у меня получается примерно 9 нс на цикл. Если считать, что частота 1.6 ГГц, получается примерно 14 тактов на цикл. Каждый цикл записывается один байт. С таким подходом ты упираешься в число инструкций в секунду, а не производительность кеша или памяти. Если я убираю строчку p[c]=c, остаётся 4.5 нс. То есть накладные расходы огромны.

Записывай большими кусками, разверни цикл. Убедись, что компилятор не хитрит (поможет objdump -d a.out).

i-rinat ★★★★★ ()
Ответ на: комментарий от cdshines

Вот есть такой код:

    	for(a = 0; a < blk/sizeof(UTL); a += 64) {
	    mem[a] = b;    mem[a+1] = b;  mem[a+2] = b;  mem[a+3] = b;
	    mem[a+4] = b;  mem[a+5] = b;  mem[a+6] = b;  mem[a+7] = b;
	    mem[a+8] = b;  mem[a+9] = b;  mem[a+10] = b; mem[a+11] = b;
	    mem[a+12] = b; mem[a+13] = b; mem[a+14] = b; mem[a+15] = b;
	    mem[a+16] = b; mem[a+17] = b; mem[a+18] = b; mem[a+19] = b;
	    mem[a+20] = b; mem[a+21] = b; mem[a+22] = b; mem[a+23] = b;
	    mem[a+24] = b; mem[a+25] = b; mem[a+26] = b; mem[a+27] = b;
	    mem[a+28] = b; mem[a+29] = b; mem[a+30] = b; mem[a+31] = b;
	    mem[a+32] = b; mem[a+33] = b; mem[a+34] = b; mem[a+35] = b;
	    mem[a+36] = b; mem[a+37] = b; mem[a+38] = b; mem[a+39] = b;
	    mem[a+40] = b; mem[a+41] = b; mem[a+42] = b; mem[a+43] = b;
	    mem[a+44] = b; mem[a+45] = b; mem[a+46] = b; mem[a+47] = b;
	    mem[a+48] = b; mem[a+49] = b; mem[a+50] = b; mem[a+51] = b;
	    mem[a+52] = b; mem[a+53] = b; mem[a+54] = b; mem[a+55] = b;
	    mem[a+56] = b; mem[a+57] = b; mem[a+58] = b; mem[a+59] = b;
	    mem[a+60] = b; mem[a+61] = b; mem[a+62] = b; mem[a+63] = b;
	}

Это из исходника ramspeed http://www.alasir.com/software/ramspeed/ramspeed-2.6.0.tar.gz

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

anonymous ()
Ответ на: комментарий от cdshines

отдельное спасибо за «What every programmer should know about memory

ты не поверишь, в твоём задании оно есть в списке литературы O_O

true_admin ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.