Rvalue reference와 함수의 반환값

C++에서 const Klass&반환값 형태의 단점들을 쓴지도 시간이 많이 지났네요. C++11에서는 많은 것이 바뀌었습니다. 대표적인 것이 rvalue reference로 대표되는 Move semantics입니다. Move는 RVO(return value optimization)가 동작할 수 없을 때 객체의 복사비용을 줄이는 목적으로 사용됩니다. Move는 객체를 “복사”하는 대신 객체가 내부에 가진 포인터만 가져옵니다. 그런이유로 속도가 매우 빠릅니다.

이 글에서는 rvalue reference와 관련해 함수의 리턴 타입과 적절한 반환값에 대해서 살펴보겠습니다.

지역 변수를 반환할 때
Herb Sutter는 widget* load_widget() 처럼 포인터를 반환하는 구시대적(?) 리턴 타입을 비판하면서 현대적 방식으로 다음 두가지 규칙을 제안했습니다.
1. 만약 반환할 객체에 다형성이 필요하다면 unique_ptr로 반환한다.
2. 만약 다형성이 필요없다면 그 반환할 객체가 값임을 의미한다. 그러므로 복사나 이동이 가능한 값으로 반환한다.

1번 규칙은 Scott Meyer의 Modern Effective C++에서 factory가 unique_ptr을 반환해야한다고 제안한 것과 일맥 상통합니다. 또 누가봐도 메모리 관리가 편하고, 메모리의 소유권이 명확하며, 객체의 복사가 필요없는 unique_ptr을 반환하는건 명확해 보입니다.

2번이 문제인데, 대체 어떻게 값으로 반환해야하는가 역시 고민거리이기 때문입니다. 이에 대한 해답을 다음 코드로 제시합니다.

#include <iostream>
#include <memory>

using namespace std;

class Foo {
  public:
    Foo(): destructed_(false) {
      cout << "ctor" << endl;
    }

    Foo(const Foo& other) {
      cout << "copy ctor" << endl;
    }

    Foo(Foo&& other) {
      cout << "move ctor" << endl;
    }

    Foo& operator=(const Foo& rhs) {
      cout << "copy assign";
    }

    Foo& operator=(Foo&& rhs) {
      cout << "move assign";
    }

    ~Foo() {
      destructed_ = true;
    }

    bool destructed_;
};

Foo retVal() {
  Foo f;  // 여기서 만들어진 객체가 그대로 main에서 사용된다.
  return f;  // RVO가 동작하므로 복사도 이동도 불필요
}

Foo retMove() {
  Foo f;
  return move(f);  // move를 명시하므로 move가 우선해서 사용됨
}

Foo&& retDangling() {
  Foo f;
  // reference 반환시 객체가 파괴되므로 런타임 오류.
  // reference는 항상 살아있는 객체에 대해서만 반환 해야한다.
  return move(f);
}

Foo retParam(Foo param_f, bool b) {
  // if-else로 인해 RVO가 동작하지 않는 경우.
  if (b) {
    Foo local_f;
    // 만약 RVO가 동작하지 않으면 자동으로 move가 시도된다.
    // 사실 이 경우가 move가 등장한 배경 중 하나.
    return local_f;  // move!
  }
  return param_f;  // move!
}

int main() {
  cout << "retVal" << endl;
  Foo f = retVal();
  cout << endl << "retMove" << endl;
  Foo f2 = retMove();
  cout << endl << "retParam, true" << endl;
  Foo f3 = retParam(Foo(), true);
  cout << endl << "retParam, false" << endl;
  Foo f4 = retParam(Foo(), false);
  cout << endl << "retDangling" << endl;
  Foo&& f5 = retDangling();
  cout << "f5 is " << (f5.destructed_ ? "destructed" : "live") << endl;
  return 0;
}

출력은 다음과 같습니다.

retVal
ctor

retMove
ctor
move ctor

retParam, true
ctor
ctor
move ctor

retParam, false
ctor
move ctor

retDangling
ctor
f5 is destructed

