Как влияет кеш на многопоточные приложения

Теоретическая составляющая.

Так сложилось, узким местом во многих компьютерах является интерфейс оперативная память — процессор. Связано это со значительным временем формирования запроса в память и с тем что частота работы памяти ниже частоты процессора. В общем случае на время получения данных из памяти исполнение программы останавливается. Для улучшения ситуации используется специализированная высокоскоростная память – кеш.

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

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

У меня возник вопрос насколько все может быть плохо. Кроме того, интересно было посмотреть как влияет длина данных.


Эксперимент.
Для проверки были написаны 2 многопоточных программы на С++ для двух случаев пересечения рабочих областей:

• Области не пересекаются и находятся в стеке каждой из нитей;
• Рабочая область для нитей общая, представляет собой массив из 1, 4 и 8 байтных слов, общей длиной 1024 байта, каждая из нитей модифицирует свои слова (например только четные или только нечетные).

Рабочих нитей – 2, каждая, меняя свои слова, проходит весь массив и, достигнув границы, возвращается к началу и так далее. Каждая из нитей делает по 100 000 000 изменений.

UPD Спасибо mikhanoid за выявленную опечатку в названии CPU.
Для тестирования использовалась рабочая станция HP xw4600, CPU Core 2 Quad (Q9300), OS Linux Slamd64 12.1, ядро 2.6.24.5, компилятор gcc 4.2.3. В итоге получалась 64-х битная программа, следовательно любая арифметическая операция для слов длиной 1,4 и 8 байт выполнялась за 1 такт.

Время исполнения измерялось командой time(1), и усреднялось по 5-и экспериментам.

Сначала была написана программа, которая просто инкрементирует слово и кладет его обратно, но оказалось что в случае массива на стеке оптимизация -O2 творит что-то непотребное. Поэтому была написана вторая программа, которая делает с данными что-то более сложное.

Результаты.
UPD: Thnx за замечание mt_ и Google Charts за api графиков. Результат в графической форме.
Желающие посмотреть цифры, могут промотать дальше.

По оси Y реальное время исполнения программы в секундах. По оси X разрядность слова (парами).

Программа 1.



Программа 2.



Программа 2 + оптимизация -O2.



Выводы
Можно точно сказать, что в случае заведомо не пересекающихся областей работает быстрее, причем значительно. Оптимизация как-то влияет, но тенденция сохраняется.

А вот зависимость от длины слова как-то мало заметна.

Идея данного опуса навеяна статьей www.ddj.com/architect/208200273.

UPD Попытка перенести в блог Совершенный код, мне кажется что это самое правильное место.

Результаты в табличной форме.
Результаты представлены в секундах.

Программа 1 (общая память).

Длина слова	64	32	8
Реальное время	1,297	1,532	0,846
Время польз. режима	2,461	3,049	1,664

Программа 1 (стек)

Длина слова	64	32	8
Реальное время	0,453	0,431	0,441
Время польз. режима	0,851	0,842	0,866

Программа 2 (общая память).

Длина слова	64	32	8
Реальное время	9,191	9,033	8,921
Время польз. режима	18,365	18,039	17,824

Программа 2 (стек)

Длина слова	64	32	8
Реальное время с	8,432	8,412	8,808
Время польз. Режима с	16,843	16,796	17,548

Программа 2 + оптимизация -O2 (общая память).

Длина слова	64	32	8
Реальное время	4,247	4,380	3,473
Время польз. режима	8,415	8,960	6,781

Программа 2 + оптимизация -O2 (стек)

Длина слова	64	32	8
Реальное время	3,282	3,718	3,308
Время польз. режима	6,550	7,384	5,565

Исходный код.

Программа 1.

#include <sys/types.h>

#include <stdio.h>
#include <stdlib.h>

#include <pthread.h>

#define TBYTES 1024
//
#define TOTAL 2
// определяет тип слова u_int8_t u_int32_t u_int64_t
#define MTYPE u_int8_t
//
#define MAXAR TBYTES/sizeof(MTYPE)
#define DOIT 100000000

MTYPE *array;

pthread_mutex_t mux = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int workers = 2;

// Определяет используется ли общая память
//#define SHARED 1

