YonMy » algorithm

Lock을 잡는 scope는 최소화 해야 하는 것은 잘 알고 있을 것이다.

swap을 활용하면 더 좋다는 것에 대해서 이야기 해보려고 한다.

개발을 하다보면 map을 만들어 놓고 객체를 등록하고, 찾고, 제거하는 일을 많이 하게 된다.

예를 들어 다음과 같은 Manager class를 만들어 사용한다고 하자

class Manager
{
private:
    std::map< int, std::unique_ptr<Foo> > _cont;

public:
    bool Register(int id, std::unique_ptr<Foo>& ptr)
    {
        return _cont.insert({ id, std::move(ptr) }).second;
    }

    bool Remove(int id)
    {
        return (_cont.erase(id) > 0);
    }
};

class Manager

{

private:

std::map< int, std::unique_ptr<Foo> > _cont;

public:

bool Register(int id, std::unique_ptr<Foo>& ptr)

{

return _cont.insert({ id, std::move(ptr) }).second;

}

bool Remove(int id)

{

return (_cont.erase(id) > 0);

}

};

만약 Manager가 멀티쓰레드 환경에서 thread safe해져야 한다면,

lock free container를 도입하거나,

lock을 사용 해야 한다.

만약 lock을 사용한다면 …

class Manager
{
private:
    std::map< int, std::shared_ptr<Foo> >   _cont;
    std::mutex                              _lock;

public:
    bool Register(int id, std::shared_ptr<Foo>& ptr)
    {
        std::lock_guard<std::mutex> guard(_lock);
        return _cont.insert({ id, std::move(ptr) }).second;
    }
        
    bool Remove(int id)
    {
        std::lock_guard<std::mutex> guard(_lock);
        return (_cont.erase(id) > 0);
    }
};

class Manager

{

private:

std::map< int, std::shared_ptr<Foo> > _cont;

std::mutex _lock;

public:

bool Register(int id, std::shared_ptr<Foo>& ptr)

{

std::lock_guard<std::mutex> guard(_lock);

return _cont.insert({ id, std::move(ptr) }).second;

}

bool Remove(int id)

{

std::lock_guard<std::mutex> guard(_lock);

return (_cont.erase(id) > 0);

}

};

보통 이렇게 할 것이다.

하지만, Remove함수에서 좀 더 최적화를 할 수 있는 여지가 남아있는데…

Remove 함수에서 lock을 잡은 후에 일어나는 일을 먼저 살펴 보면

1. _cont에서 id에 해당하는 node를 찾아서 지운다.
2. Foo의 소멸자가 호출되고, 메모리 해제가 된다.

1번의 과정은 정확히 lock이 필요하지만, 2번의 과정은 lock이 과정이 없어도 된다.
(여기서 Manager class의 lock은 map을 보호하는 것이지 class Foo 를 보호하는 것이 아님)

이 문제는 다음과 같이 swap을 활용하면 해결 할 수 있다.

bool Remove2(int id)
{
    std::shared_ptr<Foo> ptr;
    {
        std::lock_guard<std::mutex> guard(_lock);
        auto itr = _cont.find(id);
        if (itr == _cont.end())
        {
            return false;
        }

        ptr.swap(itr->second);
        _cont.erase(itr);
    }
    return true;
}

bool Remove2(int id)

{

std::shared_ptr<Foo> ptr;

{

std::lock_guard<std::mutex> guard(_lock);

auto itr = _cont.find(id);

if (itr == _cont.end())

{

return false;

}

ptr.swap(itr->second);

_cont.erase(itr);

}

return true;

}

뭔가 코드의 줄 수는 늘어나서 좋지 않아보이지만, 분명히 최적화는 되었다.

만약 Clear함수를 만든다면….

void Clear()
{
    std::lock_guard<std::mutex> guard(_lock);
    _cont.clear();
}

void Clear2()
{
    decltype(_cont) temp;

    {
        std::lock_guard<std::mutex> guard(_lock);
        _cont.swap(temp);
    }
}

void Clear()

{

std::lock_guard<std::mutex> guard(_lock);

_cont.clear();

}

void Clear2()