위 코드로 미루어볼 때 아무것도 모르는 사람이 코딩하듯이 지역변수를 반환할 때는 move없이 값으로 반환하는 것이 최상임을 알 수 있습니다. 그러면 RVO가 가능하면 RVO가 되고, 안되면 move가 시도되는 것을 알 수 있습니다. 그도 안되면 copy가 되겠죠.

이 규칙에는 한가지 예외가 있습니다. 반환하는 지역변수의 타입과 함수의 리턴 타입이 일치하지 않는 경우입니다. 다음은 함수의 리턴 타입은 optional<Foo>인데 실제 반환하는 값은 Foo인 경우를 보여줍니다. 이 경우에는 RVO나 move가 자동으로 동작하지 않아 move()를 반드시 해줘야합니다. 그러나 애초에 이런 암시적인 형변환에 의한 반환 자체가 나쁜거겠죠. 처음부터 optional<Foo>를 반환하면 될일입니다.

optional<Foo> returnOptional() {
  Foo f;
  return move(f);
}

객체의 멤버를 반환할 때
객체의 멤버 변수를 반환할 때는 지역변수와 달리 반드시 move를 해야합니다. 이에 대한 예를 다음 코드에 보였습니다.

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

class Foo {
  public:
    Foo(int v): value_(v) {
      cout << "foo ctor" << endl;
    }

    Foo(const Foo& other): value_(other.value_) {
      cout << "foo copy" << endl;
    }

    Foo(Foo&& other): value_(other.value_) {
      cout << "foo move" << endl;
    }

    int value() const {
      return value_;
    }

    ~Foo() {
      destructed_ = true;
    }

    bool isDead() {
      return destructed_;
    }

  private:
    int value_;
    bool destructed_ = false;
};

class C {
  public:
    C() {
      vals_.push_back(1);
      cout << "C ctor" << endl;
    }

    C(const C& other) {
      cout << "C copy" << endl;
    }

    C(C&& other) {
      cout << "C move" << endl;
    }

    ~C() {
    }

    void add(int v) {
      vals_.push_back(v);
    }

    vector<Foo> ret_val() &&;
    vector<Foo> ret_move() &&;


  private:
    vector<Foo> vals_;
};

// 함수명 뒤의 &&는 rvalue reference에 호출되는 함수임을 의미
vector<Foo> C::ret_val() && {
  // 그냥 반환하면 copy.
  // 지역변수의 경우와 달리 rvalue임에도 RVO나 move가 자동으로 되지 않는다.
  return vals_;
}

vector<Foo> C::ret_move() && {
  // move가 수행됨
  return move(vals_);
}

int main() {
  cout << "vals_ret" << endl;
  auto vals_ret_val = C().ret_val();
  cout << endl << "vals_move" << endl;
  auto vals_ret_move = C().ret_move();
  return 0;
}

다음은 실행 결과입니다.

vals_ret
foo ctor
foo move
C ctor
foo copy

vals_move
foo ctor
foo move
C ctor

Similar Posts:

if else 대신 빠른 return의 코딩 스타일

회사에서 코드 리뷰를 하다가 알게된 if-else 대신 빨리 return하는 코딩 스타일인데 접해보지 않은 분들도 계실것같아 올려봅니다. stack overflow에도 Programming style: should you return early if a guard condition is not satisfied?란 제목으로 글이 올라와 있기도 하고 effective go에도 간단히 언급되어 있는 스타일입니다.

stackoverflow에 있는 질문을 옮겨보자면 다음 두가지 코딩 스타일 중 어느것이 나은가라는 것입니다.

1. 반환값을 만들고 if문 또는 if else를 사용하는 경우

returnVal = null;
if (bar()) {
  returnVal = baz();
}
return returnVal;

2. 조건이 안맞으면 바로 리턴하는 경우

if (!bar()) {
  return null;
}
return baz();

저는 이 두가지 방법중 2번 방법을 선호합니다. 그 이유는 bar() 조건이 안맞는 경우 빨리 리턴해버림으로써 그 아래 코드를 읽을때 bar 조건이 안맞는 경우를 머리 속에서 제외하고 생각할 수 있기 때문에 코드 읽기가 쉬워지기 때문입니다. 위의 코드 정도야 간단해 보이지만 다음과 같이 복잡한 if-else 경우를 생각해보죠.

