때로는 성급한 최적화도 재미있다 (2025)

 (invlpg.com)
1P by GN⁺ | ★ favorite | 댓글 1개
  • 연결성 모니터링 시스템의 ICMP Echo Request 기록 구조체를 줄이는 과정에서 링 버퍼 메모리 사용량이 12KiB에서 4KiB로 감소함
  • sent_ns와 received_ns를 모두 저장하지 않고 수신 후에는 지연 시간만 남기도록 공용체를 쓰자 배열 크기가 8KiB로 줄어듦
  • 나노초 정밀도 대신 100마이크로초 단위를 쓰고 received를 비트필드로 바꿨지만, 구조체 패딩 때문에 추가 절감은 발생하지 않음
  • 소스 주소 대신 ICMP identifier의 일부 의미를 4비트 카운터로 대체하면서 구조체가 8바이트로 줄고 512개 배열이 4KiB가 됨
  • 애플리케이션은 메모리 제약이 없었기 때문에 실용적 필요는 없었지만, 필드 배치와 비트 접근 비용까지 따지는 최적화 실험이 됨

문제 설정: ping 기록을 저장하는 방식

  • 연결성 모니터링 시스템은 여러 서버에 ICMP Echo Request를 보내고, 1분·5분·15분 구간의 지연 시간과 패킷 손실 평균을 관찰함
  • 처음 떠올린 저장 방식은 512개 엔트리의 링 버퍼이며, 각 엔트리는 송신 시각, 수신 시각, 소스 주소, 시퀀스 번호, 수신 여부를 담음
  • 초기 구조체 배열 pings_rb[512]의 크기는 12KiB로 측정됨
struct ping_timestamp {
    uint64_t sent_ns;
    uint64_t received_ns;
    in_addr_t source_addr;
    uint16_t seq_no;
    bool received;
};

첫 번째 절감: 송신 시각과 경과 시간을 공용체로 통합

  • 실제로 남기고 싶은 값은 수신 이후의 received - sent 지연 시간이므로, 송신 시각과 경과 시간을 동시에 보관할 필요가 없음
  • sent_ts와 elapsed_ts를 공용체로 묶은 구조체는 같은 슬롯을 송신 전에는 송신 시각으로, 수신 후에는 경과 시간으로 사용함
  • 이 변경 뒤 512개 배열 크기는 12KiB에서 8KiB로 줄어듦
struct ping_timestamp_2 {
    union {
        uint64_t sent_ts;
        uint64_t elapsed_ts;
    };
    in_addr_t source_addr;
    uint16_t seq_no;
    bool received;
};

두 번째 시도: 정밀도 축소와 비트필드

  • ping 시간은 수십·수백·수천 밀리초 단위로 측정되므로 나노초 정밀도를 모두 저장할 필요가 없음
  • 시간 단위를 100마이크로초, 즉 0.1ms 단위로 바꾸면 43비트로 최대 20년 동안의 ping 추적이 가능함
  • received의 참·거짓 값에 8비트를 쓰는 것은 과하므로 비트필드를 적용함
  • 하지만 ping_timestamp_3의 배열 크기도 8KiB로 유지되어 추가 절감이 발생하지 않음
struct ping_timestamp_3 {
    uint64_t sent_or_elapsed_ts: 43;
    uint64_t received: 1;
    uint64_t seq_no: 16;
    in_addr_t source_addr;
};

구조체 패딩 때문에 줄어들지 않은 크기

  • ping_timestamp_2는 마지막에 정렬 요구사항을 맞추기 위한 패딩 바이트가 붙음
  • ping_timestamp_3는 첫 8바이트에 시간, 수신 여부, 시퀀스 번호를 넣지만, 뒤에 소스 주소와 패딩이 남음
  • 비트필드를 적용했어도 36비트의 패딩이 남아 구조체 전체 크기가 줄지 않음
  • 단순히 bool을 비트로 줄이는 것만으로는 메모리 배치와 정렬 문제를 해결하지 못함

소스 주소 제거와 4비트 카운터

  • 제품이 모바일 데이터 네트워크에서 동작하는 동안 소스 주소가 자주 바뀌기 때문에 기존 구조체는 소스 주소를 보관함
  • 주소가 바뀔 때 시퀀스 번호도 재설정되며, 과거에는 서로 다른 소스 주소와 같은 시퀀스 번호를 가진 패킷이 동시에 처리된 적이 있음
  • ICMP Echo Request에는 애플리케이션이 자신이 보낸 패킷을 식별할 수 있는 16비트 identifier 필드가 있음
  • 전체 16비트를 모두 쓸 필요가 없으므로, 남는 4비트를 소스 주소 변경 시 증가하는 롤링 카운터로 사용함
  • 이 카운터는 애플리케이션의 다른 위치에서 감시되는 소스 주소 변경에 맞춰 증가함
