탐색 속도 개선 계획

[JuneParkCode]

TODO

탐색 속도 개선

• block 에 해당 하는 pool을 찾는데 시간이 오래 걸리는 문제를 해결하고자한다.
• 현재 구조에서는 block 의 주소는 pool 객체의 주소와 관련이 없다.
  • 따라서, pool을 관리하고 있는 객체 속에서 순회하며 block이 속한 pool을 찾아야한다.
  • 이 순회 속도가 탐색 속도에 영향을 미친다.
• pool 관리를 위해 linked list를 사용하고 있는데, 적절한 pool의 위치를 찾는 시간이 O(N) 으로 pool의 개수가 많은 상황에서 탐색 속도가 급격히 저하되는 문제가 있다.
• pool 을 관리하는 방식을 linked list 에서 balanced binary tree로 전환하면 O(logN) 으로 낮출 수 있다.
  • 메모리 주소의 경우 새로 만들 때 이전 주소값에 비해 증가하기 때문에 일반 binary tree로 만들게 될 경우, 선형 구조가 될 위험이 있다.
• manager 의 경우, 각 타입마다 별도의 linked list를 가지고 있었는데, 새로운 구조에서는 통합된 tree 에 함께 관리하는 것이 적합하다.

binary tree

• AVL tree 를 활용한다.
  • RB-tree 보다 엄격하게 tree 의 balance 가 유지되어 탐색이 빈번한 현재 상황에 적합하다.
• node 는 pool 구조체를 그대로 사용한다.
• tree 의 key는 pool->addr 이다.

변경사항

• 변경될 요소들은 다음과 같다.
  • t_pool struct 의 내부 요소
    • tree node 화를 위한 parent / left / right
    • 기존 free_list 삭제
      • O(1) 할당을 위함. free_list 관리를 manager 단에서 수행
    • 그 결과는 다음과 같다.

    // pool sturcture
    typedef struct s_pool {
        // pool address information
        void *addr;			  // pool addr
        t_metadata *metadata; // information data space address in pool
        // tree node 
        struct s_pool *parent;
        struct s_pool *left;
        struct s_pool *right;
        // size informmation
        size_t size;		   // pool size (user space + metadata)
        size_t allocated_size; // mmap allocated size
        size_t max_size;	   // maximum allocation size -> userspace_size
        POOL_TYPE type;
    } t_pool;

  • t_mmanger struct 의 내부 요소
    • tiny_pool_head / small_pool_head / large_pool_head 가 삭제된다.
      • 대신, t_pool *pool_head 로 통합되어 관리된다.
    • bool tiny_has_free_pool / bool small_has_free_pool
      • type 별로 pool 이 관리되고 있지 않기 때문에, 각 type 에서 free_pool 이 이미 존재하는 경우, 새로운 free_pool 의 경우 즉시 반환하도록 한다.
    • t_block *tiny_free_list[MAX_TINY_ORDER]
    • t_block *small_free_list[MAX_SMALL_ORDER]
      • TINY / SMALL 에 대해서 free_list 를 manager 에서 관리한다.
      • free_list 가 포화될 위험은 낮다. free_pool 이 최대 한 개 존재할 수 있기 때문이다.
    • 그 결과는 다음과 같다.

    // ptr space
    typedef struct s_pool_space {
        t_pool *head;
        t_block *tiny_free_list[MAX_TINY_ORDER];
        t_block *small_free_list[MAX_SMALL_ORDER];
        bool tiny_has_free_pool;
        bool small_has_free_pool;
        t_pmalloc_space *pmalloc_space;
    } t_mmanager;

기대효과

• NOTE: P = POOL
• free_block 탐색 속도 개선
  • O(P) -> O(1)
  • 기존의 경우 pool 을 순회하며 free_block을 찾아야했다.
    • 높은 확률로 앞쪽 pool 에 free_block 이 있으나, 그렇지 않은 경우 문제가 발생한다.
• block 에 해당하는 pool 찾는 속도 개선
  • O(P) -> O(logP)
• free() 속도 개선
  • O(P) -> O(logP)
  • 특히 free() 의 경우 이미 많은 pool 이 존재할 경우에 free() N번의 요청에 O(N * P) 로 급격하게 증가하였으며, shrink_pool 까지 여러 번 일어나는 케이스에서는 더 악화되는 문제가 있었다.

[JuneParkCode]

660e436

• AVL_TREE 를 활용하여 O(N) -> O(logN)으로 줄였음.
• 일부 AVL_TREE 에서 발생하는 문제 변경함.