Search
Duplicate
🥕

포드존슨 과제에서 써보는 최적화 기법

간단소개
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
CS
C++
Scrap
태그
9 more properties

1. 메모리 풀

필자는 포드존슨에서 원소들을 묶기 위해 트리의 Node처럼 Block이라는 구조를 사용했는데, new/delete를 사용해서 블록을 매 번 할당하면 엄청난 코스트를 지불할 뿐더러 메모리 단편화도 발생한다. 그러므로 한 번에 크게 할당한 뒤 하나씩 떼어주는 방법으로 메모리 풀을 구현한다. 해제도 구현이 가능한데 굳이 이 과제에선 필요 없으므로 생략. 이렇게 하면 new/delete 보다 최대 100배는 빠르다. (해제까지 구현해도 속도 같음)
// Utility macros // Round up to the nearest power of 2. If x == 2^N, Then return x. #define ROUND_UP_POW2(x) ((x) == 0 ? 1 : (1 << (sizeof(size_t) * CHAR_BIT - __builtin_clzl((x) - 1)))) //< __builtin_clzl() == BSF(Bit Scan Forward) // Define Block for managing sorted blocks (like a binary tree) typedef struct _Block Block; typedef struct _Block { Block* left; Block* right; typename Container::value_type keyValue; //< the value of highest element that is contained in sub-blocks } Block; // Create fixed memory pool for Block allocation const size_t containerSizePow2 = ROUND_UP_POW2(container.size()); Block* blockPool = new Block[2 * containerSizePow2]; size_t blockPoolIndex = 0; #define ALLOCATE_BLOCK() (Block*)(blockPool + blockPoolIndex++)
C++
복사

2. 잉여 공간 활용

위에서 처럼 new로 할당된 주소는 반드시 8byte에 배수에 정렬되고, 각 원소도 8byte에 정렬될 것이다. 그러므로 주소의 하위 3bit는 무조건 0으로 채워지니 이 공간을 flag 변수 대신으로 사용할 수 있겠다.
// The address of the block will be aligned to 8-byte boundary, so the lower 3 bits are not used. // Therefore use the lower 3 bits to indicate whether the block is disassembled. #define MARK_BLOCK_AS_DISASSEMBLED(ptr) reinterpret_cast<Block*>(reinterpret_cast<uintptr_t>(ptr) | 0x01) #define UNMARK_BLOCK_AS_DISASSEMBLED(ptr) reinterpret_cast<Block*>(reinterpret_cast<uintptr_t>(ptr) & ~0x01) #define IS_BLOCK_DISASSEMBLED(ptr) (reinterpret_cast<uintptr_t>(ptr) & 0x01)
C++
복사

3. Auto vectorization

필자의 코드에는 매 스테이지 마다 모든 블록의 flag을 해제해주어야 하는데, 이 과정에서 시간이 좀 많이 소요된다.
// Unmark the disassembled blocks for (size_t j = 0; j < arrSize; j++) { arr[j] = UNMARK_BLOCK_AS_DISASSEMBLED(arr[j]); }
C++
복사
간단한 AND 연산이고 Align 가능한 주소이므로 AVX로 최적화 한다. 굳이 SIMD intrinsic이나 어셈으로 짤 필요 없이 컴파일러한테 단위와 정렬을 만족시켜주면 된다. 컴파일러가 다 해주는 세상이어도 내가 컴파일러한테 맞춰서 짜 줘야 컴파일러가 다 해줄 수 있다. 루프에서 속도가 4배 빨라지고 전체 성능이 200%로 개선됐다. (3000개 기준 1000us → 550us)
#define AVX_BYTE 32 #define AVX_NUM_PACKED_PTR (AVX_BYTE / sizeof(Block*)) // Unmark the disassembled blocks (Use AVX for performance) for (size_t j = 0; j < arrSize; j += AVX_NUM_PACKED_PTR) { for (size_t k = 0; k < AVX_NUM_PACKED_PTR; k++) { arr[j + k] = UNMARK_BLOCK_AS_DISASSEMBLED(arr[j + k]); } }
C
복사
물론 캐시라인 넘는거나 이것 저것 생각해야된다.
똑같은 방식으로 배열을 1칸 shift 하는 연산도 SIMD로 대체 가능하다. align이 보장되지 않으므로 성능향상이 드라마틱 하진 않을거다. 전체성능의 5~10% 정도 향상이 있었다. (550us → 500us)
/** BEFORE */ // Shift the array to make space for inserting the left block for (size_t j = arrSize; j > insertIndex; j--) { arr[j] = arr[j - 1]; }
C
복사
/** AFTER */ // Shift the array to make space for inserting the left block (Use AVX for performance) { // Shift 1 space by 32 bytes at a time until the remaining size is less than 32 bytes. (Unaligned move) size_t j; for (j = arrSize; j >= insertIndex + AVX_NUM_PACKED_PTR; j -= AVX_NUM_PACKED_PTR) { for (size_t k = 0; k < AVX_NUM_PACKED_PTR; k++) { arr[j - k] = arr[j - k - 1]; } } // Shift the remaining size (less than 32 bytes) for (; j > insertIndex; j--) { arr[j] = arr[j - 1]; } }
C
복사

3-1. Auto vectorization 주의점

원래는 align이 보장되지 않으므로 컴파일러는 unaligned operation을 사용한다. align을 보장해주려면 이런식으로 짜야 된다.
// Unmark the disassembled blocks (Use AVX for performance) { // Unmark until aligned to AVX memory boundary size_t j = 0; for (; j < arrSize && (reinterpret_cast<uintptr_t>(&arr[j]) & (AVX_BYTE - 1)) != 0; j++) { arr[j] = UNMARK_BLOCK_AS_DISASSEMBLED(arr[j]); } // Unmark 4 blocks at a time using AVX for (; j < arrSize; j += AVX_NUM_PACKED_PTR) { for (size_t k = 0; k < AVX_NUM_PACKED_PTR; k++) { arr[j + k] = UNMARK_BLOCK_AS_DISASSEMBLED(arr[j + k]); } } }
C
복사