It's just like pok

사실 나는 컴파일이 느려서 불만이었던적은 거의 없는데 make 파일을 작성하다가 (재)컴파일 속도를 올리는 방법을 컴파일러 입장에서 생각해보게 되었다.

컴파일을 할때 .o를 새로 만들필요가 없으면 컴파일 안하는게 가장 빠른 방법일것이다. 그래서 make는 target과 src의 업데이트를 비교해 src 파일이 업데이트가 없으면 컴파일을 수행하지 않는다.(make와 그 친구들 참조)

근데 이 작업에 의외의 난관이 있는게, c에서 include 하고 있는 헤더가 변경되면 어떻게 될것인가 여부다. 즉, c파일이 변경되었는지 아닌지를 판별하기 위해서는 .c파일과 .o 파일의 시간확인만으로는 안되고 .c파일이 의존하고 있는 .h파일들과 .o 파일의 시간확인이 필요하다.

.c파일이 include하고 있는 헤더를 확인하기위해 많이 쓰는방법이 makedep같은 의존성 확인툴을 사용하는것이다. 또 다른방법으로는 gcc -M 옵션으로 include되는 의존성을 확인하는 방법이 있다. 의존성을 확인할때는 #ifdef 같은것으로 include가 제한될수 있으므로 플래그 옵션까지 넣어서 확인하는게 일반적이다.

만일 헤더가 다른 헤더를 include하고 있다면 다시 그 include하고 있는 파일까지 일일이 .o파일과 비교해봐야 할것이다. 만일 그렇게 하지 않으려면 의존성 확인은 .c파일의 헤더만 확인하고 대신에 .c파일에서는 모든 헤더를 다 써주겠다는 프로젝트 고유의 룰을 만들고 그것을 바탕으로 make 파일을 작성해 주어야 할것이다.(gcc를 사용하면 소스파일만 적어넣어주면 .c파일과 .o 파일에 관련된 모든 종속파일들을 다 보여준다. 만일 gcc -MM 옵션을 주면 시스템 헤더등은 제외한다.)

비주얼 스튜디오를 사용하면 이런 세세한 설정을 할 수는 없지만 이녀석도 사람이 만든이상 비슷한 일을 할 것이다. 잘 알려진 좀더 나은 방법으로 삼바 프로젝트에서 한것처럼 변경사항관리같은것을 해슁해서 캐싱하고 있다가 그것을 토대로 변경사항을 확인하는 방법등이 있으니 그것을 사용하고 있을지도 모르겠다.(모르긴 몰라도 이런식의 방법이 아니면 비주얼 스튜디오가 F5를 눌렀을때 번개같이 실행하는것은 납득할수 없다. 일단 변경된지를 체크해야 하는데 그것이 위에서 말한것처럼 쉽지 않기 때문이다.)

어쨌거나 이렇게 복잡하게 얽긴 헤더는 확실히 컴파일 속도를 느리게 하는 원인이다. 복잡하게 얽힌 의존성을 확인하는데 걸린 시간이 그냥 컴파일을 하는데 걸린 시간과 비슷해질지도 모를일이다. 그래서 우선 컴파일 속도를 빠르게 하려면 헤더 종속성 문제를 코딩단계에서 고려해야 한다.

만일 .o 파일이 아닌 .a 파일(즉, 라이브러리로) 만든다면, include 의존성을 확인할 필요가 없이 .a 파일과 관련된 모든 파일들과 .a 파일의 업데이트 시간만을 비교하는것으로 재컴파일을 할지를 결정할수 있다. 내가 이 방법을 써봤는데 확실한 속도 향상이 있었다.

그래서 라이브러리를 만들어내는 중간 프로젝트들을 많이 만들어 배치하는것이 전체적인 컴파일 속도를 올리는 또 다른 방법이 될 수 있다.

이런식의 테크닉들을 적용하려고 보면 makefile을 작성하는것이 정말 아스트랄해진다. 그래서 내가 선택한것은 rake였는데 굉장히 만족하면서 사용하고 있다.

아래는 앞에서 말한 로직을 만족하는 rakefile 내 함수의 일부이다.

(Language : perl)

i = 0
size = files_to_check.length
while i < size
    break unless uptodate?(target, files_to_check[i])
    i += 1
end

# do not need build
return if i == size

# need to compile
updated_objects = 0
srcs.each do | fullPath |
    #puts fullPath
    gcc_mm = "gcc -MM #{include_flags} #{fullPath}"
    result = `#{gcc_mm}`.split
    object_file = result[0].chomp(':')
    object_file.gsub!(/\.o$/, '_g.o') if @with_debug_symbol
    need_compile = uptodate?(object_file, fullPath) ? false : true
    unless need_compile
        2.upto(result.length-1) do | result_index |
            dependent_header = result[result_index]
            #puts dependent_file
            if ( dependent_header != "\\" ) \
                and ( dependent_header.include?("wxWidgets-2.8.9") == false ) \
                and ( dependent_header.include?("/usr/") == false ) \
                and ( uptodate?(object_file, dependent_header) == false )
                puts "#{object_file} will be recompiled because #{dependent_header} was changed"
                need_compile = true
            end
            break if need_compile
        end
    end
    #compile
    if need_compile
        compiler = ( fullPath.match(/.*\.cpp$/) != nil )? 'g++' : 'gcc'
        compiler << " -g -o #{object_file}" if @with_debug_symbol
        sh "#{compiler}#{include_flags} -O3 -c #{fullPath}"
    end

    lib_flags_head << ' ' + object_file
    updated_objects += 1 unless uptodate?(target, object_file)
end

전체 소스는 여기서 볼수 있다. .h와 .c 파일의 의존성은 는 gcc( -MM옵션)를 이용해 파악하고 있다. uptodate? 라는 함수가 파일간의 timestamp를 확인하는 함수이다. .a를 빌드해내는 프로젝트라면 앞에서 말한것처럼 files_to_check 라는 배열에 .a를 만드는데 관여하는 모든 파일을 넣고 그것들의 변경여부를 확인한다.

rake로 만들어 생기는 다른 장점으로는 Hudson에 연동하기가 매우 쉽다는 점이다. 내가 Hudson에 rake 작업들을 등록하고 맨 처음에 해본일이 과연 내가만든 빌드규칙과 MS의 빌드 규칙중 누가더 빠른지를 확인하는거였는데, 물론 clean상태의 컴파일 속도가 아니라 변경사항이 일부 있을때의 재컴파일 속도이다.



위의 스샷처럼 루비 Rake를 통해 직접 작성한 gcc_debug 가 동일한 조건에서 msbuild를 이용하여 컴파일한 vc_debug 보다 6배 이상 빠르다! 흐흐.

-_- 세줄요약
1. 헤더 종속성을 고려하자
2. 라이브러리 프로젝트를 잘 활용하자.
3. rake 만세.

프로그래밍 Development, rake, 루비, 빌드

그래프의 깊이우선 탐색은 트리의 순회와 비슷하다.(그러나, 그만큼 우아하지는 않은것 같다.)
트리순회와 가장 큰 차이는 "방문여부"를 판별할 수 있는 방법이 제공되어야 하는것 뿐이다.

트리와 다르게 그래프는 여러 연결 경로가 있기 때문에 들어온곳을 다시 들어올수 있다.(-_- 이게 내가 그래프 탐색이 '우아'하지 않다고 생각하는 이유다) 예전에 방문했던곳을 탐색의 거점에서 제외하는게 그래프 탐색과 트리 순회의 핵심적인 차이이고, 그 때문에 "방문여부"를 알 필요가 있다.

방문여부는 Vertex가 방문여부를 알수 있도록 멤버로 가지고 있거나, Vertex의 ID를 인덱스로 가지는 배열이나 해쉬등을 이용해 방문여부를 표시함으로써 알수 있다. Vertex가 방문여부를 가지고 있다면, 방문전(혹은 후)에 Vertex의 방문여부를 초기화 해주어야 할 뿐만이 아니라, 하나의 그래프를 여러 Thread에서 탐색할 경우 Thread Safe하지 않으므로 그리 좋은 방법은 아니라고 생각한다.

그래프 탐색에는 깊이우선 탐색과 너비우선 탐색이 있는데 깊이우선 탐색이란, 연결된 Edge중 하나를 잡아 Vertex를 방문하고, 다시 그 Vertex에 연결된 Edge를 하나잡고 (마치, 아래로 타고 내려가듯이) 다음 Vertex를 방문하는 하다가, 더이상 연결된 Edge가 없으면 위로 올라가서 다음 Edge를 방문하는 방식(물론, 다음 Edge가 없으면 다시 위로 올라간다.)이다.

깊이우선 탐색은 다시, Vertex가 다음 방문을 위해 연결된 Edge가 없을때 위로 올라가는(예전 Vertex로 돌아가는) 방식에 따라 크게 스택을 사용하는 방식과 재귀를 사용하는 방식으로 나뉜다. - 물론 재귀를 사용하는 방식이 더 우아하다고 생각한다.

다음은 깊이우선 탐색 - 스택 버전을 Ruby로 구현한 경우다. (전체소스는 여기에 있다.)
살펴볼만한 부분이, 방문여부의 판별을 위해 루비의 Hash를 이용한 부분이다. 방문여부를 셀이 가지고 있지 않기 때문에 이 깊이우선 탐색은 Thread Safe하다.

(Language : perl)

def dfsWithStack( _rStartCell )
    aCurrentCell = @aCellContainer[_rStartCell.cell_id]
    return if aCurrentCell == nil

    aMarkedCells = Hash.new
    aDepthStack = Pok::Stack.new

    #start dfs
    aDepthStack.push_back( aCurrentCell )
    print "DFS init With Cell id : " + aCurrentCell.cell_id.to_s + "\n"

    #stack loop
    while aDepthStack.empty? == false
        aCurrentCell = aDepthStack.pop_back
        next if aMarkedCells[ aCurrentCell.cell_id ] == true

        # marking
        aMarkedCells[aCurrentCell.cell_id] = true
        print "Cell id : " + aCurrentCell.cell_id.to_s + " is now visited\n"

        #Test 확인을 쉽게 하기 위해 거꾸로 push 하도록 해서 pop할때는 작은수부터 나오게
        aConnectedCells = aCurrentCell.edge_container.sort
        aConnectedCells.reverse!
        aConnectedCells.each do | id_value_array |
            #연결된 셀을 선택
            aCandidateCell = @aCellContainer[ id_value_array[0] ]
            if aMarkedCells[aCandidateCell.cell_id] == nil
                #셀이 예전에 탐색되지 않은 셀이라면, 스택에 넣어준다.
                aDepthStack.push_back(aCandidateCell)
            end
        end
    end
end

깊이우선 탐색 - 재귀버전은 방문여부를 알기위한 장치(역시, 여기서도 Hash를 사용했다)나 기타 초기화를 하는initial condition과 Base Case과 Recursive Case를 가지고 실제 재귀를 하는 Core 부분으로 나누었다.

(Language : perl)

def dfsRecursive( _rStartCell )
    aCurrentCell = @aCellContainer[_rStartCell.cell_id]
    return if aCurrentCell == nil

    aMarkedCellsContainer = Hash.new
    print "DFS(Recursive version) init With Cell id : " + aCurrentCell.cell_id.to_s + "\n"
    dfsRecursiveCore( aCurrentCell, aMarkedCellsContainer )
end

(Language : perl)

def dfsRecursiveCore( _rCell , _rMarkedCells)
    _rMarkedCells[ _rCell.cell_id ] = true
    print "Cell id : " + _rCell.cell_id.to_s + " is just now visited\n"

    #테스트 확인을 쉽게 하기 위해 셀 번호순서대로 소팅하기
    aConnectedCellsContainer = _rCell.edge_container.sort
    aConnectedCellsContainer.each do | vertex_id_weight |
        nCell_id = vertex_id_weight[0]
        if _rMarkedCells[ nCell_id ] == nil
            dfsRecursiveCore( @aCellContainer[nCell_id], _rMarkedCells )
        end
    end
end

깊이우선 탐색의 알고리듬 수행시간은 Adjacency List의 경우에 O(|v|+|E|)로 알려져 있으나 이게 뭔말인지는 모르겠고(-_-) Fundamentals of Data Structures in C 에서는 O(e)라고 소개하고 있는것과 내가 열심히 생각해본 결과(-_-)로 보아, Undirected Graph일 경우 Edge 갯수 * 2 번만큼 순회하므로 O(2E)이다. (...-_- 일것이다.)

