Optimizing Bit Streaming & Buffering

오늘도 영어공부를 위해 ryg씨의 블로그에서 밀린 테크 포스트들을 읽고 있었다. 그 중 꽤 재미있는 토픽으로 쓴 글이 있어 정리해 둔다. 바로 “Buffered Centric IO”. 사실 본래 주제는 Bit I/O 이지만, 자연스럽게 I/O를 다루면서 보다 포괄적인 개념인 Buffered IO 개념이 동반되었다.

가끔 특정 포멧을 읽어들이는 Reader을 만들다 보면 신경써야 할 것들이 있다. 일단 가장 기본이 되는 스트림부터 시작해 보면 File 스트림인지, In-memory stream인지, 혹은 Deflate stream인지와 같은 것들이다. Deflate 에 Deflate를 포함한 경우면 필연지기 In-memory에서 읽기를 동반하게 되기 때문에, 고려하지 않을 수가 없다. 현실의 데이터는 너무나 조잡한 법이다. 그리고, In-memory 버퍼는 꼭 copy를 동반할 필요는 없다. 이러한 모든 고민에 대해서 속시원하게 정의하고 솔루션을 제시하는 것이 너무 좋았다.

또, “Consumer” 측에서 특별한 제약조건을 요구하는 경우가 있다. 개중 가장 대표적인 것 중 하나가 Bit-streamed consumer 같은 것일테다. 컴퓨터는 최소 8-bit(Byte) 단위로 접근 가능하고, 내부적으로는 4Byte(32bit)로 align 되어 있기 때문에 Bit 단위로 접근하는 것은 정말 까다롭기가 그지없다. 여기서는 U64를 “버퍼”로 사용하는 일종의 이중 버퍼 전략 비슷하게 구현을 했는데, 역시 남다른 내공으로 코드가 정말 깔끔하다. 거기에 asm레벨에서의 최적화와 batch processing을 고려한 극한의 최적화 방법까지 읽고 있으면, 정말 배울 게 아직 많구나 생각이 된다.

덤으로 영어공부도 열심히 했다. 이 분 특유의 미려하고 긴 부사절로 가득한 서너줄짜리 문장과 비유들을 정독하고 있으면 아직도 머리가 지끈거린다. 영어 공부는 갈길이 멀다… 😇

Links

대충 이 순서대로 읽으면 될 듯?

• https://fgiesen.wordpress.com/2011/11/21/buffer-centric-io/
  • 개인적으로 C 레벨에서의 error 처리가 꽤 흥미로웠음. 종종 쓰는 방식이긴 한데, 워낙 C가 오래된 언어니 만큼 Variant가 많아서…
• https://fgiesen.wordpress.com/2016/01/02/end-of-buffer-checks-in-decompressors/
  • 아래 글과 유사한 토픽인데, 훨씬 짧고 단순하게 다루었다. Bit 읽기에 있어서의 최적화 이야기. 좀 더 세부적으로는, EOF 체크를 하지 않았을 때(lookahead)의 장점 이야기. 그리고, Memmove가 Branch보다 쌀 수 있다는 것 (Branchless is important).
  • 전반적으로 Byte stream을 다루는 올바른 방법에 대해서 아주 세세하게 이야기하고 있어서 정말로 큰 도움이 된다.
  • Swapping buffer w/ minimum cost에 대해서도 이야기하고 있음.
  • “The net effect is one of concentrating a little complexity from several places in hot code paths (end-of-buffer checks on every byte consumed) into somewhat increased complexity in a single cold code path (buffer switching). This is often desirable.”
  • Caveats: lags behind, multiple source in a single stream
• https://fgiesen.wordpress.com/2018/02/19/reading-bits-in-far-too-many-ways-part-1/
• https://fgiesen.wordpress.com/2018/02/20/reading-bits-in-far-too-many-ways-part-2/
  • 다양한 bit stream variants 와 각각의 장단에 대해서 놀라울 정도로 상세히 설명하니 꼭! 해당 부분은 읽어보길 추천.
• https://fgiesen.wordpress.com/2018/09/27/reading-bits-in-far-too-many-ways-part-3/
  • Pipeline을 직접 묘사하면서, IPC를 최적으로 활용함의 중요성에 대해 다시 언급. 물론 초-구식 시스템 등의 특수 환경에서는 inst. throughput 그 자체가 중요할 수도 있겠지만.
  • Multiple stream (interleaved, or simple concatnation)에 대한 논의가 또한 주된 읽을 거리다. 단순 멀티코어 관점에서의 최적화가 아니다! 파이프라인 단에서 이를 최적화 한다는 것이 흥미로운 점.
  • Forwards/Backwards stream의 유래가 좀 재미있음. 다만 아직 잘 와닿지는 않는다
• https://fgiesen.wordpress.com/2018/03/05/a-whirlwind-introduction-to-dataflow-graphs/
  • 위 글들에서 중간중간 쓰인 “Dataflow graph” 에 대한 철학과, 이를 통해 실제 execution cost를 측정해 보는 것의 중요성에 대한 이야기.
  • B-tree가 왜 혁신적인 자료구조인지 이제야 좀 이해가 간다. CS시간때 제대로 설명 안해준 조교랑 교수님 탓을 할… 순 없을것 같고, 멍청한 내 탓이다. 😭
  • 여기서 친숙한 그 “loop unwinding”이 나오는데, 이렇게 보니까 왜 하는지 좀 더 확실하게 느껴진다 ㅎㅎ.
  • “this technique works and is useful at pretty much any scale… you can zoom out and use the same technique to figure out how your decomposition of an algorithm into tasklets processed by a thread pool works out.”
• https://fgiesen.wordpress.com/2021/08/30/entropy-coding-in-oodle-data-huffman-coding/
  • 글쓴이는 사실 이거 설명하려고 (…) 위의 비트스트리밍에 대한 글을 다뤘다고 하는데, 그래서 내용 자체는 그렇게 어려운 편은 아니다. 다만 이런저런 수식어가 많이 붙은 화려한 영어 문장이 좀 어려울 수는 있다. 한가지 재미있는 점은 huffman decode table을 빠르게 처리하기 위해서 일종의 “table”을 만들어서 처리한다는 점이고, 역시나 꼼꼼하게 downside와 advantage를 잘 정리해 놓은 점.
  • 덤으로, “the art of (de)compressing” 을 볼 수 있다는 것이 참으로 매력적인 부분이다. 이를테면, bit cache size를 통해 어째서 huffman symbol이 크기가 제한되어야 하는가 등.