if (condition1) {
  foo1();
} else if (condition2) {
  foo2();
} else {  // condition1 == false && condition2 == false
  foo3();
}

이 예에서는 간단히 foo1(), foo2(), foo3() 정도만 호출했지만 실제로는 블럭 사이에 코드가 길어질 수 있고 그 경우 코드를 위에서 아래로 읽어오다가 마지막 else 문을 만나면 앞서 확인한 조건들이 무엇인지 잊어버리기 쉽습니다. 그런 이유로 위에처럼 주석에 어떤 조건들이 제외되었는지 적어주는 스타일이 사용되기도 하죠.

그런데 이 경우는 return 을 빨리 해버리면 더 쉽게 읽고 쓸 수 있습니다.

if (condition1) {
  foo1();
  return;
}
if (condition2) {
  foo2();
  return;
}
foo3();

위에서 아래로 오면서 condition1 이 만족되면 바로 return 해버립니다. 그렇기 때문에 그 아래 if 문을 읽을땐 condition1을 머리속에서 지워버릴 수 있고, 마찬가지로 condition2에서 return 을 빨리 해버리면 condition2를 머리속에서 지워버릴 수 있어서 foo3()을 읽을때 앞서 제외된 조건이 무엇이었는지 기억하는데 부담이 덜합니다.

좀 더 극단적인 경우를 비교해보겠습니다. 다음은 if-else를 중첩하여 사용한 경우입니다.

if (condition1) {
  foo1();
  if (condition2) {
    foo2();
  } else {
    foo3();
  }
} else {
  foo4();
}

같은 코드를 적극적으로 return 하는 형태로 바꾸면 다음과 같습니다.

if (!condition1) {
  foo4();
  return;
}
foo1();
if (condition2) {
  foo2();
  return;
}
foo3();

한 함수의 길이가 20-30 라인으로 제한되면 좋다는 것이야 누구나 알지만, 바쁜 일정속에 리팩토링에 몸을 던지는 용감한 희생자가 없는한 코드는 길어지기 마련이라 복잡한 if-else는 종종 볼 수 있습니다. 더구나 마지막 예에서 보인바와같이 if-else가 한없이 깊어지기만 할 때도 있죠. 하지만 위와같이 빠른 return을 사용하면 그 복잡한 중첩들을 없앨 수 있게됩니다.

Similar Posts:

Sorting two arrays at once in Python

If two arrays should be sorted with the same criteria, use zip.

>>> x1 = ['c', 'a', 'b']
>>> y1 = [3, 1, 2]
>>> z = zip(x1, y1)
>>> z.sort()
>>> z
[('a', 1), ('b', 2), ('c', 3)]
>>> # Because zip returns tuples, we need to convert them to lists.
>>> x2, y2 = map(lambda x: list(x), zip(*z))
>>> x2
['a', 'b', 'c']
>>> y2
[1, 2, 3]

Similar Posts:

Linux Kernel 3.9 에서의 SO_REUSEPORT

http://freeprogrammersblog.vhex.net/post/linux-39-introdued-new-way-of-writing-socket-servers/2
https://lwn.net/Articles/542629/

SO_REUSE_PORT를 사용해서 소켓을 만드는 프로세스를 여러개 띄우면 부모 process 역할은 커널이 알아서 한다. 이 때 어떤 child process가 요청을 처리할지도 공평하게 분배해서 workload의 분산이 잘 이루어짐.

이 방식이 정말 사용하기 쉬운게, 자식 프로세스는 필요하면 그냥 더 띄우기만 하면 되기 때문. 더구나 이건 pre-fork model이므로 접속이 있을때마다 자식 process를 띄우는 것에 비해 프로세스의 수나 서버에 걸리는 로드를 조정하기에 편리. 시간이 좀 지나면 이렇게 코딩하는게 기본 방식이 될지도.

Similar Posts:

HTTPS상의 압축에 따른 취약점 공격: CRIME과 BREACH

