weasel의 우당탕탕 개발기

Why B 트리? B 트리는 이진트리와 다르게 하나의 노드에 많은 정보를 가질 수 있는 트리를 의미한다. 노드의 최대 자식의 개수를 M이라고 할때, M차 B트리라고 한다. B 트리는 고전적인 메모리 계층 구조의 물음에서 출발한다. 이진탐색트리의 시간복잡도가 최악이 될 때는 노드가 편향된 경우인데, 이를 해결하는 것이 AVL,RB 트리와 같은 균형이진트리다. 그런데 이것만으로 부족하다. 왜 그러냐면, O(logn) 을 보장하는 균형이진트리의 최악을 생각해보자. 최악이 있을까? 분명히 있다. RB트리에서 원소가 1백만개라고 해보면, 트리의 높이는 최대 2*log(10^6)이다. 따라서 대략 20정도이다. RB 트리에서 Red 노드는 최대 두개만 연속으로 되어있음을 생각하면 쉽게 알 수 있다. 그러면, 원하는..

GIL은 Global Interpreter Lock의 약자이다. Global이 붙으니 전역적이라는 의미이고, Lock을 사용하니 무언가를 제한한다는것은 알겠는데 Interpreter는 뭘까? 인터프리터에 대해서 제한을 건다는 것이 어떤 의미일까? 아래에서 쭉 알아보자. Interpreter 짧게 얘기하면 Python 인터프리터는 코드를 한 줄씩 읽으면서 실행하는 프로그램이다. 이 방식때문에 인터프리터 언어가 느리단 얘기가 나오는 것이고, Java에서 이를 개선해서 등장한 방식이 JIT다. 이 인터프리터의 구현체는 여러가지가 있는데 대표적인 구현체가 C로 구현한 것이고, 이를 CPython이라고 한다. 이 글에서는 CPython 기준으로 설명할 것이다. Python 위키 항목을 읽어보면 Non-CPytho..

이전편 : 가상 메모리 지역성 페이지 교체 알고리즘에 대해 언급하기 전에 먼저 지역성이라는 것에 대해서 알아야 한다. 시간 지역성 (Temporal Locality ) : 현재 참조된 메모리가 가까운 미래내에 참조될 가능성이 높음 loop,subroutine,stack 공간 지역성 (Spatial Locality) : 하나의 메모리가 참조되면 주변의 메모리가 참조될 가능성이 높음 Array 순회, 명령어의 순차실행 프로그램의 메모리 참조는 고도의 지역성을 가진다. 임의의 시간 Δt 내에 프로그램의 일부분만을 집중적으로 참조한다는 것이다. 이러한 지역성이 있기 때문에 적절한 페이지 교체 알고리즘이 중요하다. 왜 중요할까? 예를 들어서 주기적으로 두개의 페이지만 참조하는 로직이 있다고 해보자. 만약 그 두개..