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

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

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

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

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

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

А почему не

*(p+c)

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

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

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

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

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

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

А как лучше?

А как лучше?

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

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

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

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

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

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

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

Ну это понятно)

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

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

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

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

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

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

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

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

«для себя»

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

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

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

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

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

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

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

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

АПВС?

А почему не

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

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

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

Не знаю, но похоже, что нет. Вот вся лаба: ftp://pti.kpi.ua/pub/ApxEOM/Lab_5.pdf

АПВС

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

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

А, ясно. Спасибо.

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

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

ИМХО.

Да, я уже сделал: не пойму, что делает код (комментарий)

Попутный вопрос: вот такое: 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, mky, true_admin Я тут практически случайно запустил еще раз этот код и, что странно, в отличии от разультатов, которые были раньше, теперь время доступа постоянно как для кэша 2 уровня. Вот код:

http://ideone.com/uAyGrE

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

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

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

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

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

Не могу сказать, по какой причине у вас изменились результаты, может быть ядро переключило режим работы кеша 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 дело говорит.

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

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

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

    	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

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

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

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