<div id="readability-page-1" class="page"><div aria-label="Content">
        <p><a href="https://sangwoo-joh.github.io/">..</a></p><center>

<h2>Embarassingly Obvious</h2>
</center>
<hr>

<p>최애 언어로 문제를 풀어보는 시리즈긴 한데… 정식 시리즈는 아니고
 쉬어가는 에피소드 정도 되겠다.</p>

<h3 id="대체-왜-런타임에러가-났던걸까">대체 왜 런타임에러가 났던걸까?</h3>
<p>예전 <a href="https://sangwoo-joh.github.io/ocaml-ps-word-count">포스팅</a> 에서
 풀었던 1152번 문제가 불현듯 떠올랐다. 입력으로 문자열을 받을 때
 <code>read_line</code>으로 받았더니 <strong>런타임에러</strong>가 떠서 실패했던 기억이
 있다. 아쉽게도 런타임에러 메시지를 악용하면 채점 테스트케이스를 알 수
 있기 때문에 백준 사이트에서 이를 제공해주진 않지만, 이 런타임에러는
 내가 짠 로직에서 발생한 게 아니라는 생각 정도는 가지고 있었다. 그러다
 얼마전 불현듯 “대체 그 런타임에러는 뭐였을까?” 라는 생각이 떨쳐지지
 않아 끝까지 파헤쳐보기로 했다.</p>

<h3 id="scanf는-에러가-안뜨네">Scanf는 에러가 안뜨네?</h3>
<p><code>read_line</code> 함수가 하는 일은 단순하다. 입력으로 들어오는 모든
 문자열을, 공백까지 포함해서 계속 쭉 읽어들이다가, 처음으로 줄바꿈
 문자가 나오는 순간 거기서 작업을 멈추고 그때까지 읽은 문자열을
 돌려주는 친구다.</p>

<p>좀 찾아보니 <code>Scanf</code>에서 포맷 형식을 지정하면 이것과 완전히 동일한
 일을 할 수 있겠더라: <code>Scanf.scanf "%[^\n]"</code> 로 읽어들이면, <code>[ ]</code> 안에
 있는 정규표현식에 맞춰서 입력을 읽어들인다. 그래서 간단하게 <code>^\n</code>, 즉
 <em>줄바꿈 문자 말고 전부 다</em> 읽도록 하면 된다.</p>

<p>놀라운 건 이렇게 입력 함수만 바꿨을 뿐인데 예전에 런타임에러가 떠서
 실패했던 코드가 그대로 통과했다. 분명히 <code>read_line</code>에 버그가
 있어보였다.</p>

<h3 id="디스커스-커뮤니티에-물어보기">디스커스 커뮤니티에 물어보기</h3>
<p>어떤 언어를 쓰다가 모르는게 생겼을 때는 보통 그 언어 사용자나
 개발자가 주로 모이는 커뮤니티에 물어보는 것이 국룰이다. 다행히
 얼마전부터 OCaml에도 <a href="https://discuss.ocaml.org/">커뮤니티</a>가 생겨서
 종종 눈팅을 하곤 했었는데, 이 기회에 여기에 질문을 올려보기로 했다.</p>

<p>하지만 질문은 잘 하는 게 중요하다. 대체 이 현상을 뭐라고
 질문해야할까? 일단 <code>"[^\n]"</code> 로 <code>Scanf</code> 하면 잘 통과한다는 사실까진
 알아냈으니, 이걸 정리해서 <a href="https://discuss.ocaml.org/t/how-different-is-the-behaviour-of-read-line-and-scanf-scanf-n/6564"><code>read_line</code> 과 <code>Scanf.scanf "%[^\n]"</code>
 함수의 동작이 얼마나
 다른가요?</a>
 라는 글을 작성했다.</p>

<p>사실 커뮤니티가 생기긴 했지만, 크게 기대하지 않았다. 그런데 한 착한
 해커분께서 직접(!) 백준 사이트에 가입해서, 1152번 문제를 똑같은
 코드로 풀어본 뒤, 이것저것 테스트해보다가 <code>Gc</code>를 한번이라도 건들면
 <code>read_line</code>을 쓰더라도 런타임에러가 나지 않는다는 사실을
 발견했다. 그리고 더불어 채점 버전인 4.07.0 버전의 바이트코드
 컴파일러의 가비지 콜렉션에 버그가 있다는 것도 알려줬다. 오호. 슬슬
 해결의 실마리가 보이는듯 했다.</p>

<h3 id="당황스러울-정도로-명백한">“당황스러울 정도로 명백한”</h3>

<p>과연 찾아보니 <a href="https://github.com/ocaml/ocaml/pull/1896">Major GC Crash를 수정하는
 PR</a>을 확인할 수
 있었다. 수정한 개발자의 한 코멘트가 인상적이었다: “The fix is
 <strong>embarassingly obvious.</strong>” 코드를 살펴보니 정말 딱 한줄
 수정했더라. <code>caml_fl_allocate</code> 라는 함수가 정확히 뭘 하는진
 모르겠지만 (아마도 free list에 뭔가 할당하는 함수이지 않을까…),
 상수 크기의 버퍼를 만들고 반복문에서 그 버퍼에 뭔가를 저장하는데, 이
 버퍼의 인덱스를 넘어버리는 버퍼 오버플로우가 있었던 것이다. 아마도
 <code>read_line</code>이 동작할 때 이 함수와 상호작용하다가 터진 게 아닐까?</p>

