▲

C에서 타입 세이프(Generic)한 자료구조 작성법

 (danielchasehooper.com)
3P by GN⁺ 7일전 | ★ favorite | 댓글 2개
  • 이 글은 C 언어에서 타입 세이프(Generic)한 자료구조를 만드는 새로운 방법을 설명함
  • union을 활용해 타입 정보를 자료구조에 연관시키는 기법으로, 링크드 리스트 구현을 예시로 설명함
  • 기존 C 제네릭 패턴(매크로, void 포인터, Flexible Array Member)과 차별점과 각 방식의 단점을 비교함
  • 컴파일 타임 타입 체크가 가능해서 잘못된 타입 사용을 미리 막을 수 있음
  • 새로운 기법은 foo_list와 같이 명확하고 일관된 함수/자료구조 인터페이스를 제공함

서론

  • C 언어에서 제네릭 자료구조를 타입 안정성 있게 만드는 방법에 대해 소개함
  • 이 기법은 union을 사용해 타입 정보를 컴파일 타임에 자료구조에 연결함
  • 지도(Map), 배열, 바이너리 트리 등 모든 자료구조에 적용할 수 있으며, 예시로 기본 링크드 리스트 구현을 통해 설명함
  • 많은 개발자들이 C에서 제네릭이 불가능하다고 생각하므로, 단계별로 쉽게 설명을 진행함

전통적인 매크로 기반 제네릭

  • C에서 제네릭 자료구조 구현의 전통적 방식은 매크로를 이용하여 구조체와 함수의 이름, 타입을 생성함
  • 자료구조 헤더를 여러 타입에 대해 여러 번 include하는 식으로 확장함

예시:

  • 타입에 맞는 구조체와 함수명을 생성하기 위해 매크로(예: CONCAT, NODE_TYPE, PREPEND_FUNC) 사용
  • 각 타입별로 함수와 구조체가 따로 생성되어, int와 Foo 같은 타입 각각 별도의 자료구조 정의가 나옴

단점:

  • 타입 및 함수 정의 위치 파악이 어려움 (매크로로 생성되어 추적이 힘듦)
  • 코드 자동완성 기능 활용이 어렵고
  • 동일 함수 여러 개 생성으로 바이너리 크기 및 빌드 시간 증가
  • 함수 이름에 타입 접두사 필요 (예: Foo_list_prepend)

제네릭 단계 1: void 포인터 방식

  • 자료구조의 데이터 타입을 *void 로 두어 타입에 무관하게 만듦
  • 링크드 리스트의 data 필드를 void *로 선언
  • 타입 체크가 불가능하므로 런타임에 타입 오류가 발생할 수 있음, 컴파일 타임의 안전성 낮음
  • 메모리 및 캐시 활용 비효율: 노드와 데이터가 따로 할당되어 불필요한 오버헤드 및 캐시 미스 증가

제네릭 단계 2: 인라인 스토리지(Flexible Array Member)

  • Flexible Array Member(유연 배열 멤버) 를 활용, 포인터 저장 대신 데이터 자체를 노드에 함께 저장
  • 노드 하나당 한 번의 할당으로 충분하며, 캐시에 데이터와 next 포인터가 인접하게 위치함
  • 이 방식은 memcpy와 같은 크기 정보 전달이 필요하나, 일관된 메모리 배치로 성능이 개선됨
  • list_alloc_front 함수를 이용하면 memcpy 없이 구조체를 직접 초기화할 수 있음

제네릭 단계 3: 타입 체크 구현

  • union의 payload 멤버에 파라미터화된 타입 포인터를 선언하여 컴파일 타임에 자료구조에 타입 정보 추가
  • 예) #define List(type) union { ListNode *head; type *payload; }
  • 이렇게 하면 typeof(foo_list.payload) 로 해당 리스트의 타입을 얻을 수 있음
  • 매크로(list_prepend)에서 함수 타입 캐스팅을 통해, 올바른 타입이어야만 컴파일 가능
  • 잘못된 타입 사용 시 컴파일 타임에 에러 발생

에러 예시:

  • foo_list에 int를 추가 시, 'incompatible integer to pointer conversion' 컴파일 에러 메시지가 출력됨

typeof 미지원 컴파일러 대응

  • C23 이전까지 __typeof__는 표준이 아니므로 일부 컴파일러(예: 구버전 MSVC)에서는 동작하지 않음
  • struct 내 payload 멤버 활용 등 우회방법으로 비슷한 효과 가능

파라미터 전달 및 typedef

  • 동일한 형태의 List(Foo)도 컴파일러는 서로 다른 타입이라 판단함
  • typedef 사용 시, 매개변수 전달 및 대입이 원활해짐

예시:

  • typedef List(Foo) ListFoo;
  • ListFoo 변수 선언 및 함수 매개변수로 사용 가능

마무리 및 다양한 자료구조 확장

  • 이 기법은 여러 타입 파라미터가 필요한 자료구조(예: 해시맵)에도 활용 가능
  • union을 통해 key, value 각각의 타입 안전성을 보장 가능
  • 더 자세한 실습 및 매크로 구현체는 관련 코드 gist 링크 참고

