2018년 11월 14일 수요일

A*, JPS 길찾기 알고리즘 시뮬레이션 사이트

https://qiao.github.io/PathFinding.js/visual/
길 찾기 알고리즘 시행 과정을 보여주는 사이트다.

링크 메모..
시간: 댓글 없음:
라벨:

std::promise, std::future, std::async

std::promise와 std::future를 활용해서 스레드가 진행되면서 나오는 값을 반환받을 수 있다.

c++11 에서는 async를 활용하면 더 간단하게 코드 구성이 가능하지만..

std::promise 와 std::future를 사용해 본 간단한 코드..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstring>
#include <future>
#include <Windows.h> // for Sleep
 
void ThreadFunc(std::promise<int>& retVal, int value)
{
    Sleep(value);
 
    retVal.set_value(value);
}
 
int main(void)
{
    // 여기서 promise 타입으로 스레드로 반환받을 형태의 template으로 선언해준다.
    std::promise<int> p1, p2;
 
    // 아래의 auto는 std::future<std::int> 이다.
    auto f1 = p1.get_future();
    auto f2 = p2.get_future();
 
    // 스레드 만들어서 호출해주고, 스레드에 인자로 위에서 선언한 것을 넣어준다.
    // std::ref(p)로 해줘도 되고, &p 해줘도 되고..
    std::thread th1(ThreadFunc, std::ref(p1), 20000);
    std::thread th2(ThreadFunc, std::ref(p2), 1000);
 
 
    // 스레드 작업이 끝날 때까지 대기함.
    // th2 작업이 먼저 끝나지만, th1.join()으로 대기하게 됨.
    // th1 작업이 끝나서 블록해제되면 그제서야 th2.join()으로 스레드 종료된거 확인하고 값 가져옴
    th1.join();
    th2.join();
 
    std::cout << f1.get() << std::endl;
    std::cout << f2.get() << std::endl;
 
    return 0;
}
cs


std::async 를 활용하면 요렇게 하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstring>
#include <future>
#include <Windows.h> // for Sleep
 
int ThreadFunc(int value)
{
    Sleep(value);
    return value;
}
 
int main(void)
{
    std::future<int> f1 = std::async(ThreadFunc, 20000);
    std::future<int> f2 = std::async(ThreadFunc, 1000);
    
    std::cout << f1.get() << std::endl;
    std::cout << f2.get() << std::endl;
 
    return 0;
}
cs
시간: 댓글 없음:
라벨:

2018년 11월 4일 일요일

std::call_once 와 std::once_flag

std::call_once 는 아래 C++11에서 추가되었는데 아래와 같은 정의를 가지고 있다.
1
2
3
// Defined in header <mutex>
template< class Callable, class... Args >
void call_once( std::once_flag& flag, Callable&& f, Args&&... args );
cs

여러 개의 스레드에서 호출될 때, 한 번만 호출되게 할 수 있다.

물론 멀티 스레드 환경이 아니더라도 아래와 같이 쓸 수도 있다.
Singleton 패턴에도 사용할 수 있겠고..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <mutex>
using namespace std;
 
class MrRobot
{
public:
    MrRobot(int serial) : serial_number_(serial) {};
 
    void PrintSerialNumber() 
    {
        std::call_once(once_flag_, [] 
        {
            cout << "MrRobot: ";
        });
 
        cout << serial_number_ << "\n";
    }
 
private:
    std::once_flag once_flag_;
    int serial_number_;
};
 
int main(void)
{
    MrRobot a(1);
    a.PrintSerialNumber();
    a.PrintSerialNumber();
 
    MrRobot b(2);
    b.PrintSerialNumber();
 
    return 0;
}
cs

위에 코드를 실행하면 결과는 아래와 같다.

MrRobot: 1
1
MrRobot: 2

디버깅 모드에서 once_flag_ 변수의 변화를 살펴보니 0x00000000 -> 0x00000002로
람다함수를 실행하면서 변경해준다.

그래서 memset 함수를 사용해서 저 변수를 다시 0으로 초기화하는 코드를 넣어보면
아래처럼 출력된다.

MrRobot: 1
MrRobot: 1
MrRobot: 2