제가 SSL/TLS는 잘 몰라서 틀린점이 있을 수 있습니다. 그리고 편의를 위해 개략적으로만 설명합니다.

CRIME의 기본 아이디어는 다음과 같습니다..

(편의를 위해 공격자: attacker, 악의적인 사이트: evil.com, 피해자: victim, 공격대상 사이트: target.com 의 용어를 사용)

  1. TLS상에 주고받는 데이터를 해독할 수는 없지만 주고받는 데이터의 크기는 알 수 있다고 가정.
  2. attacker가 사용자가 대상 사이트에 전송하는 데이터에 임의의 값을 삽입할 수 있다고 가정. 이 단계는 의외로 쉽게 할 수 있는데, 예를들어 evil.com 에서 [img src=’target.com/xyz.png’]와 같은 HTML을 페이지에 넣고 victim이 evil.com을 방문하게 하면 됩니다.
  3. attacker는 target.com에 전송되는 victim의 cookie를 알고 싶어하는데, 이 cookie값이 abcde라고 하겠습니다.
  4. victim이 img src 태그를 보면 브라우저는 이미지 태그에 대한 요청을 target.com으로 보냅니다. 이 때, http request에는 xyz.png 라는 이미지 주소가 들어가겠죠. 그런데 이 주소와 #3에 설명한 cookie값은 한덩어리로 묶어서 압축됩니다. 즉 xyz.png와 abcde의 두개 문자열이 들어있는 http request는 한덩어리의 텍스트로 취급되어 압축됩니다. 그런데 attacker가 파일명을 ayz.png로 바꾸면 무슨일이 생길까요.. ayz.png와 abcde에는 ‘a’가 반복됩니다. 따라서 ayz.png, abcde를 압축한 결과의 바이트수는 xyz.png, abcde를 압축한 바이트 수보다 작습니다.
  5. 따라서 attacker는 img src의 주소를 계속 바꾸면서 http request의 바이트 크기가 최소가되는 지점을 찾아 cookie를 알아냅니다.

CRIME의 아이디어는 TLS상의 compression이 enable되어있는 경우가 드물기때문에 효과적이진 않았습니다.

BREACH는 http request가 아닌 http response에 초점을 맞춥니다. 공격자가 준 입력이 http의 response에 나타난다면 공격자는 입력을 바꿔가면서 http response의 크기를 재서 response에 있는 문자열을 예측해낼 수 있습니다. 예를들어 CSRF Token 탈취를 생각해 볼 수 있겠죠. http상의 gzip 압축은 자주 사용됩니다. 따라서 response를 사용한 공격 가능성은 더 많은 사람들에게 영향을 줍니다.

Similar Posts:

더 빠른 모바일 사이트를 위한 구글의 가이드라인

https://developers.google.com/speed/docs/insights/mobile

DNS Lookup, TCP Connection, HTTP Request/Response에 600ms 가 소요되므로 1초안에 페이지를 로딩하려면 400ms안에 (서버/클라이언트) 렌더링이 끝나야함.

특히 다음에 유의:
1) 서버측 렌더링은 200ms 안에 종료할 것.
2) 리다이렉트는 최소화할 것
3) TCP Slowstart로 인해 congestion window가 커지기 전까지 총 10개의 TCP Packet(14KB)를 주고 받으므로 이 안에 ATF(above the fold)의 렌더링을 끝낼 것.
4) ATF에서 javascript, CSS의 외부참조로 인한 지연이 없도록 전부 inline하거나 ATF 렌더링 뒤에 불리도록 지연시킬 것.
5) 브라우저 렌더링에 200ms는 소요됨을 고려할 것.
6) js 실행과 렌더링 최적화를 할 것.

Similar Posts:

Term의 분포

Heaps law
코퍼스내 unique term의 수는 (문서의 길이)^b 에 비례. b는 보통 0.4-0.6사이의 수

Zipf’s Law
어떤 term의 빈도는 term빈도에따라 term들을 나열했을때의 랭킹에 반비례

Similar Posts:

웹 분석과 데이터 마이닝을 위한 확률적 자료구조

