Search
Duplicate
🙄

GNL OPEN_MAX vs Linked list?

간단소개
GNL에서 사용하는 자료구조에 대한 제 의견을 작성해봤습니다.
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
C
42cursus
42seoul
Scrap
태그
get_next_line
open_max
linked_list
9 more properties

가변 길이 자료구조 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의 개수 등이 있다는 것에 대해서 깊게 생각해볼 수 있는 좋은 기회가 되었다.
다른 의견이 있으시다면 자유롭게 댓글 남겨주세요!