시간: 댓글 없음:
라벨:

Read Lock, Write Lock 그리고 shared_mutex

게임 서버 구현 과정에서 멀티 스레드를 사용하려다보니 특정 메모리 영역에는 동기화를 위한 작업이 필요하다.


그런데 무작정 락을 걸자니 이래저래 mutex를 남발하면 멀티 스레드가 무슨 소용인가.. 커널 왔다갔다하면서 비용이 많이 들텐데..


CRITICAL_SECTION으로 하면 유저 영역에서 해결이 되긴 한다는데...



뭐 어쨋든 락을 가능한 적게 걸기 위해, Read Lock, Write Lock 방법을 생각했는데


이 방식을 간략하게 설명하자면 아래와 같다.

"해당 영역에 변화를 주지 않는다면 여러 스레드가 접근해도 좋다"


Read Lock

 - Read하는 스레드끼리는 모두 읽어도 된다. 데이터를 변화시키지만 않는다면.

   단, 성능적인 측면을 위해 Write를 대기하는 스레드가 있다면 추가적으로 Read하는 스레드를 허용하지 않는다.


Write Lock

 - Write하는 스레드가 있을 경우, Read 스레드도 제한하고 다른 Write 스레드도 제한한다.




음.. 일단 내가 고려한 방식은 크게 2가지다. 2가지 측면을 고려하면서 성능적인 측면에서 아래와 같은 궁금증이 생겼는데


아직 테스트는 못 해봤다. 우선은 정리 먼저 해두고 테스트 코드 만들어서 해봐야지. 평일은 안 되겠고 주말에...


mutex를 사용하면 커널 영역에서 이루어지니까 2번 방법인 Interlock 함수를 이용하는 것보다 비용이 비싸지 않을까?


첫 번째는 C++11 에서 포함된 shared_mutex, unique_lock, shared_lock을 사용하는 것이다.


Read Lock을 하는 경우에는 아래처럼 사용한다.


1
shared_lock<shared_mutex> lock(mutex);
cs


그리고 Write Lock을 하는 경우에는 아래처럼 사용한다.


1
unique_lock<shared_mutex> lock(mutex);
cs


두 번째 방법으로는 Interlock 함수를 사용하는 방식이다. 
ReadWriteLock.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#pragma once
#include <Windows.h>
 
class ReadWriteLock
{
public:
    ReadWriteLock();
    ~ReadWriteLock();
 
    ReadWriteLock(const ReadWriteLock& rhs) = delete;
    ReadWriteLock& operator=(const ReadWriteLock& rhs) = delete;
 
    // exclusive mode
    void EnterWriteLock();
    void LeaveWriteLock();
 
    // share mode
    void EnterReadLock();
    void LeaveReadLock();
 
    long GetLockFlag() const { return lock_flag_; }
 
 
private:
    enum LockFlag
    {
        LOCK_FLAG_WRITE_MASK = 0x7FF00000,
        LOCK_FLAG_WRITE_FLAG = 0x00100000,
        LOCK_FLAG_READ_MASK  = 0x000FFFFF  // 하위 20비트를 readlock을 위한 플래그로 사용한다.
    };
 
    volatile long lock_flag_;
};
cs

ReadWriteLock.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include "pch.h"
#include "ReadWriteLock.h"
 
ReadWriteLock::ReadWriteLock()
{
}
 
ReadWriteLock::~ReadWriteLock()
{
}
 
// exclusive mode
void ReadWriteLock::EnterWriteLock()
{
    while (true)
    {
        // 다른 스레드가 write lock 풀어줄 때까지 기다린다.
        while (lock_flag_ & LOCK_FLAG_WRITE_MASK)
        {
            YieldProcessor();
        }
 
        if (LOCK_FLAG_WRITE_FLAG == (InterlockedAdd(&lock_flag_, LOCK_FLAG_WRITE_FLAG) & LOCK_FLAG_WRITE_MASK))
        {
            // 다른 스레드가 read lock 풀어줄 때까지 기다린다.
            while (lock_flag_ & LOCK_FLAG_READ_MASK)
            {
                YieldProcessor();
            }
 
            return;
        }
        InterlockedAdd(&lock_flag_, -LOCK_FLAG_WRITE_FLAG);
    }
}
 
