코딩

이번엔 본격적으로 우선 순위 큐에 대해 알아보겠습니다. 우선 순위 큐란 힙이라는 구조를 활용하여 우선 순위가 있는 데이터를 다루기 위하여 고안된 특별한 데이터 구조입니다. 힙이란 Heap Property를 만족하는 특별한 트리의 형태를 말합니다. Heap Property란 다음 두 가지를 의미합니다. 완전 이진 트리(CBT, Complete Binary Tree) 각각의 부모 노드는 자식 노드보다 그 값이 같거나 클 것(Max Heap) 혹은 같거나 작을 것(Min Heap) ​ 위와 같은 형태를 띠는 구조가 바로 힙, 우선 순위 큐입니다. 우선 순위 큐에서 수행할 수 있는 연산은 삽입(Insertion), 삭제(Deletion) 등이 있습니다. 먼저 삽입은 Shift-up 방식을 사용합니다. 트리의 제..

compile: g++ -std=c++11 A -o B #include #include class SmallMemoryAllocator { public: SmallMemoryAllocator(std::size_t block_size, std::size_t num_blocks) : block_size_(block_size), num_blocks_(num_blocks) { memory_pool_ = new char[block_size * num_blocks]; initialize(); } ~SmallMemoryAllocator() { delete[] memory_pool_; } void* allocate() { if (free_list_ == nullptr) { std::cerr next = free_lis..

I am toying with certain caching algorithm, which is challenging somewhat. Basically, it needs to allocate lots of small objects (double arrays, 1 to 256 elements), with objects accessible through mapped value, map[key] = array. time to initialized array may be quite large, generally more than 10 thousand cpu cycles. By lots I mean around gigabyte in total. objects may need to be popped/pushed a..

#include #include int main() { for (int i=0; i

-카네기 멜론 대학교(CMU)의 malloc-lab 동적할당기 구현 Implicit Allocator & Explicit Allocator Implicit Allocator Implicit Allocator는 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는지를 할당기가 스스로 검출할 수 있다. 가장 잘 알려진 예로는 가비지 컬렉터(Garbage Collector, GC)가 있다. 가비지 컬렉터는 자동으로 사용하지 않는 블록들을 반환시켜주며, 이 작업을 가비지 컬렉션이라고 부른다. Explicit Allocator Explicit Allocator는 할당기가 스스로 블록을 반환하지 않으며, 할당된 메모리 블록을 명시적으로 직접 해제 해주어야 하는 할당기이다. 가장 잘 알려진 예로..

tcmalloc tcmalloc은 특정 상황에서 더 유리한 선택일 수 있으며 다음과 같은 상황에서 사용되기 좋습니다: 멀티스레드 환경: tcmalloc은 멀티스레드 환경에서 효율적으로 동작하도록 최적화되어 있습니다. 스레드 간 메모리 관리와 캐싱을 통해 성능을 향상시킵니다. 따라서 멀티스레드 애플리케이션에서 사용하기 좋습니다. 대규모 및 분산 시스템: 대규모 분산 시스템, 클라우드 환경 또는 대용량 서버 애플리케이션과 같은 대규모 애플리케이션에서 tcmalloc은 효과적으로 메모리 할당 및 해제를 관리할 수 있어 유용합니다. 성능 최적화: tcmalloc은 일반적으로 glibc malloc과 비교하여 더 빠른 메모리 할당 및 해제 성능을 제공합니다. 따라서 성능이 중요한 응용 프로그램에서 사용하면 이점을..

Custom Memory Management implementation https://github.com/miguelperes/custom-malloc/blob/master/README.md my memory.h #define SYSTEM_MALLOC 1 #define STRUCT_SIZE 24 #define MULTIPLIER 10 #define ALIGN_SIZE 8 #define ALIGN(size) (((size) + (ALIGN_SIZE-1)) & ~(ALIGN_SIZE-1)) typedef struct chunkStatus { int size; int available; struct chunkStatus* next; struct chunkStatus* prev; char end[1]; } ch..

동적 메모리 할당(Dynamic Memory Allocation) 동적 메모리 할당이란 컴퓨터 프로그래밍에서 실행 중(런타임)에 사용할 메모리 공간을 할당하는 것을 의미한다. 프로그램이 실행되기 위해서는 메모리가 필요하다. 컴파일러는 컴파일 시점에 소스 코드를 읽고, 변수 타입들의 크기에 따라 메모리를 할당한다. 이처럼 프로그램이 실행되기 전, 컴파일 시점에 소스 코드를 읽고 메모리 공간을 확보하는 것을 정적 할당(static allocation) 이라고 한다. 그렇다면 **동적 할당(dynamic allocation)**이란 무엇일까? 컴파일 타임이 아닌 프로그램이 실행되는 중인 런타임에 필요한 만큼의 메모리 공간을 확보하는 것을 의미한다. 동적 할당이 필요한 이유? 그렇다면 동적 할당이 필요하는 이유..