이진검색을 활용하여 결함을 유발하는 커밋 찾기 (Git Bisect)

leetcode에서 278. first bad version 이라는 문제를 풀다가 이 문제가 git 명령어인 git bisect의 구현과 일맥상통한다는 것을 깨달았다. git bisect를 살펴보면 이진 검색이 실제로 어떻게 활용되는지 알 수 있어 이진 검색에 대해 더 깊은 이해가 가능하다.

이 글에서는 1. 이진 탐색이 무엇인지 2. git bisect는 어떻게 사용하는지 3. git bisect 내부 구현은 어떻게 되어있을지 first bad version 문제를 통해 추론해보고 마지막으로 4.정리해보자.

1. 이진 검색이란

이진 검색이란

• 이진 검색은 정렬된 값들 중에서 원하는 값을 찾기 위해 범위를 절반씩 줄여가며 값을 찾아가는 방식이다.
• 숫자가 오름차순으로 정렬된 배열에서 26을 찾는다고 할때 이진 검색으로 찾는 방법을 수도 코드로 표현해보면 다음과 같다.

1. 배열의 중앙에 있는 값을 확인한다
2. 만약 값이 26이라면
3.    그 인덱스를 반환한다
4. 그렇지 않고 만약 값이 26보다 작다면
5.    그 뒷부분 배열의 중앙에 있는 값을 확인한다
6.    2번째 줄부터 반복한다
7. 그렇지 않고 만약 값이 26보다 크다면
8.    그 앞부분 배열의 중앙에 있는 값을 확인한다
9.    2번째 줄부터 반복한다
10. 그렇지 않으면(탐색할 범위가 더이상 없다면)
11.   그만둔다

선형 검색과 비교해서 장점

선형검색과 이진 검색은 best case의 경우에 모두 O(1) 시간 복잡도를 가진다. 하지만 worst case의 경우에 선형검색은 모든 값을 확인해야해서 O(N) 복잡도를 가지지만 이진 검색은 최대 LogN개의 값만 확인하면 되어 O(LogN)시간 복잡도를 가지게 된다. 이진 검색은 입력값의 크기인 N이 클수록 선형 검색에 비해 탐색 속도가 빨라진다. 입력값의 크기가 100,000,000(1억개)이라고 했을때 선형 검색은 최대 1,000,000번을 탐색해야 하지만 이진 검색은 최대 27번만 탐색하면 된다.

주의할 점

• 이진 검색이 선형 검색에 비해 더 효율적인 알고리즘이긴 하지만 언제나 이진 검색이 더 좋은 선택인 것은 아니다. 이분탐색은 배열이 정렬되어 있어야한다는 조건이 있기 때문에 입력 데이터가 처음부터 정렬되어 주어지는 경우나 탐색을 여러번 해야 할 때 사용하기 좋다. 탐색을 한번만 하게 되는 경우라면 굳이 시간복잡도가 O(NlogN)인 정렬을 하고서 이진 검색을 하는게 더 느린 방법이다.

파라매트릭 서치(Parametric Search)

• 파라매트릭 서치는 이분 탐색과 매우 유사하지만 문제 유형에 따라 이분 탐색이 아니라 파라매트릭 서치를 사용할 수 있어야 한다. 정확히 그 값을 찾는 이진 검색과 달리 파라매트릭 서치는 문제 상황을 만족하는 변수의 최솟값, 최댓값을 구하는 문제에 사용된다.
• 파라매트릭 서치란 문제 상황을 만족하는 변수의 최솟값, 최댓값을 구하는 최적화 문제를 Yes, No로 답할 수 있는 결정 문제로 바꾸어 푸는 것이다.
• 더 쉽게 이해하기 위해 예를 들어보자. 나이순으로 정렬된 사람들이 있다. 이 중에서 나이가 26살이 사람을 찾는다면 이분 탐색을 찾으면 된다. 하지만, 나이가 26이상인 사람 중 가장 어린 사람을 찾는다면 파라매트릭 서치를 사용하면 된다. 파라매트릭 서치는 정 가운데 사람이 나이가 26 이상인지 살펴보고 26 이상이라면(Yes) 왼쪽 사람들을 대상으로, 26 미만이라면(No) 오른쪽 사람들을 대상으로 다시 26이상인지 살펴보며 나이가 26미만인 사람과 26이상인 사람의 “경계”를 찾아나가는 것이다.

2. git bisect 사용법

git bisect이란

• 한마디로! 문제가 된 커밋을 빠르게 찾기위해서 사용하는 git 명령어이다 . 제품에 버그가 발견되었는데 “엥? 이게 언제부터 이렇게 되어 있었지? ㅠㅠ 분명히 잘 작동했었는데?” 하면서 커밋 하나씩 되돌아가면서 일일이 확인해 본 적이 있을거다. 커밋이 몇 개 없다면 일일이 확인할 수 있지만 아주 오래 전에 발생한 버그인데 발견하지 못한 채 그 위에 차곡차곡 커밋을 쌓아왔다면 문제가 된 그 커밋!을 찾는데에만 오랜 시간이 소요될 수 있다. 그럴때 사용하라고 git에서 제공하는 기능이 ⭐️git bisect⭐️이다.
• 그럼 이제 어떻게 사용하는지 살펴보자