Probabilistic Data Structures for Web Analytics and Data Mining

이런 훌륭한 글이 있군요. 위 글은 많은 양의 데이터에서 각 아이템의 출현횟수를 세거나 unique 아이템의 수가 몇개인지 세거나 하는 방법들입니다. 예를들어 integer가 엄청나게 많을때 각 값의 출현횟수 세기같은 경우죠.

간단하게 관심가는 것들, 기본적인 내용으로 정리해봅니다.

1. 입력에 몇개의 unique한 수가 있는지 세기(Cardinality Esitmation): Linear Counting
m 비트를 준비합니다. 주어진 입력을 0~(m-1) 사이로 해싱합니다. 그 다음 해당 비트의 값을 1로 셋팅. 결국 1로 셋팅된 비트의 수를 세면 이게 입력에 있는 unique한 숫자의 갯수가 되겠죠.

2. 입력에 몇개의 unique한 수가 있는지 세기(Cardinality Esitmation): Log Log Counting
전에 대량의 데이터에서 대략적으로 UNIQUE ITEM 의 수 세기에서 썼던 내용입니다. 다시 정리하자면, 주어진 입력을 해싱함. 해싱한 수들을 살펴보고 제일 앞자리에 최대 몇개의 0이 연속으로 나오는지 봅니다. 이 때 최대 r자리의 연속된 0을 봤다고 하면 2^r개의 unique item이 있구나 하고 보는 방법입니다.

이유는 간단하죠. 해시값의 제일 앞자리에 0이 나올려면 2개의 unique숫자를 봤어야합니다. 1개만 봤을때는 앞자리가 1일수 있으니까요. 마찬가지로 해시값 앞자리에 연속된 0이 2개, 즉 00이 나오려면 4개의 unique숫자를 봤어야합니다. 예를들어 3개만 봤다면 해시값 앞자리가 11, 10, 01이었을 수 있으까요.

사실 2^r은 너무 거친 추정이므로 여러개의 해시함수를 써서 평균을 내던가 하는 방법을 씁니다.

3. 각 입력의 출현횟수 세기: Count-Min Sketch
대량의 데이터에서 각 입력값이 몇번 나왔나 세는 방법입니다. 예를들어 integer로 구성된 데이터였다면 1은 몇개나왔나, 2는 몇개나왔나 등을 세는 것이죠.

방법은 이렇습니다. 0으로 초기화된 d행 w열의 행렬 m을 준비합니다. 그리고 해시 함수 d개를 준비합니다. 이들을 각각 h_1, h_2, …, h_d 라고 합시다. 이 해시는 각각 0~(w-1)까지의 숫자로 입력을 해싱해 줍니다. 처리할 대량의 데이터에대해 다음을 수행합니다.

for each of datum in input
  for i in 1..d
    m[i, h_i(datum)] += 1
  end for
end for

자 그러면 각 입력에대해 총 d개 셀을 1씩 추가시키는 것이죠.

이게 끝나고나서, 역으로 어떤 숫자 k의 출현횟수를 세고 싶다고 하면 다음과 같이 k의 출현횟수를 찾습니다.

cnt = INT_MAX
for i in 1..d
  cnt = min(cnt, m[i, h_i(k)])
end for

여기서 min이 필요한 이유는 이 방법이 본질적으로 hash collision이 있기 때문에 항상 count를 overestimate하기 때문입니다.

4. Range Query: 다수의 Count-Min Sketch 사용
Count-Min Sketch로 어떤 수 k가 몇회나왔는가는 잘 셀수 있게 되었습니다. 이번엔 range query로 1, 2, 3, .., k 까지의 수가 몇번 나왔나? 혹은 500, 501, …, k까지의 수가 몇회나왔나? 와 같은 질문이 주어졌을때 답하는 방법입니다.

