데이터 패킹

이 실습은 데이터 패킹에 관한 실습입니다.

데이터를 더 효율적으로 패킹하면 애플리케이션의 메모리 트래픽을 줄일 수 있습니다. 그 방법으로는 다음과 같은 것들이 있습니다.

컴파일러가 추가한 패딩을 제거합니다.
메모리를 덜 차지하거나 정밀도가 낮은 타입을 사용합니다. 예: (int -> short, double -> float).
비트필드를 사용하여 데이터를 한층 더 패킹합니다.

참고 1: 데이터 패킹 요약(Data Packing Summary) 영상에서는 분기 예측 실패를 이 실습의 주요 병목으로 언급합니다. 분기 예측 실패의 주된 원인이었던 std::sort가 계수 정렬(counting sort)로 대체되었으므로 이는 더 이상 사실이 아닙니다.

참고 2: 비트필드는 구현에 따라 다르게 동작합니다. 영상에서 제시한 풀이를 Windows에서 실행하면 구조체의 크기가 예상보다 크다는 것을 알 수 있습니다. 이는 서로 다른 타입의 비트필드를 함께 패킹하지 않는, 문서화되지 않은 Microsoft 고유의 동작 때문입니다. Zen 플랫폼에서 성능 테스트를 통과하려면 이 점을 고려하십시오.

힌트

힌트 1:

구조체에서는 항상 크기가 가장 큰 객체부터 먼저 선언하십시오.

힌트 2:

S의 여러 필드에 사용되는 최댓값에 주목하면 크기를 더 줄일 수 있지 않을까요? 더 나아가, 정수 필드에는 비트필드를 활용할 수 있지 않을까요?

힌트 3:

여기서 사용된 일부 정수 데이터 타입은 지정할 수 있는 비트필드 크기에 제한이 있습니다. long long, int, short, bool을 표현할 때 제약이 덜한 정수 데이터 타입을 사용하여 이들을 최적화할 수는 없을까요? 크기를 최적화한 뒤에는 가장 작은 크기가 되도록 필드를 배치해 보십시오.

이제 정렬되지 않는 비트필드를 사용하고 있으므로, 구조체의 필드를 단순히 큰 것부터 작은 것 순으로 배치한다고 해서 최적의 결과가 보장되지는 않는다는 점에 유의하십시오.

풀이:

배경:

구조체 S는 최적으로 패킹되어 있지 않습니다.

// FIXME: this data structure can be reduced in size
struct S {
  int i;
  long long l;
  short s;
  double d;
  bool b;

  bool operator<(const S &s) const { return this->i < s.i; }
};

위와 같은 상태에서는 다음 위치에 추가 패딩이 있습니다.

int i와 long long l 사이에 4바이트
short s와 double d 사이에 6바이트
bool b 뒤의 7바이트 꼬리 패딩

이로 인해 17바이트의 추가 패딩이 생기며, 결과적으로 sizeof(S) = 40 바이트가 됩니다.

해결책

핵심 아이디어는 클래스에서 가장 큰 데이터 멤버를 먼저 선언하여 크기를 최소화하는 것입니다.

struct S {
  long long l;
  double d;
  int i;
  short s;
  bool b;

  bool operator<(const S &s) const { return this->i < s.i; }
};

이 구조체는 끝에만 크기 1의 패딩이 있으므로, 여기서는 sizeof(S) = 24입니다.

실제로는 비트필드를 사용하여 이보다 더 개선할 수 있습니다.

실습의 입력 데이터를 살펴보면, int i와 short s에 전달될 수 있는 가장 큰 값이 99라는 것을 알 수 있습니다. 7비트 폭의 정수는 0부터 127까지의 수를 표현할 수 있으므로, int i를 일반적인 32비트(4바이트) 대신 uint8_t(8비트)에 해당하도록 만들 수 있고, short s 역시 (16비트 대신) 7비트로 줄일 수 있습니다.

같은 논리로, 이 두 수를 곱해 l의 값을 구하므로 l은 10,000을 넘지 않는다는 것을 알 수 있습니다. 따라서 l은 16비트 폭으로 줄일 수 있습니다. double 또한 나눗셈에서 고려하는 범위에 비해 너무 큰 데이터 타입이므로 float로 대체할 수 있습니다.

불리언 필드는 단순히 1비트로 만들 수 있습니다.

비트필드를 사용한 버전은 다음과 같습니다.

struct S {
  long long l:16;
  float d;
  int i:7;
  short s:7;
  bool b:1;

  bool operator<(const S &s) const { return this->i < s.i; }
};

이렇게 하면 최종적으로 sizeof(S) = 16 바이트의 객체가 만들어지며, bool b 뒤에 2바이트의 패딩만 남습니다.

실제로는 이보다도 더 개선할 수 있습니다. 모든 정수 값은 unsigned에 들어갈 수 있으므로, long long을 unsigned로 바꾸면 크기를 16비트 대신 14비트로 줄일 수 있습니다(2^14 - 1 = 16383 > 10000이며, 10,000은 우리가 다루는 S::l의 최댓값입니다). 이를 통해 크기를 더 줄일 수 있습니다.

struct S {
  unsigned l:14;
  unsigned i:7;
  unsigned s:7;
  bool b:1;
  float d;

  bool operator<(const S &s) const { return this->i < s.i; }
};

이렇게 배치하면 최종 크기는 sizeof(S) == 8 바이트가 됩니다.

해결책 코드(링크):

해법 링크