Arrays, Strings & Memory Layout

1. Overview

배열, 문자열 및 메모리 레이아웃(Arrays, Strings & Memory Layout, ASL)은 데이터 구조의 가장 밑바닥에 위치한 '물리적 실체'를 다루는 학문입니다. 모든 고차원 자료구조는 결국 메모리의 연속된 공간에 비트를 어떻게 배치하느냐에서 시작됩니다.

컴퓨터의 램(RAM)은 거대한 일차원 배열과 같습니다. 학습자는 인덱스(Index) 연산이 왜 $O(1)$이라는 경이로운 속도를 내는지 그 수리적 주소 계산 원리를 배웁니다. 또한, 문자의 나열인 문자열이 메모리에서 \0(Null)으로 끝날지, 길이를 앞에 적을지에 따른 설계 철학과, 데이터가 인접해 있을 때 CPU 캐시가 폭발적으로 성능을 높여주는 **캐시 지역성(Cache Locality)**의 물리학을 심도 있게 다룹니다. 이를 통해 '공간'을 어떻게 나누어 써야 '속도'를 얻을 수 있는지에 대한 감각을 확보합니다.

2. Scope & Boundaries

In-Scope

• Physical Array Layout: 1차원 및 다차원 배열의 행/열 중심(Row/Column-major) 메모리 사상
• String Representations: C-style (Null-terminated) vs Pascal-style (Length-prefixed) vs UTF-8 레이아웃
• Dynamic Arrays: 정적 할당의 한계를 넘는 리사이징(Resizing) 및 분할 상환(Amortized) 비용 분석
• Memory Alignment: 성능 최적화를 위한 바이트 정렬과 패딩(Padding) 물리

Out-of-Scope

• 고수준 리스트 추상화(예: Python List, Java ArrayList)의 API 사용법 상세
• 정렬이나 검색 알고리즘 (04-03-XX 알고리즘 영역으로 위임)

Boundaries

• ASL vs. Pointer Logic: ASL이 '데이터가 놓인 모양새'에 집중한다면, 포인터 로직(04-01-02)은 '데이터를 가리키고 연결하는 선술'에 집중하여 구분합니다.

3. Counterexample

• 단순히 "리스트를 만드는 법"이라 설명하는 것은 ASL 학습이 아닙니다. 왜 다차원 배열을 순회할 때 루프의 안팎을 바꾸는 것만으로도 수십 배의 성능 차이가 발생하는지 '캐시 라인(Cache Line)' 점유 물리 관점에서 증명할 수 있어야 하며, 문자열 복사 시 Deep Copy와 Shallow Copy의 차이가 물리적 램(RAM) 점유와 수명(Lifetime)에 어떤 파급력을 주는지 설명하지 못한다면 ASL의 정수를 놓친 것입니다.

4. Prerequisites

• Bare-metal Memory Mapping (Basic): 텍스트, 데이터, 힙, 스택의 하드웨어 배치 기초가 필수입니다. (02-05-01 BMM)
• Central Processing & CPU Physics (Recommended): 캐시 계층 구조 이해가 권장됩니다. (02-01-01 CPP)

5. Learning Map

1. The Grid Logic: 주소와 오프셋만으로 데이터를 즉시 찾아내는 수리적 정렬을 배웁니다.
2. Dynamic Expansion: 좁은 공간을 탈출하여 더 큰 땅(Memory)으로 이사하는 물리적 리사이징을 익힙니다.
3. The String DNA: 0과 1의 조합이 어떻게 인간의 언어(String)로 사상되고 기록되는지 분석합니다.
4. Locality Mastery: 데이터 비트를 따닥따닥 붙여 CPU가 한 번에 읽어 들이게 만드는 캐시 친화적 배치를 완성합니다.

6. Learning Topics

Basic

Core: 정적 배열의 물리적 가동 원리 (Static Array Physics)

• Why to Learn: 모든 자료구조의 최소 단위인 $O(1)$ 접근성을 수리적으로 증명하기 위함입니다.
• What to Learn:
  • Address Calculation: Base + (Index * Element_Size) 수리 모델
  • Random Access: 인덱스 번호가 물리적 오프셋으로 직결되는 하드웨어 기작
  • Bounds Checking: 배열 범위를 벗어날 때 발생하는 메모리 오염의 물리적 위험
• How to Learn:
  • 배열의 주소를 한 칸씩 옮기며 실제 메모리 값이 어떻게 4바이트(int)나 8바이트(double)씩 변하는지 디버거로 관찰 실습
  • 10만 개의 요소를 가진 배열에서 첫 번째와 마지막 요소를 읽을 때의 물리 소요 시간 동일성 검증
• Implement: 배열의 인덱스를 주소 연산으로 직접 계산하여 값을 도출하는 기초 함수

Recommended

Core: 가변 배열과 분할 상환 분석 (Dynamic Array Mechanics)