<p>여기까지 알아냈으면 내가 할 수 있는 일은 좁혀졌다.</p>
<ul>
  <li>일단 <code>ignore (Gc.get ()) ;</code> 과 같은 우회 코드를 삽입해서
<code>read_line</code>을 쓰거나, 아니면 <code>Scanf.scanf</code>를 쓰거나 해서 문제는
계속 풀 수 있다. <code>Scanf.scanf</code> 쪽이 좀 더 느리긴 하지만.</li>
  <li>채점 컴파일러에 버그가 있는게 명백하니, 업그레이드를
요청해야겠다. 겸사겸사 바이트 코드로 컴파일하는 현재의 컴파일
커맨드를 네이티브 코드로 바꿔달라고도 해야겠다.</li>
</ul>

<h3 id="백준-만세">백준 만세</h3>
<p>백준 온라인 저지 사이트의 기능 요청을 받는
 <a href="https://github.com/startlink/boj-feature-request">깃허브</a>가
 있더라. 여기에 정성스럽게
 <a href="https://github.com/Startlink/BOJ-Feature-Request/issues/186">이슈를</a>
 <a href="https://github.com/Startlink/BOJ-Feature-Request/issues/188">올렸다</a>. 지금
 쓰이는 컴파일러 버전에 심각한 버그가 있으니 올려주세요. 네이티브
 컴파일 해주세요. 더불어 자바랑 유사하니까 시간 제한 좀 늘려주세요.</p>

<p>그리고 인고의 기다림 끝에 드디어!!! 백준 온라인 저지에 모든 것이
 반영되었다. 백준 만만세! 이제 백준 사이트에서는</p>
<ul>
  <li>OCaml 4.11.1 버전을 사용하며,</li>
  <li><code>ocamlopt -O2</code> 커맨드로  네이티브 코드 컴파일이 된다.</li>
</ul>

<p>그리고 백준님께서 테스트해본 결과 네이티브 코드의 속도가 충분히
 빨라서 자바와 같은 시간/메모리 제한을 할 필요는 없어보인다고 답글을
 달아주셨다. 비록
 <a href="https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/ocaml-java.html">벤치마크</a>에서는
 대부분 자바에 시간은 밀리긴 했지만, 메모리 사용량은 일단
 월등했다. 그래서 직접 예전 시간초과로 실패했던 몇몇 문제를 그대로
 제출해보니, 과연 잘 통과하더라.</p>

<p>역시 네이티브 코드 컴파일러야. 성능 확실하구만.</p>

<h3 id="마무리">마무리</h3>
<p>오랜만에 재밌었다. 사실 그냥 넘어갈 수도 있었는데, “대체 왜
 런타임에러가 나지?” 라는 궁금증을 도저히 떨칠 수 없어서 시작한 일이
 결국 채점 컴파일러까지 업그레이드하게 되었다.  친절하게 답변해준
 OCaml 커뮤니티와 백준님께도 감사의 마음을 표한다. 뉴비들에게 친절한
 커뮤니티는 항상 옳다.</p>

<p>이제 찬찬히 단계 별로 문제를 풀어보도록 해야지.</p>









      </div></div>

Caml Shaving

Sangwoo Joh

최애 언어로 문제를 풀어보는 시리즈긴 한데… 정식 시리즈는 아니고
 쉬어가는 에피소드 정도 되겠다.
대체 왜 런타임에러가 났던걸까?
예전 포스팅 에서
 풀었던 1152번 문제가 불현듯 떠올랐다. 입력으로 문자열을 받을 때
 read_line으로 받았더니 런타임에러가 떠서 실패했던 기억이
 있다. 아쉽게도 런타임에러 메시지를 악용하면 채점 테스트케이스를 알 수
 있기 때문에 백준 사이트에서 이를 제공해주진 않지만, 이 런타임에러는
 내가 짠 로직에서 발생한 게 아니라는 생각 정도는 가지고 있었다. 그러다
 얼마전 불현듯 “대체 그 런타임에러는 뭐였을까?” 라는 생각이 떨쳐지지
 않아 끝까지 파헤쳐보기로 했다.
Scanf는 에러가 안뜨네?
read_line 함수가 하는 일은 단순하다. 입력으로 들어오는 모든
 문자열을, 공백까지 포함해서 계속 쭉 읽어들이다가, 처음으로 줄바꿈
 문자가 나오는 순간 거기서 작업을 멈추고 그때까지 읽은 문자열을
 돌려주는 친구다.
좀 찾아보니 Scanf에서 포맷 형식을 지정하면 이것과 완전히 동일한
 일을 할 수 있겠더라: Scanf.scanf "%[^\n]" 로 읽어들이면, [ ] 안에
 있는 정규표현식에 맞춰서 입력을 읽어들인다. 그래서 간단하게 ^\n, 즉
 줄바꿈 문자 말고 전부 다 읽도록 하면 된다.
