2017-12-20

Raft - electionTimeout

broadcastTime ≪ electionTimeout ≪ MTBF
 Raft가 정상적으로 동작하기 위해서는 반드시 위의 조건을 만족해야 한다.
 electionTimeout은 leader election에서 설명한 random 한 timeout의 최대치를 의미한다. 사실 broadcastTime, electionTimeout, MTBF 중에서 사용자가 설정할 수 있는 것은 electionTimeout 뿐이다. 따라서 위의 조건을 만족시킨다는 것은 적절한 electionTimeout을 선택한다는 것이다.

 MTBF는 평균 무고장 시간(Mean time between failures)의 약자로, 한 서버가 시작한 뒤 죽기 전까지의 평균 시간을 의미한다. 보통 MTBF가 길면 availability가 높지만, availability와 일치하지는 않는다. MTBF가 길더라도 MTTR(Mean time to repair)가 길면 availability은 떨어질 수 있다.
 MTBF는 시스템의 고유한 속성이다. MTBF는 보통 노드가 하는 일의 종류와 개발자의 숙련도, 얼마나 비싼 하드웨어를 사용하는지에 따라 결정된다.
 Raft paper는 electionTimeout을 MTBF보다 작게 할 것을 권장한다. 실질적으로 MTBF는 최소 몇 주에서 몇 개월 정도 되기 때문에 electionTimeout을 이보다 더 크게 설정하는 것은 쉽지 않다. 이는 그냥 electionTimeout을 너무 크게 설정하지 말라는 정도로 받아들여도 된다. 리더가 죽은 뒤 electionTimeout 동안 client의 요청을 전혀 처리 못 하니 네트워크 전체의 availability를 올리기 위해서 가능하면 작은 electionTimeout을 설정해야 한다.

 하지만 electionTimeout을 너무 작게 설정하면 안 된다. electionTimeout은 아무리 작아도 broadcastTime보다 커야 한다. broadcastTime이란, 한 노드에서 네트워크 안의 다른 모든 노드로 보낸 요청이 처리되어 응답이 오기까지 걸린 시간의 평균을 의미한다. 이 또한 MTBF와 마찬가지로 시스템의 고유한 속성이다. 하지만 숙련된 개발자나 비싼 하드웨어를 사용하여 올릴 수 있는 MTBF와는 다르게 broadcastTime은 물리적으로 최솟값이 정해진다.
 만약 electionTimeout을 잘못 설정하여 broadcastTime보다 작게 설정한다면, follower들이 leader의 heartbeat을 듣지 못하고 자신을 candidate으로 만들어 requestVote 메시지만 전송하고 아무도 leader로 선택되지 못 하고 시간만 허비하게 된다.

 Raft paper는 broadcastTime를 0.5 ms에서 20 ms 사이의 시간이 될 것을 가정하고 쓰여 있다. 따라서 다른 지역에 존재하는 서버 사이의 consensus가 아닌 한 지역에 존재하는 서버들 사이에서의 consensus를 위한 것이다. 만약 broadcastTime이 이보다 더 긴 네트워크를 구성했다면, electionTimeout도 더 길게 선택해야 한다.
 예를 들어 AWS를 사용할 때, 서울과 오레곤 사이의 latency는 평균 120 ms정도 걸린다. 따라서 서울 지역과 오레곤 지역에 양쪽에 설치된 서버 사이의 consensus를 위해서는 electionTimeout을 120 ms보다 더 크게 설정해야 한다.

2017-12-13

Raft - consistency

 Raft는 모든 결정을 leader가 맡아서 한다. 따라서 term이 변경되기 전에는 leader의 결정을 따르면 된다. 문제는 leader에 문제가 생기거나 네트워크 파티션으로 인해 leader가 변경되고 다음 term으로 진행된 경우다.

 Consistency를 위해 가장 이상적인 것은 모든 노드가 하나의 leader만 따르도록 하는 것이다. 하지만 이는 사실상 불가능하다. 이게 가능하면 애초에 합의에 도달한 것이다. 그래서 Raft에서는 특정 시간에 2개 이상의 리더가 존재할 수 있다. 단, state를 변경시킬 수 있는 리더는 1개 밖에 있을 수 없다. 이 두 말은 별 차이 없는 것 같지만, 이 차이가 분산 환경에서 구현 가능한 시스템이 되도록 만들어준다.

 Raft에서는 leader에 커밋 된 로그만이 state를 변경시킨다. Leader가 커밋하기 위해서는 네트워크에 참여하는 노드 과반의 동의가 필요하다. 새 leader가 선출되면 과거의 leader는 절반 이상의 지지를 받지 못한다. 모든 요청에 요청하는 노드의 term이 담겨있고, 요청받은 쪽은 자신의 term보다 작은 term인 노드가 보낸 요청은 모두 거절한다. 새 leader가 선출됐다는 것은 이미 절반 이상의 노드가 다음 term으로 넘어갔다는 것이고 과거의 leader를 지지하는 노드는 절반이 되지 않기 때문에 과거 leader는 더 이상 상태를 변경시킬 수 없다. 따라서 같은 시간에 두 개의 노드가 상태를 변경시키는 것은 불가능하다.

 물론 leader가 아닌 노드들이 가지고 있는 상태는 consistent 하지 않다. 새 RequestVote를 받기 전에 과거의 leader가 보낸 AppendEntries 메시지를 받고 자신의 상태를 변경시킬 수 있기 때문이다. 하지만 네트워크의 상태는 리더에 커밋 된 로그를 기준으로 만들어지기 때문에 각 노드의 inconsitecy는 클라이언트가 보는 네트워크 상태에 영향을 주지 않는다.

 그렇다면 leader에 커밋 된 로그를 가지지 않은 노드가 leader가 되면 어떻게 될까? 다행히도 raft에서는 이런 일이 발생하지 않는다. RequestVote 메시지에는 candidate이 가지는 최신 로그의 index와 그 index가 생성된 term이 저장돼 있다. 이 index가 자신이 알고 있는 로그의 최신 index보다 작으면 이 RequestVote 요청은 거절된다. 즉, 가장 최신 로그를 가지고 있는 노드만 리더가 될 수 있고, 이 최신 로그에는 최소한 leader에 커밋 된 로그를 포함된다.

 그렇다면 leader를 포함하여 커밋 된 로그를 가진 노드가 모두 죽으면 어떻게 될까? Leader가 어떤 로그를 커밋했다는 것은 최소 과반의 노드가 이 로그를 가지고 있다는 것이다. 이 노드가 모두 죽었다는 것은 네트워크에 남은 노드가 절반이 되지 않는다는 것이고 새 candidate을 지지하는 노드가 절반 이하가 되기 때문에 새 leader를 선출할 수 없고 이후로 네트워크는 상태를 변경할 수 없다. 만약 네트워크에 과반의 노드가 살아있다고 하면, 이는 비둘기집 원리에 따라 커밋 된 로그를 가지고 있는 노드가 최소한 한 개 존재한다는 것이고, 이 노드가 leader가 되면서 consistency를 유지된다.

2017-12-08

Raft - log replication

 Raft가 가장 중요하게 생각하는 요소는 이해할 수 있는 알고리즘을 만드는 것이다. 이해할 수 있고 구현하기 쉬운 알고리즘이 Raft의 가장 중요한 요소이기 때문에 Raft는 로그를 누적시킬 수는 있지만 지울 수는 없는 append only 정책을 사용한다. Append only 정책을 사용하기 때문에 Raft의 state를 바꾸는 명령은 AppendEntries 밖에 존재하지 않는다. 사실 Raft가 정의하는 필수 RPC(Remote procedure call)은 지난번 글에서 설명한 RequestVote와 이번에 설명할 AppendEntries 뿐이다. leader가 보내는 heartbeat은 빈 entry를 추가하는 AppendEntries 메시지이다.

 Client가 state를 변경하자고 leader에게 요청하면, leader는 새로운 로그를 만든다. 하지만 이 로그는 아직 state를 변경시킨 것은 아니다. Leader는 새 entry를 커밋하라고 follower들에게 AppendEntries 메시지를 보낸다. follower는 AppendEntries 메시지를 받으면 각자의 스토리지에 받은 로그를 커밋하고 leader에게 답변을 보낸다. Leader는 과반의 follower가 로그를 커밋했다는 메시지를 받으면, 자신도 로그를 커밋한다. 이렇게 leader에 log가 커밋된 뒤에야 state가 성공적으로 변경된 것이고, 클라이언트에게 요청이 처리됐다고 응답을 보낸다.

 AppendEntries 메시지는 follower가 가져야 할 로그들을 담고 있다. follower는 각자 저장하고 있는 로그의 상태가 다르기 때문에 follower들에게 보내야 할 로그의 양도 전부 다르다. 이는 leader가 nextIndex라는 이름으로 각 follower에 어떤 로그를 보낼지 저장하고 있다가 메시지를 보낼 때 사용된다. Follower가 할 일은 leader가 보낸 로그를 저장할 수 있는지 보고 leader에게 응답을 보내준다.

 Follower는 AppendEntries에는 새로 추가할 log 이외에도 이미 follower가 저장했을 거라고 생각하는 prevLogIndex와 prevLogTerm을 같이 보낸다. Follower는 해당하는 index의 로그가 prevLogTerm일 경우 이 로그는 저장할 수 있는 로그다. 만약 prevLogIndex에 해당하는 log가 존재하지 않거나, prevLogTerm에 생성된 로그가 아니면 이 로그는 현재 leader가 가지고 있는 로그가 아니므로 유효하지 않다. 이 경우 prevLogIndex를 포함한 그 이후 모든 로그를 지우고 leader에게 저장할 수 없었다고 알린다. 그러면 leader는 전에 보냈던 index보다 작은 index의 로그를 포함하는 새 AppendEntries를 보낸다.

 Log를 저장할 수 있는 경우. 즉, prevLogIndex에 해당하는 로그를 가지고 있고, 이 로그가 prevLogTerm에 생성된 경우. follower는 leader가 보낸 로그를 저장하고 저장했다는 사실을 leader에게 알린다. 이때 follower가 이미 prevLogIndex 이후의 로그를 가지고 있었다면, 이 로그를 전부 지우고 leader가 보낸 로그로 덮어쓴다. 모든 state 관리를 leader에게 맡기고, leader의 state를 그대로 따르기 위해서다.
 Raft의 log replication은 leader가 commit 한 로그는 다음 term이 되어도 롤백 되지 않는 것을 보장한다. Term의 변경은 네트워크에 문제가 생겼을 때 발생하므로, 쉽게 말해 Raft는 CAP theorem에서 말하는 CP category에 분류된다. 이에 관해서는 다음 글에서 자세히 설명하도록 하겠다.

2017-12-05

Raft - leader election

 Raft에서는 모든 결정을 leader가 한다. 클라이언트의 모든 요청은 리더를 통해서만 가능하고, 새로운 로그를 추가하는 것도 새로운 노드가 추가되거나 기존의 노드를 지우는 것도 리더를 통해서 결정된다. leader의 명령을 따르는 노드들은 follower라고 하는데 follower들은 leader의 명령을 그대로 따른다. Follower는 leader가 보낸 명령에 따라 자신의 상태를 변경하고, 새로운 클라이언트가 접속하면, 클라이언트에게 어떤 노드가 리더인지 알려준다. Raft에서는 의도적으로 follower가 할 수 있는 일이 별로 없도록 만들었고 덕분에 프로토콜을 단순하게 만들 수 있었다.

 Leader인 노드는 일정 주기로 follower들에 heartbeat을 보낸다. follower들은 leader의 heartbeat을 듣고 있다가 일정 시간 동안 heartbeat을 듣지 못하면 leader가 죽었다고 생각하고 자신을 후보로 추천하며 다른 노드들에 자신을 leader로 뽑아달라고 RequestVote 요청을 보낸다. 이렇게 자신을 RequestVote 요청을 받은 노드를 candidate이라고 부른다. RequestVote를 받은 노드는 현재 자신의 상태를 보고 candidate이 더 최신 상태라면 새 leader를 지지하는 응답을 보내고, 그렇지 않으면 거절하는 응답을 보낸다. 반 이상의 노드가 자신을 지지한다고 응답하면 이 candidate은 leader가 된다. RequestVote를 보내고 일정 시간 동안 leader가 되지 못한 candidate은 다시 한번 모든 노드에게 RequestVote를 보낸다. 이때 얼마 만에 다시 RequestVote를 보낼지는 특정 범위 내에서 랜덤하게 결정된다. 랜덤한 timeout을 사용한다는 것은 Raft를 효율적으로 동작하게 하는데 매우 중요하다. 만약 고정된 시간을 사용한다면 모든 후보가 자기 자신에게 투표하라고 주장하며 선거가 끝나지 않을 수 있다. Candidate이 더 최신인지 아닌지는 term과 lastLogIndex를 보고 결정한다.

 Term은 leader의 재임 기간이다. Leader가 바뀌면 term이 바뀐다. 하지만 모든 term에 leader가 존재하지는 않는다. Term은 단조 증가하는 숫자로 서버별로 자신의 term을 저장하고 있다. Raft에서 메시지를 보낼 때는 언제나 자신이 생각하는 term을 함께 보내고, 메시지를 받은 노드는 메시지에 들어있는 term과 자신의 term 중 더 큰 값을 자신의 term으로 만든다. 혹은 RequestVote를 보낼 때도 term을 증가시키고 보낸다.

 Message에 들어있는 term이 자신의 term보다 크다는 것은 candidate이 자신보다 더 최신의 상태라는 것이다. 따라서 자신의 상태를 바로 follower로 바꾸고 candidate을 지지한다는 응답을 보낸다. 이것은 자신이 leader였을 때도 마찬가지다. 이런 경우 네트워크 등의 문제로 다른 노드가 자신의 heartbeat을 듣지 못했다는 것이고, 이 경우 다른 노드들이 이미 state를 진행했을 수 있기 때문에 새 leader의 상태를 따른다. 반대로 요청의 term이 자신의 term보다 낮다면, 이 요청은 그냥 무시하면 된다.

 자신과 같은 term의 RequestVote 메시지가 메시지에 있는 lastLogIndex를 본다. lastLogIndex가 자신의 log index보다 작다면 이 candidate은 지지하지 않는다. 이는 partition 상황에서도 consistency를 유지하기 위함이다. 이는 다음에 log replication을 설명하며 자세히 설명하도록 하겠다.

