https://www.acmicpc.net/problem/5639

이 문제 하나로 기나긴 여정이 시작되었다.

주의! 본문에 위 문제에 대한 솔루션이 일부 포함됨

tl;dr

1. 자바스크립트로 PS 하는 않는 것을 감히 권장드립니다.
2. JS는 파라미터가 무겁습니다. 재귀를 짤 때 조심하십시오.

문제를 제기해주신 J님, 도움을 주신 서강대학교 ICPC 학회원님들, SGCC 동아리원님들 모두 감사합니다.

파라미터 개수 때문에 틀렸다고?

위 백준 문제의 가장 간단한(?) 풀이는 post-order traverse를 사용한다. 그런데 이걸 node, 즉 자바스크립트로 재귀함수를 만들어 제출하면, 파라미터가 있냐 없냐에 따라서 AC 여부가 갈리는 것이 확인되었다.

런타임 에러 (StackSizeExceeded) 코드

다음은 "RangeError: Maximum call stack size exceeded" 에러가 나서 실패하는 코드의 일부다.

// vis: 방문한 노드 체크하는 객체 (사실 없어도 됨)
// res: 출력하기 위해 방문한 순서대로 기록하는 배열
// nodes : 모든 노드 정보를 담은 중첩 객체. 노드 값으로 인덱싱
// cur : 현재 방문 중인 노드의 값
function traverse(vis, res, nodes, cur) {
  if (nodes[cur].left) traverse(vis, res, nodes, nodes[cur].left);
  if (nodes[cur].right) traverse(vis, res, nodes, nodes[cur].right);
  if (!vis[nodes[cur].self]) {
    vis[nodes[cur].self] = true;
    res.push(nodes[cur].self);
  }
  return res;
}

4개의 파라미터 중 앞 세 개는 object 타입이므로, 함수 내에서 파라미터 자체에 새 값을 할당하지 않는 이상 reference로 전달된다.

cur은 숫자이므로 Number 타입일 것이다. 근데 Object이긴 함

통과 코드

아래 코드는 통과한다.

let vis = {};
let res = [];
let nodes = {};
function traverse(vis, res, nodes, cur) {
  if (nodes[cur].left) traverse(vis, res, nodes, nodes[cur].left);
  if (nodes[cur].right) traverse(vis, res, nodes, nodes[cur].right);
  if (!vis[nodes[cur].self]) {
    vis[nodes[cur].self] = true;
    res.push(nodes[cur].self);
  }
  return res;
}

'왜 파라미터 개수에 따라서 결과가 달라질까?'라는 궁금증이 생겼고, 제대로 CS를 공부하지 않은 덕에 한참을 빙빙돌아 결론에 도달할 수 있었다.

백준 채점 서버 환경

여기서 잠깐! 백준 서버가 어떤 환경에서 채점하는지 확인해보자

https://www.acmicpc.net/help/judge
https://www.acmicpc.net/help/language

...에 따르면,

프로세서 아키텍쳐: 64-bit
OS: Ubuntu 16.04.6 LTS
실행: node Main.js
버전: v14.15.0
시간 제한: ×3+2 초
메모리 제한: ×2 MB

원인은 바로 v8의 call stack size

여러 고민 지점이 있었고, 굉장히 많은 구글링과 고찰이 있었으나 결국 정리하면 이는 콜 스택 사이즈 때문이다.

백준에서 언어 선택지로 제공하는 NodeJS는 내부적으로 V8 엔진을 사용하여 자바스크립트 코드를 구동한다. 그런데 v8은 아래 사진에서 보이듯이 heap 영역과 stack 영역이 다르다.