void ReadWriteLock::LeaveWriteLock()
{
    InterlockedAdd(&lock_flag_, -LOCK_FLAG_WRITE_FLAG);
}
 
// share mode
void ReadWriteLock::EnterReadLock()
{
    while (true)
    {
        // wait for release write lock
        while (lock_flag_ & LOCK_FLAG_WRITE_MASK)
        {
            YieldProcessor();
        }
 
        // check write lock
        if ((0 == InterlockedIncrement(&lock_flag_) & LOCK_FLAG_WRITE_MASK))
        {
            return;
        }
        else
        {
            InterlockedDecrement(&lock_flag_);
        }
    }
}
 
void ReadWriteLock::LeaveReadLock()
{
    InterlockedDecrement(&lock_flag_);
}
 
cs


시간: 댓글 없음:
라벨:

std::launch::async VS ThreadPool

이번에 std::lauch::async와 ThreadPool의 성능을 간단하게 비교해 볼 일이 있었는데..

결과부터 말하면 내가 테스트한 환경에서는 ThreadPool 이 더 좋았다.

CPU를 고르게 쓴 것도 ThreadPool 쪽이 좀 더...


std::lauch::async의 cpu 사용 그래프

ThreadPool의 cpu 그래프

수행 시간은 ms 단위다
Loopstd::launch::asyncThreadPool: 6개 스레드ThreadPool: 12개 스레드
20,00029,753,41428,068,95228,290,221
20,00030,571,60127,823,25129,157,295
100,000147,357,532136,098,045141,674,844
100,000148,868,279136,130,447141,939,465

아래에서는 visual stduio 2017 환경에서 조사식의 @CLK를 활용한 수행시간 체크도 가볍게 말씀드린다.
테스트 CPU는 아래 링크해뒀다.

테스트에 사용했던 ThreadPool은 아래 링크다. 일부 변경된 상태로 테스트 했다.싱글톤 패턴을 넣었다던가, 스레드 개수를 생성자가 아니라 따로 함수를 만들어서 받으면서 시작했다던가..

std::lauch::async 테스트 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int ThreadLoopMax = 100000;
int main(void)
{
    auto func = [&]()
    {
          // 테스트를 위한 람다 함수
    };
    // 수행시간 체크 시작하는 부분
    cout << "start" << "\n";
    for (int tLoop = 0; tLoop < ThreadLoopMax; tLoop++)
    {
        std::future<void> ret = std::async(std::launch::async, func);
        ret.get();
    }
    // 수행시간 체크 종료하는 부분
    cout << "end" << "\n";
    return 0;
}
cs

ThreadPool 테스트 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int ThreadLoopMax = 100000;
int main(void)
{
    auto func = [&]()
    {
          // 테스트를 위한 람다 함수
    };
    // 스레드 개수 설정.
    ThreadPool::GetIns().Start(12);
    // 수행시간 체크 시작하는 부분
    cout << "start" << "\n";
    for (int tLoop = 0; tLoop < ThreadLoopMax; tLoop++)
    {
        auto ret = ThreadPool::GetIns().enqueue(func);
        ret.get();
    }
    // 수행시간 체크 종료하는 부분
    cout << "end" << "\n";
    return 0;
}
cs

여기서부터 @CLK를 통해 수행 시간을 체크하는 방법을 간략하게 소개한다.우선 체크하고자 하는 지점에 브레이크를 걸어둔다. 위의 예시로 든 코드에서는 start, end를 출력하는 부분이다.




그리고 디버그 모드로 실행하면, 조사식에 @CLK를 입력해준다.우선 start를 출력하는 시점에 브레이크가 걸리면서 해당 시점에 Clocking 값을 보여줄 것이다.



우선 지금 시점부터 수행 시간을 체크하는게 목적이므로, @CLK 값을 0으로 초기화해준다. 아래처럼..