2017-11-29

Raft - 이해하기 쉬운 consensus algorithm

 분산 시스템을 구축할 때, 모든 노드가 독립적으로 돌아가는 시스템을 설계한 것이 아니라면, 공유된 상태를 합의하기 위한 모종의 방법이 필요하다. 이런 식으로 분산 환경에서 상태를 공유하는 알고리즘을 consensus algorithm이라고 한다.
 consensus algorithm 중에서 가장 유명한 알고리즘은 Paxos다. 하지만 Paxos는 구현은커녕 이해하는 것 자체가 어렵기 때문에, Paxos를 구현한 라이브러리가 거의 없었고, 일부 분산 시스템들이 내부적으로 사용하는 정도였다.
 그래서 분산 시스템을 구축할 때 현실적으로 사용할 수 있는 방법은 Zab algorithm을 사용하는 Zookeeper를 이용하는 것이었다. Zookeeper는 매우 훌륭하다. 사실 지금까지도 분산 환경에서 consensus를 위해 사용할 수 있는 검증 된 거의 유일한 라이브러리라고 말할 수도 있을 정도다. 하지만 Zookeeper는 메시지의 순서가 보장돼야 하기 때문에 반드시 TCP를 사용해야만 한다. 또한, Zab algorithm이 Zookeeper의 구현과 긴밀하게 엮여 있기 때문에 다른 구현을 만들기 힘들어 반드시 JVM을 띄워야 하는 문제가 있다.

 Raft는 구현체를 만들기 어렵다는 기존 consensus algorithm의 문제를 해결하기 위해 이해하기 쉬운 것을 최우선으로 설계된 consensus algorithm이다.
 Raft에서는 노드 간 공유될 state를 append-only state machine으로 본다. 따라서 노드 간에 상태가 합의됐다는 것은 이 state machine을 변경시키는 append command가 같은 순서로 적용됐다는 것을 의미한다. append command를 추가하는 것을 로그를 추가한다고 하고, 모든 노드가 같은 state를 가지게 하는 것을 log replication이라고 한다. 이때 어떤 append command를 추가할 것인지를 모든 노드가 일치한 정보를 가지는 것이 중요한데, Raft는 리더를 선출하여 모든 결정을 리더에게 위임하는 방법을 택했다. 이를 strong leader라고 하는데 덕분에 리더가 결정되고 나면 log replication은 매우 단순하게 진행된다. 이 leader election이 어떻게 되는지 다음 글에서 자세히 다뤄보도록 하겠다.

2017-11-27

[CppCoreGuidelines] const_cast는 언제 써야 하는가

 C++의 const_cast는 레퍼런싱하는 object의 cv-qualifier를 제거하는 캐스팅이다. cv-qualifier는 타입에 constness와 volatility를 더해주는 한정자이므로 const_cast는 constness뿐 아니라 volatility도 제거할 수 있다. constness를 제거하면 수정할 수 없었던 object를 수정할 수 있게 해주고, volatility를 제거하면 해당 object에 접근하는 코드가 최적화되어 사라질 수 있게 해준다. 따라서 const_cast는 실제 존재하는 object가 별도로 있고, 그것에 접근하는 방법을 변경한다.
 문제는 volatile object의 레퍼런스를 const_cast로 volatility를 없앤 뒤 이 object에 접근하는 것이나, const object의 레퍼런스를 const_cast로 constness를 없앤 뒤 이 object를 수정할 경우 이 코드가 어떻게 동작할지는 undefined behavior라는 것이다. 즉 아래와 같은 코드들은 전부 undefined behavior이다.

 그렇다면 const_cast는 언제 사용하는 것일까? 사실 const_cast를 사용해야만 하는 경우는 없다. 무언가를 하기 위해 반드시 const_cast가 필요하다고 느껴진다면 디자인에 무언가 문제가 있는 것이다. 그래서 C++ Core Guidelines에서는 const_cast를 사용하지 않는 것을 권장한다. 흔히 const_cast를 사용하는 패턴을 정리하면 아래의 3가지 패턴으로 분류할 수 있다. 이제부터 그 3가지 패턴이 왜 사용하면 안 되는지 설명할 것이다.

  첫 번째 용례는 어떤 object의 cv-qualifier를 cv1이고, 이 object를 레퍼런싱하는 cv1보다 더 cv-qualified 된 cv2를 가지는 변수를 가지고 있을 때, cv1보다 높고, cv2보다는 낮은 레벨의 cv-qualifier를 갖도록 하는 것이다. 즉, int i1이 선언돼 있고 이 i1를 지칭하는 const int& i2가 있을 때, i2를 int&로 캐스팅하는 용도다.
 하지만 잘 설계됐다면 undefined behavior를 감수하고 중간에 cv-qualified 된 레퍼런스로 들고 다닐 이유가 없다.

 두 번째는 non-const method를 가지는 클래스의 const instance가 있을 때, 이 instance를 통해 non-const method를 호출하는 것이다.
 하지만 어떤 메소드가 non-const method인 이유는 그 함수 안에서 mutable이 아닌 subobject를 수정하기 때문이다. 이를 const_cast를 통해서 강제로 호출할 경우 subobject를 수정하는 동작이 undefined behavior가 될 수 있으므로 안전하지 않다.

 마지막 사용 방법은 어떤 클래스의 const 메소드와 non-const 메소드 두 개를 정의할 때 코드의 중복을 없애기 위해서다.  이는 Scott Meyers의 Effective C++에서 추천하는 방법이기도 하고 실제로 매우 많이 보게 되는 코드다. 일반적으로 이 경우 const*로 캐스팅한 this가 반드시 non-const object를 레퍼런싱하는 것을 보장하기 때문에 안전하다. 하지만 이는 f 함수가 리턴하는 레퍼런스가 S의 멤버라는 가정하에서만이다. 예를 들어 f가 리턴하는 reference_to_r이 static storage를 가지는 const R이었다면 위의 코드는 정상적으로 컴파일되지만, non-const인 S의 instance를 통해 f를 호출할 경우 그 결과값은 const object를 지칭하는 non-const 레퍼런스이기 때문에 안전하지 않다.
 그래서 C++ Core Guidelines에서는 const_cast의 사용을 금지하고, C++11에서 추가된 decltype을 이용해서 아래와 같이 해결하는 것을 권장한다.  위의 코드에서는 f_impl의 리턴 타입이 템플릿 파라미터인 T에 의존하고, f의 결과값은 f_impl의 결과값이기 때문에, reference_to_r이 const-object의 레퍼런스라면 R& f를 컴파일할 때 에러가 발생하기 때문에 안전하게 선언할 수 있다.

 이상으로 const_cast를 사용하는 코드가 어째서 위험한지 알아보았다. 사실 C++11 이전에도 const_cast가 위험하다는 것은 널리 알려져 있었다. 하지만 코드의 중복을 제거하기 위해 const_cast를 사용하는 것을 대체할 방법이 없었기 때문에, 일반적으로 const_cast를 사용하지 말라고 할 수 없었다. 하지만 C++11에 들어간 decltypeconst_cast 없이도 코드의 중복을 없앨 방법을 제공한다. 따라서 C++11 이후로는 undefined behavior가 되기 쉬운 const_cast를 더는 쓸 이유가 없다.

2017-11-26

[C++] as-if rule - 소스에 적힌 순서대로 실행되지 않는 이유

 as-if rule이란, 프로그램의 실행 결과가 변하지 않는다면 소스에 적혀있는 것이 아닌 다른 방법으로 실행하는 것을 허용하는 규칙을 말한다. 이러한 규칙을 as-if rule이라는 이름으로 부르는 것은 C++에서만 찾을 수 있지만, C를 비롯한 다른 언어에서도 이러한 부류의 최적화를 허용한다.

 as-if rule을 허용하는 이유는 크게 두 가지로 보인다. 우선 컴파일러의 최적화를 방해하지 않기 위함이다. 만약, 표준 문서에서 적용할 수 있는 최적화 방법을 화이트 리스트로 관리한다면, 새로운 최적화 기법이 나왔을 때, 컴파일러가 이를 적용하기 위해서는 표준을 수정해야 한다. 하지만 표준에서 허용하지 않는 동작만 기술해두면 컴파일러 구현체에서 새로운 최적화를 구현하는데 조금 더 자유로울 수 있다.
 두 번째 이유는 C++이 가정하는 abstract machine이 엄밀하게 정의되지 않았기 때문이다. 일반적으로 C++의 실행 타깃은 native processor다. 이 프로세서는 제조사에 따라서, 혹은 칩 아키텍처에 따라서 다른 특성을 가질 수 있는데, C++ 표준은 이때 실행할 프로세서의 종류나 특성을 한정 짓지 않는다. CPU 별로 메모리 오더, 레지스터 크기, 레지스터 개수 등이 전부 다르기 때문에 가능한 최적화도 전부 다르다. 따라서 표준에서 어떤 최적화를 허용할지 명시할 수 없고 as-if rule이라는 이름으로 코드의 실행결과를 바꾸지 않는 최적화를 전부 허용하도록 명시한 것이다.

2017-11-20

[C++] Visual C++의 volatile

 지난번 글에서 말했듯이 C++ 11 이전에는 메모리 접근의 순서를 보장할 수 있는 표준 방법이 없었다. 따라서 플랫폼에 따라 다른 코드를 사용해야 했다. x86은 mfence, ARM이라면 DMB 인스트럭션을 인라인 어셈블리를 사용하여 집어넣거나, gcc의 __sync_synchronize 나 Visual C++의 MemoryBarrier 매크로를 사용하는 방법이 일반적이다. 여기에 Visual C++은 volatile에 추가적인 제약을 거는 방법으로 메모리 접근 순서를 보장하는 방법을 마련하였다.

 Visual C++의 컴파일 옵션에서는 volatile의 동작을 2가지 중 하나로 선택할 수 있다. /volatile:iso로 컴파일하면, iso 표준대로 메모리 접근 순서와 상관없이 as-if rule에 의해 코드가 최적화되어 사라지는 것만을 방지한다. 하지만 /volatile:ms로 컴파일하면 iso 표준에서 규정하는 제약에 추가적으로 volatile object에 접근하는 것이 load-acquire, store-release semantic을 따른다. 즉, 간략히 말하면 store는 뒤에 있는 load가 실행된 다음에 실행될 수 있지만, 다른 메모리 접근의 순서는 순서대로 실행되는 게 보장된다.

 컴파일 때 아무 옵션을 안 주면 x86에서는 /volatile:ms가 기본값이다. 사실 x86 CPU는 load-acquire, store-release semantic을 따르기 때문에 volatile object에 접근하는 코드는 컴파일 타임에 순서를 바꾸지 않겠다는 것이다.
  ARM에서는 /volatile:iso가 기본값이다. 따라서 /volatile:ms를 이용하여 컴파일하면 DMB 인스트럭션을 이용하여 CPU가 순서를 바꿔 실행하는 것을 막기 때문에 성능이 떨어진다. 하지만 x86에서 테스트 된 코드를 그대로 사용할 수 있다.

2017-11-19

[C++] memory barrier - 메모리 접근의 순서 보장하기

 지난번 글에서 말했듯이 C++의 volatile object에 대해서 메모리 접근 순서를 보장하지 않지만, 메모리 접근 순서를 보장한다고 잘못 아는 사람이 많이 있다. 이는 지난번에 글에서 말했듯이 Java나 C#으로 멀티 스레드 프로그래밍을 배운 사람들이 잘못 알기 때문이기도 하지만 C와 C++로 멀티 스레드 프로그래밍을 배운 사람들도 잘못 아는 경우가 많다. 그런 경우는 보통 아래와 같은 착각을 하기 때문이다.

