가변 길이 자료구조 vs OPEN_MAX를 활용한 배열
•
과제 get_next_line의 풀이에 대해 작은 논란이 있다.
•
이 논란은 가변 길이의 자료구조와, OPEN_MAX 값을 활용한 배열을 통해 풀이하는 두 방법 중 어떤 것이 옳은 것인가? 라는 질문에서 시작된다.
•
필자의 경우 linked list를 활용한 풀이와 OPEN_MAX를 활용한 풀이를 모두 구현했다. 그러나 결과적으로는 OPEN_MAX로 풀이하는 것이 올바른 풀이라고 생각하여 OPEN_MAX를 통한 풀이로 제출하였다.
•
해당 글은 필자는 왜 OPEN_MAX를 활용한 배열을 통해 풀이를 하였는 지에 대해서 작성하였다.
우선, 해당 논란에서 가변길이의 자료구조를 활용해야한다는 의견의 주장은 OPEN_MAX에서부터 시작된다.
OPEN_MAX를 통한 풀이의 문제
OPEN_MAX는 Linux에서 정의되어 있지 않다.
•
OPEN_MAX 값을 활용하게 될 경우, “limits.h” 에 정의되어있는 OPEN_MAX 값을 활용하게 된다.
•
그러나 limits.h 에서 OPEN_MAX가 정의되지 않은 운영체제가 존재한다.
•
따라서 함수를 정의하며 임의로 OPEN_MAX 값을 정의해야한다.
◦
이 경우에는 헤더에 임의로 정의해둔 OPEN_MAX 값을 활용하게 된다.
◦
필자의 경우, 이 임의의 OPEN_MAX 값으로서 클러스터 맥에서 제한되어있는 file descriptor 의 한계값이었던 4만 이상으로 설정하였다. (별도로 테스트 코드를 만들어 돌려 ulimit 을 통해 해제를 하더라도 약 4만 개 이상의 파일은 더 이상 열리지 않음을 확인했다.)
◦
m1 macbook air 환경에서는 file descriptors를 90000으로 해제하더라도 10240개 이상 열리지 않는다.
◦
따라서 각 운영체제마다 설정된 최대 file descriptors 개수가 정해진 것으로 추측된다. (ulimit와 별도로...)
테스트에 활용한 코드
OPEN_MAX를 통해서는 파일을 모두 열지 못할 수도 있다.
•
앞서 OPEN_MAX 에 대해서 잠시 살펴보았듯이, OPEN_MAX 값은 항상 운영체제에서 설정된 file descriptors 값과 같다는 보장이 없다.
◦
limits.h 에 지정된 값의 경우 10,240이었지만, 실제로는 10,240보다 더 큰 값까지 한계를 설정할 수 있었다.
◦
10,240개 이상의 파일을 열려고 할 경우 해당 함수는 오류를 발생할 것이다.
•
이러한 이유로 인해서 OPEN_MAX를 통한 풀이는 적절하지 않다.
따라서 위와 같은 논리를 통해서 OPEN_MAX 를 이용한 풀이는 다소 적절하지 못하다고 주장할 수 있다.
그러나, 나는 위와 같은 문제를 인지하고 있음에도 OPEN_MAX를 통해 풀이하였다. 이를 설명하기 위해서 가변길이 자료구조의 문제를 서술해보고자한다.
가변길이 자료구조의 문제
•
앞서 제기된 문제로 인하여 OPEN_MAX를 활용한 풀이에서 벗어나고자한 사람들의 대부분은 Linked list를 통해 해당 문제를 풀이하였다. 그래서 linked list를 예시로 이러한 구조의 문제점에 대해서 작성한다.
효율성의 문제
•
가변길이 자료구조의 가장 큰 문제는 효율성이다.
•
결국 해당 구조를 사용하는 것은, limits.h 에 정의된 10240개 그 이상의 파일을 동시에 연 경우에 대해서 염두를 두고 함수를 설계하는 것이다.
•
가변길이 자료구조로서 가장 간단한 linked list를 활용하게 될 경우 발생하는 효율성 문제는 다음과 같다.
◦
해당 fd 에 해당하는 자료를 찾기 위한 시간이 너무나 길다. O(1) vs O(N)
◦
자료구조를 유지하기 위한 시간도 별도로 고려해야한다.
◦
차지하는 공간 또한 노드의 크기만큼 수 배 커질 수 있다.
▪
물론, 일정 크기 이하에서는 해당 방법이 공간 효율적일 수도 있다.
•
위 문제 중 하나인 탐색 속도를 해결하기 위해서 Hash map 과 같은 구조를 활용할 수도 있다. 그러나 두 번째 공간 활용성에 대한 문제는 여전히 남으며, 후술하게 될 문제도 안게된다.
해당 과제에 적합하지 않다.
•
“적합하지 않다” 라는 표현이 어쩌면 너무 강할 수도 있다. 하지만 가변길이 구조를 통해 함수를 구현해본 결과 필자는 다음과 같은 결론에 이르렀다.
1.
norminette 규칙 내에서 자료구조를 적절히 구현할 수 없다.
•
libft 과제에서 구현한 linked list만 하더라도 자체적으로 담고 있는 함수가 약 10개가 된다.
•
임의의 자료구조를 구현하여 이식한다고 하더라도, norminette를 만족하기 위해서는 오직 GNL을 위한 어떤 함수를 만들어서 작성해야한다.
◦
해당 함수는 굉장히 더러운 함수가 될 것이다.
•
해당 자료구조를 활용함에 있어 필수적인 함수들을 제거, 통합하고 함수의 단위 역할을 무시한채 억지로 집어 넣는 것이 올바른 코드인가?
•
만약 42에서 해당 함수를 그렇게 작성하도록 유도했다면 10개의 함수만으로 GNL을 구현하도록 하지 않았을 것이라고 생각한다.
2.
함수의 용도와 목적에 부합하지 않는다.
•
언제나 설계를 할 때는 해당 설계의 용도와 목적이 있다.
•
GNL 함수의 경우 이후 남은 과제에 활용하게 될 libft에 이식하게된다.
◦
앞으로 libft에 이식된 GNL을 이용하면서 수 만개 이상의 파일을 동시에 열 가능성이 존재하는가?
→ 필자는 해당 가능성에 대해서 “없다" 라고 생각했다.
•
어떤 것을 충족하기 위해서는 어떤 것을 내어줘야한다.
◦
GNL에서 가변길이 자료구조와 OPEN_MAX를 통한 풀이에서는 ‘효율성'과 ‘극한의 환경’ 이 그 문제이다.
→ 일반적인 용도 내에서 활용하게 될 GNL에 대해서 활용에 있어 가능성이 희박한 경우에 대해 대응하는 코드를 작성하여 굳이 무겁게 동작하도록 할 이유가 있을까?
•
그래서 필자는 만약 GNL을 아주 많은 파일을 열고 사용하는 환경에서 활용해야한다면 마치 int를 벗어나는 범위의 수를 다룰 때 long long 을 활용하는 것처럼 해당 환경에 알맞는 GNL을 별도로 작성하는 것이 올바르다고 생각한다.
그래서 결론...
•
개인적인 생각으로는 해당 과제를 OPEN_MAX 가 아닌, 가변길이 자료구조를 활용하여야’만’ 옳은 풀이라는 의견에는 공감할 수 없었고, 위와 같은 이유로 GNL은 OPEN_MAX를 통해서 풀이하는 것이 보다 좋은 풀이라고 생각된다.
•
하지만 함수에 어떤 자료구조를 사용해야하는가, 시스템에서 제한하고 있는 file descriptor의 개수 등이 있다는 것에 대해서 깊게 생각해볼 수 있는 좋은 기회가 되었다.
다른 의견이 있으시다면 자유롭게 댓글 남겨주세요!