{

decltype(_cont) temp;

{

std::lock_guard<std::mutex> guard(_lock);

_cont.swap(temp);

}

Clear() 보다 Clear2()가 코드 줄수는 조금 더 길지만, 최적화 되었다.

std::map(set) insert 정확하게 사용하기

꽤나 많은 프로그래머들이 std::map insert 의 사용을 잘 못 하고 있는 경우가 있어서, 오늘은 그것에 대해 이야기 하려고 한다.

우선 std::map의 insert의 기본형을 보면 다음과 같다.

pair<iterator,bool> insert (const pair<const Key, Type>& val);

여기서 중요한점은 리턴값으로 pair를 돌려주고 있는데, 이 리턴값의 의미를 정확히 이해 하고 있어야 한다.

insert 결과	첫번째(iterator)	두번째(bool)	언제 발생
성공	insert되어진 element의 iterator	true	중복된 Key가 존재 하지 않을때
실패	중복된 Key의 element의 iterator	false	중복된 Key가 존재 할때

insert를 한다는 것도 내부적으로 insert할 위치를 찾아가며, (이는 Red-black tree 를 구성 하려면 당연하다.)

std::map은 이를 활용 할 수 있도록 리턴값으로 제공하고 있다. (잘 활용하라는 의도)

많은 프로그래머들이 다음과 같이 사용하는 것을 종종 봤는데….

std::map<int, std::string> temp;
auto itr = temp.find(1);
if (itr == temp.end())
{
    temp.insert({ 1, "number 1" });
}
else
{
    itr->second = "number 1";
}

std::map<int, std::string> temp;

auto itr = temp.find(1);

if (itr == temp.end())

{

temp.insert({ 1, "number 1" });

}

else

{

itr->second = "number 1";

}

위의 리턴값의 의미를 정확히 이해하고 있다면, 이렇게 사용하면 안될 것이다.

std::map<int, std::string> temp;
auto ret = temp.insert({ 1, "number 1" });
if (!ret.second)
{
    ret.first->second = "number 1";
}

std::map<int, std::string> temp;

auto ret = temp.insert({ 1, "number 1" });

if (!ret.second)

{

ret.first->second = "number 1";

}

operator[]의 경우 insert한 결과의 iterator->second를 돌려준다(second의 성공, 실패 여부와 관계없이)는 사실을 알고 있다면,

operator[]를 호출하는 순간 insert가 발생한 다는 것을 알고 있어야 한다.

std::map<int, std::string> temp;
temp[1]; // == temp.insert({1, std::string()});

1 2	std::map<int, std::string> temp; temp[1]; // == temp.insert({1, std::string()});

종종 뒤에 insert하는 Value의 메모리를 할당하는 것이 부담되어(insert를 성공 할지 실패 할지 않수 없을때)

역시, 잘못된 방법으로 사용하는 경우가 있는데…

std::map<int, Foo*> temp;
temp.insert({ 1, new Foo });

...

{// 이렇게 하는 것은 중복된 Key를 삽입하는 경우가 많아지면, 무의미하게 new를 했다가 delete를 하는 부담이 생긴다.
    Foo* pFoo = new Foo;
    auto ret = temp.insert({ 1, pFoo });
    if (!ret.second)
    { 
        delete pFoo;
    }
}

{// 그래서 다음과 같이 잘못 사용 하게 된다.
    auto itr = temp.find(1);
    if (itr == temp.end() )
    {
        temp.insert({ 1, new Foo });
    }
}

std::map<int, Foo*> temp;

temp.insert({ 1, new Foo });

...

{// 이렇게 하는 것은 중복된 Key를 삽입하는 경우가 많아지면, 무의미하게 new를 했다가 delete를 하는 부담이 생긴다.

Foo* pFoo = new Foo;

auto ret = temp.insert({ 1, pFoo });

if (!ret.second)

{

delete pFoo;

}

{// 그래서 다음과 같이 잘못 사용 하게 된다.

auto itr = temp.find(1);

if (itr == temp.end() )

{

temp.insert({ 1, new Foo });

}

이 경우는 두가지 해결책을 제시 할 수 있는데,

auto ret = temp.insert({ 1, nullptr });
if (ret.second)
{
    ret.first->second = new Foo;
}

auto ret = temp.insert({ 1, nullptr });

if (ret.second)

{

ret.first->second = new Foo;

}

auto itr = temp.lower_bound(1);
if ((itr == temp.end()) || std::less<int>()(1, itr->first))
{
    temp.insert(itr, { 1, new Foo });
}

auto itr = temp.lower_bound(1);

if ((itr == temp.end()) || std::less<int>()(1, itr->first))

{

temp.insert(itr, { 1, new Foo });

}

STL에는 대비책이 다 마련되어 있다.(insert with hint)

lower_bound로 찾은 다음에 operator==으로 비교 하는 것보다. std::less로 비교하는 것이 더 정확하다.

(만약 std::map template의 세번째 파라미터로 std::greater로 정의 하였다면, 당연히 std::greater로 비교)

참고

http://www.cplusplus.com/reference/map/map/insert/

algorithm

swap을 사용하면 최적화 할 수 있다.

std::map(set) insert 정확하게 사용하기

최신 글

카테고리

algorithm

swap을 사용하면 최적화 할 수 있다.

std::map(set) insert 정확하게 사용하기

최신 글

카테고리

태그