Access to volatile objects are evaluated strictly according to the rules of the abstract machine. - C++14 intro.execution 1.9.8.1
 C++ 표준에 적혀있는 위의 문장에 따르면 volatile object에 접근이 엄격하게 실행된다고 적혀있다. 이 문장을 잘못 이해해서 엄격한 순서로 실행된다고 받아들이는 사람들이 있다. 하지만 이는 그저 volatile object에 접근하는 코드는 as-if rule에 의해 최적화되지 못한다는 것으로 메모리에 접근해야 할 코드를 최적화해서 없애거나, 레지스터 등을 이용해서 최적화하지 못한다는 것이다. 그보다 중요한 것은 abstract machine의 규칙을 따른다는 것이다.

 여기서 말하는 abstract machine은 다른 구현체에서 같은 동작을 보장하기 위해 C++ 표준이 기술한 가상의 기계를 의미한다. 근데 이 abstract machine은 의존성이 없는 다른 메모리 영역에 접근하는 것에 대해 순서를 보장하지 않는다. 이는 컴파일러가 as-if rule에 따라 최적화할 여지를 남겨두기 위해 서기도 하지만, 실제로 CPU가 실행 시간에 메모리 접근을 재배치할 수 있기 때문이다. 그래서 실제로 어셈블리의 순서대로 실행될지 알 수 없다.
 물론 모든 인스트럭션이 재배치되는 것은 아니고 CPU마다 자신이 재배치하여 실행할 수 있는 조합이 있다. 예를 들어 가장 많이 사용되는 X86의 경우 메모리에 저장하는 인스트럭션이 메모리에서 값을 읽는 인스트럭션 뒤로 가는 것만 허용하고, 저장-저장, 읽기-읽기의 순서와 메모리를 읽는 인스트럭션이 뒤에 오는 저장 인스트럭션보다 먼저 실행될 것은 보장해준다. 하지만 이 동작에 의존하면 ARM이나 PowerPC 같이 모든 메모리 접근 순서가 보장되지 않는 CPU에서는 의도하지 않은 동작을 할 수 있다.
 그렇다면 순서를 보장하기 위해서는 어떻게 해야 할까? C++11이 들어오기 전에는 표준에 스레드와 관련된 내용이 없었다. 이 말은 다른 말로 C++의 abstract machine은 싱글 스레드로 가정하였다는 것이고, 당시에는 의존성 없는 메모리에 접근하는 순서가 중요하지 않았다. 그래서 당시 표준에서는 메모리 접근 순서를 보장하는 방법도 존재하지 않았고, 자신이 실행할 플랫폼에서 지원하는 방법을 사용해야 했다. 하지만 C++11에서는 멀티 스레드를 지원하도록 변하면서 fence를 칠 방법이 표준에 들어왔다.
 C++11에서 지원하는 std::atomic_thread_fence는 x86의 경우 mfence 계열의 인스트럭션으로 번역되고, ARM의 경우 DMB 같은 인스트럭션으로 번역된다. 이런 메모리 순서를 보장하는 특별한 instruction을 memory barrier 혹은 memory fence라고 한다.

2017-11-18

[C++] volatile

 volatile은 C++에서 가장 오해받고 있는 키워드 중 하나일 것이다. 오해받는 이유는 크게 2개라고 생각한다. 첫 번째로 C++의 volatile이 Java나 C# 등 다른 언어에서 말하는 volatile과 다르기 때문이고, 두 번째로 C++의 volatile은 CPU와 컴파일러가 어떻게 동작하는지 알지 않으면 이해하기 어려운 비직관적인 기능이기 때문이라고 생각한다.

 Java나 C# 등 다른 언어에서 volatile은 다른 스레드에서 visibility를 보장해주기 위해 사용된다. 따라서 변수의 접근이 리오더링 되는 것을 막고, 언제나 최신 값을 유지하는 것을 보장해준다. 특히나 멀티 스레드 프로그래밍을 한다면 누구나 한 번쯤 읽어본다는 고전 명작 The Art of Multiprocessor Programming에서 그 예제 코드가 Java로 돼 있기 때문에 C++에서도 volatile 키워드가 같은 의미를 가진다고 생각하는 사람이 많다.

 하지만 C++에서 volatile은 멀티 스레드와 아무런 관련이 없다. 이는 과거 C 표준에 스레드와 관련된 내용이 없던 시절에 추가된 이후로 지금까지 스펙이 변경되지 않았기 때문이다. 그래서 C++의 volatile은 싱글 스레드 코드에서 변수의 접근이 최적화되어 사라지는 것을 막을 뿐이다. 예를 들어 int a가 있을 때 a += 1을 반복하는 코드가 3회 반복될 때, 이 중간에 a에 접근하는 코드가 없으면, 이 코드는 a += 3으로 최적화될 수 있다. 만약 중간에 a에 접근하는 코드가 있어도, 매번 a를 메모리에서 접근하지 않고, a를 레지스터에 집어넣어 최적화할 수 있다. 하지만 a의 타입이 volatile int였다면, 이와 같은 최적화는 할 수 없고 a를 메모리에서 읽어 1을 더하여 메모리에 쓰는 코드가 3번 들어가야 한다.
 하지만 리오더링 되는 것을 막지 않는다. 따라서 의존성이 없는 두 변수가 volatile로 선언돼 있을 때 이 두 변수 사이에 읽기/쓰기는 다른 순서로 실행될 수 있다. 아래의 코드가 volatile이 리오더링되는 것을 막지 않기 때문에 C++이 volatile을 사용했을 때 다른 언어와 다르게 동작하는 대표적인 예제다.
 위의 코드에서 thread1_mainthread2_main이 다른 스레드에서 동시에 실행될 때 코드가 쓰여 있는 순서대로 실행된다면 b가 1이고 a가 0인 순간이 올 수 없기 때문에, 절대로 assert에 걸리지 않는다. 하지만 앞에서 말했듯이 C++의 volatile은 리오더링을 막지 않기 때문에 thread1_mainb = 1a = 1보다 먼저 실행될 수 있어서 b는 1이지만 a는 0인 순간이 올 수 있고 assert에 걸릴 수 있다.

2017-10-30

[C++] C++ Core Guidelines - modern C++을 위한 안내서

 C++은 사용하기 어려운 언어이다. C++ 이후에 나온 언어들에 비해 사용자에게 너무 많은 자유도를 주기 때문에 안전하게 사용하기 어렵다. 그래서 구글, 웹킷, LLVM 등 많은 스타일 가이드들이 단순히 문법적인 포맷을 어떻게 작성할지 디자인에 대한 부분도 같이 제안한다.

 오늘 소개할 C++ Core Guidelines도 이런 스타일 가이드 문서 중 하나다. modern C++, 즉, C++ 11 이후 C++을 어떻게 사용할지에 초점을 맞힌 가이드 문서로, C++의 창시자인 Bjarne Stroustrup이 주축이 되어 작성되었다. C++ Core Guidelines는 다른 문서보다 C++ 자체를 어떻게 하면 더 안전하게 쓸 수 있을지에 초점을 두기 때문에 문법적인 포맷에 대한 조언은 거의 하지 않는다. 그보다는 어떻게 하면 로직의 문제를 최대한 빠르게, 가능하면 컴파일 타임에 잡을 수 있는지에 대한 디자인 조언을 많이 한다. 개인적으로는 지금까지 읽었던 modern C++ 코딩에 관한 문서 중 가장 실용적인 문서라고 생각한다.

 C++ Core Guidelines를 읽다 보면 GSL이라는 단어가 자주 나온다. C++ Core Guidelines는 반복되는 몇 가지 사용 패턴을 위해서 몇몇 라이브러리를 사용할 것을 권하고 있다. 이를 Guideline Support Library, 줄여서 GSL이라고 부른다. 정의상으로는 가이드라인에서 제안하는 GSL의 스펙을 만족하는 라이브러리는 모두 GSL이라고 부를 수 있다. 하지만 현존하는 구현체는 Microsoft에서 만든 GSL뿐이기 때문에 사실상 Microsoft의 GSL과 같은 의미라고 생각해도 된다.

 앞으로 시간 나는 대로 C++ Core Guidelines와 GSL의 내용 중에서 좋아하는 항목 몇 개를 소개할 생각이다. 하지만 그와는 별개로 앞으로 계속해서 C++ 프로그래머를 할 생각이라면 한 번쯤은 읽어보기를 추천한다.

2017-10-17

crash-only software - high availability server 만들기

 지난번 글에서 high availability 서버를 만들기 어려운 이유를 설명했었다. 그럼에도 high availability 서버를 만드는 것은 중요하기 때문에 availability를 높이기 위한 여러 가지 방법들이 존재한다. 이번에 설명할 crash-only software도 그중 하나다.

 Crash-only software의 기본 철학은 해결할 수 없는 문제가 발생했을 때, 다른 시도를 하지 않고 바로 종료시키는 것이 오히려 availability를 올린다는 것이다. 이렇게 하면 서버가 떠 있는지만 검사하면 되기 때문에 서버에 문제가 생겼는지 바로 알 수 있고, 문제가 생기면 바로 crash로 끝내기 때문에 빠르게 종료할 수 있다.

 다만 crash-only software는 언제든지 죽을 수 있기 때문에 persistence layer가 프로그램 외부로 빠져야 한다. 즉, 로직 레이어와 데이터 레이어가 구분되는 multitier architecture가 된다.

 자연스럽게 로직 레이어는 스테이트를 가지지 않게 되기 때문에 컴포넌트별로 독립시키기 쉽기 때문에 자연스럽게 마이크로 서비스로 만들게 되고, 서비스 하나의 크기가 줄어들기 때문에 재시작에 걸리는 시간도 줄어들고, 자연스럽게 availability가 증가하게 된다.

 또한, crash-only-software에서 사용하는 공유 자원은 사용권을 소유한다는 개념이 아니라 사용권을 빌린다는 개념으로 접근해야 한다. 사용권을 빌렸기 때문에 명시적으로 사용권을 돌려주지 않았더라도 일정 시간이 지나면 사용권을 잃고 다른 컴포넌트에서 사용할 수 있어야 한다.

2017-10-13

high availability 서버를 만들기 어려운 이유

 서비스에서 availability를 보장해주는 것은 매우 중요하다. three-nine(99.9%)의 availability를 보장하려면 일 년에 아홉 시간 이하의 다운타임만 있어야 하고, four-nine(99.99%)을 보장하려면 약 한 시간 이하, five-nine(99.999%)을 보장하려면 일 년에 다운 타임이 오 분 이하여야 한다.

 보통 서버 장애는 서버가 가장 바쁠 때 발생하기 때문에 가능하면 다운 타임을 줄이는 것이 중요하지만, 현실적으로 이는 쉽지 않다. 상용 서비스 중에서도 three-nine 이상 보장하는 서비스를 찾기 힘들고, 어느 정도 이름 있는 서비스들은 돼야 four-nine, 정말 안정화가 잘 돼 있는 서비스들만이 five-nine 이상의 availability를 보장한다.
 이는 high availability 서버를 만드는 것이 근본적으로 어려운 일이기 때문이다. 다운 타임이 적은 서버를 만들기 위해서는, 일단 버그가 없는 것은 기본이어야 한다. 하지만 서버 다운의 이유가 버그만 있는 게 아니다. 디스크나 네트워크 등 하드웨어 문제로 예상치 못하게 서버를 사용할 수 없게 되는 경우도 있다. 따라서 high availability 서버를 만들기 위해서는 문제가 생겼을 때 빠르게 재시작하는 것이 가장 중요한데 이를 위해서는 서버에 문제가 발생했을 때 이를 감시하고 있던 모니터가 빠르게 감지하여 서버에 문제가 발생하면 서버를 안전하게 죽이고, 새 서버를 띄워야 한다.

  보통 서버에서 일정 시간 간격으로 메시지를 보내고 메시지가 오지 않으면 죽은 것으로 판단하는 heartbeat 방식을 많이 사용한다. 이때 heartbeat 자체는 보통 몇 초에 한 번 보내지만, 실제 서버가 죽지는 않았지만, 네트워크나 다른 문제로 메시지가 오지 않았을 것을 대비하여 몇 번의 메시지가 도착하지 않았을 때 서버가 죽었다고 판단한다. 즉, 실제로 서버에 문제가 발생해도 그를 감지하는 데만 적게는 십수초 많게는 몇십초의 시간이 걸린다.
 그다음 문제는 서버를 빠르고 안전하게 죽이는 것이다. 보통은 프로그램이 죽는 것은 크게 신경 쓰지 않아도 된다. 프로그램이 죽으면 프로그램에서 사용하던 리소스는 OS가 알아서 처리해준다. 하지만 프로그램이 파일 시스템 등의 공유 자원을 사용하고 있었다면, 문제가 복잡해진다. 이 경우 수정한 공유자원을 원래대로 되돌리거나 처리하던 작업을 완료할 때까지 프로그램의 종료를 기다려야 한다.
 마지막 문제는 서버를 빠르게 띄우는 것이다. 단순히 서버를 실행시키는 것은 시간이 오래 걸리지 않는다. 하지만 실행된 서버가 클라이언트의 요청을 정상적으로 처리할 수 있는 상태가 되는데 얼마나 걸릴지는 다른 문제다. 서버에서 사용해야 하는 다른 자원이 있으면 이 자원들을 초기화해야 하고, 서버에서 다른 서비스들을 이용하고 있다면 이 서비스들과의 접속도 다시 확인해야 한다. 게다가 하드웨어의 문제로 서버가 죽은 경우라면 기존에 사용하던 공유자원을 깔끔하게 정리하지 못하고 죽었을 것이기 때문에 이를 정리하는 일까지 해야 한다.

 일반적으로 이상의 작업을 하면 서버에 문제가 발생하여 다시 시작하는 데까지 몇 분의 시간이 소모된다. 즉, 1년에 몇번의 장애만 발생해도 five-nine은 물론이고 four-nine조차 달성하기 어렵다.

2017-10-09

[C++] array to pointer decay

 C++은 그 근본이 C에서 나왔기 때문에 C에서 많은 문제점을 물려받았다. 대표적으로 implicit conversion이 그런데, 그중에서 array가 pointer로 implicit conversion 되는 것을 decay. 혹은 다른 decay들과 구분하기 위해 array to pointer decay라고 부른다. 이는 말 그대로 T[N] 타입으로 선언된 변수의 값이 T* 타입의 변수에 바인딩 될 때 implicit casting이 되는 것을 말한다. 이는 컴파일 타임 정보인 배열의 크기를 잃는다는 문제도 있지만, 그보다 더 큰 문제는 포인터에 대해서 upcasting 또한 implicit conversion이 가능하다는 데서 생긴다.

 위와 같은 코드가 있다고 해보자. A를 상속받은 B 클래스가 있고, B instance의 크기는 A instance의 크기보다 크다(정확히 따지자면 사용하는 alignment의 크기가 B 클래스보다 작은지 따져봐야 하지만, 여기서는 설명을 간단히 하기 위해 int 크기로 align 된다고 가정하고 진행하도록 하겠다). 이때 f 함수가 하는 일은 다음과 같다.

  1. B(3, 4)를 생성한다.
  2. 1에서 생성한 객체의 A 부분만 slice 한 A(3)을 인자로 받은 a 위치에 넣는다.
  3. B(5, 6)를 생성한다.
  4. 3에서 생성한 객체의 A 부분만 slice 한 A(5)를 인자로 받은 a에 1 더한 주소에 저장한다.
 앞에서 말했듯이 위의 코드는 일단 포인터는 실제 배열의 크기를 알지 못하기 때문에 f 함수가 받은 a의 길이가 2 이상인지 알 수 없다는 문제가 있다. 하지만 이보다 더 큰 문제가 있다. 만약 f 함수를 아래와 같이 사용했다고 해보자.  B[4] 타입인 aB* 타입으로 decay 되고, B*는 부모 타입인 A*로 upcasting 되어 f 함수에 넘어간다.

