[android] flood fill algorithm performance tests.

android, flood fill algorithm performance tests.

위와 같은 공룡의 엉덩이, 발, 그리고 꼬리에 이르는 부분을 FloodFill algorithm 을 적용하여 색칠해보았다.

avg 값은 5회의 결과를 평균 낸 값이다.

1. Very Intuitive and Simple Flood Fill Algorithm

Recursive method call 을 이용하여, 한 점을 기준으로 동,서,남,북 pixel 에 대해 recursive call 을 호출하는 방식이다.

private void floodFill3(Bitmap bitmap, Point fillStartPoint, int targetColor, int replacementColor){

Queue<MyPoint> queue = new LinkedList<MyPoint>();

queue.add( new MyPoint( fillStartPoint ) );

while (queue.size() > 0) {

MyPoint node = queue.poll();

    if ( bitmap.getPixel( node.x, node.y ) != targetColor ) continue;

    bitmap.setPixel( node.x, node.y, replacementColor );

    

    if ( !node.isFromWest() && node.x-1 > 0 )

     queue.add( new MyPoint( node.x-1, node.y, MyPoint.FROM_EAST ) );

    if ( !node.isFromEast() && node.x+1 < mBitmapWidth )

     queue.add( new MyPoint( node.x+1, node.y, MyPoint.FROM_WEST ) );

    if ( !node.isFromSouth() && node.y+1 < mBitmapHeight )

     queue.add( new MyPoint( node.x, node.y+1, MyPoint.FROM_NORTH ) );

    if ( !node.isFromNorth() && node.y-1 > 0 )

     queue.add( new MyPoint( node.x, node.y-1, MyPoint.FROM_SOUTH ) );

}

}

avg = 2015.4 ms.

onDraw 에서 floodFill logic 을 수행하기 떄문에,

2초나 UI thread 를 막는 결과를 초래했다. 

이 녀석을 사용할 수 없다. 다른 방법을 찾아봐야 한다.

2. Better but little bit Complex Flood Fill Algorithm.

Recursive Call 은 stack overflow 를 발생시킬 소지가 다분하며, 기본적인 algorithm 은 효율성이 떨어진다.

Wiki 를 참조하여 더 나은 방법을 찾았으니,

한점을 기점으로 좌, 우의 pixel 포인트를 정하고,

그 점의 위, 아래 pixel 에 대해 이 logic 을 recursive 하게 돌리는 것이다.

단, 진짜 recursive call 이 아닌, Queue 와 같은 collection 을 이용하 loop 를 recursive 하게 돌리는 것이다.

private void floodFill(Bitmap bitmap, Point fillStartPoint, int targetColor, int replacementColor){

Queue<Point> queue = new LinkedList<Point>();

queue.add(fillStartPoint);

while (queue.size() > 0) {

    Point node = queue.poll();

    if ( bitmap.getPixel( node.x, node.y ) != targetColor ) continue;

    Point westNode = node;

    Point eastNode = new Point( node.x + 1, node.y );

    

    while ( (westNode.x > 0) && (bitmap.getPixel( westNode.x, westNode.y ) == targetColor) ){

     expandToUpDownNode( queue, bitmap, westNode, targetColor, replacementColor );

        westNode.x--;

    }

    

    while ( (eastNode.x < mBitmapWidth ) && (bitmap.getPixel(eastNode.x, eastNode.y) == targetColor) ) {

     expandToUpDownNode( queue, bitmap, eastNode, targetColor, replacementColor );

        eastNode.x++;

    }

}

}

private void expandToUpDownNode( Queue<Point> pointQueue, Bitmap bitmap, Point node, int targetColor, int replacementColor ){

bitmap.setPixel( node.x, node.y, replacementColor );

    if ( (node.y > 0) && ( bitmap.getPixel( node.x, node.y - 1) == targetColor ) )

     pointQueue.add( new Point( node.x, node.y - 1) );

    if ( (node.y < mBitmapHeight) && ( bitmap.getPixel( node.x, node.y + 1 ) == targetColor ) )

     pointQueue.add( new Point( node.x, node.y + 1 ) );

}

avg = 1288 ms.

확실히 기본 recursive algorithm 에 비해서는 약 2배의 성능향상이 있었지만,

아직도 onDraw 에서 그려 UI Thread 를 약 1초 이상 hold 시키기 때문에 사용성 문제로 

performance optimization 이 더 수행되어야 한다.

3. 안드로이드 최적화 가이드에서 제시하는 방법들 적용.

3-1. function remove.

recursive 는 아니더라도, function call 자체도 필요 이상으로 불리게 되면 ( 지나친 refactoring 의 폐해 )

성능저하를 가져올 수 있다고 한다.

그래서 위 코드의 expandToUpDownNode 를 제거하고, 그 코드를 floodFill method 안에 그대로 넣어주었다.

avg = 1215ms.

표본수가 부족하기 때문에 정확한 성능향상이 있었다고 이야기하기는 어렵지만,

그냥 눈에 보이기에는 미약하게나마 조~금 좋아보인다..

3-2. use local variable.

안드로이드 최적화 가이드에서는 2회 이상 사용하는 global variable 들에 대해서

local variable 로 assign 하여 사용하는 것을 추천하고 있다.

같은 범주에 있더라도, local 이 훨씬 접속하는데 성능이 좋다는 것이리라..

그래서 위에서 bitmap 의 width 나 height 같은 부분을 local 로 바꾸어 적용해보았다.

avg = 1208ms.

이 역시 표본수 부족으로 확신을 할 수는 없지만, 눈에 보이기에는 미약하게나마 조금 성능향상이 있는 것 같다.

3-3. MyPoint 적용.

기본 Point 에는 x, y 값 뿐만 아니라 이것저것 다른 function 들도 들어있다.

"그럴리는 없겠지만" 하는 생각과 함께, 혹시나 몰라 MyPoint 라는 녀석을 만들어 다른 기능은 싹 빼고,

x, y 만 정의해서 사용하는 방법을 적용해보았다.

private static class MyPoint2{

public int x;

public int y;

public MyPoint2( int x, int y ){

this.x = x;

this.y = y;

}

}

avg = 1179.2 ms.

역시나 표본수 부족으로 신뢰가 가는 결과는 아니지만,

그래도 역시나 눈에 보이는대로는 약간의 성능 향상이 있었다.

4. 성능이슈는 역시나 JNI.

JNI 는 Java Native Interface 의 약자로, C, C++ 과 같은 Native 언어로 복잡도가 높은 코드를 수행하고,

그 결과를 다시 Java 단으로 전달하는 것을 이야기한다.

Java 는, 특히 Android 의 경우는 VM ( Dalvik ) 이 Native code 에 비해 성능이 느린 것은 익히 알려진 사실이다.

물론 JNI 를 통하면 NDK 도 있어야 하고, 복잡도도 올라가고, debugging 등도 어렵고, 이해해야 할 것도 훨씬 많긴 하지만, 그래도 성능향상의 결과는 확실했다.

avg = 34 ms.

표본수 부족이라는 핑계는 전혀 댈 수 없을정도로 엄청난 성능향상이 있었다.

가능한 복잡도 높은 operation 은 이제 무조건 JNI로!!!

algorithm, Android, C, C++, dalvik, debug, flood fill algorithm performance tests., floodfill, function call, Global Variable, Java Native Interface, JNI, local variable, MYPOINT, NDK, ondraw, Performance, UI Thread, vm, 복잡도, 성능, 성능 테스트, 성능 향상, 알고리즘, 전역변수, 지역변수, 최적화, 표본