(이미지 출처 : SO

그래서 맨 처음의 코드를 실행하면 다음과 같은 일이 벌어진다.

• 재귀 함수가 호출될 때마다 해당 함수의 stack frame이 call stack에 queue 형태로 차곡차곡 쌓인다
  - 그런데 이 문제는 최악의 경우 10000개의 frame이 쌓인다
• 그런데 파라미터를 4개 (3 Objects, 1 Number) 넣으면 대략 6천개 정도에서 call stack size가 한계치에 도달한다.

아래는 콜 스택이 몇개의 함수를 버티는지 확인하기 위해 만든 코드다. 내 브라우저에선 6000 정도가 찍힌다.

function loop(vis, res, nodes, cur) {
  try {
    return 1 + loop(vis, res, nodes, cur + 1);
  } catch (e) {
    return 1;
  }
}
a = {};
b = [];
c = {};
const loopCnt = loop(a, b, c, 1); 
console.log(loopCnt);

그러는 와중 내 맥북에 설치된 node의 스택 사이즈가 984KB 인 것을 확인했다.

❯❯❯ node --v8-options | grep -B0 -A1 stack-size # (또는 stack_size)
  --stack-size (default size of stack region v8 is allowed to use (in kBytes))
        type: int  default: 984

그리고 파라미터를 1개로 줄이면, 가뿐히 10000 이상 쌓이는 것 또한 확인했다.

function loop(cur) {
  try {
    return 1 + loop(cur + 1);
  } catch (e) {
    return 1;
  }
}
const loopCnt = loop(1);
console.log(loopCnt); // 9665

엥? 이상하네 10000이 넘어야 하는데;;;

라고 생각하고 온갖 방법으로 서커스를 한 뒤에 로컬에 깔린 node 버전이 16.xx 인 것을 확인했다. 14.xx 에서는 10200 ~ 10500 정도가 찍힌다. 계산대로다.

Q. 엥? 어떤 글에선 백준에서 스택 메모리를 따로 제한하지 않는다고 하던데요? 그래서 로컬에서 실패하는 것도 백준 서버에서는 성공하는 경우도 있대요. (VS의 default 스택 깊이가 1000밖에 안되어서)
A. 그거에 대해선 오피셜 정보를 찾을 수가 없었습니다 (그래서 더 헤맸음 🤦‍♂️) 하지만 백준 사이트에서 node main.js로 코드를 돌려본다는 것은 오피셜하게 확인할 수 있었고, node --stack-size=10000 main.js 같은 형태로 스택 사이즈 조절이 가능하였으므로, 64bit 환경 기본값인 984KB를 쓰는 것으로 예상됩니다.
TODO: https://www.acmicpc.net/board/view/28085 이 대화가 진전되면 글 수정할 것

새로 배운 것들, 한번 더 확인한 것들

• stack과 heap은 다르다.

• (아마도) v8은 OS에 무관하게 동일한 형태로 stack frame을 저장한다. (node 버전을 똑같이 조절했을 시 ubuntu16.04, mac10.15.7에서 동일한 결과를 확인하였음)

• stack frame 사이즈 계산은 무척 어렵다. 온갖 최적화가 끼어있기도 하고, 내가 CS 지식이 너무 빈약하기도 하고... 아래는 카톡방에 공유했었던 '파라미터 조건 별 스택 프레임 사이즈' (를 추정한 값)

// X/Y = N kb (condition)

X : 984000 kb : 제 스택 메모리
Y : 저 함수의 리턴값. 몇번이나 들어갔는지 확인 가능
N : 1 stack frame의 사이즈. 얼추 규칙적으로 16bytes씩 증가. (특이하게도, cur 과 cur + 1 사이에 8kb 만큼의 차이가 발생)

984000/10470 = 93.982808 kb (cur)
984000/9665 = 101.810657 kb (cur+1)
984000/8376 = 117.47851 kb (cur & 2개 파라미터)
984000/7391 = 133.134894 kb (cur & 3개 파라미터)
984000/6613 = 148.797822 kb (cur & 4개 파라미터)
984000/5983 = 164.465987 kb(cur & 5개 파라미터)

• stack frame 사이즈 관측은 cpp 을 열어보기 전까진 불가능한 것 같다. (젯브레인 WebStorm 프로파일러까지 동원해서 어떻게 해보려고 했으나 Fail 😞)

• 정확한 이유는 모르겠으나, 파라미터를 추가하면 객체 레퍼런스의 무게인 8bytes가 아니라 16bytes 만큼 무거워진다. 스택 프레임의... 복잡한 이유가 있겠거니 싶다. (더 알아보려다 이 답변 보자마자 뒤도 안돌아보고 접음)

• JS는 primitive에 대해 pass by value, object에 대해 copy of a reference (=call by sharing)이 적용된다. SO

• PTC, TCO, STC 라는 걸 처음 들어봤다. (첫인상보다 의외로 꽤 쉬운 개념소개 링크) 참고로 지금 node 환경에선 TCO가 적용되지 않는다. (사파리에서 되므로 크롬과 사파리 각각 loop 함수 실행시켜보는 걸 추천함)

• 사람들이 '아니 왜 그렇게 집착해요' 라던가 '와ㄷㄷ' 같은 반응을 보이면 쓸데없이 더 오래 파고드는 성향이... 있는 것 같다. 참 재미있었다 ^___^

수십개의 SO, 열개 남짓한 백준 글들, 세개 정도의 v8 문서를 읽고 백번이나 똑같은 코드를 돌려가며 테스트 했던 고난이 (물론 내가 모자라서 그렇게 된거긴 한데..흠흠..) 글에 다 담기지 않은 것 같아 너무나도 아쉽다ㅠㅠ!

같이 보면 좋은 글

• https://ui.toast.com/weekly-pick/ko_20210611 : 때맞춰 JS 메모리 누수에 대한 얘기가 토스트 블로그에 올라왔다. 별로 내용적으로 유의미하게 얽혀있진 않지만 이 글보단 유익할 것 같다. 참고로 여기서 말하는 context와 내 글의 stack frame은 같은 대상 다른 표현으로 보임

• https://v8.dev/blog/adaptor-frame : 나만 당할 순 없지 v8의 스택 프레임 구조에 대한 이야기다.

• https://glebbahmutov.com/blog/javascript-stack-size : 위에 글보다 10만배쯤 쉬움

• https://2ality.com/2014/04/call-stack-size.html : TCO에 대한 짤막한 소개

• https://www.valentinog.com/blog/node-usage : node의 내장 함수 process.memoryUsage()를 사용하면 '현재' 사용중인 스택 사이즈를 확인할 수 있다. 그런데 이 함수를 호출하는 것만으로도 결과 영향이 심하게 왜곡되어서 정작 이번 경우엔 많이 활용하지 못함