f 함수를 실행한 뒤 사용자가 원했던 모습은 아마 위와 같은 모습일 것이다. 혹은 object slice가 일어난다는 것을 생각하지 않고 아래와 같은 결과를 생각했을 수도 있다.
 하지만 실제 실행한 결과는 다음과 같은 값을 가지게 된다.

 이는 실제 정의된 메모리 레이아웃과 f 함수가 해석한 메모리 레이아웃이 다르기 때문이다.

실제 레이아웃
f가 해석한 레이아웃
 우리는 분명히 B의 배열을 선언하였다. 따라서 실제 메모리에는 B의 인스턴스가 연속으로 존재한다. 하지만 f 함수가 인자로 받은 타입은 A의 포인터 타입이기 때문에 이를 B가 4개 존재하는 메모리가 아닌 A가 8개 존재하는 메모리로 해석하게 된 것이다. 따라서 a[1] = B(5, 6)를 실행하였을 때 2번째 B가 있는 메모리가 아닌 첫 번째 Bint b에 해당하는 영역에 두 번째 A 인스턴스가 존재한다고 생각하고 A(5)를 할당하게 된 것이다.

 이 문제를 해결하는 방법은 크게 2가지 있다. 첫 번째 방법은 함수를 정의할 때 배열을 넘기기 위해서 포인터를 사용하지 않는 것이다. 이는 함수에 넘겼을 때 배열의 크기라는 정보를 잃지 않기 위해서이기도 한데 C++ Core Guidelines에서 추천하는 방법이기도 하다.

 두 번째 방법은 배열을 선언할 때 C 스타일의 []가 아닌 std::array를 사용하는 것이다. std::array는 C++ 11에 추가된 배열을 표현하기 위한 타입으로, C 스타일 배열과 다르게 이터레이터와 begin, end 등이 정의돼있어서 다른 표준 컨테이너들과 같은 코드를 공유할 수 있다는 장점이 있다. 하지만 여기서는 코드를 재사용할 수 있다는 것보다 이는 템플릿 클래스이고 따라서 AB의 부모일 때, std::array<A, N>std::array<B, N>의 부모가 아니라는 특성이 더 중요하다. 따라서 template<int N> void f(std::array<A, N>& a)라는 함수를 호출할 때 인자로 Bstd::array를 넘길 수 없기 때문에 위와 같은 문제가 발생하지 않는다.

[C++] Variadic template

 전통적인 C나 C++에서 잘못 쓰면 위험한 것 중 하나로 stdarg가 있었다. 이를 이용하면 임의의 개수의 인자를 받는 variadic function을 만들 수 있지만, 함수의 시그니쳐를 통한 타입 체크를 완전히 무시하기 때문에, 함수의 호출자가 규약을 지키지 않고 함수를 사용하더라도 컴파일 타임에 문제를 잡을 수 없기 때문에 실행 시에 여러 가지 문제가 발생했다. 이런 문제를 피하고자 stdarg를 사용하지 않고, 예상되는 인자의 최대 개수를 예상해서 받는 인자의 개수가 다른 함수를 오버로딩하여 사용하는 경우가 더 많았다.

 C++11에서는 variadic function을 타입 시스템과 붙여 컴파일 시간에 타입 체크 할 수 있게 하려고 variadic template이라는 문법을 추가하였다. Variadic template을 사용하면 사용된 인자의 타입 별로 instantiation 되기 때문에 바이너리의 크기는 커지지만, 컴파일 타임에 타입 체크를 할 수 있으며 실행 시에 생기는 비용을 줄여준다. Variadic template이 될 템플릿 인자는 ellipsis(...)를 붙여 다음과 같이 사용한다.  Variadic template을 사용하는 패턴은 크게 2가지이다.

 첫 번째는 다른 함수로 인자를 전달하는 것이다. 대표적으로 make_unique가 이런 경우에 속한다. Possible implementation에서 볼 수 있듯이 make_uniquestd::forward(args)...를 이용해 T 타입의 생성자에게 모든 인자를 전달한다. 여기서 std::forward 함수 호출 뒤에 ellipsis가 붙어있다는 것이 중요하다. 이를 pack expansion이라고 하는데 std::forward 함수에 인자를 넘기는 패턴을 variadic arguments인 args에 전부 적용하는 것이다. 따라서 argsN 개의 인자였으면 번의 std::forward 함수가 불리게 된다. 이때 단순히 전달하는 것이 아니라 값을 수정해서 다른 함수로 전달할 수도 있다.  위의 예제가 값을 수정하여 전달한 예제이다. 위의 예제는 variadic arguments인 args의 각각을 mapper에 적용한 뒤 reducer에 전달한다. 따라서 args는 모두 같은 타입이어야 하며, mapperargs중 하나를 인자로 받는 함수여야 하고, reducermapper의 리턴 타입들을 args의 개수만큼 받아 하나의 리턴값으로 만드는 함수여야 한다.

 두 번째 패턴은 base case를 만들고 재귀적으로 호출하는 함수를 정의하는 것이다.  위의 코드가 재귀적으로 정의한 주어진 숫자를 전부 합치는 코드이다. operator+가 정의된 모든 타입이 아닌 숫자만 인자로 받기 위해서 std::enable_if를 이용해서 인자로 받는 타입을 제한했다. 이번에 설명할 내용은 아니니 그것을 제외하고 보면, 아무런 인자를 받지 않는 int sum() 함수가 base case가 되고, 인자가 하나 이상일 때는 T t와 variadic arguments를 인자로 받는 함수를 정의하였다. 그러면 sum의 인자가 없을 때는 base case가 불리고, 인자가 하나 이상일 때는 두 번째 정의된 함수가 불린다. 이때는 첫 번째 인자는 T t에 매칭되고 나머지 인자는 Args... args에 매칭된다.
 아니면 sum 함수를 아래와 같이 정의할 수도 있다.  이 sum 함수는 인자 하나를 받는 함수를 base case로 삼았다. 인자를 넘기지 않고 함수를 부르면 컴파일 에러가 발생하고, 인자를 하나만 사용하여 함수를 부를 때 sum(T t) 함수가 불린다. 따라서 인자를 2개 이상 넘길때만 variadic function이 호출된다.

2017-08-13

c++ static

 C++을 처음 배울 때 사람들이 많이 헷갈리는 것 중 하나가 static이다. 사실 이건 배우는 사람의 문제도 아니고 가르치는 방법의 문제도 아니다. 그저 C++에서 static을 다양한 용도로 사용하고 있기 때문이다.

static storage

 static 키워드를 사용하는 한 가지 목적은 지역 변수에 할당할 객체를 static storage로 만들기 위해서다. C++에서 block scope에 선언되는 변수가 가지는 객체는 기본적으로 automatic storage에 선언되어 block이 끝나면 자동으로 소멸한다. 하지만 간혹 특정한 범위 내에서만 접근할 수 있으면서 프로그램이 끝날 때까지 살아있는 객체, 다시 말해 지칭하는 변수는 block scope에 선언됐지만, static storage duration을 가지는 객체가 필요할 때가 있다. 이럴 때 static 한정자를 사용하면 된다. block scope에 선언되는 지역 변수에 static 한정자를 붙이면 이 변수가 가리키는 객체는 static storage duration을 가지고, block이 종료돼도 소멸하지 않는다.

internal linkage

 static 한정자는 namespace scope에 선언되는 변수에도 사용될 수 있다. 하지만 namespace scope에 선언된 변수가 가지는 객체는 기본적으로 static storage에 할당된다. 따라서 namespace scope에 선언된 변수에 붙은 static 한정자는 객체가 할당될 storage에 영향을 주지 않는다. 여기서 static은 다른 의미를 가진다.
 static 한정자는 namespace scope에서는 변수뿐 아니라 함수 선언에도 붙일 수 있다. 이 경우 선언된 변수나 함수의 linkage를 internal linkage로 바꿔서 translation unit 밖으로 나가지 않도록 해준다.

static member

 C++에서 static이 가지는 마지막 의미는 클래스의 멤버 변수나 함수를 전역 멤버 변수와 전역 함수로 만드는 것이다.
 클래스의 전역 멤버 변수는 프로그램이 종료될 때까지 살아있는 객체로, static storage에 할당된다. 전역 멤버 변수는 클래스와 독립적인 생명 주기를 가지기 때문에 전역 멤버 변수가 될 타입은 선언하는 시점에서 complete type일 필요가 없다. 전방 선언된 타입을 이용해 선언하더라도 정의하는 시점에서 complete type을 알기만 하면 된다.
 전역 멤버 함수는 클래스와는 관련 있지만, 객체와 연관되지 않는 함수를 말한다. 즉, 자기 자신(this)을 포인터로 넘겨받지 않으며, virtual function이 되거나 함수의 선언에 const를 붙일 수도 없다.
 또한, 전역 멤버 변수나 전역 멤버 함수는 그 클래스와 같은 linkage를 가진다. 즉, block scope에 선언된 클래스의 전역 함수나 전역 변수는 linkage를 가지지 않고, unnamed namespace 안에 선언된 클래스의 전역 함수나 전역 변수는 internal linkage를 가진다.

 static storage, internal linkage, static member 이 세 가지가 C++에서 static 키워드가 가지는 의미이다. 사실 이 3가지는 완전히 독립된 개념인데 같은 키워드를 사용하였기에 사람들을 헷갈리게 한다.
 C++ 뿐 아니라 다른 언어에서도 이런 경우가 종종 있다. 왜냐하면, 새 키워드를 추가하면 추가된 키워드를 다른 이름으로 사용하던 기존의 코드가 돌아가지 못하게 되고, 이는 하위 호환성을 잃는 결과를 가져오기 때문에 보통 언어에서 새 키워드를 추가하는 것을 싫어하기 때문이다.
 사실 C++에는 이미 unnamed namespace를 사용해서 이름을 internal linkage로 만드는 방법이 있다. 그래서 C++11이 제정될 때 namespace scope에 선언된 이름을 internal linkage로 만들기 위해서 static 한정자를 사용하는 것을 deprecate 시키자는 의견도 있었으나 하위 호환성을 깨지 않는 방향으로 가기 위해 받아들여지지 않았다. 결국, 이 3가지 기능이 전부 남게 되었고, 앞으로도 한동안은 이 중 어느 한 기능도 없어지지 않을 것으로 보인다.

2017-08-11

[C++] internal linkage와 external linkage의 차이

 보통 프로그램은 하나의 소스가 아닌 여러 개의 소스로 구성된다. 이 소스를 C++ 표준에서는 translation unit이라고 하고, 소스를 컴파일하는 과정을 translation이라고 한다. translation의 마지막 단계는 link인데, 이 과정을 제외하고는 모든 translation은 독립적으로 진행된다. 이때 translation unit 내에서 이름이 어느 범위까지 사용될 수 있는가를 정하는 것이 지난번 글에서 설명한 스코프이다.
 이번에 설명할 linkage는 같은 이름이 같은 entity를 지칭하는 범위를 정하는 것이다. 각 이름은 어떤 linkage를 가지는가에 따라서 translation의 마지막 단계에서 어떻게 link 될지 달라진다.
 linkage에는 internal linkage와 external linkage 두 가지 종류의 linkage가 있다. 하지만 모든 이름이 linkage를 가지는 것은 아니다. 우선은 linkage를 가지지 않는 이름에 대해 알아보도록 하겠다.

no linkage

 영어로는 has no linkage라고 하여 has internal/external linkage와 자연스럽게 대구가 된다. 하지만 한국어로 말하면 no linkage를 가진다고 하는 것은 어색하므로 그냥 linkage를 가지지 않는다고 하는 것이 적당해 보인다.
 어찌 됐든 모든 이름이 linkage를 가지는 것은 아니다. block scope에 선언된 이름은 함수와 extern으로 선언된 변수를 제외하면 전부 linkage를 가지지 않는다. 따라서 함수 안에서 선언한 로컬 클래스, enumeration, enumerator, 타입 등은 전부 linkage를 가지지 않는다.
 linkage를 가지지 않는 이름은 선언된 스코프에서밖에 접근할 수 없고, 스코프 밖에서 그 이름을 다시 사용해도 그건 다른 entity를 지칭하는 것이 된다. static 한정자를 사용하여 static storage에 저장한 경우도 마찬가지다. 이는 block scope에 선언된 이름은 함수 안에서만 사용하기 위한 것이기 때문이다.

internal linkage

 internal linkage를 가지는 이름은 외부 translation unit으로 공개되지 않는다. internal linkage를 가지는 이름은 다음과 같다.

  1. namespace scope에 선언된 static specifier가 붙은 이름
  2. namespace scope에 선언된 anonymous union의 데이터 멤버
  3. namespace scope에 선언된 const 혹은 constexpr이 붙고 volatile은 아닌 변수
  4. unnamed namespace에 선언된 모든 이름

 internal linkage를 가지는 이름은 두 개 이상의 translation unit에서 공유할 수 없다. 따라서 다른 translation unit에서 같은 스코프에 같은 이름으로 선언된 변수나 함수가 있어도 물리적으로 이는 다른 객체를 가리킨다. 따라서 헤더 파일에 internal linkage를 가지는 mutable 한 객체를 선언한 경우 읽는 사람이 코드를 잘못 읽을 여지를 줄 수 있기에 namespace scope에 선언되는 mutable 한 객체는 헤더 파일에 선언하지 않는 것이 좋다. 만약 반드시 헤더 파일에 선언해야 한다면, external linkage를 가지도록 해야 한다.