이는 Count-Min Sketch만으로는 부족합니다. 각 숫자의 출현횟수를 매번 구하기가 어려울 수 있으니까요. 이를 위해 Count-Min Sketch를 여러개 쓸 수 있습니다. 예를들어 일단 기본적인 Count-Min Sketch를 만듭니다. 그다음은 1, 2를 하나의 수로 3,4를 하나의 수로, … 과 같이 연속된 2개씩의 숫자들을 카운트를 세는 Count-Min Sketch를 만듭니다. 거기에더해 1~4, 5~8, … 과 같이 연속된 4개의 숫자를 묶어서 세는 Count-Min Sketch를 만듭니다. 이런식으로 계속해서 2배씩 키워나가는 Count-Min Sketch를 많이 만듭니다.

이걸로 range query를 어떻게 처리할지 벌써 감이 오시죠?

예를들어 1, 2, 3, …, 10 의 총 발생횟수는 1~8, 9~10 의 2개의 Count-Min Sketch로 답합니다. 또 다른 예로 1~6의 발생횟수는 1~4, 1~2의 2개로 답하면 되겠죠.

5. 집합에 속해있는지. Bloom Filter.
아주 많은 숫자들의 집합이 있습니다. 어떤 입력이 주어졌을때 그 수가 집합의 원소인지 빠르게 답하는 방법이 바로 bloom filter입니다. 방법은 이렇습니다.

m 비트를 만들고 각 자리를 0으로 초기화합니다. 그리고 n 개 해시 함수 h_1, h_2, …, h_n을 만들어놓습니다. 그 다음 집합에 속해있는 데이터에 대해서 다음을 수행합니다.

for each of datum in input
  for i in 1..n
    m[h_i(datum)] = 1
  end for
end for

결국 각 데이터에 대해 n개의 해시함수를 적용해서 각 자리를 1로 셋팅하는 것이죠. 다 준비가 되면 각 입력에 대해 다음을 수행하면 그 입력이 집합에 속하는지 알 수 있습니다.

is_member = true
for i in 1..n
  is_member = is_member && m[h_i(input)]
  if !is_member
    return false
  end if
end for
return true

물론 hash collision이 있기에 이 방법은 false positive가 있습니다.

앞서의 방법들 모두 오차가 있습니다. 그 오차의 한계를 관리하기위해 m, n, d, w 등의 파라미터를 잘 정해주어야 합니다.

Similar Posts:

OSX에서 Latex 설치하기

http://curriq.com/course/73

ktug 링크가 죽어있는 것 같아서 정리된 내용을 찾아 올려둡니다.

Similar Posts:

대량의 데이터에서 대략적으로 unique item 의 수 세기

http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation

HyperLogLog 라고 하는 알고리즘. 셋이 주어지면 아이템들의 해시값을 구한 뒤 해시값의 맨 앞에서 연속적으로 나타난 0의 최대 갯수를 세고, 이로부터 전체 unique 데이터 갯수를 알아냅니다.

예를들어 해시함수의 출력이 m자리 이진수라고 해보죠. n개 수를 해싱했더니 나온 n개 해시값들중에서 연속된 0이 가장 길게 나온경우는 세자리였다고 해보겠습니다. 연속적으로 0이 3자리 나오는건 약 2^3개의 엘리먼트를 볼때마다이므로 unique item 수를 약 8로 추정합니다. 이 알고리즘의 나머지 부분은 이 정확도를 더 개선시키기위해 더 많은 해시함수를 작용하는 등의 최적화입니다.

정확도는 1 billion 갯수에대해 약 2% 정도의 오차가 있는 정도로 준수하다고 합니다.

Flajolet Martine Algorirhm이라고 해시값의 끝에 몇개의 연속된 0이 나오는지 세서 그 0의 수가 R이면 2^R로 unique item수를 측정할수도 있습니다.

해시값에 영향을 많이 받기때문에 다수의 해시함수를 구하고, 이들을 그룹으로 묶어 각 그룹내에서 측정한 값의 평균을 내놓고, 그 평균들의 median을 구하기도 합니다. (자세한건 mining massive datasets라는 책 참고하세요)

물론 이외에도 bloom filter등을 쓰는 방법도 있겠습니다. 아이템이 주어지면 bloom filter를 사용해 이미 셋에 있는지보고 이미 있다면 패스. 없다면 필터에 추가. 이를 반복하면 됩니다.

Similar Posts: