Contents #
Introduction #
Allen Newell과 J. C. Shaw는 문제의 증명을 기호 논리를 통해 찾는 프로그램인 Logical Theorist (LT)를 개발하는 과정에서 연결 리스트를 제안하였다. LT를 구현하기 위해서는 표현식이나 논리 문제를 해결하는데 사용한 프로세스의 리스트를 다룰 수 있어야 했고, 이를 위한 요구사항을 해결하기 위해 개발한 언어인 Information Processing Language (IPL)이 리스트를 표현한 방식이 연결 리스트 (Linked list)였던 것이다. 이때 그 요구사항을 간략히 정리하면 다음과 같다[1].
- Flexibility of Memory Management
- No restrictions on the number of different lists of items of information
- No restrictions on the nature of the items in a list
- Possible to add, delete, insert and rearrange items of information in a list
- Flexibility in the Specification of Processes
- No limitation on the size and complexity of hierarchies of definitions
- No restriction on the number of references in the instructions or on what is referenced
- Possible to define processes implicitly (e.g., by recursion)
- Unnecessary to have single integrated plan or set of conventions for the form of informations
상기의 요구사항을 읽어보면 Flexibility of Memory Mangement가 제네릭 데이터를 다루기 위한 연결 리스트와 연관이 있음을 알 수 있다.
이렇게 Allen Newell과 J. C. Shaw이 개발한 IPL은 다음과 같이 연결 리스트를 표현하였다[1].
+--------+ +--------+ +--------+
--->|Location|--->|Location|--->|Location|---> (-1)
+--------+ +--------+ +--------+
| | |
V V V
element element element
위 그림에서 각 Location은 다음 Location을 가리키며, 리스트의 끝은 -1로 표현한다. 이러한 리스트는 Location만으로 순회가 가능하며, Location을 통해 element에 접근할 수 있다. 이는 다음과 같은 노드 구조와는 다른 것으로 보인다[1].
1struct node {
2 void *element;
3
4 struct node *next;
5};
그러나 IPL에서 표현한 연결 리스트는 현대에도 게임이나 커널 분야에서 사용되고 있으며, 흔히 intrusive linked list라고 불린다. 본 글에서는 이러한 방식의 연결 리스트에 대한 사용예를 살펴보고, 간단한 구현 예시를 제공할 것이다.
Intrusive Linked List #
Intrusive Linked List는 연결 리스트에서 한 노드와 그 다음 노드 간 연결을 위한 타입이 존재하여 이 타입이 임의의 다른 타입에 멤버 변수로 속해있는 경우를 의미한다. 이를 C 언어로 표현하면 다음과 같다[2].
1struct element {
2 /* ... */
3
4 struct node list;
5};
6
7struct node {
8 struct node *next;
9};
위 코드와 그 앞에서의 C 코드 (Node structure of Non-intrusive linked list)를 비교해보면 어떤 차이가 있는지 알 수 있을 것이다.
상기의 코드와 같은 구현 방식은 제네릭 데이터를 linked list로 다루고자 할 때 메모리 할당 횟수를 감소시킨다는 장점이 있다. Non-intrusive linked list의 경우에는 노드 구조체와 데이터 구조체를 할당해야 하므로 두 번의 메모리 할당이 필요하다. 반면 intrusive linked list는 데이터 구조체만 할당하면 된다. 노드 구조체는 이미 데이터 구조체 내에 포함되어 있기 때문이다. 이러한 할당 횟수의 감소는 에러 처리 횟수의 감소를 의미하는 것이기도 하다.
다만, 현대에 intrusive linked list를 구현할 때 circular하게 구현하는 경우가 있다. 이는 NULL check가 필요없도록 만들어 branch prediction miss로 인한 성능 저하를 감소시킬 수 있다. 이는 Doom 3와 리눅스 커널의 코드를 보면 보다 명확히 보일 것이다.
Doom 3's list structure #
Doom 3는 C++로 작성되었지만 intrusive linked list 구현부를 이해하기에 큰 어려움은 없다. 여기서는 gpfault에서 작성한 글 [2]을 기반으로 하여 살펴볼 것이다.
Doom 3는 다음과 같이 리스트 타입을 구현한다[3].
1// neo/idlib/containers/LinkList.h
2
3template< class type >
4class idLinkList {
5public:
6 idLinkList();
7 ~idLinkList();
8
9 bool IsListEmpty( void ) const;
10 bool InList( void ) const;
11 int Num( void ) const;
12 void Clear( void );
13
14 void InsertBefore( idLinkList &node );
15 void InsertAfter( idLinkList &node );
16 void AddToEnd( idLinkList &node );
17 void AddToFront( idLinkList &node );
18
19 void Remove( void );
20
21 type * Next( void ) const;
22 type * Prev( void ) const;
23
24 type * Owner( void ) const;
25 void SetOwner( type *object );
26
27 idLinkList * ListHead( void ) const;
28 idLinkList * NextNode( void ) const;
29 idLinkList * PrevNode( void ) const;
30
31private:
32 idLinkList * head;
33 idLinkList * next;
34 idLinkList * prev;
35 type * owner;
36};
위 코드에서 눈여겨 봐야하는 것은 private 부분이다. 그럼 각 노드는 이전 노드와 다음 노드에 대한 정보 뿐만 아니라 head 노드와 그 노드를 가진 데이터에 대한 정보를 가지고 있음을 알 수 있다. 이때 head 노드는 리스트에 대한 handle의 의미를 가진다. 다음 코드를 읽어보자[3].
1// neo/idlib/containers/LinkList.h
2
3
4/*
5================
6idLinkList<type>::idLinkList
7
8Node is initialized to be the head of an empty list
9================
10*/
11template< class type >
12idLinkList<type>::idLinkList() {
13 owner = NULL;
14 head = this;
15 next = this;
16 prev = this;
17}
위 코드를 읽어보면 head 노드는 owner 없이 리스트를 핸들링하기 위한 노드임을 알 수 있다. 이를 그림으로 나타내면 다음과 같다.
+---------+
+--------| head |-------------+
| +---->| |<---------+ |
| | +---------+ | |
| | | |
V | | V
+---------+ +---------+
| node2 |<--------------------| node1 |
| |-------------------->| |
+---------+ +---------+
상기의 그림을 살펴보면 NULL을 가리키는 노드가 없음을 알 수 있다. 즉, NULL check를 할 필요가 없는 것이다. 아래 코드를 보자[3].
1// neo/idlib/containers/LinkList.h
2
3/*
4================
5idLinkList<type>::Remove
6
7Removes node from list
8================
9*/
10template< class type >
11void idLinkList<type>::Remove( void ) {
12 prev->next = next;
13 next->prev = prev;
14
15 next = this;
16 prev = this;
17 head = this;
18}
19
20// ...
21
22/*
23================
24idLinkList<type>::InsertAfter
25
26Places the node after the existing node in the list. If the existing node is the head,
27then the new node is placed at the beginning of the list.
28================
29*/
30template< class type >
31void idLinkList<type>::InsertAfter( idLinkList &node ) {
32 Remove();
33
34 prev = &node;
35 next = node.next;
36 node.next = this;
37 next->prev = this;
38 head = node.head;
39}
위 코드를 보면 포인터 값을 바꾸는 것만으로 node insertion을 수행하는 것을 볼 수 있다. 이렇게 NULL check가 필요 없도록 만듦으로써 branch prediction miss로 인한 성능 저하를 감소시킬 수 있는 것이다.
Linux kernel's list structure #
리눅스 커널 코드를 읽다보면 list_head 구조체를 많이 접하게 된다. 이는 리눅스 커널에서 제공하는 연결 리스트에 관한 구조체이며, 그 구조는 앞서 살펴본 Doom 3의 것과 유사하다. 여기서는 리눅스 커널 5.15.30 버전을 기반으로 살펴볼 것이다.
리눅스 커널은 다음과 같은 노드 구조체를 제공한다[4].
1/* include/linux/types.h */
2
3struct list_head {
4 struct list_head *next, *prev;
5};
위 코드를 통해 Doom 3의 노드가 가지고 있는 정보에 비해 적은 정보를 가지고 있음을 알 수 있다. 리눅스 커널은 head 노드는 별도로 관리하고, owner는 container_of 매크로를 이용하여 얻는다. 그래서 next와 prev만으로도 리스트를 핸들링할 수 있는 것이다.
리눅스 커널은 노드 삽입을 일반화한 함수를 정의하고 이를 이용하여 list_add_tail과 같은 함수를 구현한다[4].
1/* include/linux/list.h */
2
3
4/*
5 * Insert a new entry between two known consecutive entries.
6 *
7 * This is only for internal list manipulation where we know
8 * the prev/next entries already!
9 */
10static inline void __list_add(struct list_head *new,
11 struct list_head *prev,
12 struct list_head *next)
13{
14 if (!__list_add_valid(new, prev, next))
15 return;
16
17 next->prev = new;
18 new->next = next;
19 new->prev = prev;
20 WRITE_ONCE(prev->next, new);
21}
22
위 코드를 통해 알 수 있는 것은 모든 노드가 어딘가를 가리키고 있기 때문에 노드 삽입이 두 노드 사이에 한 노드를 삽입하는 것으로 일반화할 수 있다는 것이다. 즉, 리스트의 처음 또는 리스트의 끝에 삽입하는 경우를 생각할 필요가 없다.
노드를 삭제하는 것은 Doom 3와 거의 동일하므로 생략하겠다.
Implementation example of intrusive linked list #
여기서는 상기에 살펴본 것에 대한 구현 예시를 제공한다. 이를 통해 지금까지 다룬 것이 어떻게 동작할지에 대한 감을 잡을 수 있을 것이다.
여기서 구현할 것은 int 타입의 key를 데이터로 하는 리스트이다. 이때 삽입 방식은 끝에 붙이거나 오름차순 정렬을 제공한다. 이에 대한 연결 리스트 구현은 다음과 같다.
1#ifndef __LIST_NODE_H__
2#define __LIST_NODE_H__
3
4#include <stdio.h>
5#include <stddef.h>
6
7struct list_node {
8 struct list_node *head; /*
9 * first node and handle
10 * for the list
11 */
12 struct list_node *prev;
13 struct list_node *next;
14 void *obj; /* object holding this node */
15};
16
17inline void list_node_remove(struct list_node *node)
18{
19 node->next->prev = node->prev;
20 node->prev->next = node->next;
21 node->head = node;
22 node->prev = node;
23 node->next = node;
24}
25
26void list_node_clear(struct list_node *list,
27 void (*destroy)(void *));
28
29inline void list_node_insert(struct list_node *prev,
30 struct list_node *node,
31 struct list_node *next)
32{
33 node->next = next;
34 node->prev = prev;
35 prev->next = node;
36 next->prev = node;
37 node->head = prev->head;
38}
39
40void list_node_add_tail(struct list_node *list,
41 struct list_node *node);
42
43inline void list_node_init(struct list_node *node,
44 void *obj)
45{
46 node->head = node;
47 node->prev = node;
48 node->next = node;
49 node->obj = obj;
50}
51
52#define LIST_HEAD_NODE_INIT(headp) \
53 list_node_init((headp), NULL)
54
55#define LIST_NODE_FOREACH(listp, currp, nextp) \
56 for ((currp) = (listp)->head->next, \
57 (nextp) = (currp)->next; \
58 (currp) != (listp)->head; \
59 (currp) = (nextp), (nextp) = (nextp)->next)
60
61
62#endif
63
1#include <stdio.h>
2#include "list_node.h"
3
4extern inline void list_node_remove(struct list_node *node);
5
6void list_node_clear(struct list_node *list,
7 void (*destroy)(void *))
8{
9 struct list_node *curr, *next;
10
11 LIST_NODE_FOREACH(list, curr, next) {
12 list_node_remove(curr);
13 destroy(curr->obj);
14 }
15}
16
17extern inline void list_node_insert(struct list_node *prev,
18 struct list_node *node,
19 struct list_node *next);
20
21void list_node_add_tail(struct list_node *list,
22 struct list_node *node)
23{
24 list_node_insert(list->prev, node, list);
25}
26
27extern inline void list_node_init(struct list_node *node,
28 void *obj);
위 구현을 살펴보면 inline된 함수들이 있음을 알 수 있다. 함수를 inlining하는 것은 함수 호출 비용을 줄일 수 있다는 장점이 있지만, instruction cache를 소모한다는 단점도 가지고 있다. 다만, 위 코드에서의 inline은 컴파일러에 대한 요청일 뿐임을 기억하라. 컴파일러는 요청에 따라 확인할 것이고 inlining이 필요하다면 할 것이다. 이제 key 리스트를 구현한 예제를 읽어보자.
1#include <stdio.h>
2#include <stddef.h>
3#include <stdlib.h>
4#include "list_node.h"
5
6struct key {
7 unsigned int key;
8 struct list_node klist;
9};
10
11typedef struct list_node keylist_t;
12
13#define KEYLIST_INIT(headp) LIST_HEAD_NODE_INIT(headp)
14
15static struct key *key_init(unsigned int key);
16static void key_add_tail(keylist_t *list, struct key *k);
17static void key_add_asc(keylist_t *list, struct key *k);
18static void key_print(keylist_t *list);
19static void key_destroy(void *k);
20static void key_remove(keylist_t *list, unsigned int key);
21static void keylist_destroy(keylist_t *list);
22
23int main()
24{
25 struct key *k;
26 keylist_t keylist;
27
28 KEYLIST_INIT(&keylist);
29
30 k = key_init(42);
31 key_add_tail(&keylist, k);
32 key_print(&keylist);
33
34 k = key_init(23);
35 key_add_tail(&keylist, k);
36 key_print(&keylist);
37
38 k = key_init(32);
39 key_add_tail(&keylist, k);
40 key_print(&keylist);
41
42 key_remove(&keylist, 24);
43 key_print(&keylist);
44
45 k = key_init(255);
46 key_add_tail(&keylist, k);
47 key_print(&keylist);
48
49 key_remove(&keylist, 32);
50 key_print(&keylist);
51
52 k = key_init(12);
53 key_add_tail(&keylist, k);
54 key_print(&keylist);
55
56 k = key_init(12);
57 key_add_tail(&keylist, k);
58 key_print(&keylist);
59
60
61 keylist_destroy(&keylist);
62 return 0;
63}
64
65static struct key *key_init(unsigned int key)
66{
67 struct key *k;
68
69 k = malloc(sizeof(*k));
70 if (k == NULL) {
71 perror("malloc");
72 return NULL;
73 }
74
75 k->key = key;
76 list_node_init(&(k->klist), k);
77 return k;
78}
79
80static void key_add_tail(keylist_t *list, struct key *k)
81{
82 list_node_add_tail(list, &(k->klist));
83}
84
85static void key_add_asc(keylist_t *list,
86 struct key *k)
87{
88 struct list_node *curr, *next;
89 struct key *kk;
90
91 LIST_NODE_FOREACH(list, curr, next) {
92 kk = curr->obj;
93 if (kk->key >= k->key) {
94 list_node_insert(curr->prev, &(k->klist), curr);
95 return ;
96 }
97 }
98 key_add_tail(list, k);
99}
100
101static struct key *key_search(keylist_t *list,
102 unsigned int key)
103{
104 struct list_node *curr, *next;
105 struct key *kk;
106
107 LIST_NODE_FOREACH(list, curr, next) {
108 kk = curr->obj;
109 if (kk->key == key)
110 return kk;
111 }
112 return NULL;
113}
114
115static void key_print(keylist_t *list)
116{
117 size_t cnt;
118 struct list_node *curr, *next;
119 struct key *k;
120
121 printf("\n\n---< Keys >---\n");
122 cnt = 0;
123 LIST_NODE_FOREACH(list, curr, next) {
124 k = curr->obj;
125 printf("key: %d, ", k->key);
126 cnt++;
127 }
128 printf("-- [%ld]\n", cnt);
129 printf("--------------\n");
130}
131
132static void key_destroy(void *k)
133{
134 free(k);
135}
136
137static void key_remove(keylist_t *list, unsigned int key)
138{
139 struct key *k;
140
141 k = key_search(list, key);
142 if (k) {
143 list_node_remove(&(k->klist));
144 key_destroy(k);
145 }
146}
147
148static void keylist_destroy(keylist_t *list)
149{
150 list_node_clear(list, key_destroy);
151}
위 코드는 head 노드를 어떻게 다루어야 하는지를 설명한다. 즉, 상기의 그림과 같이 리스트를 핸들링하기 위한 노드라는 것이다.
Conclusion #
정리하면, intrusive linked list는 할당 횟수 (그리고 에러 처리 횟수)를 감소시킬 수 있다는 장점이 있고, circular하게 구성함으로써 NULL check를 없앨 수 있으며 branch prediction miss 감소와 노드 삽입 일반화가 가능하다. 물론, non-intrusive linked list가 쓰이지 않는 것은 아니다. Glibc의 tcache 구현에서는 single linked list를 구현할 때 non-intrusive한 방식으로 구현한다. 중요한 것은 어떤 구현 방식이 현재 상황에 더 적합한지 따져보는 것이다.
References #
- Allen Newell and J. C. Shaw, "Programming the Logic Theory Machine," Proceedings of the Western Joint Computer Conference, pp. 230 – 240, 1957.
- gpfault, Dec. 2014, "Intrusive Linked List in Doom 3," gpfault.net. [Online]. Available: https://gpfault.net/posts/intrusive-lists-doom3.txt.html
- Edgars, 2012, "ABOUT," [Online]. Available: https://github.com/Edgarins29/Doom3
- Torvalds, Mar. 2022, "linux kernel," [Online]. Available: https://github.com/torvalds/linux