external linkage

 위에서 설명한 internal linkage와 다르게 external linkage를 가지는 이름은 다른 translation unit과 공유된다. 다시 말해서 어떤 이름이 external linkage를 가진다면 그 이름은 서로 다른 translation unit에서 사용되더라도 같은 내용을 가져야 한다.

  1. namespace scoep에 선언 된 이름 중 internal linkage가 아닌 이름.
  2. block scope에 선언된 함수
  3. block scope에 선언된 변수 중에서 extern으로 선언된 변수

external linkage를 가지는 이름은 위와 같다. 만약 external linkage로 선언된 이름이 함수일 경우 이 함수는 다른 translation unit에서 같은 코드 영역을 가리키게 되며, 그 함수에서 선언된 static storage나 thread_local storage에 저장되는 지역 변수도 공유하게 된다. 만약 그 이름이 객체를 지칭하는 변수라면, 다른 translation unit에서 사용될 때 같은 메모리를 여역을 공유하며, 따라서 한 translation unit에서 객체의 값을 수정하면 다른 translation unit에서도 수정된 값을 보게 된다. 또한, external linkage로 선언된 클래스가 있다면 그 클래스의 멤버 함수들과 전역 멤버 변수들도 전부 external linkage를 가지게 된다.

2017-08-02

[C++] 이름과 스코프

 C++에서는 많은 것들이 이름을 가질 수 있다. 변수는 모두 이름을 가지고, 객체는 변수를 통해서 이름을 가질 수 있다. 타입도 이름이 있고, 함수도 이름이 있다. 람다 함수는 익명 함수라는 번역 그대로 이름이 없지만, 변수에 할당하여 이름을 통해 접근할 수도 있다.
 이 이름을 어디서부터 어디까지 사용할 수 있는가를 그 이름의 스코프라고 하는데, C++은 상황에 따라 다른 스코프를 사용한다. 이번 글에서는 C++의 이름이 가지는 스코프에 관해서 설명하도록 하겠다.

block scope

 block scope는 선언된 문장부터 선언된 block이 끝날 때까지 사용할 수 있다. block 밖에서 선언된 같은 이름이 있으면 이름이 선언되기 전까지는 block 밖에서 선언된 이름을 그대로 가지고, 선언된 문장부터 새로 선언한 의미를 가진다.
 예를 들어 위와 같은 코드가 있을 때 4번째 줄까지 a는 2번째 줄에서 선언된 a이지만, 4번째 줄부터 block이 끝나는 10번째 줄까지는 4번째 줄에서 선언된 a이다. 또한, block scope를 가지는 이름은 같은 block 안에서 다른 의미를 가지기 위해 다시 사용될 수 없다. 즉, 위에서 5번째 줄에서 10번째 줄까지 사이에서는 a를 다른 의미로 사용할 수 없다.
 스코프를 가지는 이름의 대표적인 예제로는 함수 안에서 선언된 변수인 지역 변수(local variable)가 있다. 이때 지역 변수와 automatic storage에 저장되는 지역 객체를 혼동하면 안 된다. 스코프는 어디까지나 컴파일 시 그 이름을 어디까지 사용할 수 있는가 하는 것이지 객체의 라이프타임과는 상관없다. 지역 변수 중에서도 static이나 thread_local 같은 storage를 지정해주는 specifier가 붙은 경우 이 객체들은 automatic storage에 저장되지 않는다.
 지역 변수 외에도 typedefusing으로 선언되는 type alias, 함수 안에서 선언되는 class와 enum 같은 경우도 함수 안에서 선언됐다면 block scope를 가진다.
 함수의 인자, for 문에서 선언된 변수, catch 된 exception, C++17이라면 if control 문에서 선언된 변수도 block scope를 가지는데, 이들은 해당 문장이 있는 block이 아닌, 문장 다음에 있는 block에 종속된다.

namespace scope

 block scope보다 약간 큰 범위를 가지는 것은 namespace scope다. namespace scope는 이름 그대로 namespace에 선언된 모든 이름을 의미한다. 당연히 이 namespace에는 global namespace도 포함되므로 outermost namespace 밖에 선언된 이름도 namespace scope를 가진다. namespace scope를 가지는 이름은 block scope를 가지는 이름과 마찬가지로 선언된 문장부터 접근할 수 있다. 하지만 block scope와는 다르게 선언된 namespace가 끝나더라도 접근 불가능하지 않다. 아래와 같이 ::(scope resolution operator)를 통해서 접근할 수 있다.

enumeration scope

 enumeration scope는 C++11에 처음 들어간 기능으로 enum class가 들어가면서 같이 들어갔다. C++11의 enum class는 scoped enum이라고 부르기도 하는데, 이는 enumerator의 이름이 enumeration에 한정되기 때문이다.  같은 스코프 내에서 선언된 이름을 다시 선언할 수 없다는 규칙은 enumeration scope도 마찬가지므로 enumerator의 이름을 중복해서 사용할 수 없다. 하지만 enum class가 선언된 block scope나 namespace scope의 이름을 더럽히지 않기 때문에 해당 스코프에는 중복되는 이름이 있어도 괜찮다. enumerator를 사용할 때는 enumeration의 이름과 합쳐서 scope resolution operator를 사용한다.

function scope

 function hoisting이란 선언된 이름이 마치 함수의 시작 부분으로 옮겨진 것처럼 해석되는 경우를 말한다. JavaScript에서는 모든 변수가 function hoisting 되므로 JavaScript를 써본 사람이라면 익숙한 개념일 것이다. 하지만 마치 JavaScript의 특이한 기능인 것처럼 알려졌기 때문에 C++에서도 function scope에는 function hoisting이 사용된다.
 사실 function scope를 사용하는 이름은 label 딱 한 경우뿐이고, 대부분의 경우 goto를 사용하는 것을 피하므로 사용할 일이 거의 없다. 어찌 됐든 이 라벨은 같은 함수 안에서 선언됐다면, 그 선언된 위치와 상관없이 어디서나 라벨을 사용할 수 있다.

class scope

 class scope는 클래스 정의 안에서 선언된 모든 이름이 가지는 스코프다. 같은 클래스 안에서 선언됐다면, 클래스의 멤버 변수나 멤버 함수는 물론이고, static 멤버, static 함수, nested class나 class 안에서 정의된 enumeration과 타입들도 모두 같은 class scope로 묶인다.
 이때 function scope처럼 모든 이름이 hoisting 된 것으로 해석된다. 예를 들어 아래와 같은 함수가 있을 때, S::f 함수 안에서 i를 사용할 때, 아직 S::i는 선언되지 않았기에 func 함수에 지역 변수로 선언된 i를 의미하는 것 같지만, 실제로는 S 클래스의 모든 변수 선언이 hoisting 됐기 때문에 클래스 S 안에서 사용되는 i는 모두 S::i를 의미한다.

function prototype scope

 위에서 이미 함수의 인자는 block scope를 가진다고 말했기 때문에 function prototype scope가 따로 존재한다는 것이 이상할 수 있다. 하지만 이 이름을 잘 보면 답을 알 수 있다. function prototype scope는 function declarator에 한정되는 scope이다. function prototype scope에 해당하는 이름. 즉, 함수의 파라미터는 선언된 순간부터 function declarator가 끝나는 순간까지 사용할 수 있다.  따라서 위와 같은 코드가 있을 때 f 함수의 인자로 선언된 abf의 선언이 끝날 때까지 function prototype scope를 가지고, function body에서는 block scope로 사용된다. 이때 선언된 순간부터 사용할 수 있으므로, a의 기본값으로 사용된 b는 첫 번째 줄에서 선언된 constexpr intb이다.  하지만 위와 같은 코드에서는 b의 기본값으로 a를 사용하기 전에 이미 a를 인자로 선언했기 때문에 첫 번째 줄에서 선언한 a가 아닌 첫 번째 인자인 a가 된다. 이때 a가 무엇인지 컴파일 타임에 알 수 없으므로 이는 컴파일 에러를 발생시킨다.
 하지만 아래처럼 컴파일 타임에 값을 알 수 있는 경우에는 사용할 수 있다.  이때 sizeof에 사용된 a는 첫 번째 줄에서 사용된 int32_t가 아닌, 첫 번째 인자인 int8_t 이므로 기본값은 1이 된다.

template parameter scope

 마지막으로 설명할 스코프는 template parameter scope다. 이름 그대로 template parameter의 스코프를 정해주기 위한 것으로 선언된 순간부터 접근 가능하며, 선언을 포함한 가장 작은 template의 구현이 끝나는 시점까지다. template parameter scope인 이름은 해당하는 스코프가 끝날 때까지 다른 이름으로 사용할 수 없다. 즉, template 함수나 template 클래스 안에서 template parameter의 이름을 다른 이름으로 사용할 수 없다.
 하지만 template parameter scope 안에 다른 template parameter scope가 있을 때, 바깥 스코프에서 선언된 이름을, 안쪽 스코프에서 다시 선언하여 사용할 수는 있다.

 지금까지 C++이 가지는 스코프의 종류에 관해서 설명하였다. 요약하자면 C++은 block scope, namespace scope, enumeration scope, function scope, class scope, function prototype scope, template parameter scope의 7가지 스코프를 가지고 있으며, 이 중 class scope와 function scope는 선언한 위치에 상관없이 스코프 내에서 모든 언제나 의미를 가지지만, 나머지 5개 스코프는 이름이 선언된 순간부터 의미를 가진다. 또한, namespace scope, enumeration scope, class scope의 경우 스코프 밖에서도 ::(scope resolution operator)를 통해서 접근할 수 있다.

2017-07-24

[C++] object는 언제 생성돼서 언제 소멸되는가 - storage

 C++에서는 타입을 가지는 일정 크기의 값을 object라고 한다. object의 중요한 특징 중 하나는 lifetime. 즉, object가 언제 소멸하는가 하는 것이다. 이 object는 객체 지향 프로그래밍에서 말하는 객체와는 살짝 다른 개념이다. C++ 표준에서 object는 타입, alignment, lifetime 등의 특성을 가지는 일정 크기의 연속된 값을 의미한다. 이는 객체 지향 프로그래밍에서 말하는 객체와는 약간 다른 의미이지만 이 글에서는 그냥 객체라고 부르도록 하겠다.
 C++에서 객체의 lifetime을 알기 위해서는 우선 객체가 어디에 생성되는지를 알아야 한다. 일반적으로 C++ 개발자에게 객체가 어디에 생성되는지를 물으면 다음과 같이 대답할 것이다.

 로컬 객체는 stack에, new로 생성된 객체는 heap에 저장되는데 stack과 heap은 같은 메모리 영역을 공유하며 stack은 메모리가 감소하는 방향으로 커지고, heap은 메모리가 증가하는 방향으로 커진다. 또한, 전역 변수 중 initialize 되지 않은 것은 bss에 initialize 된 것은 data 섹션에 저장된다.
 이 대답은 기술적으로 맞는 대답이다. 사실 매우 훌륭한 대답이다. 실질적으로 대부분의 머신에서 대부분의 컴파일러는 위와 같은 방식으로 코드를 컴파일한다. 하지만 다시 한번 생각해보자. stack과 heap이 같은 메모리를 나누어 쓰는 이유는 한정된 크기의 메모리에서 컴파일 타임에 알 수 없는 두 종류의 동적 메모리를 할당하기 때문이고, bss 영역과 data 영역이 나누어지는 이유는 바이너리 파일의 크기를 줄이기 위한 최적화 때문이다. 즉, stack, heap, data, bss 등의 메모리 영역 등은 구현에 관련된 것일 뿐이다. 그렇다면 C++ 표준 문서에서는 이에 대해서 어떻게 기술하고 있을까?
 C++ 표준에서는 객체가 메모리에 생성된다고 하지 않고, 스토리지에 생성된다고 한다. 구현과 표준을 분리하기 위한 결정으로 구체적인 메모리 레이아웃 등을 정하지 않음으로써 컴파일러들에게 실행 머신에 따라 최적화시킬 여지를 주기 위해서다. C++에는 원래 automatic, dynamic, static 3개의 스토리지가 있었고 C++11에서 thread_local이 추가되어 네 종류의 스토리지가 있다.

automatic storage

 가장 기본적인(?) 스토리지는 automatic storage다. C++에 익숙한 사람이라면 스택 영역이라고 생각하면 된다. static specifier가 없는 로컬 객체는 automatic storage에 할당되는데, 이는 선언된 위치에서 생성되고, block을 떠날 때 생성된 역순으로 소멸된다.
 C++ 11 이전에 있었던 auto specifier는 객체를 automatic storage에 저장하라는 의미였다. 로컬 객체는 따른 specifier가 없으면 모두 automatic storage에 저장되므로 아무 의미가 없으므로 별로 사용되지 않았고 지금은 auto 키워드는 타입 추론과 관련된 의미로 변경됐다.

dynamic storage

 dynamic storage는 다른 이름으로 free storage라고 부르기도 한다. new 키워드로 생성된 객체는 dynamic storage에 생성되고 명시적으로 delete가 불리기 전에는 소멸하지 않는다. 일반적으로 dynamic storage에 저장되는 object는 메모리의 힙 영역에 저장되도록 구현된다. delete가 불리지 않으면 소멸하지 않고, 같은 객체에 대해서 두 번 호출되면 메모리가 오염되는 문제가 생긴다. 따라서 dynamic storage에 생성되는 객체를 automatic storage에 생성되는 객체와 같은 라이프타임을 가지게 하는 RAII같은 기술이 많이 사용된다. 특히 C++11 이후의 modern C++에서는 shared_ptr이나 unique_ptr에 종속되지 않은 dynamic 객체가 존재하는 것을 좋지 않은 코드로 본다.