프로그래밍 그래프, 루비, 자료구조

그래프는 Node(혹은 Vertex)와 Edge로 이루어져 있다.(An undirected graph is a tuple (V,E) where V is a set of nodes and E is a set of edges, each of which being a collection of exactly two elements in V.)

그래프의 Node(Vertex, 혹은 Cell)와 Edge를 컴퓨터 상의 Data Structure로 표현하기 위해 Adjacency Matrix와 Adjacency List를 사용한다.

Adjacency Matrix는 노드의 ID를 Array의 인덱스로 사용하는 2중배열(Matrix)을 만들고 그 배열의 값을 노드간의 연결 - Edge - 로 나타내는 표현방법이다. 예를들면, 노드 아이디 3번과 7번이 연결이 되어있다면 adj_mat[3][7] = 1, 연결되어 있지 않다면 adj_mat[3][7] = 0 식으로 나타낸다.

Adjacency List는 노드가 연결된 노드를 가짐으로써 Edge를 나타내는 표현 방식이다. 대표적인 구현이 List를 Linked-List 방식으로 구현하는 것이지만, map< vertex_id, weight > 방식으로 표현될 수도 있다. - 앞에서도 말했듯이, 이 표현의 핵심은 노드의 연결(edge)을 '노드들간의 가짐(linked-list든 pair-map이든)'으로 표현한다는데 있다.

탐색에 있어서 Adjacency Matrix는 기본적으로 O(n^2) 인 반면에 Adjacency List는 (Undirected graph라고 가정하고) O(2e)(e는 edge의 갯수) 만큼의 시간복잡도를 가진다. 뿐만 아니라 Adjacency Matrix는 표현하기 위해 Node의 갯수^2 만큼의 메모리 영역을 차지한다. 그래서 보통 표현에 있어서 Adjacency List를 통해 그래프라는 자료구조를 나타낸다.

아래의 코드는 루비와 Adjacency List 표현을 통해 만든 그래프
(Cell이 node를 의미한다. 전체 Graph Code는 여기서 볼 수 있다.)

(Language : perl)

class Cell
    attr_accessor :cell_id, :edge_container
    def initialize
        @edge_container = Hash.new
    end
    def addEdge( _rConnectedCell, nWeight )
        if @edge_container[_rConnectedCell.cell_id] != nil && @edge_container[_rConnectedCell.cell_id] != nWeight
            puts "Hei, this graph is not directional graph. weight between vertexes must be same!\n"
        end
        @edge_container[_rConnectedCell.cell_id] = nWeight 
    end
end

class Graph
    def initialize( _nCellidStartNum )
        @nNextCellid = _nCellidStartNum
        @aCellContainer = Hash.new
    end
    def makeCell
        aCell = Cell.new
        aCell.cell_id = @nNextCellid
        @aCellContainer[ aCell.cell_id ] = aCell
        @nNextCellid += 1
        return aCell
    end
    def connectCells( _rCell1, _rCell2 , nWeight)
        _rCell1.addEdge( _rCell2, nWeight )
        _rCell2.addEdge( _rCell1, nWeight )
    end
end

프로그래밍 그래프, 루비, 자료구조

루비는 오리타입을 지향한다.
오리타입이라 함은 '오리처럼 행동하면, 오리로 봐라' 를 행동강령으로 가지는 타입을 의미한다.

오리타입의 대표적인 예가 Array이다.
루비에는 Queue나 Stack이 없다. 대신, Array로 Queue와 Stack의 역할을 할 수 있다.
Array가 Queue처럼 굴면, Queue로 보고 Stack 처럼 굴면 Stack으로 보라는게 루비의 철학이다.

나 같은 경우는 제일 익숙한 언어인 C++을 기준으로 저 Array의 오리타입을 오리로 바꾸어 사용한다.

(Language : perl)

module Pok

    class Stack < Array
        def push_back( _element )
            push(_element)
        end

        def pop_back
            pop
        end
    end

    class Queue < Array
        def push_back( _element )
            push(_element)
        end

        def pop_front
            shift
        end
    end

end

프로그래밍 루비