같은 알고리즘일 때 C와 Java의 속도 차이.

출처: http://cherrykyun.tistory.com/28

USACO Section 1.2의 첫번째 문제 Milking Cows를 풀고 모범 답안을 보게 되었다.
기분이 좋았다. C로 프로그래밍이 되어있는데, 내가 짠 프로그램과 알고리즘 및 로직이 거의 똑같았다.
  일반적인 상식으로 Java는 C보다 느리다. 그래서 한번 생각을 해봤다. 동일한 알고리즘일 때 포인터를 이용하여 C로 짠 프로그램과, Java를 이용한 프로그램이 어느정도 시간 차이를 보이는지 측정해 보기로 했다. Java로 짠 프로그래밍은, Scanner를 통한 Input을 BufferedRearder를 이용한 방법으로 변경하였다. 일반적으로 Scanner를 통한 Input보다 Byte를 읽는 BufferedReader가 좀더 빠르기 때문이다. C와 속도비교를 하려면 이정도는 되야 하지 않겠는가?

[Java]로 짠 소스는 아래와 같다.

감추기

/*
ID: myway761
LANG: JAVA
TASK: milk2
*/
import java.util.*;
import java.io.*;

/**
* Data Structure
*/
class FarmerType implements Comparable<FarmerType> {
    int startTime;
    int endTime;
   
    FarmerType() {
        this(0,0);
    }
   
    FarmerType(int startTime, int endTime) {
        this.startTime = startTime;
        this.endTime = endTime;
    }
   
    public int compareTo(FarmerType another) {
        return new Integer(startTime).compareTo(another.startTime);
    }
   
    public int getGapTime() {
        return endTime - startTime;
    }
   
    public boolean isOverlap(FarmerType anotherFarmer) {
        return (endTime >= anotherFarmer.startTime) ? true : false;
    }
}

/**
* Main Program
*/
public class milk2 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new FileReader("milk2.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("milk2.out")));
       
        // variable
        FarmerType[] farmers = new FarmerType[Integer.parseInt(in.readLine())];
        FarmerType currentTime = new FarmerType();
        FarmerType currentGap = new FarmerType();
        int maxTime = 0;
        int maxGap = 0;
        String input;
       
        for(int i=0 ; I<farmers.length ; i++) {
            input = in.readLine();
            farmers[i] = new FarmerType(Integer.parseInt(input.split(" ")[0]), Integer.parseInt(input.split(" ")[1]));
        }
       
       
        Arrays.sort(farmers); // Quick Sort
       
        currentTime.startTime = farmers[0].startTime;
        currentTime.endTime = farmers[0].endTime;
        maxTime = currentTime.getGapTime();
       
        for(int i=1 ; i<farmers.length ; i++) {
            if (currentTime.isOverlap(farmers[i])) { // case overlap
                if(farmers[i].endTime > currentTime.endTime)
                    currentTime.endTime = farmers[i].endTime;
                if(currentTime.getGapTime() > maxTime)
                    maxTime = currentTime.getGapTime();
            }
            else {
                currentGap.startTime = currentTime.endTime;
                currentGap.endTime = farmers[i].startTime;
               
                if(currentGap.getGapTime() > maxGap)
                    maxGap = currentGap.getGapTime();
               
                currentTime.startTime = farmers[i].startTime;
                currentTime.endTime = farmers[i].endTime;
            }
        }
       
        out.println(maxTime + " " + maxGap);
       
        out.close();
        System.exit(0);
    }
}

감추기

[C]자, USACO에서 제공하는 모범답안은 아래와 같다.

감추기 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #define MAXMILKING 5000 typedef struct Milking    Milking; struct Milking {     int begin;     int end; }; Milking milking[MAXMILKING]; int nmilking; int milkcmp(const void *va, const void *vb) {     Milking *a, *b;         a = (Milking*)va;     b = (Milking*)vb;         if(a->begin > b->begin)     return 1;     if(a->begin < b->begin)     return -1;     return 0; } void main(void) {     FILE *fin, *fout;     int i, j, t, tmilk, tnomilk;     Milking cur;         fin = fopen("milk2.in", "r");     fout = fopen("milk2.out", "w");     assert(fin != NULL && fout != NULL);         /* read input, sort */     fscanf(fin, "%d", &nmilking);     for(i=0; i<nmilking; i++)         fscanf(fin, "%d %d", &milking[i].begin, &milking[i].end);         qsort(milking, nmilking, sizeof(Milking), milkcmp);         /* walk over list, looking for long periods of time */     /* tmilk = longest milking time */     /* tnomilk = longest non-milking time */     /* cur = current span of milking time being considered */         tmilk = 0;     tnomilk = 0;     cur = milking[0];     for(i=1; i<nmilking; i++) {         if(milking[i].begin > cur.end) {    /* a down time */             t = milking[i].begin - cur.end;             if(t > tnomilk)                 tnomilk = t;                         t = cur.end - cur.begin;             if(t > tmilk)                 tmilk = t;                         cur = milking[i];             } else {             if(milking[i].end > cur.end)                 cur.end = milking[i].end;         }     }         /* check final milking period */     t = cur.end - cur.begin;     if(t > tmilk)         tmilk = t;         fprintf(fout, "%d %d\n", tmilk, tnomilk);     exit(0); } 감추기