struct ping_timestamp {
    uint64_t elapsed_or_sent_ts : 43;
    uint64_t received : 1;
    uint64_t counter: 4;
    uint64_t seq_no: 16;
};

최종 결과와 필드 배치

  • 최종 구조체는 소스 주소 필드를 제거하고 64비트 안에 시간, 수신 여부, 카운터, 시퀀스 번호를 담음
  • 512개 링 버퍼 배열 크기는 4KiB가 되어 한 페이지 데이터로 줄어듦
  • 초기 12KiB 대비 총 8KiB를 절감함
  • 필드 순서는 seq_no가 16비트 경계에 맞도록 조정되어, 로드 시 시프트 없이 단일 ldrh 명령으로 읽을 수 있음
  • elapsed_or_sent_ts를 읽을 때는 마스크만 필요함

추가 최적화: 수신 비트 접근 비용 줄이기

struct ping_timestamp {
    uint64_t elapsed_or_sent_ts : 43;
    uint64_t counter: 4;
    uint64_t not_received : 1;
    uint64_t seq_no: 16;
};

결론

  • 최적화 결과는 메모리 사용량을 12KiB에서 4KiB로 줄였지만, 애플리케이션 자체는 메모리 제약을 받지 않음
  • 실제 필요성과 별개로 구조체 레이아웃, 패딩, 비트필드, 명령어 수준 접근 비용을 따져보는 실험이 됨
  • 마지막 주석에서는 “문제”라는 표현도 느슨하게 쓴 것이며, 벤치마크조차 하지 않았다고 밝힘

함께 보면 좋은 글 β

GN⁺   [-]
Lobste.rs 의견들

  • 이런 문제를 생각해보는 게 더 이상 재미없어지는 날이 오면, 그날이 프로그래밍을 그만둘 때라고 봄

  • 성급한 최적화는 언제나 재미있음
    그 최적화가 왜 성급했는지 깨달은 뒤에 생기는 결과를 처리하는 일은 보통 재미없지만

    • 맞음. 나중에 발목 잡을 수 있다는 걸 알아서 스스로 말려야 하는데, 그래도 재미있어서 하게 됨

  • 타임스탬프에 43비트를 쓴다는 부분이 좀 헷갈림. 24비트면 충분해 보임
    512개짜리 링 버퍼를 말하는 걸 보면 2초마다 새 ping을 보내고, 최근 17분 4초 동안의 ping을 추적하는 것으로 보임
    첫 단계로 이상적인 타이머/순번 대비 델타 인코딩을 쓰면 됨. 마지막 전송 시간을 2초씩 증가시키고 링 버퍼 인덱스를 보면 패킷이 언제 보내져야 하는지 쉽게 알 수 있으니, 정확히 제시간에 보냈는지, 0.1ms 늦었는지, 2.3ms 늦었는지 등을 기록하면 됨
    경과 시간도 ping이 그 뒤에는 만료될 테니 17분 4초를 넘길 필요가 없어 보임. 512 × 2s = 10,240,000 × 100μs라서 그 정밀도에서는 약 23.3비트면 충분하고, 원하면 24비트로 올리면 됨. 남는 유효하지 않은 비트 패턴 약 6,536,216개도 다른 용도로 쓸 수 있을지 모름
    덤으로 24비트면 “전송됨” 정밀도를 훨씬 높여 양자화 오차를 줄일 수 있음. 마이크로초 정밀도에서도 ping이 최대 16초 늦게 보내질 수 있으니 충분히 넉넉해 보임
    샘플을 64비트에서 48비트로 줄였을 때 성능에 도움이 될지 방해가 될지는 모르겠음. x86과 ARM의 32비트/64비트 환경마다 결과가 달라도 놀랍지 않음

    • AArch64, AArch32(아마 ARMv5부터), 최신 x86-64는 모두 비트 필드 추출/삽입 명령이 있고, 그게 없어도 비용은 작음
      다만 원래 크기도 꽤 오래된 프로세서의 데이터 캐시에 아주 쉽게 들어갈 수준이라, 메모리 절약이 차이를 만들 것 같지는 않음

  • 우리가 성급하게 최적화하는 이유가 바로 그거라고 확신함. 재미로 하는 스포츠임

  • 시스템을 설계하거나 저수준 시스템 언어로 작업할 때 성급한 최적화는 솔직히 가장 좋아하는 일 중 하나임
    최소한 나중에 시간과 메모리를 아껴줄 거라는 희망이 있음. 중간쯤 되는 결과는 “왜 이렇게 만들었지?”를 파악하느라 두통이 조금 더 심해지는 정도이고, 최악의 경우이자 때로는 오히려 나은 경우는 설계 중 최적화 작업이 너무 커져서 프로젝트 자체를 못 하게 되는 것임. “아, 너무 꼬였는데 이걸 왜 하지?” 하고 프로그램을 닫게 됨

답변달기