Go 언어로 구현된 새로운 Diff 라이브러리, 성능과 가독성을 모두 잡다!
저자는 기존 Diff 라이브러리의 제한적인 기능(Limited Functionality), 특히 텍스트 외의 데이터 지원 부족에 불만을 제기함
새로운 Go Diff 라이브러리 znkr.io/diff는 임의의 시퀀스(Arbitrary Sequences) 지원, 다양한 출력 형식, 단순한 API, 우수한 성능을 목표로 설계됨
Myers 알고리즘을 기반으로, 성능 최적화(Performance Optimization)를 위해 전처리, 휴리스틱, 후처리 기법을 적용함
Diff 가독성 향상을 위해 Michael Haggerty의 들여쓰기 휴리스틱(Indentation Heuristic)을 선택적으로 적용하여, 더 나은 결과물을 제공함
Diff 알고리즘의 복잡성과 성능 트레이드오프
저자는 대부분의 Diff 라이브러리가 Myers 알고리즘을 사용하지만, 최악의 경우 𝒪(N^2)의 시간 복잡도를 갖는다는 점을 지적한다. 특히, 유사성이 낮은 대규모 입력 데이터의 경우 성능 저하가 발생할 수 있다. 이러한 문제를 해결하기 위해, 저자는 전처리, 휴리스틱, 후처리 기법을 활용하여 성능을 개선했다. 예를 들어, 고유 요소 제거(Unique Element Removal)를 통해 런타임을 최대 99%까지 줄였다고 언급한다.
가독성을 위한 Diff 결과 최적화
Diff 알고리즘은 여러 개의 최소 Diff 결과를 생성할 수 있으며, 이 중 인간이 이해하기 쉬운 결과를 선택하는 것이 중요하다. 저자는 Michael Haggerty의 들여쓰기 휴리스틱(Indentation Heuristic)을 통해 Diff 가독성을 향상시켰다. 이 기법은 Diff 결과의 들여쓰기를 조정하여 코드 변경 사항을 더 명확하게 보여준다. 또한, 저자는 znkr.io/diff 라이브러리에서 이 기능을 선택적으로 사용할 수 있도록 했다.
znkr.io/diff 라이브러리의 API 설계
znkr.io/diff 라이브러리는 임의의 시퀀스를 지원하고, 다양한 출력 형식을 제공하며, 단순한 API를 갖도록 설계되었다. 특히, Edits 및 Hunks 함수를 통해 구조화된 Diff 결과를 반환하며, Func 접미사를 사용하여 사용자 정의 비교 함수를 제공한다. 또한, 텍스트 Diff를 위한 Unified 함수를 textdiff 패키지에 제공하여 텍스트 기반 Diff(Text-based Diff)를 간소화했다.
성능 향상을 위한 전처리, 휴리스틱, 후처리 기법
저자는 Myers 알고리즘의 성능을 개선하기 위해 다양한 기법을 적용했다. 전처리 단계에서는 공통 접두사 및 접미사를 제거하고, 고유 요소를 제거하여 입력 데이터의 크기를 줄였다. 휴리스틱 기법으로는 Anchoring, Good Diagonal, Too Expensive 기법을 사용하여 최악의 경우 시간 복잡도를 개선했다. 후처리 단계에서는 들여쓰기 휴리스틱을 적용하여 Diff 가독성을 향상시켰다. 이러한 기법들을 통해 성능과 가독성(Performance and Readability)을 모두 잡으려 노력했다.