결론

  • 새로운 방식은 기존 방식의 단점(가독성, 빌드 효율성, 유지보수성)을 극복하고, 일관성 있는 함수 명명 체계와 타입 안전성 제공함
  • 여러 자료구조 및 복수 타입 파라미터 지원이 용이함
  • 컴파일 타임 타입 체크를 통해 제네릭 자료구조 사용의 안전성과 효율성을 동시에 확보함

감사의 말

  • 이 글은 Martin Fouilleul의 피드백 및 격려를 받아 완성함
▲
click 7일전  [-]

간단하게 Zig 쓰면 되는거 아닌가? 하는 의문점이 들긴 합니다

답변달기
▲
GN⁺ 7일전  [-]
Hacker News 의견

  • 2단계 코드에서 uint64_t data[]; 사용 방식은, 정렬 요구사항이 uint64_t보다 큰 타입에는 적합하지 않고, 반대로 작은 타입엔 불필요하게 낭비라는 점 지적, 예를 들어 64비트 아키텍처의 ilp32 ABI에선 더 문제가 됨. 3단계 코드에선 int main() { List(Foo) foo_list = {NULL}; 이렇게 해야 한다는 의견 전달. typeof가 없는 상황에선 반환값을 돌려주지 못하며, 대체 코드의 경우 const 관련 오류가 발생할 수 있고, == 연산자 대칭성 때문에 이런 문제가 부각됨. payload를 빼면 크기 정보가 없어 안전하지 않음, 예를 들어 List(int64_t)에 int32_t를 추가하면 괜찮을 것 같지만, 실제 int32_t의 크기 판단 불가. 더 안전하게 하려면 보완이 필요하다는 이야기. C에서 제네릭 사용에 있어 두 가지 큰 한계가 있다고 생각, 첫째 vtable 위임 방식이 구조체가 매크로를 포함할 수 없어 기능 제한, 둘째 외부 vtable로 위임할 땐 사용할 타입 전부를 미리 선언해야 한다는 점. 가장 좋은 방법은 typedef 선언이 들어있는 헤더에서 정적 함수만 선언하는 것인데, GCC와 Clang이 각기 다르게 undefined static 경고를 내는 타이밍이 다르다고 부연 설명. 마지막엔 서로 다른 버퍼 구조체를 받는 함수 설계 사례를 예로 들며, const 버전까지 전부 관리가 필요하다는 점 강조

    • 외부 vtable 위임 이슈에 대해, 예전 프로젝트에서 직접 이걸 해결하기 위해 컴파일러까지 만든 경험 공유, 아파치 Clownfish 프로젝트에서 시작할 때 .h 파일 파싱하다가 결국 클라운피시 헤더(.cfh)라는 자체 포맷을 만듦. 실제 obj의 "Clone" 메서드를 호출하는 코드를 예시로 보여주며, 객체 지향 기능이 필요한 동적 언어 바인딩을 위해 이런 무리한 코드를 대량 생성해야 했던 경험 소개. Clownfish의 목적이 최저 공통 객체 모델 제공이었고, 바인딩 언어 타입도 .cfh에서 생성함. 이런 복잡성 때문에 대다수가 void* 캐스팅으로 타입 안전성을 포기하고 있다고 덧붙임. https://github.com/apache/lucy-clownfish

    • int main()에 관해, C에서 int main()은 인수 개수 미정임을 뜻함. int main(void)로 선언해야 인수가 없다는 뜻이 됨. 많은 C++ 작성자들이 자주 잊는 사실이라고 강조

    • union이 연합(union)되는 구조를 기대, 즉 한 타입이 다른 타입의 union 일부로 자신을 선언 가능했으면 좋겠다는 의견

    • malloc 할 때 내부 padding 문제 때문에 계산된 크기가 실제보다 작을 수 있다는 점 지적, 예를 들어 malloc(sizeof(*node) + data_size); 같이 했을 때 위험성 제기

  • 트릭#0 내용을 반박, 자신이 C의 전체 방언을 만들 때 이 트릭을 사용했음. 예를 들어 generic binary heap 구현 예시 코드 공유 https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h. 문법은 다소 무겁지만 최종적으로는 일반적인 C 구조체가 되어 최적화와 예측 가능성에 큰 이득이 있음. 다른 구현에선 void*와 런타임 메모리 사이징, 매크로 정의가 불가피하다고 봄

    • 글쓴이로서, binary heap과 linked list는 목적이 다름을 설명. binary heap은 저장 시 데이터를 읽어야 하기 때문에 접근이 다르며, generic binary heap 작성 시엔 선택이 다를 수 있음을 밝힘. 본문 각주에서도 언급했다고 부연

    • 헤더 구현 선호 이유 여러 가지 제시. 디버깅할 때 매크로 함수보다 코드 추적 및 타입 정보 활용이 쉬움. 컴파일러가 각 인스턴스마다 monomorphized 최적화가 가능해 런타임 비용이나 가변 크기 부담 없음. 스택에 generic 구조체를 둘 수 있음. 저자가 언급한 문제점 두 가지는 우회 가능, 함수명 매크로로 이름을 쉽게 바꿀 수 있고, weak symbol 활용해 링크 시 이중 정의를 자동으로 합칠 수도 있음. 포인터 타입 generic 컨테이너엔 또 다른 문제가 있지만, typedef 등으로 해결 가능. C에서 intrusive data structure가 여전히 편하나, 디버깅은 어렵다는 생각

    • "컴파일러가 도넛 먹듯 먹는다"는 표현에 크게 웃음 터짐

  • 함수 타입 변환 시, 예를 들어 Foo와 void의 내부 표현이 동일하다고 가정하는데, 표준 C에서는 보장되지 않음. 타입 간 호환성("compatible")이 없는 상황에서 이런 캐스팅은 정의되지 않은 동작으로 이어질 수 있음. 컴파일러가 alias 분석 등에서 영향을 받을 수도 있다고 (참고 링크 동봉) https://news.ycombinator.com/item?id=44421185

    • 본문 각주에 언급되어 있고, 캐스팅이 타입 안전성 핵심은 아니라는 주장. 전체 글을 읽어보길 권함

  • "C에서 generics 쓰려면 왜 이런 무리수를 두는가, 그냥 C++ 쓰면 되는 것 아닌가"라는 질문

    • 안전 기준과 기타 요구 때문에 레거시 프로젝트에서는 C++로의 마이그레이션이 당장 불가능한 경우가 많다는 경험 공유. 새로운 프로젝트는 표준을 정해 C++을 도입하지만, 기존 프로젝트는 당분간 C를 유지해야 한다고 봄. 단순히 "그냥 C++ 쓰지"라는 시각이 좀더 맥락에 따뜻했으면 한다는 의견

    • 실제로, C를 쓰는 현장에선 C++로 전환하는 게 더 복잡하고 문제를 많이 야기할 수 있음

    • 반대로, 약간의 노력만으로 C에서 같은 결과를 얻을 수 있는데 굳이 C++까지 갈 필요가 없다는 입장 전개

  • 리눅스 커널에서 실제로 사용하는 방식 소개, 리스트 정보를 담은 struct list_head를 타입별 구조체 안에 포함시키는 패턴. 관련 참고 링크 제공 https://kernelnewbies.org/FAQ/LinkedLists

    • 리눅스 커널의 LIST_HEAD_INIT, INIT_LIST_HEAD 라는 매크로 명칭이 직관적이지 않다고 느낌

  • "typeof on old compilers" 섹션 코드에서 (list)->payload = (item);는 실은 no-op이 아니라, 리스트 헤드가 item으로 덮어써진다는 지적. 예상한 동작이라면 if(0)로 감싸야 하다는 제안

    • 예제에서는 union을 struct로 바꿨던데, 이 역시 낭비로 보임. if(0) 안에서 처리하는 편이 더 나아 보인다는 의견

  • D 언어에서는 이런 generic list 구조가 훨씬 간단함을 보여주며, C의 프리프로세서는 마치 손톱에 망치질하는 느낌, 못질에는 Nail gun이 훨씬 빠르고 깔끔하다는 은유로 C 매크로의 불편함을 강조

    • 해당 게시글은 C에 대한 것이고, 일부 프로젝트에서는 반드시 C를 써야 한다는 입장 밝힘

  • union과 typeof()를 활용하는 아이디어가 흥미로움. 본인의 경우 intrusive 자료구조에서는 결국 대형 매크로로 감싸는 래퍼가 필요하다고 느꼈고, union과 typeof로도 이런 구현이 가능한지 의문 제기. 예시로 hash table 래퍼 구현 코드와 문서 링크 공유 https://github.com/FRRouting/frr/blob/master/lib/typesafe.h#L823-L971 https://docs.frrouting.org/projects/dev-guide/en/latest/lists.html

  • 개인적으로 이미 실험적 라이브러리에서 이 기법을 쓰고 있다는 공유 https://github.com/uecker/noplate/blob/main/src/list.h

    • intrusive 구조체, 즉 데이터에 노드 구조를 포함해서 객체가 여러 컨테이너에 동시에 속할 수 있는 방법에 대한 아이디어를 문의

  • 함수 포인터의 타입을 활용해 타입 안전성을 확보한다는 개념이 핵심으로 보임, 흔히 사용하는 핸들 타입 대신 이렇게 구현. C23 표준에서는 타입 호환 문제가 개선됐으며, 해당 표준 문서와 최신 GCC/Clang 지원 상황 공유 https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3037.pdf

    • 글쓴이로서, 핵심 아이디어는 union을 이용해 generic 데이터 타입에 타입 정보를 연동하는 것임을 강조, 함수 캐스팅만이 방법이 아니라 여러 대안을 논의했고, footnote와 "typeof on old compilers"에도 자세히 다뤘음을 언급
답변달기