거의 로직이 비슷한 것을 확인 했다면, 이제 속도를 비교해보자.
기대해도 좋다. 나도 결과를 보고 깜짝 놀랐다.

먼저 Java로 Uploading을 한 결과이다.

이번에는 C로 Uploading한 결과이다.

깜짝 놀랐다. 이미 이정도 속도차이를 알고있었던 사람을 제외하고는 왠만한 사람은 나처럼 놀랐을 것 같다.

주목해 볼 점은 다음과 같다.

TestCase 1의 경우 Input은 1 + 1 * 2 = 3  총 3개를 입력한다. 

3개를 입력했을때 Java는 Byte입력으로 0.163 초가 걸렸고 C는 0.000xxx초가 걸렸다.
적어도 Java가 파일을 입력할때 준비하는 시간이 0.16초 정도 걸린다는 뜻이다.

그렇다면 Java가 Scanner로 입력을 받으면 어느정도 시간이 더 걸릴까?
측정을 해봤는데 약 0.05초가 추가된 0.21정도의 시간이 걸렸다.

마지막 Testcase의 input 개수는 1 + 2 * 5000 = 10001개이다.
이때 시간을 보면, Java는 0.3915, C는 0.024가 걸린 것을 알 수 있다.

이번 Case인 경우, 여러가지 요소가 시간의 차이에 영향을 미쳤다고 생각이 된다.

아까 보여진 것과 같이, 파일 입력을 준비하는 시간, 그리고 입력시 매번 new를 통해 메모리를 할당받아 Object를 생성하는 것이 이렇게 시간 차이에 영향을 미친 것 같다. 하지만, 매번 new를 이용하는 것이 잘못된 것은 아니다. 객체를 쉽게 생성하고 사용할 수 있는 것이 Java의 특징이 아니던가? 또 C는 포인터를 사용할 수 있다는 것이 특징이지 않는가?

사실 0.02초나 0.39초나 OS, 시스템 프로그래밍이 아니라면 그다지 느린 것은 아니다.

하지만 알고리즘 문제에서는 1초안에 모든것을 해결해야 되기 때문에 상당히 큰 차이다.
잘못하면 2~3만개 Input을 받을 경우, Java로는 해결을 못하는 경우가 발생할 듯 싶다.

그래도, 소스를 보면 알겠지만, Java로 짠 소스가 좀더 읽기가 좋고, 사용이 좀 더 용이함을 알 수 있다.

Java의 막강한 API를 이용해서 이런 불리함을 극복해 보도록 좀더 노력해야 겠다.

<최적화 옵션에 따른 속도차이 >(어느 위키 댓글에서 퍼옴)
gcc 컴파일 옵션 변경에 따른 결과값입니다.
소스는 원문 소스에서 변경한 것 없고
시스템은 Core2 Duo 6300에 Fedora Core 6입니다.
jdk나 gcc 버전은 아래 결과에 포함되어 있습니다.
제대로 컴파일 옵션을 주고 나면 속도가 비교가 안되네요.

jhpark@crouter:~/a 176$java -version
java version "1.6.0_03"
Java(TM) SE Runtime Environment (build 1.6.0_03-b05)
Java HotSpot(TM) Client VM (build 1.6.0_03-b05, mixed mode, sharing)
jhpark@crouter:~/a 31$java -server Speed_K
Elapsed time:0.997
Elapsed time:1.021
Elapsed time:0.387
Elapsed time:0.369
Elapsed time:0.387
jhpark@crouter:~/a 32$java -client Speed_K
Elapsed time:0.808
Elapsed time:0.807
Elapsed time:0.806
Elapsed time:0.807
Elapsed time:0.806
jhpark@crouter:~/a 178$gcc --version
gcc (GCC) 4.1.2 20070626 (Red Hat 4.1.2-13)
Copyright (C) 2006 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

jhpark@crouter:~/a 33$gcc -O2 Speed_K.c -o a
jhpark@crouter:~/a 34$./a
sizeof int=4 long=4
Elapsed time:1.451029
Elapsed time:1.370664
Elapsed time:1.453891
Elapsed time:1.370636
Elapsed time:1.451029
jhpark@crouter:~/a 35$gcc -O3 Speed_K.c -o a
jhpark@crouter:~/a 36$./a
sizeof int=4 long=4
Elapsed time:0.134384
Elapsed time:0.134390
Elapsed time:0.134395
Elapsed time:0.134375
Elapsed time:0.134376
jhpark@crouter:~/a 37$gcc -fprofile-generate -O3 Speed_K.c -o a
jhpark@crouter:~/a 38$./a
sizeof int=4 long=4
Elapsed time:0.976994
Elapsed time:0.976884
Elapsed time:0.976423
Elapsed time:0.976341
Elapsed time:0.976097
jhpark@crouter:~/a 39$gcc -fprofile-use -O3 Speed_K.c -o a
jhpark@crouter:~/a 40$./a
sizeof int=4 long=4
Elapsed time:0.000002
Elapsed time:0.000052
Elapsed time:0.000014
Elapsed time:0.000025
Elapsed time:0.000010