수행하고 나서 end를 출력하는 시점에 다시 브레이크가 걸리면 조사식을 통해 @CLK값을 확인할 수 있다.
간략한 테스트에는 위 방법을 써도 좋지만, 표본이 많이 필요한 경우라면 그냥 시간 저장해서 파일로 로그를 남기던가 하는게 더 좋겠다.
시간: 댓글 없음:
라벨:

2018년 10월 27일 토요일

cpp_redis 설치부터 tcp_client와 tcp_server 사용하기

음.. 이번에 Redis를 접하면서 경험했던 것들을 하나씩 정리한다.

일단 redis 설치부터 시작해서, cpp_redis 라이브러리 빌드 그리고

tcp_client와 tcp_server를 활용해 async_write, async_read 까지 테스트해본다.

언제나 그렇듯 부족하거나 틀린 부분이 있으면 지적해주시면 확인해보고 수정하겠습니다 :)



테스트 환경은 윈도우10 64비트이다.

우선 설치부터 시작해보자.

1. 아래 링크에서 .msi 파일을 다운로드하여 설치한다.
https://github.com/MicrosoftArchive/redis/releases

2. 아래 링크는 redis manager인데, 지금하고자 하는 것에는 사용하지 않는다.
다만, 1번 링크 설치 후에 간단한 key/value 값 넣고 확인해본다거나 하실려면 설치!

https://sourceforge.net/projects/redis-desktop-manager.mirror/

3. redis를 사용할 수 있는 것들 중 나는 cpp_redis를 선택했다.
아래 링크에서 체크아웃하였다. 우리는 visual studio를 통해 빌드할 예정이다.
https://github.com/Cylix/cpp_redis

4. 3번에서 체크 아웃 받은 프로젝트의 폴더로 가보면 아래 경로에 tacopie.sln 이 있다.
..\cpp_redis\msvc15

5. 만약 현재 환경이 visual studio 2017이고, Windows SDK 버전도 상위라면
프로젝트 속성에서 변경해줘야 한다.

6. 빌드를 완료하면, 아래 경로에 tacopie.lib 파일이 있을 것이다.
\cpp_redis\msvc15\x64\Debug 또는 Release

7. 이제 테스트를 위한 윈도우 콘솔 솔루션을 생성하고
TestRedisClient, TestRedisServer 와 같이 2개의 프로젝트를 생성한다.
프로젝트명은 각자 원하시는대로 하시면 된다.

8. 두 프로젝트 모두 다 tacopie.lib를 사용하기 위한 설정을 해준다.
나는 아래와 같이 4개의 항목을 수정했다.

디렉터리는 아래와 같이 2개를 추가 했다.
\cpp_redis\includes
\cpp_redis\includes\tacopie
 - 이 폴더 안에 tacopie.lib 파일을 넣어두었다.


 구성속성 > VC++ 디렉터리 > 포함 디렉터리
 구성속성 > VC++ 디렉터리 > 라이브러리 디렉터리
 구성속성 > C/C++ > 추가 포함 디렉터리
 구성속성 > 링커 > 입력 > 추가 종속성 (tacopie.lib 추가)


자.. 그러면 프로젝트 준비는 어느 정도 된 것 같고 아래에는 내가 테스트한 소스다.
github에 보면 example 코드가 있는데 그거와 거의 동일하다.
몇 가지 내가 주석을 달고, client 측에서 async_write를 사용한 것 빼고..