static storage

 구현에서는 초기화됐는지 아닌지에 따라 data 영역과 bss 영역을 구분한다. 하지만 이는 바이너리 파일의 크기를 줄이기 위한 최적화일 뿐이고 표준 문서에서는 둘을 구분하지 않는다. 명시적으로 static 한정자가 붙었거나, namespace 스코프의 변수는 모두 static storage에 생성된다. 초기화됐건 선언만 했건 둘 다 static storage에 할당되고 그저 초기화되지 않은 static 객체는 0으로 초기화된다고 할 뿐이다.
 static storage에 생성된 객체는 프로그램이 종료될 때, 생성이 완료된 순서의 역순으로 소멸한다. 하지만 프로그램이 어떻게 종료되더라도 언제나 소멸되는 것은 아니다. main 함수가 종료돼서 끝나거나 exit 함수에 의해서 종료되면 static 객체는 소멸하지만 termiate에 의해서 종료되거나 예외를 잡지 못해서 종료되면 static 객체는 소멸하지 않는다.

thread-local storage

 thread-local storage는 C++11이 스레드를 지원하면서 새로 생긴 스토리지다. 변수 선언 시 thread_local 한정자를 붙이면 thread-local storage에 객체가 할당된다. 이는 static storage와 비슷하지만 스레드별로 생성되고 그 라이프타임도 스레드에 종속된다
 보통의 컴파일러들이 thread local 객체를 구현하는 방법도 static 객체와 비슷하다. 선언만 된 객체들의 크기의 합과 초기화된 객체의 값이 따로 저장된다. 각 영역은 흔히 tbss와 tdata라고 불린다. 파일 포맷에서는 static object와 비슷하지만, 실행시킬 때는 사실 stack에 저장되기 때문에 메모리상에서는 스택과 비슷한 위치에 생성된다. 조금 더 정확히는 스레드별로 별개의 스택 시작 위치를 가지는데, 이때 스택의 시작 부분에 thread local 객체들을 생성한다.
 thread local 객체는 스레드 시작에서 생성자가 불리고, 스레드가 종료될 때 소멸하는데 static 객체와 마찬가지로 예외에 의해서 종료되거나 terminate에 의해서 종료되면 thread local 객체는 소멸하지 않는다.

 이상이 C++11이 가지고 있는 네 종류의 스토리지에 대한 설명이었다. 이 스트로지는 객체의 lifetime을 결정하기 때문에 잘 알고 있어야 한다. automatic storage에 할당된 객체는 그 레퍼런스가 해당 block을 벗어나지 않도록 해야 하고, dynamic storage에 할당된 객체는 반드시 한 번만 소멸하도록 신경 써서 코드를 작성해야 하며, static storage는 프로그램 전체에서 하나만 생기고, thread-local sotrage는 스레드마다 하나씩 생기며 스레드와 라이프타임을 공유한다. static storage와 thread-local storage에 생성된 객체의 소멸자는 생성자가 완료된 순서의 역순으로 호출된다는 것을 조심해야 한다. 소멸한 객체에 대한 접근은 잡기 힘든 버그를 만드니 자신이 만든 객체가 어떤 storage에 저장되고 어떤 lifetime을 가지는지 반드시 신경 써야 한다.

2017-07-12

[C++] glvalue와 prvalue

 지난번 글에서 lvalue와 rvalue의 특징을 설명하면서 예고했듯이 이번에는 glvalue와 prvalue의 특징에 관해서 설명하도록 하겠다.
 전에도 말했듯이 C++의 value category의 최하단에 있는 lvalue, xvalue, prvalue 중에서 lvalue와 xvalue가 glvalue에 포함된다. lvalue는 iM, xvalue는 im이고, prvalue는 Im이므로 glvalue와 prvalue를 나누는 기준은 i인지 아닌지. 즉, identity를 가지는지 여부이다. identity를 가진다는 것은 그 값이 expression을 넘어서까지 살아있다는 것이다. 그래서 identity를 가진다는 것은 그 값이 persist하다고 말하기도 한다.

temporary object

 prvalue는 persist 하지 않다. 이는 prvalue인 expression이 의미하는 object가 특정한 스토리지를 점유하지 않는다는 것이다. 만약 스토리지에 할당될 필요가 있으면 prvalue는 temporary object를 생성한다. 생성된 temporary object는 레퍼런스 변수에 할당되지 않으면, expression이 끝나고 소멸한다.

incomplete type

 prvalue는 구체화할 때 temporary object를 생성하므로, 컴파일 타임에 expression의 타입을 정확히 알아야 한다. 따라서 전방 선언만 돼있는 incomplete type인 prvalue는 있을 수 없다. 하지만 실행될 일 없는 decltype 안에 있는 expression의 경우 incomplete type인 prvalue가 있을 수 있다.

polymorphic

 incomplete type의 prvalue가 있을 수 없는 것과 비슷하게 prvalue는 polymorphic 할 수 없다. 다시 말해서 prvalue인 object의 dynamic type은 그 expression의 static type과 항상 같다. persist 하지 않다는 prvalue의 특성을 생각하면 이것도 매우 당연한 성질이다. C++에서 어떤 object를 polymorphic하게 사용하려면, derived type의 object를 만들어 놓고 base type의 레퍼런스로 접근해야 한다.  하지만 변수나 레퍼런스가 아닌 타입을 리턴하는 함수는 prvalue가 될 수 없으므로, prvalue는 polymorphic 할 수 없다는 것은 자연스럽다.

2017-06-30

[C++] lvalue와 rvalue

 지난번 글에서 C++의 value category에 관하여 설명하였다. 요약하면 다른 값으로 move될 수 있는지와 identity를 가지는지에 따라서 lvalue, xvalue, prvalue로 나뉘고, lvalue와 xvalue를 합쳐서 glvalue, xvalue와 prvalue를 합쳐서 rvalue라고 부른다는 것이다.
 앞에서도 말했듯이 C++의 value category를 나누는 기준은 move 될 수 있는지와 identity를 가지는지 여부이다. 이중 iM은 lvalue라고 부르고, im인 xvalue와 Im인 prvalue를 합쳐 rvalue라고 부른다. identity를 가지지도 않고, move 될 수도 없는 IM은 C++에 존재하지 않기 때문에 사실상 lvalue와 rvalue를 나누는 기준은 move 될 수 있는지 아닌지이다. 따라서 move 될 수 없으면 lvalue이고, move될 수 있으면 rvalue이다. 이번 글에서는 그래서 lvalue와 rvalue가 구분되는 특성을 설명할 것이고 다음 기회에 glvalue와 prvalue가 구분되는 특성을 설명하도록 하겠다.

overloaded function

 우선 lvalue와 rvalue의 가장 중요한 차이는 overload 된 함수가 있을 때 어떤 함수가 호출될지가 달라진다는 것이다.
위처럼 같은 타입의 lvalue reference를 받는 함수와 rvalue reference를 받는 함수가 overload돼있을 때, argument가 lvalue이면 lvalue reference를 받는 함수가 호출되고, rvalue이면 rvalue reference를 받는 함수가 호출된다.
따라서 위와 같이 사용했을 때, func(a)a가 lvalue이므로 0이 리턴되지만, std::move(a)는 xvalue이고 1prvalue이므로 func(std::move(a))func(1)1이 리턴된다.

universal reference

 rvalue reference(&&)처럼 생겼지만, 타입 추론을 해야 하는 경우. 즉, template parameter T가 있을 때 T&&라거나, auto&& 같은 경우 이 타입은 lvalue reference가 될 수도 있고, rvalue reference가 될 수도 있다. 그래서 이런 레퍼런스는 universal reference라고 불린다. 이 universal reference는 bind 되는 값이 lvalue이면 lvalue이면 lvalue reference가 되고, rvalue이면 rvalue reference가 된다. C++의 템플릿 타입 추론에 대해서 설명할 일이 있으면 더 자세히 설명하겠다. 우선은 universal reference는 bind 되는 값이 lvalue인지 rvalue인지에 따라서 어떤 값인지에 따라서 달라진다는 것만 알아두자.

& operator

 lvalue가 rvalue와 다른 중요한 특성 중 하나는 주소를 가지고 오는 & operator의 인자로 lvalue는 사용할 수 있지만, rvalue는 사용할 수 없다는 것이다. 언뜻 생각하면 identity를 가지는 xvalue의 주소를 가지고 오는 것도 가능할 것 같지만, C++11은 & operator의 인자로 올 수 있는 것은 lvalue만이라고 한정하고 있다.

assign operator

 또 다른 특징은 rvalue는 assign operator(=)의 왼쪽에 올 수 없다는 것이다. 조심해야 할 것은 rvalue가 assign operator의 왼쪽에 올 수 있다는 것이지, lvalue가 assign operator의 오른쪽에 올 수 있다는 말은 아니라는 것이다. C++에는 const modifier가 있으므로 모든 lvalue가 assign operator의 왼쪽에 올 수 있지는 않다. 따라서 왼쪽에 올 수 있는 것은 modifiable lvalue라고 따로 분류해서 부른다.


  • 2017-06-30 universal reference 부분을 추가했습니다.

2017-06-17

왜 c++은 복잡한 value category를 가지게 됐는가

 C++11이 나오기 전, C++의 value category는 lvalue와 rvalue만으로 이루어진 단순한 분류체계를 가지고 있었다. 하지만 C++11이 나오면서 xvalue, glvalue, prvalue가 추가되면서 복잡한 분류체계를 가지게 됐다. 이번 글에서는 C++11에서 변경된 value category에 대해서 알아보도록 하겠다.

until c++03

 C++11에서 새로 추가된 value들을 알기 전에 C++03 이전에도 있었던 lvalue와 rvalue가 뭔지부터 확실히 하고 넘어가야 한다. 흔히들 많이 실수하는 것이 lvalue는 assign operator(operator =)의 왼쪽에 올 수 있는 값이고, rvalue는 올 수 없는 값이라고 생각하는 것이다. C에서 lvalue라는 개념이 처음 나왔던 시절에는 assign operator를 기준으로 lvalue인지 아닌지를 구분하는 것이 맞았다. 하지만 C89에서 const 한정자가 추가되면서 더는 맞지 않다. const variable은 lvalue이지만 assign operator의 왼쪽에 올 수 없기 때문이다.
 따라서 C89에서는 lvalue를 left value가 아닌 locator value. 즉, 실제 값이 아닌 값이 있는 주소를 지칭하는 locator value라고 정의했다. 즉, 변수는 locator이기 때문에 lvalue이고, 1, 2 같은 숫자 리터럴이나 'a', 'b' 같은 문자 리터럴, 혹은 함수의 실행 결괏값 같은 경우 특정한 주소를 지칭하는 locator가 아니므로 lvalue가 아니다. 이 중에서 const 한정자가 붙지 않은 경우를 modifiable lvalue라고 따로 분류하여, modifiable lvalue만 assign operator의 왼쪽에 올 수 있다. 후에 나온 C++98도 C89의 lvalue 정의를 따랐기 때문에 C++98에서의 lvalue도 locator 라고 보면 된다. 다만 C89와 다르게 레퍼런스를 리턴하는 함수가 존재하기 때문에, 함수의 결과 타입이 레퍼런스일 경우, 함수의 실행 결과가 lvalue가 된다.

identity

 C++11에서는 기존의 lvalue가 가지는 특성을 identity를 가진다고 표현한다. 어떤 expression이 identity를 가진다고 하면 그 expression은 다른 expression이 표현하는 것이 같은 것(원문은 entity라고 하는데 이를 표현할 번역을 못 찾았다.)인지 비교할 수 있다는 것을 의미한다. 예를 들어 a라는 변수와 b라는 변수가 있으면 이 둘은 주소를 비교해서 같은 값을 가리키는지 아닌지 비교할 수 있으니 변수는 lvalue이다. 하지만 숫자 literal이나 boolean literal은 두 expression이 같은 entity인지 비교할 수 없기 때문에 rvalue이다. 또한 리턴 타입이 레퍼런스가 아닌 함수의 실행이나 타입 캐스팅같이 임시값으로 해당 expression이 넘어가면 사라지는 임시값들도 rvalue이다. 즉, lvalue의 경우 expression이 넘어서까지 entity가 존재하는 expression이기 때문에 identity를 가진다는 것을 persistence가 있다고 표현하기도 한다.

move

 C++11에서는  identity 말고 한 가지 특성이 더 추가됐다. C++11의 새 기능 중 가장 유명한 move가 추가됐기 때문이다. 모든 값이 move 될 수 있는 것은 아니기 때문에 이제 C++에서는 어떤 값이 다른 값으로 move 될 수 있는지 아닌지도 매우 중요한 특성이 됐다.
 이제부터 어떤 값이 move 될 수 있으면 m, move 될 수 없으면 M이라고 부르겠다. 또한, 앞에서 설명한 identity를 가지는 경우 이 값을 i, identity를 가지지 않는 경우 I라고 부른다. 이 identity를 가지는지와 move 될 수 있는지를 조합하면 iM, im, Im, IM 4가지 조합이 나온다. 하지만 이 중 IM. 즉, identity를 가지지도 않고, move 될 수도 없는 값은 있을 필요가 없으므로 우리는 iM, im, Im 3가지 조합만 살펴보면 된다.