# git bisect 세션을 시작
$ git bisect start

# 결함이 존재하지 않음이 확인된 커밋 정보를 입력
$ git bisect good 49c747d

# 결함이 존재함이 확인된 커밋 정보를 기술한다. 일반적으로, HEAD 즉 가장 최근 커밋을 사용.
$ git bisect bad HEAD

# git이 이진검색을 하며 절반에 해당하는 커밋으로 전환(checkout)하면
# 사용자가 코드나 산출물을 검사하여 해당 버전이 "good" 혹은 "bad"인지 확인한다
$ git bisect good 혹은 $ git bisect bad

# 위의 내용을 결함을 유발시킨 최초의 버전을 찾을때까지 반복한다
# git bisect reset을 실행하여 bisect세션을 종료하면, HEAD로 복귀한다
$ git bisect reset

• 그럼 git bisect은 얼마나 빠를까?
  • 만약 내가 마지막으로 기억하고 있는 버그 없이 돌아가는 버전을 1이라고 하고 그 후로 100개의 커밋을 쌓아왔다고 가정해보자(100개의 커밋이 생각보다 많지 않다. 10명의 팀원이 매일 하나씩 커밋을 한다고 했을때 10일만 지나도 100개의 커밋이 쌓이게 된다). 100번째 커밋을 하고 나서 테스트를 했는데 버그가 발견되었다고 해보자.
    • 하나씩 되돌아가면서 확인해보니 28번째 커밋에서 수정한 코드가 문제를 일으킨 것이었다. 총 72개의 커밋을 확인해야 했다.
    • 만약 git bisect을 통해 확인했다면? 총 7개의 커밋만 확인한 후 28번째 커밋에서 문제가 생겼다는걸 알아낼 수 있다.
  • 만약 2번째 커밋에서 문제가 발생했다고 하면 일일이 돌아가면서 98개의 커밋을 확인하는 것보다는 git bisect을 통해 7번의 커밋만 확인하는게 훨씬 빠르다.

⇒ 이제 버그가 생긴 커밋을 찾을때 git bisect을 이용하는게 효율적이라는 것을 알게 되었을것이다.

3. first bad version 문제를 통해 git bisect 내부 구현 추론

그럼 이제 git bisect은 어떻게 구현되어있을지 알아보자. 이를 위해서는 leetcode의 278.first bad version 문제를 참고할 수 있다.

278.first bad version

• 버전을 의미하는 int 배열이 오름차순으로 정렬되어있고, 특정 버전 이후는 모두 badVersion일때 첫번째 badVersion을 찾는 문제이다. 예를 들어 [1,2,3,4,5] 버전이 있고 4,5가 badVersion일때 4를 반환해야 하는 문제이다.

First Bad Version - LeetCode

• 이는 나쁜 버전 중 최소값을 찾는 최적화 문제이며, 나쁜 버전인지 확인하는 내부 API isBadVersion()은 True/False를 반환하는 결정 문제라고 볼 수 있다. 따라서 이 문제는 파라메트릭 서치로 풀 수 있다.

first bad version과 git bisect과의 비교

• first bad version에서의 버전은 git의 commit으로 볼 수 있다. git의 커밋은 시간 순서대로 쌓이기 때문에 오름차순 정렬된 형태이다. 또 버그를 포함하는 커밋을 bad version이라고 한다면 그 이후의 커밋은 모두 bad version이 된다. 즉 [good,good,bad,bad,…bad]형태가 되는 것이다. 즉 버그를 해결하기 위해서는 첫 bad version을 찾기 위해서 파라매트릭 서치를 해야한다.

4. 정리

• 가장 좋은 방법은 테스트를 자동화해서 버그가 발생하는 즉시 발견하고 해결하는 것이다. 이는 버그가 발생한 것을 모르고 지나쳐 다른 부분에도 영향을 미쳐 큰 결함을 발생시키는 것을 미리 방지할 수 있고, 결함이 생긴 시점을 찾아내기 위해 비용이 들지 않기 때문이다.
• 그렇지만 미처 테스트 코드를 작성하지 못한 부분에서 버그가 발생했고 어디서 발생했는지 찾아야 한다면 git bisect을 통해서 빠르게 찾을 수 있을 것이다.
• 또 명령어 사용법만 알고 사용할 수도 있겠지만, 내부에 어떻게 구현되어있을지 고민해보면 후에 왜 그런 방식으로 사용해야하는지 더 쉽게 이해할 수도 있고, 비슷한 문제를 해결해야 할때 해결책을 빠르게 생각해낼 수 있을 것이다.