void*
runner(void* args){
  unsigned int which = *(unsigned int*)args; delete (unsigned int*)args;
  unsigned int index = which;
  MTYPE array1[MAXAR];
  //
  for ( unsigned int i = 0; i < DOIT; ++i){
    if ( index >= MAXAR)
      index = which;
    //
#if defined(SHARED)
    array[index] = array[index] + 1;
#else
    array1[index] = array1[index] + 1;
#endif
    //
    index += TOTAL;
  }
  //
  pthread_mutex_lock(&mux);
  -- workers;
  pthread_mutex_unlock(&mux);
  pthread_cond_broadcast(&cond);
  //
  return 0;
};  

int
main() {
  //
  array = (MTYPE*)calloc(MAXAR, sizeof(MTYPE));
  //
  unsigned int *which;
  pthread_t t1;
  pthread_attr_t attr;
  //
  pthread_attr_init(&attr);
  pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
  //
  which = new unsigned int(0);
  pthread_create(&t1, &attr, runner, (void*)which);
  //
  which = new unsigned int(1);
  pthread_create(&t1, &attr, runner, (void*)which);
  //
  pthread_mutex_lock(&mux);
  while(!pthread_cond_wait(&cond, &mux)){
    if ( !workers)
      break;
  };
  pthread_mutex_unlock(&mux);
  //
  return 0;
};
//  

* This source code was highlighted with Source Code Highlighter.

Программа 2.

#include <sys/types.h>

#include <stdio.h>
#include <stdlib.h>

#include <pthread.h>

#define TBYTES 1024
//
#define TOTAL 2
// определяет тип слова u_int8_t u_int32_t u_int64_t
#define MTYPE u_int64_t
//
#define MAXAR TBYTES/sizeof(MTYPE)
//#define DOIT 100000000 * (sizeof(u_int64_t) / sizeof(MTYPE))
#define DOIT 100000000

MTYPE *array;

pthread_mutex_t mux = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int workers = 2;

template<typename RTYPE, int TLEN>
RTYPE scramble(u_int16_t *seed, RTYPE a){
  int d;
  //
  for ( d = 0; d < 8; ++d){
    u_int16_t mask;
    //
    mask = (*seed & 0x1) ^ ( (*seed >> 1) &0x1);
    mask = mask & 0x1;
    *seed = (mask << 15) | (*seed >> 1);
    //
    a = a ^ ((RTYPE)mask << d);  
  }
  //
  return a;
};

// Определяет используется ли общая память
//#define SHARED 1

void*
runner(void* args){
  unsigned int which = *(unsigned int*)args; delete (unsigned int*)args;
  unsigned int index = which;
  u_int16_t seed = 0x4a80;
  MTYPE array1[MAXAR];
  //
  for ( unsigned int i = 0; i < DOIT; ++i){
    MTYPE data;
    if ( index >= MAXAR)
      index = which;
    //
#if defined(SHARED)
    data = array[index];
    array[index] = scramble<MTYPE, 8*sizeof(MTYPE)>(&seed, data);
#else
    data = array1[index];
    array1[index] = scramble<MTYPE, 8*sizeof(MTYPE)>(&seed, data);
#endif
    //
    index += TOTAL;
  }
  //
  pthread_mutex_lock(&mux);
  -- workers;
  pthread_mutex_unlock(&mux);
  pthread_cond_broadcast(&cond);
  //
  return 0;
};  

int
main() {
  //
  array = (MTYPE*)calloc(MAXAR, sizeof(MTYPE));
  //
  unsigned int *which;
  pthread_t t1;
  pthread_attr_t attr;
  //
  pthread_attr_init(&attr);
  pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
  //
  which = new unsigned int(0);
  pthread_create(&t1, &attr, runner, (void*)which);
  //
  which = new unsigned int(1);
  pthread_create(&t1, &attr, runner, (void*)which);
  //
  pthread_mutex_lock(&mux);
  while(!pthread_cond_wait(&cond, &mux)){
    if ( !workers)
      break;
  };
  pthread_mutex_unlock(&mux);
  //
  return 0;
};
//  

* This source code was highlighted with Source Code Highlighter.