• Why to Learn: 미리 크기를 정할 수 없는 실전 데이터에 대응하기 위한 물리적 확장력을 얻기 위해서입니다.
• What to Learn:
  • Reallocation Strategy: 기존 데이터를 새 큰 공간으로 통째로 옮기는 물리 시퀀스
  • Growth Factor: 1.5배 혹은 2배씩 늘려가는 전략에 따른 공간/시간 효율성 비교
  • Amortized $O(1)$: 가끔 발생하는 무거운 복사 비용을 평탄하게 나누는 수리 기법
• How to Learn:
  • 배열이 꽉 찼을 때 새 메모리 블록을 할당하고 복사하는 과정을 단계별로 덤프하여 관찰 실습
  • 수천 번의 삽입을 수행하며 전체 소요 시간을 측정하고, 확장 시점의 튀는 지점(Spike) 분석
• Implement: 용량이 초과될 때 자동으로 2배 확장되는 자신만의 Vector 자료구조

Practical

Core: 문자열 레이아웃과 인코딩 물리 (String Internals)

• Why to Learn: 텍스트 처리가 앱 성능의 절반을 차지하며, 인코딩 오류가 물리적 데이터 파손을 부르기 때문입니다.
• What to Learn:
  • Terminating Physics: Null 문자가 갖는 물리적 경계 의미와 오버플로우 위험성
  • Memory Compaction: 짧은 문자열(Small String Optimization, SSO)의 스택 직접 배치
  • Immutable Strings: 문자열을 바꾸지 않고 새로 만드는 방식의 메모리 단편화 영향
• How to Learn:
  • "Hello" 문자열이 메모리 상에서 실제 16진수 바이트로 어떻게 적히는지(ASCII/UTF-8) 확인 실습
  • 문자열 끝에 Null이 누락되었을 때 printf가 메모리 속을 영원히 헤매는 현상 재현
• Implement: 두 문자열을 합치는 루틴에서 메모리 할당과 복사 횟수를 최소화하는 최적화 코드

Advanced

Core: 캐시 지역성과 데이터 지향 설계 (Data-Oriented Layout)

• Why to Learn: 현대 컴퓨팅 성능의 병목은 연산이 아니라 '메모리로부터 데이터를 가져오는 물리 지연'에 있기 때문입니다.
• What to Learn:
  • Spatial Locality: 주변 데이터를 한꺼번에 캐시로 불러오는 하드웨어 특성
  • Structural Alignment: CPU가 한 번에 읽기 편하도록 데이터 구조체에 패딩을 넣는 이유
  • AOS vs SOA: 배열의 구조체(Array of Structures)와 구조체의 배열(Structure of Arrays) 간 캐시 효율 비교
• How to Learn:
  • 큰 행렬을 행(Row) 방향으로 읽을 때와 열(Column) 방향으로 읽을 때의 캐시 미스 횟수 차이 측정 실습
  • 데이터 구조체에서 변수 순서만 바꿔도 전체 램 점유량이 줄어드는 물리적 현상 검증
• Implement: 데이터 처리를 위해 캐시 라인(64bytes) 크기에 맞춰 정렬된 고성능 데이터 버퍼

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Computing Foundations / Data Structure Basics — Array and layout fundamentals.
• [P1] CS2023 - SDF/Fundamental Data Structures (Arrays) — Core requirements.

Secondary

• [Introduction to Algorithms (CLRS)] Cormen — Formal analysis of arrays.
• [The Art of Computer Programming, Vol 1] Knuth — Fundamental algorithms and layouts.

Industry

• [Intel: Optimization Reference Manual (Memory Layout)] — Hardware-specific alignment strategies.
• [CPP Reference: std::vector and contiguous storage] — Real-world dynamic array spec.

9. Final Checklist

Primary

• 배열의 특정 인덱스에 접근할 때 왜 '상수 시간($O(1)$)'의 물리적 연산만 필요한지 수리적으로 설명 가능한가? (P1)
• 문자열이 메모리에 적재될 때 '인코딩(Encoding)' 방식에 따라 각 문자가 차지하는 물리 바이트 수가 왜 달라지는지 입증할 수 있는 가? (P1)

Secondary

• **캐시 미스(Cache Miss)**가 빈번하게 발생하는 배열 접근 패턴이 시스템 전체 성능을 왜 수십 배까지 깎아먹는지 소통 가능한가?
• 정적 배열과 동적 배열 사이에서 '메모리 파편화(Fragmentation)'가 발생하는 물리적 시나리오를 도출할 수 있는 가?

Industry

• 고성능 게임 엔진이나 금융 시스템 설계 시, 왜 'Array of Structures(AOS)'보다 'Structure of Arrays(SOA)'가 CPU 연산 효율 면에서 유리한지 제안할 수 있는 가? (SFIA)
• 임베디드 장치에서 램 공간을 아끼기 위해 구조체 패딩(Padding)을 최소화하는 '비트 필드(Bit field)' 적용의 물리적 손익을 기술할 수 있는 가?