현재 구현되고 있는 STL도 동일할 지는 모르겠습니다만.
prefix의 경우에는 이터레이터를 수정한 후 그 레퍼런스를 리턴하는데 비해,
postfix는 이터레이터를 수정하기 전에 이를 카피하고 수정된 이터레이터를 리턴합니다.
따라서 단순히 이터레이터 값만을 변화시키고 리턴된 값을 다시 사용하지 않는 경우에는 prefix가 빠를 수 있습니다.
모두가 아시겠지만 그래도 설명드리자면, 전위 증감은 객체 자신을 증감시킨 뒤 바로 그 레퍼런스를 반환하는 반면,
후위 증감은 객체를 복사하여 임시 객체를 만든 뒤, 객체를 증감시키고, 임시 객체를 반환하죠.
후위 증감이 전위 증감에 비해 복사하는 비용이 들어가므로, 사본을 필요로 하지 않는 경우에 후위 증감을 쓰는 건 낭비가 되지 않을까 염려할 수도 있습니다.
가장 대표적인 경우가 for문에서의 사용이죠. for(int i=0;i<N;i++) 같은 표현 많이 쓰잖아요? 정수 복사 한 번쯤이야 별 거 아니지만, 루프가 수십 수백만번 쯤 돌다 보면 문제가 되지 않을까요.
2.포인터나 정수 타입, 즉 소위 프리미티브 타입에 대해서는 걱정할 필요 없습니다.
이들의 전위/후위 증감이나 복사에 대해서는 컴파일러가 잘 알고 있거든요. 특히 이들이 사이드 이펙트가 없다는 점을 말이죠.
후위 증감 연산자가 사용됐다고 해도 그 사본이 사용되지 않는다는 걸 컴파일러가 파악하면, 아무 거리낌 없이 전위 연산자로 바꿔 컴파일해줄 수 있다는 얘깁니다.
컴파일러가 그 정도로 똑똑하지 않다고 해도 상관 없습니다. 후위 증감 그대로 컴파일해서 정수나 포인터의 사본이 만들어진다 해도, 이들이 쓰이지 않으면 컴파일러 최적화의 좋은 먹잇감이거든요. 컴파일러 최적화 이론을 배우신 분이라면 Liveness analysis와 Dead code elimination에 대해서 아시겠지요. 현실적으로, C/C++를 사용하는 개발 환경에서 이 정도의 최적화조차 지원이 안 되는 경우는 거의 없을 겁니다.
다시 말하면, 프리미티브 타입(정수, 포인터)에 대해서 사본을 사용하지 않는 후위 증감은 복사 비용이 들어가지 않습니다. mauri님께서 이미 확인하셨듯이, 대체로 전위 증감으로 바꾼 코드와 동일한 어셈블리를 생성합니다.
3.프리미티브 타입이 아닌 경우, 그러니까 사용자 정의 class이고 전위/후위 증감 연산자를 오버로딩한 경우는 그렇게 간단하지 않습니다.
설령 반환값이 사용되지 않는다고 해도, 컴파일러가 후위 증감 연산자 호출을 마음대로 전위 증감 연산자 호출로 바꿀 수 없습니다. 컴파일러는 사용자 정의 함수 호출은 반드시 사이드 이펙트가 있을 거라고 가정하기 때문이죠. 전위 증감과 후위 증감이 전혀 다른 semantic을 가지도록 만들어졌을 수도 있고요. (정상적인 프로그래머라면, 꼭 그래야 할 이유가 없는 한 그렇게 코딩하지는 않을 테지만...)
사용자 정의 class의 전위/후위 증감이 프리미티브 타입의 그것과 비슷한 시맨틱으로 정의되었다면, 후위 증감 연산자 함수는 객체 복사를 포함할 수밖에 없습니다. 컴파일러가 이 함수를 호출하는 걸 피할 수도 없고요.
4.하지만 STL 컨테이너의 iterator에 대해서는 조금 더 생각해볼 여지가 있습니다.
우선, STL 컨테이너의 iterator는 일반화된 포인터입니다. gilgil님이 말씀하신 게 이런 뜻이었던 것 같은데요.
실제로 몇몇 STL 컨테이너의 iterator는 구현에 있어서도 raw pointer와 거의 다를 게 없습니다. 대표적으로 vector와 array(C++11)이 그렇죠. 근데 그렇다고 iterator가 꼭 raw pointer라고 할 수는 없는데요. 예를 들어 g++ 5.2.0에서 array의 iterator 정의는 value_type *의 typedef인 반면, vector의 iterator는 raw pointer 달랑 하나 멤버로 가진 래퍼 클래스입니다. (이 클래스는 iterator_type, iterator_category 등의 typedef 정의도 포함하고 있습니다.)
반면에 구현 상 도저히 raw pointer일 수 없는 iterator도 있는데, 대표적으로 list의 iterator가 있습니다. 이 iterator의 증감은 구현상으로는 linked list의 link를 쫓아가는 코드가 있어야 하니까요.
요점은, 일부 STL 컨테이너의 iterator는 사용자 정의 클래스로서, 위의 3번 항목의 적용을 받습니다. 즉 slee0303님 말씀처럼 사본을 사용하지 않는 후위 증감 연산에서 복사 비용이 낭비될 여지가 있는 거죠. 그런데 과연 그럴까요.
STL 컨테이너 iterator는 비록 사용자 정의 클래스라고 해도 별로 복잡하지 않습니다. 애초에 그럴 수밖에 없는 게, 무슨 자원 관리 같은 걸 하는 건 아니니까요.
다시금 g++를 보면 vector뿐만 아니라 list, set, map 등의 iterator 클래스들도 뜯어보면 포인터 필드 하나만 달랑 있는데, 저런 컨테이너들이 대충 어떤 자료구조로 구현되어 있을지 생각해 보면 납득할 만 할 겁니다. 이런 iterator가 사용자 정의 클래스로 만들어진 이유는 내부 자료구조가 복잡하기 때문이 아니라 연산자 오버로딩을 써먹고 싶기 때문이죠.
즉, iterator의 복사는 그저 포인터 필드들의 복사일 뿐인 겁니다.
한 가지 더. STL 컨테이너의 코드는 본질적으로 죄다 템플릿화 된 코드들이고, 컴파일 타임에 훤히 보입니다. 그리고 컴파일러는 iterator의 전위/후위 증감이나 복사 함수 같은 가벼운 함수 호출들은 어렵지 않게 인라인 처리 해 버릴 수 있죠. 특히 iterator 증감은 루프에서 자주 쓰이므로 함수 호출/반환 딜레이를 없애는 게 무척 효과적이니까요. 그 결과 남는 건 고스란히 노출된 포인터 복사들 뿐이고, 컴파일러는 사용되지 않을 포인터 사본 따위는 최적화로 없애 버립니다. (위의 2번 항목)
결국 STL 컨테이너 iterator들도 사본을 사용하지 않는 후위 증감에서 낭비되는 비용이 없어지는 겁니다.
"정말로 그렇게 되느냐" 라는 질문에는, 음. 여기서 적용된 테크닉은 2번 항목에서 언급한 것보다는 약간 더 고급이긴 합니다만 (Unboxing, inline expansion 등) STL 컴파일을 지원할 정도의 컴파일러라면 웬만하면 지원이 될 텐데요.
그래도 못 믿으시는 분들은, 직접 해보세요.
저도 직접 몇 개 해봤는데, g++ 4.8.2에서 최적화 옵션 -O1만 주더라도 vector, deque, list, set, map의 iterator를 for문에서 전위/후위 증감을 사용했을 때 동일한 결과물을 생성하던데요.
요약하자면,
(1) 정수나 포인터 변수는 후위 증감을 써도 문제 없습니다.
(2) 사용자 정의 클래스이며 객체 복사 비용이 확연히 비싸고 복잡한 경우에는 전위 증감을 쓰는 편이 낫습니다.
(3) 그러나 STL 컨테이너의 iterator처럼 복사가 간단하고 인라인 처리가 쉽게 이루어지는 경우에는 마찬가지로 후위 증감도 별 문제 없습니다.
지금 생각해 보니 막연히 iterator가 무조건 pointer가 아닐 수도 있겠네요. vector iterator는 array pointer 혹은 array index일 수 있겠고, list iterator는 next pointer일 수 있겠고...
아무튼 primitive type이나 stl container이나 다음과 같은 성질은 똑같이 적용되어 진다고 보여 집니다.
. prefix increment는 자신의 reference를 반환
. postfix increment는 증가되기 이전의 본사본을 반환
. postfix방식을 사용하는 데 있어서 caller가 반환되는 복사본 받아서 활용하지 않는다면 복사해서 반환하는 행위는 의미가 없고 컴파일러에 의해 코드가 무시됨.
그러고보니 그렇네요..
여태 별 생각없이 습관적으로 사용해왔는데요.
생각해보니 차이가 있을듯 싶기도 하군요.
단순히 생각을 해보자면 i++은 어딘가에 값을 푸쉬해놓고, 푸쉬해 놓은값을 되돌린후에 i를 증가시킬듯 싶으니
++i보다 한 스텝 느릴듯 싶습니다... 라고 생각을 해서 코드를 작성해서 어셈블코드를 보니 차이가 없네요.. ^^);;
똑똑한 컴파일러가 for문내의 증감연산은 알아서 ++i로 처리해 주는 것 같습니다.
뭐.. 설사 차이가 있다하더라도 실제 체감할 수 없겠지요?
STL에서 iterator를 사용하는 경우 전위
STL에서 iterator를 사용하는 경우 전위 증감이 빠를 수 있습니다.
오! 그렇겠네요.
댓글 감사합니다!!!
오오오!
감사합니다~
gilgil.net
stl의 iterator도 결국 pointer인데 prefix나 postfix나 비슷하지 않나요?
iterator it; it++(혹은 ++it);
char* p; p++(혹은 ++p);
결국 2개가 같은 개념인데...
www.gilgil.net
네. 비슷은 할겁니다.
위에 달았듯이 for문내에서의 전위/후위는 컴파일러가 알아서 처리를 해주니 똑같다 할 수 있구요.
댓글을 달때 반복자는 전혀 생각도 하지 못했었는데, 반복자의 경우는 체감할 수 없긴 하지만 원글에 적었듯이 "어딘가에 값을 저장해 놓고, 증감작업"을 할 테니 그만큼 한 스텝을 더 거치게 되고, 코스트도 반복자 하나분이 더 들어가게 될겁니다.
뭐.. 체감할 수는 없지만 지금까지 습관처럼 i++ 또는 itr++을 했는데, foreach를 사용할게 아니라면 이왕이면 ++i, ++itr을 사용하는게 더 좋겠다고 생각한겁니다.
현재 구현되고 있는 STL도 동일할 지는
현재 구현되고 있는 STL도 동일할 지는 모르겠습니다만.
prefix의 경우에는 이터레이터를 수정한 후 그 레퍼런스를 리턴하는데 비해,
postfix는 이터레이터를 수정하기 전에 이를 카피하고 수정된 이터레이터를 리턴합니다.
따라서 단순히 이터레이터 값만을 변화시키고 리턴된 값을 다시 사용하지 않는 경우에는 prefix가 빠를 수 있습니다.
stl iterator는 pointer처럼 쓸 수
stl iterator는 pointer처럼 쓸 수 있는것이지 pointer는 아닙니다.
stl::list<>::iterator는 별도의 클래스로 구현되어있고, gcc stdlibc++의 소스를 보면 다음과 같이 구현되어있습니다.
_Self& operator++() _GLIBCXX_NOEXCEPT { _M_node = _M_node->_M_next; return *this; } _Self operator++(int) _GLIBCXX_NOEXCEPT { _Self __tmp = *this; _M_node = _M_node->_M_next; return __tmp; }prefix의 경우 현재 iterator instance의 내부 값을 변경하지만
postfix의 경우 현재 iterator를 복사해 새 iterator를 만들고 현재 iterator의 내부 값을 변경 시킨 후 새 iterator를 반환합니다.
이 경우에는 operator++의 구현이 간단하고 컴파일러 인라이닝 때문에 ++it와 it++의 성능이 차이가 안날 확률이 높습니다만 iterator의 copy constructor의 비용이 비쌀 경우 성능 차이가 나게 됩니다.
미묘한 문제로군요.
1.개념적으로 보면, 전위 증감과 후위 증감의 성능은 분명히 다릅니다.
모두가 아시겠지만 그래도 설명드리자면, 전위 증감은 객체 자신을 증감시킨 뒤 바로 그 레퍼런스를 반환하는 반면,
후위 증감은 객체를 복사하여 임시 객체를 만든 뒤, 객체를 증감시키고, 임시 객체를 반환하죠.
후위 증감이 전위 증감에 비해 복사하는 비용이 들어가므로, 사본을 필요로 하지 않는 경우에 후위 증감을 쓰는 건 낭비가 되지 않을까 염려할 수도 있습니다.
가장 대표적인 경우가 for문에서의 사용이죠. for(int i=0;i<N;i++) 같은 표현 많이 쓰잖아요? 정수 복사 한 번쯤이야 별 거 아니지만, 루프가 수십 수백만번 쯤 돌다 보면 문제가 되지 않을까요.
2.포인터나 정수 타입, 즉 소위 프리미티브 타입에 대해서는 걱정할 필요 없습니다.
이들의 전위/후위 증감이나 복사에 대해서는 컴파일러가 잘 알고 있거든요. 특히 이들이 사이드 이펙트가 없다는 점을 말이죠.
후위 증감 연산자가 사용됐다고 해도 그 사본이 사용되지 않는다는 걸 컴파일러가 파악하면, 아무 거리낌 없이 전위 연산자로 바꿔 컴파일해줄 수 있다는 얘깁니다.
컴파일러가 그 정도로 똑똑하지 않다고 해도 상관 없습니다. 후위 증감 그대로 컴파일해서 정수나 포인터의 사본이 만들어진다 해도, 이들이 쓰이지 않으면 컴파일러 최적화의 좋은 먹잇감이거든요. 컴파일러 최적화 이론을 배우신 분이라면 Liveness analysis와 Dead code elimination에 대해서 아시겠지요. 현실적으로, C/C++를 사용하는 개발 환경에서 이 정도의 최적화조차 지원이 안 되는 경우는 거의 없을 겁니다.
다시 말하면, 프리미티브 타입(정수, 포인터)에 대해서 사본을 사용하지 않는 후위 증감은 복사 비용이 들어가지 않습니다. mauri님께서 이미 확인하셨듯이, 대체로 전위 증감으로 바꾼 코드와 동일한 어셈블리를 생성합니다.
3.프리미티브 타입이 아닌 경우, 그러니까 사용자 정의 class이고 전위/후위 증감 연산자를 오버로딩한 경우는 그렇게 간단하지 않습니다.
설령 반환값이 사용되지 않는다고 해도, 컴파일러가 후위 증감 연산자 호출을 마음대로 전위 증감 연산자 호출로 바꿀 수 없습니다. 컴파일러는 사용자 정의 함수 호출은 반드시 사이드 이펙트가 있을 거라고 가정하기 때문이죠. 전위 증감과 후위 증감이 전혀 다른 semantic을 가지도록 만들어졌을 수도 있고요. (정상적인 프로그래머라면, 꼭 그래야 할 이유가 없는 한 그렇게 코딩하지는 않을 테지만...)
사용자 정의 class의 전위/후위 증감이 프리미티브 타입의 그것과 비슷한 시맨틱으로 정의되었다면, 후위 증감 연산자 함수는 객체 복사를 포함할 수밖에 없습니다. 컴파일러가 이 함수를 호출하는 걸 피할 수도 없고요.
4.하지만 STL 컨테이너의 iterator에 대해서는 조금 더 생각해볼 여지가 있습니다.
우선, STL 컨테이너의 iterator는 일반화된 포인터입니다. gilgil님이 말씀하신 게 이런 뜻이었던 것 같은데요.
실제로 몇몇 STL 컨테이너의 iterator는 구현에 있어서도 raw pointer와 거의 다를 게 없습니다. 대표적으로 vector와 array(C++11)이 그렇죠. 근데 그렇다고 iterator가 꼭 raw pointer라고 할 수는 없는데요. 예를 들어 g++ 5.2.0에서 array의 iterator 정의는 value_type *의 typedef인 반면, vector의 iterator는 raw pointer 달랑 하나 멤버로 가진 래퍼 클래스입니다. (이 클래스는 iterator_type, iterator_category 등의 typedef 정의도 포함하고 있습니다.)
반면에 구현 상 도저히 raw pointer일 수 없는 iterator도 있는데, 대표적으로 list의 iterator가 있습니다. 이 iterator의 증감은 구현상으로는 linked list의 link를 쫓아가는 코드가 있어야 하니까요.
요점은, 일부 STL 컨테이너의 iterator는 사용자 정의 클래스로서, 위의 3번 항목의 적용을 받습니다. 즉 slee0303님 말씀처럼 사본을 사용하지 않는 후위 증감 연산에서 복사 비용이 낭비될 여지가 있는 거죠. 그런데 과연 그럴까요.
STL 컨테이너 iterator는 비록 사용자 정의 클래스라고 해도 별로 복잡하지 않습니다. 애초에 그럴 수밖에 없는 게, 무슨 자원 관리 같은 걸 하는 건 아니니까요.
다시금 g++를 보면 vector뿐만 아니라 list, set, map 등의 iterator 클래스들도 뜯어보면 포인터 필드 하나만 달랑 있는데, 저런 컨테이너들이 대충 어떤 자료구조로 구현되어 있을지 생각해 보면 납득할 만 할 겁니다. 이런 iterator가 사용자 정의 클래스로 만들어진 이유는 내부 자료구조가 복잡하기 때문이 아니라 연산자 오버로딩을 써먹고 싶기 때문이죠.
즉, iterator의 복사는 그저 포인터 필드들의 복사일 뿐인 겁니다.
한 가지 더. STL 컨테이너의 코드는 본질적으로 죄다 템플릿화 된 코드들이고, 컴파일 타임에 훤히 보입니다. 그리고 컴파일러는 iterator의 전위/후위 증감이나 복사 함수 같은 가벼운 함수 호출들은 어렵지 않게 인라인 처리 해 버릴 수 있죠. 특히 iterator 증감은 루프에서 자주 쓰이므로 함수 호출/반환 딜레이를 없애는 게 무척 효과적이니까요. 그 결과 남는 건 고스란히 노출된 포인터 복사들 뿐이고, 컴파일러는 사용되지 않을 포인터 사본 따위는 최적화로 없애 버립니다. (위의 2번 항목)
결국 STL 컨테이너 iterator들도 사본을 사용하지 않는 후위 증감에서 낭비되는 비용이 없어지는 겁니다.
"정말로 그렇게 되느냐" 라는 질문에는, 음. 여기서 적용된 테크닉은 2번 항목에서 언급한 것보다는 약간 더 고급이긴 합니다만 (Unboxing, inline expansion 등) STL 컴파일을 지원할 정도의 컴파일러라면 웬만하면 지원이 될 텐데요.
그래도 못 믿으시는 분들은, 직접 해보세요.
저도 직접 몇 개 해봤는데, g++ 4.8.2에서 최적화 옵션 -O1만 주더라도 vector, deque, list, set, map의 iterator를 for문에서 전위/후위 증감을 사용했을 때 동일한 결과물을 생성하던데요.
요약하자면,
(1) 정수나 포인터 변수는 후위 증감을 써도 문제 없습니다.
(2) 사용자 정의 클래스이며 객체 복사 비용이 확연히 비싸고 복잡한 경우에는 전위 증감을 쓰는 편이 낫습니다.
(3) 그러나 STL 컨테이너의 iterator처럼 복사가 간단하고 인라인 처리가 쉽게 이루어지는 경우에는 마찬가지로 후위 증감도 별 문제 없습니다.
자세한 설명 감사드립니다.
막연히 이러겠지?라고 생각하던거 어셈블로 뜯어보고 그렇구나~ 하고 넘어갔는데요.
덕분에 용어라던지 개념이 확실히 잡혔습니다!
정말 감사드립니다!!!!
gilgil.net
자세한 설명 감사합니다.
지금 생각해 보니 막연히 iterator가 무조건 pointer가 아닐 수도 있겠네요. vector iterator는 array pointer 혹은 array index일 수 있겠고, list iterator는 next pointer일 수 있겠고...
아무튼 primitive type이나 stl container이나 다음과 같은 성질은 똑같이 적용되어 진다고 보여 집니다.
. prefix increment는 자신의 reference를 반환
. postfix increment는 증가되기 이전의 본사본을 반환
. postfix방식을 사용하는 데 있어서 caller가 반환되는 복사본 받아서 활용하지 않는다면 복사해서 반환하는 행위는 의미가 없고 컴파일러에 의해 코드가 무시됨.
www.gilgil.net
스레드 사용시 오류가 발생한다면.
iterator 대신.
스레드에서 싱글락을 건후. for 문을 사용하시는것도 좋을거 같습니다.
얼마전 자바 소스를 보니. syncronized()로 묶어주고. for문을 사용해야 했습니다.
----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.
매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.
각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com
댓글 달기