iM - lvalue

 iM. 즉, identity를 가지지만, move 될 수도 없는 expression을 C++11에서는 lvalue라고 부른다. C++03까지의 lvalue 정의에 move 될 수 없다는 조건이 더 추가된 것이다. lvalue의 가장 큰 특징은 lvalue만이 & operator의 피연산자로 사용될 수 있다는 것이다, Im은 identity를 가지지 않기 때문에, iM은 move 돼 버릴 수 있으므로 & operator의 피연산자로 사용될 수 없다.

im - xvalue

 identity를 가지지만 move 될 수 있는 im의 경우는 eXpiring에서 따와 xvalue라고 부른다. xvalue는 이름 그대로 만료되어 가는 값이다. 따라서 expression이 끝나고 expression이 의미하던 주소로 접근했을 때 값이 존재할 수도 있고, 존재하지 않을 수도 있다. rvalue reference를 리턴하는 함수의 결괏값이나 rvalue rference로 타입 캐스팅 하는 expression이 xvalue에 해당한다. std::move도 rvalue reference를 리턴하는 함수이기 때문에 무언가를 move한 값은 xvalue에 속하고, lvalue를 move할 수 있게 만드는데 사용된다.

Im - prvalue

 마지막으로 identity를 가지지 않는 Im은 pure rvalue라는 의미에서 prvalue라고 부른다. 이는 C++03까지의 rvalue와 같다고 봐도 무방하다. prvalue는 C++에서 유일하게 identity를 가지지 않는다. non-reference를 리턴하는 함수의 실행결과나 non-reference로의 타입 캐스팅 혹은 숫자 boolean 리터럴들이 여기에 속한다.
 또한, identity를 가지지 않는다는 특성 때문에 prvalue는 다른 값들과 다르게 incomplete type일 수 없다. expression이 사용되는 시점에서 값이 존재해야 하기 때문이다.

m - rvalue

 Im이 rvalue가 아니라 pure rvalue인 이유는 rvalue가 따로 있기 때문이다. C++03 이전에는 identity를 가지지 않는 값을 rvalue라고 불렀지만, C++11에서는 m. 즉, move될 수 있는 값을 rvalue라고 부른다. 그래서 im인 xvalue와 Im인 prvalue 둘은 rvalue에 속하고, move될 수 없는 im, lvalue는 rvalue가 아니다.

i - glvalue

 move 될 수 있는지를 기준으로 lvalue와 rvalue를 나누듯이 identity를 가지는지 아닌지로 glvalue와 prvalue를 나눈다. 그래서 iM(lvalue)와 im(xvalue)는 glvalue로 분류된다. identity를 가진다는 것은 해당 expression이 끝나도 object는 남아있다는 것이고, 이 expression은 그저 object를 가리키는 무언가일 뿐이라는 것이다. 그래서 glvalue에 속하는 lvalue나 rvalue는 incomplete 한 타입일 수 있고, polymorphic 할 수도 있다.

2017-04-30

round - 실수를 정수로 근사하기

 지난번 글에서 round라는 것은 반올림이 아니고 근삿값을 구하는 방법이기에 다양한 방법이 있다고 설명했었다. 하지만 프로그래밍에서 round 함수는 대부분 실수를 정수로 만드는 round이다. 그래서 이번 글에서는 실수를 정수로 근사하는 방법들을 설명하도록 하겠다.

 우선 실수를 정수로 만드는 근사법 중에서 가장 유명한 것은 ceilfloor이다. 이는 각각 round upround down이라고 부르기도 하는데 이를 번역하여 한국어로는 올림과 내림이라고 부른다. 번역 그대로 ceil은 근삿값을 구하는 자릿수에서 값을 올리고, floor는 내린다. 따라서 ceil(2.5)는 3이 되고 floor(2.5)는 2가 된다. 또한, 이 둘은 양의 무한과 음의 무한을 향해 가는 모습이기 때문에 각각 round towards positive infinityround towards negative infinity라고 불리기도 한다.
 이와 구현이 비슷한 것으로 truncate가 있다. truncate는 보통 버림이라고 번역되는데, 이는 근삿값을 구할 자릿수 아래의 값을 버린다. 따라서 truncate(2.5)는 2가 된다. 이는 floor와 같아 보이지만 다른 구현이다. 예를 들어 floor(-2.5)의 경우 이는 음의 무한을 향해 가기 때문에 -3이 되지만, truncate(-2.5)는 자릿수를 버려 -2가 된다. 이는 0에 가까운 수를 고르는 것 같은 동작을 하므로 round towards zero라고 부른다. 이와는 반대로 0에서부터 멀어지는 방향으로 움직이는 round away from zero라고 부르는 방법도 있지만, truncate에 비해 딱히 특색이 있지는 않아서 잘 쓰이지 않는다.

 지금까지 설명한 ceil, floor, truncate, round away from zero는 모두 큰 쪽이거나 작은 쪽이거나 한 방향으로 움직인다. 하지만 이보다 더 많이 사용되는 것은 가까운 정수(to nearest)로 만드는 것이다. 예를 들면 round(2.4)의 경우 2와의 거리는 0.4고 3과의 거리는 0.6이기 때문에 2가 되고, round(-6.1)의 경우 -6과의 거리는 0.1이고, -7과의 거리는 0.9이기 때문에 -6이 된다. 사실 대부분의 수학 라이브러리에서 round 라는 이름의 함수는 이런 방식으로 동작한다.
 가장 가까운 수를 구하는 to nearest round에서는 반드시 정해야 하는 것이 있다. 만약 가장 가까운 수가 2개 있으면 어떤 수를 돌려줘야 할까? 이를 tie-breaking이라고 하는데 가장 많이 쓰이는 방법은 반올림이라고 알려진, 둘 사이의 거리가 같을 경우 위쪽 수를 돌려주는 half up 방식이다. half up 방법에서는 2.5의 경우는 3이 3.5는 4가 된다. 반대로 두 수 사이의 거리가 같으면 아래쪽 수를 선택하는 half down이라고 불리는 방법도 있고, 0을 기준으로 가까운 수를 선택하는 half towards zero나 0에서 먼 수를 선택하는 half away from zero도 있지만, half up 방식보다 장점이 없어서 잘 사용되지 않는다.
 일반적으로 half up은 널리 사용되는 round 방식이지만, 근본적으로 큰 문제가 있다. 둘 중 거리가 같을 때 위쪽 수를 택하기 때문에 일렬의 수 집합을 전부 반올림하면 전체적으로 값이 한쪽으로 평향되는 문제가 생긴다. 이 문제를 해결하기 위해 사용되는 방법이 half to even이다. half to even은 두 수 사이의 거리가 같을 경우 짝수를 선택하는 방법이다. 즉, round(2.5)는 2가 되고 round(3.5)는 4가 된다. 이는 IEEE 754에서 기본값으로 사용되는 방법이기도 하다.
 비슷한 방식이지만 홀수를 택하는 half to odd라는 방법도 있지만, half to even에 비해서 딱히 장점이 없어서 잘 사용되지 않는다.

 half to even이나 half to odd의 경우 잘 분포돼있는 입력에 대해서 round한 값의 평균이나 합이 편중되지 않은 것을 보장하지만, 개별적인 값의 분포를 봤을 때 짝수나 홀수로 편중되는 결과가 나올 수 있다. 이런 문제를 해결하기 위한 방법으로 stochastic round가 있다.
 stochastic round는 가까운 정수로 보내는데 둘 사이의 거리가 같을 때 어느 수를 택할지 확률적으로 결정하는 것이다. 이는 편향성을 높은 확률로 제거할 수 있다. 하지만 랜덤하게 실행마다 결과가 달라진다는 점 때문에 거의 사용되지 않는다.
 이런 랜덤성을 최소화하기 위해 사용되는 방법이 alternate round라는 방법이다. alternate round는 둘 사이의 거리가 같을 때 한 번은 홀수 한 번은 짝수를 선택하는 방법이다. 처음 선택은 1/2 확률로 선택해도 되고 아니면 홀수나 짝수로 고정해도 된다. alternate round를 이용하면 랜덤성을 최소화하며 편향을 없앨 수 있다. 하지만 round 함수가 불리는 순서가 같을 것이 보장돼야 한다는 제약이 있다.

 이래저래 다양한 방법을 설명했지만, IEEE 754에서 제시하는 표준은 ceil, floor, truncate, half up, half to even이고 기본 값은 half to even이기 때문에 보통 수학 라이브러리는 이 5개의 함수 정도만을 제공한다. 대부분의 경우 tie break에서 생기는 편향이 큰 문제가 되지 않기 때문에 이는 별문제가 되지 않지만 만약 tie break의 편향성이 걱정된다면, stochastic roundalternate round를 고려해봐야 한다.

2017-03-13

round(1234.5)의 결과는 무엇일까

 혹시 1235라고 생각했는가? 그렇다면 아마 다음과 같은 과정을 거쳤을 것이다. round는 주어진 실수를 정수로 반올림하는 것이다. 반올림은 가장 가까운 수를 만드는 것이다. 반올림할 자릿수가 0, 1, 2, 3, 4이면 내리고 5, 6, 7, 8, 9이면 올린다. 따라서 1234.5의 5는 올려야 하므로 답은 1235이다. 만약 이렇게 생각했다면 round가 무엇인지 제대로 이해하지 못한 것이다.

 round가 무엇인지 알기 위해 우선 round의 정의부터 확실히 해보자. 흔히들 착각하는 것이 ceil은 올림, floor는 내림, round는 반올림이라고 생각하는 것이다. 하지만 round는 반올림이 아니다. Wikipedia에서 말하는 round의 정의는 다음과 같다.

Rounding a numerical value means replacing it by another value that is approximately equal but has a shorter, simpler, or more explicit representation.

 round란 것은 반올림이 아니라 근삿값을 구하는 것이다. 즉, 반올림을 구하는 것도 round이지만, 올림과 내림도 round고, 12345678 같은 복잡한 분수를 15로 간단하게 표현하는 것도 round이다.

 또한, 반드시 일의 자리까지 round 할 필요도 없다. 물론 보통의 round 구현은 실수를 입력받아 정수 근삿값을 만든다. 하지만 반드시 이럴 필요는 없다. 경우에 따라서 십의 자릿수 까지 근사값을 만들 수도 있고, 백의 자릿수 까지 근사값을 만들 수도 있다. 즉, round(1234.5)의 답은 1000이 될 수도 있고, 1200이 될 수도 있고, 50 단위로 근사값을 구한다면 1250이 될 수도 있다.

 따라서 round를 어떻게 구현했는지 사용하는 라이브러리의 스펙을 확인해봐야 한다.

2017-03-05

JavaScript와 IEEE 754

 JavaScript는 표준에서 숫자 타입은 IEEE 754-2008, 64 bit format을 따른다고 명시돼있다. 따라서 숫자 타입의 연산도 IEEE 754-2008을 따를 거로 생각했다. 하지만 ECMAScript 명세에서 NaN이나 Infinity를 포함한 연산에 대해 다른 결과를 내도록 정의한다.

 그 대표적인 경우가 1-1이다. IEEE 754-2008는 지수를 계산하는 방법을 3가지 정의한다. 첫 번째는 pown으로 지수가 정수인 경우에 대해 정의돼있고, 두 번째 pow는 밑과 지수가 모든 실수인 경우 사용할 수 있도록 정의돼 있고, 마지막은 powr으로 밑이 0 이상의 실수인 경우에 대해서 정의돼 있다. 우선 첫 번째인 pown는 지수가 가 되지 못하므로 관심 대상이 아니다. 다른 두 지수 함수인 powpowr1에 대해 다른 결과를 내도록 정의한다. pow1을 리턴하고, powrinvalid operator exception을 발생하도록 정의했다. 사실 이는 양쪽 다 이상한 것은 아니다. limx1x1에 수렴하지만 1 자체는 부정이기 때문에 1인 경우와 invalid operator exception이 발생하는 경우 양쪽 모두 말이 되기 때문이다. 그렇다면 IEEE 754-2008은 -1를 어떻게 정의할까?
 이 경우 밑이 0보다 작으므로 pow만이 유효한 함수고, 이에 대해서 1을 리턴하도록 정의했다. limx-1x는 발산하고, -1는 부정이기 때문에 이는 수학적으로 올바른 정의가 아니고, IEEE 754에서 어떻게 이렇게 정했는지는 모르겠다. 역사적인 이유이거나 이렇게 할 경우 구현이 편해지기 때문일 것인데 혹시 정확한 이유를 알고 있는 사람이 있으면 알려주기 바란다.

 ECMAScript에서는 1-1의 연산에 대해서 NaN을 리턴하도록 정의했다. 이는 ECMAScript는 1997년 만들어졌다. 즉, 아직 IEEE 754-2008이 나오기 전이었고 그 당시는 가 지수인 것에 대해 어떻게 계산해야 하는지 표준이 없었다. 그래서 ±1x일 경우 부정이라고 하는 수학적 성질을 따라 NaN이라고 정하였고, format은 IEEE 754-2008을 쓰기로 한 지금도 NaN을 리턴하도록 정해진 것이다.

 또 한 가지 다른 점은 나머지 연산이다. 나머지는 xy로 나눴을 때, x-q*y로 정의된다. 이는 xy가 둘 다 양수일 경우 명확하지만, 둘 중 하나라도 음수가 되면 q를 정하는 다양한 수가 나올 수 있다. IEEE 754-2008은 이에 대해서 단순한 솔루션을 제시한다. round(x / y)q로 삼는 것이다. 이는 간단하게 구현할 수 있지만, 일반적으로 예상하는 나머지가 나오지 않는 경우가 많아 많은 언어에서 float division은 다른 방식으로 정의하여 사용한다. 이는 ECMAScript도 마찬가지다. ECMAScript는 floor(abs(x / y))를 절댓값으로 가지고, xy의 sign이 같으면 양수, 다르면 음수인 값을 q로 삼는다.

