CPU cache
CPU가 매번 메모리에 접근하여 데이터를 가져오는 것은 느리기 때문에 지역성의 특성을 이용해 CPU 캐시에 데이터를 추가로 가져온다.
(추가로 가져오는 데이터의 단위는 캐시 라인이며, 대부분의 CPU는 64 bytes로 구성되어 있다.)
이와 관련한 그림으로 아래의 그림을 많이 보았을 것이다.
그러나 병렬 처리 환경에서는 CPU cache으로 인해 오히려 성능이 낮아질 때도 있다. (false sharing 문제)
False sharing
False sharing은 "거짓 공유"의 문제로 실제로 쓰레드간 공유되지 않은 데이터이지만, 동일한 캐시 라인의 데이터를 마치 공유하는 것처럼 인식하여 성능 저하를 일으키는 문제를 말한다.
이에 대하여 병렬처리 환경에서 false sharing 문제가 어떻게 발생되는지 그림으로 확인하면 이해가 쉽다.
False sharing 문제는 메모리가 연속적 (정확히는 한 캐시 라인에 두 데이터가 포함) 일 때, 나타나는 문제이기 때문에 배열, 구조체 등에서 자주 발생된다.
False sharing으로 인한 성능 저하 테스트
#include <iostream>
#include <thread>
#include <chrono>
#define FALSE_SHARING
// #define RNAD_TEST
// #define __DEBUG
#define TEST_CNT 100
#define ITER_CNT 1000000
#ifdef FALSE_SHARING
struct Info {
volatile int num1;
volatile int num2;
} info;
volatile long long num3 = 0;
#else
struct Info {
volatile long long num1 = 0;
alignas(64) volatile long long num2 = 0; // cache line의 범위를 벗어나도록 64 bytes 만큼 padding을 추가함 (align)
} info;
alignas(64) volatile long long num3 = 0;
#endif
void fun1() {
for (long long i = 0; i < ITER_CNT / 2; i++)
#ifndef RNAD_TEST
info.num1 += 1;
#else
info.num1 += rand();
#endif
}
void fun2() {
for (long long i = 0; i < ITER_CNT / 2; i++)
#ifndef RNAD_TEST
info.num2 += 1;
#else
info.num2 += rand();
#endif
}
void fun3() {
for (long long i = 0; i < ITER_CNT; i++)
#ifndef RNAD_TEST
num3 += 1;
#else
num3 += rand();
#endif
}
std::chrono::duration<double> test(bool is_multi_test) {
auto beginTime = std::chrono::high_resolution_clock::now();
if (is_multi_test) {
std::thread t1(fun1);
std::thread t2(fun2);
t1.join(); t2.join();
}
else {
fun3(); //Single Thread 실행
}
auto endTime = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> resultTime = endTime - beginTime;
#ifdef __DEBUG
std::cout << "-------[single]-------\n";
std::cout << "total value: " << num3 << std::endl;
std::cout << "excution time: " << resultTime.count() << std::endl;
#endif
return resultTime;
}
int main() {
double single_total = 0, multi_total = 0;
for (int i = 0; i < TEST_CNT; i++) {
info.num1 = 0;
info.num2 = 0;
num3 = 0;
single_total += test(false).count() / TEST_CNT;
multi_total += test(true).count() / TEST_CNT;
#ifdef __DEBUG
std::cout << "---------------------\n";
std::cout << std::endl;;
#endif
}
std::cout << "single test excution time: " << single_total << std::endl;
std::cout << "multi test excution time: " << multi_total << std::endl;
}=== [False sharing test] ===
single test excution time: 0.00161374
multi test excution time: 0.00260395 (false sharing으로 인해 병렬 처리 환경임에도 더 오래걸림)
=== [ False sharing Mitigated ] ===
single test excution time: 0.00177046 (false sharing 문제를 해결하면 single thread가 더 느림을 확인 할 수 있음)
multi test excution time: 0.00119301example
in linux
리눅스에서도 false sharing 문제를 회피하기 위한 코드들을 확인할 수 있다.
in structure
struct page_counter {
/*
* Make sure 'usage' does not share cacheline with any other field. The
* memcg->memory.usage is a hot member of struct mem_cgroup.
*/
atomic_long_t usage;
CACHELINE_PADDING(_pad1_);
/* effective memory.min and memory.min usage tracking */
unsigned long emin;
atomic_long_t min_usage;
atomic_long_t children_min_usage;
/* effective memory.low and memory.low usage tracking */
unsigned long elow;
atomic_long_t low_usage;
atomic_long_t children_low_usage;
unsigned long watermark;
unsigned long failcnt;
/* Keep all the read most fields in a separete cacheline. */
CACHELINE_PADDING(_pad2_);
unsigned long min;
unsigned long low;
unsigned long high;
unsigned long max;
struct page_counter *parent;
} ____cacheline_internodealigned_in_smp;위는 리눅스에서 사용되는 page_counter 구조체이다. 주석을 보면 page_counter 구조체의 usage 멤버 변수가 hot member (자주 사용되는 변수)라고 설명되어 있다. 이 usage 변수가 다른 멤버 변수들과 같은 캐시 라인에 위치하게 되면, false sharing 문제로 인해 성능이 심각하게 저하될 수 있다. 그래서 이를 방지하기 위해 CACHELINE_PADDING을 추가하여 다른 멤버 변수들과 같은 캐시라인에 들어오지 않도록 하고 있다.