<TestRedisClient>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include "pch.h"
#include <iostream>
#include <WinSock2.h>
#include <tacopie/tacopie>
#include <condition_variable>
#include <mutex>
#include <signal.h>
using namespace std;
std::condition_variable cv;
void signint_handler(int) 
{
    // 주의:
    // 스레드는 아래 두 메서드에 의해 깨어날 수도 있지만,
    // 타임 아웃으로 인해 깨어날 수도 있다.
    // 이 조건 변수를 기다리고 있는 스레드 중 한 개의 스레드를 깨운다.
    //cv.notify_one();
    // 이 조건 변수를 기다리고 있는 모든 스레드를 깨운다.
    cv.notify_all();
}
void on_new_message(tacopie::tcp_client& client, const tacopie::tcp_client::read_result& res) 
{
    if (res.success) 
    {
        std::cout << "Client recv data" << std::endl;
        client.async_write({ res.buffer, nullptr });
        client.async_read({ 1024, std::bind(&on_new_message, std::ref(client), std::placeholders::_1) });
    }
    else 
    {
        std::cout << "Client disconnected" << std::endl;
        client.disconnect();
    }
}
int main()
{
    WORD version = MAKEWORD(2, 2);
    WSADATA data;
    // 이 과정을 해주지 않으면 cpp_redis 정상적으로 동작하지 않는다.
    // 이 녀석도 소켓을 쓰는 거니까
    if (0 != WSAStartup(version, &data))
    {
        cout << "WSAStartup fail" << "\n";
        return -1;
    }
    tacopie::tcp_client client;
    client.connect("127.0.0.1", 3000);
    client.async_read({ 1024, std::bind(&on_new_message, std::ref(client), std::placeholders::_1) });
    vector<int> v = { 1, 2, 3, 4, 5 };
    tacopie::tcp_client::write_request a;
    a.buffer.push_back(1);
    a.buffer.push_back(2);
    a.buffer.push_back(3);
    a.buffer.push_back(4);
    a.buffer.push_back(5);
    client.async_write({ a.buffer, nullptr });
    // SIGINT 값은 사용자가 Ctrl+C키를 입력했을 때 들어온다.
    // 즉, signint_handler함수를 호출해 notify 해줌으로써 
    // 아래에서 lock(mtx)에 잠긴 스레드를 깨운다.
    signal(SIGINT, &signint_handler);
    std::mutex mtx;
    std::unique_lock<std::mutex> lock(mtx);
    
    cv.wait(lock);
    
    WSACleanup();
    system("pause");
    return 0;
}
cs

<TestRedisServer>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include "pch.h"
#include <tacopie/tacopie>
#include <condition_variable>
#include <iostream>
#include <mutex>
#include <signal.h>
#include <Winsock2.h>
std::condition_variable cv;
void signint_handler(int) 
{
    cv.notify_all();
}
void on_new_message(const std::shared_ptr<tacopie::tcp_client>& client, const tacopie::tcp_client::read_result& res) 
{
    if (res.success) 
    {
        std::cout << "Client recv data" << std::endl;
        client->async_write({ res.buffer, nullptr });
        client->async_read({ 1024, std::bind(&on_new_message, client, std::placeholders::_1) });
    }
    else 
    {
        std::cout << "Client disconnected" << std::endl;
        client->disconnect();
    }
}
int main(void) 
{
    //! Windows netword DLL init
    WORD version = MAKEWORD(2, 2);
    WSADATA data;
    if (WSAStartup(version, &data) != 0) 
    {
        std::cerr << "WSAStartup() failure" << std::endl;
        return -1;
    }
    tacopie::tcp_server s;
    s.start("127.0.0.1", 3000, [](const std::shared_ptr<tacopie::tcp_client>& client) -> bool 
    {
        std::cout << "New client" << std::endl;
        client->async_read({ 1024, std::bind(&on_new_message, client, std::placeholders::_1) });
        return true;
    });
    signal(SIGINT, &signint_handler);
    std::mutex mtx;
    std::unique_lock<std::mutex> lock(mtx);
    cv.wait(lock);
    WSACleanup();
    system("pause");
    return 0;
}
cs
시간: 댓글 없음:
라벨:
피드 구독하기: 글 (Atom)

A*, JPS 길찾기 알고리즘 시뮬레이션 사이트

https://qiao.github.io/PathFinding.js/visual/ 길 찾기 알고리즘 시행 과정을 보여주는 사이트다. 링크 메모..

  • lock-free aba problem에 대해..
    예전에 게임 서버 포폴 만드는 공부에서 IOCP 구조로 만든 네트워크 스레드(n개)에서 받아들여온 패킷들을  Lock-Free Queue에 넣고, 게임 로직 스레드에서 꺼내다가 로직처리하도록 만들었었다. I have developed my game ...
  • A*, JPS 길찾기 알고리즘 시뮬레이션 사이트
    https://qiao.github.io/PathFinding.js/visual/ 길 찾기 알고리즘 시행 과정을 보여주는 사이트다. 링크 메모..