놀라운 건 이렇게 입력 함수만 바꿨을 뿐인데 예전에 런타임에러가 떠서
 실패했던 코드가 그대로 통과했다. 분명히 read_line에 버그가
 있어보였다.
디스커스 커뮤니티에 물어보기
어떤 언어를 쓰다가 모르는게 생겼을 때는 보통 그 언어 사용자나
 개발자가 주로 모이는 커뮤니티에 물어보는 것이 국룰이다. 다행히
 얼마전부터 OCaml에도 커뮤니티가 생겨서
 종종 눈팅을 하곤 했었는데, 이 기회에 여기에 질문을 올려보기로 했다.
하지만 질문은 잘 하는 게 중요하다. 대체 이 현상을 뭐라고
 질문해야할까? 일단 "[^\n]" 로 Scanf 하면 잘 통과한다는 사실까진
 알아냈으니, 이걸 정리해서 read_line 과 Scanf.scanf "%[^\n]"
 함수의 동작이 얼마나
 다른가요?
 라는 글을 작성했다.
사실 커뮤니티가 생기긴 했지만, 크게 기대하지 않았다. 그런데 한 착한
 해커분께서 직접(!) 백준 사이트에 가입해서, 1152번 문제를 똑같은
 코드로 풀어본 뒤, 이것저것 테스트해보다가 Gc를 한번이라도 건들면
 read_line을 쓰더라도 런타임에러가 나지 않는다는 사실을
 발견했다. 그리고 더불어 채점 버전인 4.07.0 버전의 바이트코드
 컴파일러의 가비지 콜렉션에 버그가 있다는 것도 알려줬다. 오호. 슬슬
 해결의 실마리가 보이는듯 했다.
“당황스러울 정도로 명백한”
과연 찾아보니 Major GC Crash를 수정하는
 PR을 확인할 수
 있었다. 수정한 개발자의 한 코멘트가 인상적이었다: “The fix is
 embarassingly obvious.” 코드를 살펴보니 정말 딱 한줄
 수정했더라. caml_fl_allocate 라는 함수가 정확히 뭘 하는진
 모르겠지만 (아마도 free list에 뭔가 할당하는 함수이지 않을까…),
 상수 크기의 버퍼를 만들고 반복문에서 그 버퍼에 뭔가를 저장하는데, 이
 버퍼의 인덱스를 넘어버리는 버퍼 오버플로우가 있었던 것이다. 아마도
 read_line이 동작할 때 이 함수와 상호작용하다가 터진 게 아닐까?
여기까지 알아냈으면 내가 할 수 있는 일은 좁혀졌다.
일단 ignore (Gc.get ()) ; 과 같은 우회 코드를 삽입해서
read_line을 쓰거나, 아니면 Scanf.scanf를 쓰거나 해서 문제는
계속 풀 수 있다. Scanf.scanf 쪽이 좀 더 느리긴 하지만.
채점 컴파일러에 버그가 있는게 명백하니, 업그레이드를
요청해야겠다. 겸사겸사 바이트 코드로 컴파일하는 현재의 컴파일
커맨드를 네이티브 코드로 바꿔달라고도 해야겠다.
백준 만세
백준 온라인 저지 사이트의 기능 요청을 받는
 깃허브가
 있더라. 여기에 정성스럽게
 이슈를
 올렸다. 지금
 쓰이는 컴파일러 버전에 심각한 버그가 있으니 올려주세요. 네이티브
 컴파일 해주세요. 더불어 자바랑 유사하니까 시간 제한 좀 늘려주세요.
그리고 인고의 기다림 끝에 드디어!!! 백준 온라인 저지에 모든 것이
 반영되었다. 백준 만만세! 이제 백준 사이트에서는
OCaml 4.11.1 버전을 사용하며,
ocamlopt -O2 커맨드로  네이티브 코드 컴파일이 된다.
그리고 백준님께서 테스트해본 결과 네이티브 코드의 속도가 충분히
 빨라서 자바와 같은 시간/메모리 제한을 할 필요는 없어보인다고 답글을
 달아주셨다. 비록
 벤치마크에서는
 대부분 자바에 시간은 밀리긴 했지만, 메모리 사용량은 일단
 월등했다. 그래서 직접 예전 시간초과로 실패했던 몇몇 문제를 그대로
 제출해보니, 과연 잘 통과하더라.
역시 네이티브 코드 컴파일러야. 성능 확실하구만.
마무리
오랜만에 재밌었다. 사실 그냥 넘어갈 수도 있었는데, “대체 왜
 런타임에러가 나지?” 라는 궁금증을 도저히 떨칠 수 없어서 시작한 일이
 결국 채점 컴파일러까지 업그레이드하게 되었다.  친절하게 답변해준
 OCaml 커뮤니티와 백준님께도 감사의 마음을 표한다. 뉴비들에게 친절한
 커뮤니티는 항상 옳다.
이제 찬찬히 단계 별로 문제를 풀어보도록 해야지.

OCaml과 함께 PS를… 하다가 세그폴트가?

댓글