2017-02-10

[c++] 생성자에서 예외가 발생하면 어떻게 될까

 R.A.I.I.를 사용하다 보면, 생성자에서 복잡한 일을 해야 할 경우가 종종 생긴다. 복잡한 일은 실패할 수도 있고, 그 경우 예외가 발생하기도 한다. 여기서 궁금한 점이 생긴다. 생성자에서 예외가 던져져도 아무 문제 없을까?

 우선 걱정되는 것은 메모리 릭이다. 하지만 다행히도 메모리 릭은 발생하지 않는다. 스택에 생성된 변수는 스택 unwind를 통해 메모리가 해제되며, new operator를 통해 힙에 할당하다 예외가 발생한 경우에도 new operator가 알아서 메모리를 해제하고 nullptr를 리턴해준다.

 그다음으로 걱정되는 것은 멤버 변수의 소멸자가 잘못 불리지 않을까 하는 것이다. 하지만 이 역시 문제없다. 예외가 발생한 시점에서 멤버 변수는 초기화가 완료된 멤버 변수, 초기화 중이었던 멤버 변수, 초기화되지 않은 멤버 변수 3가지로 나눌 수 있다.
 초기화가 완료된 멤버 변수는 말 그대로 생성자가 불렸고 정상적으로 메모리 할당을 완료한 멤버 변수다. 위 코드에서는 b에 해당하는데, 이들은 예외가 발생하면 이 변수들은 정상적으로 소멸자가 불리며 리소스를 해제한다.
 초기화 중이었던 변수는 위 코드에서 c에 해당하는 멤버 변수다. 위 코드는 E 클래스의 생성자에서 C인 변수 c의 생성자가 예외를 발생시켰다. 이 경우 E 클래스 입장에서 c는 초기화 중인 변수가 된다. 위 코드와 같이 멤버 변수의 초기화 중에서 예외가 발생하면 초기화 중인 변수가 1개 존재하지만, 생성자의 본체에서 예외가 발생하면 초기화 중인 변수는 존재하지 않는다.
 마지막으로 초기화되지 않은 변수의 경우 생성자가 불리지 않았으니 소멸자가 불리지 않는다. 하지만 이 경우는 아직 생성자가 불리지 않았기 때문에 소멸자가 안 불리는 것이 맞다.

 상속받는 경우는 어떨까? 부모 클래스에서 할당한 리소스는 정상적으로 해제될까? 당연히 이 경우도 아무 문제없다. 생성자에서 예외가 발생했을 때, 초기화가 완료 된 멤버 변수의 소멸자가 전부 불리고 나면, 부모 클래스의 소멸자가 불리며 리소스를 해제한다. 따라서 위의 코드를 실행시키면 다음과 같은 결과가 나온다.

 다시 처음 질문으로 돌아가 보자. 생성자에서 예외를 발생시키는 것은 아무 문제 없을까?
 위에서 보았듯이 아무런 문제도 없다...... 라고 말하고 싶지만, 사실 여기는 한 가지 가정이 필요하다. 클래스가 잘 설계되었다는 가정 하에서 생성자에서 예외가 던져져도 아무런 문제도 없다.

 그렇다면 잘 설계되지 않은 클래스는 무엇이고, 이 경우 어떤 문제가 있을?
 위의 코드를 보자. B의 생성자에서 A를 힙에 할당하고, 소멸자에서 명시적으로 delete를 호출하여 해제한다. 생성자에서 예외가 발생하지 않는다면 이 코드는 문제없다. B가 할당될 때 예외가 발생하면, A가 할당되며, B가 소멸할 때, A가 소멸한다.
 하지만 B의 생성자에서 예외가 발생하면 문제가 된다. B의 멤버 변수들을 정리할 때 a는 단순히 A의 포인터이기 때문의 A의 소멸자가 불리지 않는다. 또한, B가 초기화되지 않았기 때문에 B의 소멸자가 불릴 일도 없고 a는 메모리 릭이 된다. 이것을 막기 위해서는 아래와 같이 A의 라이프 타임을 B와 일치시켜야 한다.

2017-01-28

[Python] negative index를 사용하자

 일반적으로 random access 가능한 자료 구조에서 뒤에서 k번째 원소를 가져오는 방법은 다음과 같다.

  1. 자료구조의 크기를 가져온다.
  2. 크기를 기반으로 접근할 인덱스를 구한다.
  3. 원하는 자료를 가져온다.

 이를 코드로 표현하면 다음과 같다.
 파이썬에서는 이를 보다 간결하게 표현하기 위해 negative indexing을 지원한다. negative indexing은 말 그대로 음수를 이용해서 뒤에서부터 자료에 접근하는 것이다. negative indexing을 이용하면 위의 코드는 아래와 같이 표현된다.

 파이썬에서는 뒤에서부터 접근할 때 negative indexing을 사용하는 것이 권장되지만 다른 언어로 코딩을 처음 배운 사람들은 파이썬에서도 길이를 가져와 인덱스를 계산하는 방식을 사용하는 경우가 종종 있다. 이런 사람들은 negative indexing이 단순한 syntactic sugar라고 생각하는 것 같다. 하지만 negative indexing은 syntactic sugar가 아니다.
 negative indexing이 syntactic sugar라면 negative indexing을 쓴 것과 같은 바이트 코드가 생성돼야 한다. 하지만 둘은 서로 다른 바이트 코드가 생성된다. 위의 각 코드가 실제로 생성하는 바이트 코드는 다음과 같다.
 첫 번째 코드는 global memory에서 len 함수를 찾아 호출하여 그 결과에 k를 뺀 값을 인덱스로 사용하는 코드를 생성하고, 두 번째 코드는 k를 음수로 만들어 바로 인덱스로 사용한다. 인덱싱을 통해 값을 가지고 오는 바이트 코드는 BINARY_SUBSCR인데, 물론 인터프리터가 BINARY_SUBSCR 를 실행할 때 주어진 인덱스가 음수이면 내부적으로 리스트의 길이를 가져와 인덱스를 다시 계산하는 과정을 거친다. 하지만 Global Interpreter Lock(a.k.a. GIL) 때문에 이 둘의 동작은 같지 않다.
 파이썬의 GIL은 바이트 코드 단위의 atomic만을 보장한다. LOAD_FAST 같은 몇몇 바이트 코드는 GIL을 릴리즈하지 않지만, CALL_FUNCTION을 포함한 대부분의 바이트 코드는 실행 후 GIL을 릴리즈 할 수도 있다.

 또한, 두 코드는 생성되는 바이트 코드가 다르므로 수행 시간도 다르다. 첫 번째 코드는 global memory에서 len 함수를 가지고 와 호출하는 비용이 더 든다.
 게다가 negative indexing을 사용할 때 BINARY_SUBSCR가 내부적으로 계산한 인덱스와 다르게 첫 번째 코드에서 직접 계산한 인덱스는 단순한 정수가 아니라 정수를 들고 있는 PyObject이다. 따라서 값을 할당하고 해제하는 비용이 더 들기 때문에 negative indexing을 사용하는 것이 더 빠르다.

2017-01-10

Python은 어떻게 swap하는가

 지난번 글에서 Lua의 multiple assignment를 이용한 swap이 내부적으로 어떻게 돌아가는지 설명했었다. 그렇다면 파이선은 어떨까?

 자신의 버추얼 머신의 구현까지 제공하는 루아와 다르게 파이선은 공식적으로 어떤 버추얼 머신을 사용해야 하는지 제공하지 않는다. dis 라이브러리를 통해서 어떤 바이트 코드가 나오는지 알 수 있지만, 구체적인 버추얼 머신의 스펙을 정의하거나 바이트 코드의 구현을 정의하지 않는다. 덕분에 PyPy, IronPython, Jython 등 다양한 구현체가 존재한다. 이번에는 우선 그중에서 사실상 표준 구현체라고 할 수 있는 CPython의 구현에 대해서 살펴보겠다.
 CPython의 버추얼 머신이 어떻게 구현돼야 하는가는 명확히 기술되지 않았지만, CPython의 바이트 코드를 보면, CPython은 Lua가 레지스터 머신을 사용하는 것과 다르게 스택 머신을 사용한다는 것을 쉽게 알 수 있다. CPython의 버추얼 머신은 스택과 글로벌/로컬 메모리를 가지고 있다. 글로벌 메모리와 로컬 메모리는 객체의 레퍼런스를 저장하는 데 사용되고 계산을 하기 위해서는 스택으로 레퍼런스를 복사해온 뒤 사용해야 한다.

 이제 swap이 CPython에서 어떤 바이트 코드로 컴파일되는지 살펴보자.  위와 같은 코드는 아래와 같은 바이트 코드로 컴파일된다.  여기서 ROT_TWO는 스택의 가장 위의 두 아이템의 위치를 바꿔주는 바이트 코드다. 즉, 위의 바이트 코드는 스택에 a를 올리고 b를 올린 뒤, 스택의 가장 위의 두 아이템의 위치를 바꾸고, 스택 가장 위의 아이템을 b에 다음 아이템을 a에 저장하는 것이다.

 그렇다면 ROT_TWO는 어떻게 구현됐을까? 현재 CPython에서 ROT_TWO는 임시 변수 2개를 사용하여 스택의 두 값의 위치를 바꾸는 것으로 돼 있다. 즉, CPython에서는 변수 2개를 스왑하기 위해서 스택의 두 자리, ROT_TWO에서 사용하는 임시 변수 두 자리까지 총 6개의 의자가 필요하다.

 로컬 메모리를 바로 복사하지 않고 스택에 올린 뒤 다시 로컬 메모리로 아이템을 옮기도록 하는 이유는 CPython이 로컬 메모리 사이의 연산을 허용하지 않는 stack-based 머신이기 때문이다. 하지만 이 점을 고려해도 CPython의 swap 구현은 비효율적이다. 왜냐하면, 이미 스택을 다른 의자로 사용하고 있는데, ROT_TWO의 내부 구현이 다시 임시변수를 의자로 사용하기 때문이다. 그래서 조금 더 효율적인 바이트 코드를 생성하는 PyPy의 경우 이는 아래와 같은 바이트 코드를 생성한다.  이는 단순히 스택에 a를 올리고, b를 올린 뒤 스택의 가장 위에 있는 아이템을 a로 다음 아이템을 b로 내리는 코드이다. 하지만 여전히 스택에 ab를 둘 다 올릴 자리가 필요하므로 총 4개의 의자가 필요하다.

 그렇다면 파이선에서도 전통적인 방법으로 3번째 변수를 사용해서 스왑하는 것이 좋을까? 아쉽게도 그렇지 않다. 이는 파이선이 스택 머신이기 때문이다. 전통적인 스왑 코드를 컴파일하면 CPython이나 PyPy 양쪽 모두 다음과 같은 바이트 코드가 나온다.  전통적인 방법을 사용하면 우선 a의 아이템을 스택에 올린 뒤 스택에 있는 아이템을 temp에 내린다. 같은 방식으로 ba로 옮기고, tempb로 옮긴다. 즉, temp 변수를 사용하더라도 스택을 한 칸 사용하기 때문에 역시나 총 4개의 의자가 필요하다. 또한, PyPy를 사용하면 LOAD_FASTSTORE_FAST를 각각 한 번씩 적게 사용하고, CPython을 사용하더라도 LOAD_FASTSTORE_FAST를 하는 것보다 ROT_TWO를 하는 것이 더 빠르므로 성능 면에서도 multiple assignment를 이용해 스왑하는 것이 더 빠르다.

2017-01-08

Lua를 쓰면 3번째 의자가 필요하지 않을까 - lua는 어떻게 swap할까

 프로그래머들 사이에서 자주 하는 농담 중에 프로그래머 두 명이 자리를 바꾸려면 의자가 3개 필요하다는 농담이 있다. 둘이 동시에 자리에서 일어나 자리를 옮길 수 있는 사람과 달리 컴퓨터가 다루는 값은 언제나 어딘가에는 할당돼 있어야 해서 나온 말이다. c++로 작성하면 아래와 같은 코드가 되는데, 여기서 local 변수인 temp가 3번째 의자가 된다.

 그렇다면 multiple assignment가 가능한 lua같은 언어는 어떨까?

 lua로 swap 하는 함수를 짜면 위와 같은 코드가 된다. 일단 겉보기에는 3번째 의자가 필요 없어 보인다. 하지만 정말로 3번째 의자가 필요 없을까? 어떤 트릭을 쓰기에 그런 것이 가능한 것일까?

 일단 결론부터 말하면 그런 마법은 없다. 위의 코드가 루아 바이트 코드로 컴파일되면 다음과 같은 바이트 코드가 나온다.
 이 코드를 이해하기 위해 우선 루아 버츄얼 머신을 이해해야 한다. 루아 버츄얼 머신은 stack-based가 아니라 register-based 머신이다. 루아 버츄얼 머신은 최대 256개의 레지스터를 사용할 수 있으며, 함수의 인자는 순서대로 0번 레지스터부터 할당된다. 물론 이는 어디까지나 버츄얼 머신이 이렇다는 것이기 때문에 실제로 256개의 레지스터가 필요하지는 않고, 적절히 번역돼서 실행된다.
 이제 위의 바이트 코드를 읽어보자. b, a = a, bMOVE 2 0; MOVE 0 1; MOVE 1 2로 컴파일됐다. 이를 이해하기 위해서는 MOVE x y는 x번째 레지스터에 y번째 레지스터의 값을 복사해 넣는 바이트 코드라는 것과 인자로 넘어온 ab는 각각 0번 레지스터와 1번 레지스터에 저장돼 있다는 것을 알아야 한다. 그러면 위의 바이트 코드는 3번째 의자인 2번 레지스터를 이용해서 두 변수를 스왑한다는 것을 알 수 있다.