BigDataSort

마지막으로 [b]

내용출력

로그인[l]

대용량 데이타 정렬하기

1. 하나의 파일 안에 들어있는 3백만 라인 정렬

1.1. 테스트 상황

: 1.1.1. 테스트에 사용된 코드

1.2. 메모리에 다 불러와서 정렬

1.3. 키 별로 개별 파일에 저장 후 병합

1.4. open 횟수를 줄이려는 시도

1.5. FileCache 모듈 사용

: 1.5.1. 핸들을 제 때 닫지 않아서 생기는 문제

1.6. exists 검사와 cacheout을 같이 쓰는 경우

1.7. Sort::External 사용

: 1.7.1. 정렬용 비교 함수를 제공
: 1.7.2. 펄 내장 sort 사용 (GRT, sprintf)
: 1.7.3. 펄 내장 sort 사용 (GRT, pack)

1.8. Radix sort

1.9. 결과 요약

2. Comments

1. 하나의 파일 안에 들어있는 3백만 라인 정렬

[펄스터디] 까페에 한군님이 대용량 파일의 내용 정렬 질문글을 올리셨던 것과 비슷한 상황을 만들어서 해 봤음.

일단은 Perl을 사용해서 정렬하는 여러가지 방법을 테스트해 보았다. 처음에는 Perl/FileCache 모듈의 성능을 시험하려던 거라서 그 페이지에 올린 내용인데, 다른 모듈들까지 테스트하게 되면서 페이지를 따로 분리하였다.

1.1. 테스트 상황

다음과 같은 파일이 있다:

키      일련번호
0       1
0       2
0       3
1       1
2       1
2       2
...

첫번째 컬럼에 있는 숫자를 키라고 하고, 각 키마다 다시 일련번호가 붙는다. (일련번호는 중요한 게 아니고, 그저 각 라인을 구성하는 데이타의 일부로써 나중에 결과가 제대로 나오는지 확인하기 위해 넣은 것이다) 각 키가 파일 안에 나타나는 횟수가 다 다르다. 이것을 키가 가장 많이 나타나는 순으로 정렬하고 싶다.

일단 이런 형태의 데이타를 생성하기 위해서

Math::Random 모듈의 random_exponential 함수를 사용했다. 결과적으로 다음과 같이 생성되었다.

키값이 작은 쪽(0,1,2,...)은 빈도가 3000여 번 나옴
키값이 커질 수록 빈도수가 작아지다가 끝에 가면 1번만 나오는 키들이 매우 많음
키의 총 가짓수는 8573개
전체 라인 수는 3백만개
입력 파일 전체 크기는 약 25MB

원래 한군님이 정렬해야 될 데이타는 키의 가짓수는 6천여개였고 라인 수가 더 길었는데 (7백만 정도?), 시간이 너무 걸려서 좀 줄였다.

그리고 원본 파일의 구성을 두 가지로 준비했다

순차 파일은 위에 예로 든 것과 같이, 하나의 키에 해당하는 라인들이 모두 모여있음. 즉 어떤 키에 해당하는 라인들이 죽 이어서 나오고 그 이후로는 다시는 나오지 않음
랜덤 파일은 라인들이 무작위로 섞여 있음.

실행한 환경은

리눅스 커널 2.6
Perl 5.14.2
메모리 2GB
CPU Intel(R) Core(TM)2 Duo CPU E4600 @ 2.40GHz

테스트에걸리는 시간은 코드 내에서 직접 측정해서 출력하게 했고, 메모리 사용량은 옆에서 top을 띄워둔 후 virtual image 크기를 대충 눈으로 봤음.

1.1.1. 테스트에 사용된 코드

아래 두 코드 외에도 검증용 코드 등은 github에 올려두었다.

https://github.com/gypark/bigdatasort

두 개의 입력파일(순차파일과 랜덤파일)을 생성하고, 생성된 입력파일에 대한 정보(각 키 별 빈도수 등)를 담은 로그파일을 같이 생성하는 데 사용한 코드

#!/usr/bin/env perl
use strict;
use warnings;
use autodie;

use Math::Random qw/random_exponential/;


# 평균이 1000이고 지수분포를 따르는 랜덤한 수 3백만 개의 배열
my @array = random_exponential( 3000000, 1000 );

# 소숫점은 잘라내고 1의 자리 단위로 빈도수 카운트
my %freq;
$freq{ int($_) }++ foreach ( @array );

print "size : ", scalar @array, "\n";


# 값이 작은 순으로 배치한 순차 파일
open my $f_seq, ">", "input_seq.txt";
foreach my $key ( sort {$a<=>$b} keys %freq ) {
    foreach my $count ( 1 .. $freq{$key} ) {
        print {$f_seq} "$key\t$count\n";
    }
}
close $f_seq;

# @array에 나타난 순서로 배치한 랜덤 파일
open my $f_rnd, ">", "input_rnd.txt";
my %count = ();
foreach my $num ( @array ) {
    my $key = int($num);
    $count{$key}++;
    print {$f_rnd} "$key\t$count{$key}\n";
}
close $f_rnd;

# 검증을 위해 따로 데이타에 대한 정보를 남겨둠
open my $f_log, ">", "input_log.txt";
my ( $max_n, $max_f ) = (0, -1);
print {$f_log} "------- freq --------\n";
foreach ( sort {$a<=>$b} keys %freq ) {
    print {$f_log} "[$_][$freq{$_}]\n";
    if ( $max_f < $freq{$_} ) {
        $max_n = $_;
        $max_f = $freq{$_};
    }
}
print {$f_log} "\n";

print {$f_log} "------- sorted freq --------\n";
foreach ( sort {$freq{$b}<=>$freq{$a}} keys %freq ) {
    print {$f_log} "[$_][$freq{$_}]\n";
}
print {$f_log} "\n";

print {$f_log} "max: [$max_n][$max_f]\n";
print {$f_log} "# of keys: ", scalar (keys %freq), "\n";
print {$f_log} "# of nums: ", scalar (@array), "\n";
close $f_log;

정렬 시간 측정에 사용한 전체 코드

#!/usr/bin/env perl
use strict;
use warnings;
use autodie;
use FileCache maxopen => 128;
use Time::HiRes qw/gettimeofday tv_interval/;
use Sort::External;
use Sort::Radix;

if ( not defined $ARGV[0] or not grep { $ARGV[0] == $_ } (11,12,21,22,31,32,41,42,51,52,61,62,71,72,81,82,91,92,101,102) ) {
    print <<EOF;
arg:
11 - in-memory sort. sequantial
12 - in-memory sort. random

21 - open-close in each iteration. sequatial
22 - open-close in each iteration. random

31 - open-close once. maybe die. sequantial
32 - open-close once. maybe die. random

41 - use cacheout. sequantial
42 - use cacheout. random

51 - use cacheout. sequantial
52 - use cacheout. maybe error. random

61 - use Sort::External. sequatial
62 - use Sort::External. random

71 - use Sort::External, GRT(sprintf). sequatial
72 - use Sort::External, GRT(sprintf). random

81 - use Sort::External, GRT(pack). sequatial
82 - use Sort::External, GRT(pack). random

91 - use Sort::External, GRT(sprintf). Memory size. sequatial
92 - use Sort::External, GRT(sprintf). Memory size. random
EOF
    exit 1;
}

my $input_file = ( $ARGV[0] % 10 == 1 ) ? 'input_seq.txt' : 'input_rnd.txt';
my $output_postfix = ( $ARGV[0] % 10 == 1 ) ? 'seq.txt' : 'rnd.txt';
my $method = int($ARGV[0] / 10);

if ( $method == 1 ) {       # in-memory sort
    print "method 1 - in-memory sort. [$input_file]\n";
    my $t0 = [ gettimeofday ];

    open my $in, '<', $input_file;
    my @array = <$in>;
    close $in;
    print " laptime time after loading file : ", tv_interval($t0), "\n";

    my %freq = ();
    foreach my $line ( @array ) {
        my $key = (split /\s+/, $line)[0];
        $freq{$key}++;
    }

    print " laptime time after counting : ", tv_interval($t0), "\n";

    my @sorted =
        map { $_->[1] }
        sort { $freq{$b->[0]} <=> $freq{$a->[0]} or $a->[0] <=> $b->[0] }
        map { [ (split /\s+/, $_)[0], $_ ] }
        @array;
    print " laptime time after sorting : ", tv_interval($t0), "\n";

    my $output_file = "sorted_1_$output_postfix";
    open my $out, ">", $output_file;
    foreach ( @sorted ) {
        print {$out} $_;
    }
    close $out;
    print "method 1 - save [$output_file]\n";
    print " total elapsed time : ", tv_interval($t0), "\n";

}
elsif ( $method == 2 ) {    # open-close in each iteration
    print "method 2 - open-close in each iteration. [$input_file]\n";
    my $t0 = [ gettimeofday ];

    my %freq = ();
    open my $in, '<', $input_file;
    while ( my $line = <$in> ) {
        my $key = (split /\s+/, $line)[0];
        $freq{$key}++;

        open my $tmp, '>>', $key;
        print {$tmp} $line;
        close $tmp;
    }
    close $in;
    print " laptime time after loading, counting, splitting : ", tv_interval($t0), "\n";

    my $output_file = "sorted_2_$output_postfix";
    open my $out, ">", $output_file;
    foreach my $key ( sort { $freq{$b} <=> $freq{$a} or $a <=> $b } keys %freq ) {
        open my $tmp, '<', $key;
        while ( my $line = <$tmp> ) {
            print {$out} $line;
        }
        close $tmp;
        unlink $key;
    }
    close $out;

    print "method 2 - save [$output_file]\n";
    print " total elapsed time : ", tv_interval($t0), "\n";
}
elsif ( $method == 3 ) {    # open-close once
    print "method 3 - open-close once. [$input_file]\n";
    my $t0 = [ gettimeofday ];

    my %freq = ();
    my %fh = ();
    open my $in, '<', $input_file;
    while ( my $line = <$in> ) {
        my $key = (split /\s+/, $line)[0];
        $freq{$key}++;

        if ( not exists $fh{$key} ) {
            open $fh{$key}, '>', $key;
        }
        print {$fh{$key}} $line;
    }
    close $in;
    close $_ foreach ( values %fh );
    print " laptime time after loading, counting, splitting : ", tv_interval($t0), "\n";

    my $output_file = "sorted_3_$output_postfix";
    open my $out, ">", $output_file;
    foreach my $key ( sort { $freq{$b} <=> $freq{$a} or $a <=> $b } keys %freq ) {
        open my $tmp, '<', $key;
        while ( my $line = <$tmp> ) {
            print {$out} $line;
        }
        close $tmp;
        unlink $key;
    }
    close $out;

    print "method 3 - save [$output_file]\n";
    print " total elapsed time : ", tv_interval($t0), "\n";
}
elsif ( $method == 4 ) {                      # cacheout
    no strict 'refs';
    print "method 4 - use cacheout. [$input_file]\n";
    my $t0 = [ gettimeofday ];

    my %freq = ();
    my %fh = ();
    open my $in, '<', $input_file;
    while ( my $line = <$in> ) {
        my $key = (split /\s+/, $line)[0];
        $freq{$key}++;

        $fh{$key} = cacheout "$key.txt";
        print {$fh{$key}} $line;
    }
    close $in;
    # 필수!
    cacheout_close $_ foreach ( values %fh );
    print " laptime time after loading, counting, splitting : ", tv_interval($t0), "\n";

    my $output_file = "sorted_4_$output_postfix";
    open my $out, ">", $output_file;
    foreach my $key ( sort { $freq{$b} <=> $freq{$a} or $a <=> $b } keys %freq ) {
        open my $tmp, '<', "$key.txt";
        while ( my $line = <$tmp> ) {
            print {$out} $line;
        }
        close $tmp;
        unlink "$key.txt";
    }
    close $out;

    print "method 4 - save [$output_file]\n";
    print " total elapsed time : ", tv_interval($t0), "\n";
}
elsif ( $method == 5 ) {
    no strict 'refs';
    no warnings 'closed';
    print "method 5 - use cacheout (maybe error with random sequence). [$input_file]\n";
    my $t0 = [ gettimeofday ];

    my %freq = ();
    my %fh = ();
    open my $in, '<', $input_file;
    while ( my $line = <$in> ) {
        my $key = (split /\s+/, $line)[0];
        $freq{$key}++;

#         if ( not defined $fh{$key} ) {
#         if ( not defined $fh{$key} or $fh{$key} ne "$key.txt"  ) {
#         if ( not defined $fh{$key} or tell($fh{$key}) == -1  ) {
        if ( not exists $fh{$key} ) {
            $fh{$key} = cacheout "$key.txt";
        }
        print {$fh{$key}} $line;
    }
    close $in;
    cacheout_close $_ foreach ( values %fh );
    print " laptime time after loading, counting, splitting : ", tv_interval($t0), "\n";

    my $output_file = "sorted_5_$output_postfix";
    open my $out, ">", $output_file;
    foreach my $key ( sort { $freq{$b} <=> $freq{$a} or $a <=> $b } keys %freq ) {
        open my $tmp, '<', "$key.txt";
        while ( my $line = <$tmp> ) {
            print {$out} $line;
        }
        close $tmp;
        unlink "$key.txt";
    }
    close $out;

    print "method 5 - save [$output_file]\n";
    print " total elapsed time : ", tv_interval($t0), "\n";
}
elsif ( $method == 6 ) {            # Sort::External;
    print "method 6 - use Sort::External. [$input_file]\n";
    my $t0 = [ gettimeofday ];

    # 일단 freq 계산을 먼저 해야 함
    my %freq = ();
    open my $in, '<', $input_file;
    while ( my $line = <$in> ) {
        my $key = (split /\s+/, $line)[0];
        $freq{$key}++;
    }
    close $in;

    print " laptime time after loading, counting : ", tv_interval($t0), "\n";

    my $sortex = Sort::External->new(
                        sortsub => sub { $freq{(split(/\s+/,$Sort::External::b))[0]}
                                         <=>
                                         $freq{(split(/\s+/,$Sort::External::a))[0]}
                                                        or
                                         (split(/\s+/,$Sort::External::a))[0]
                                         <=>
                                         (split(/\s+/,$Sort::External::b))[0]
                                                        or
                                         (split(/\s+/,$Sort::External::a))[1]
                                         <=>
                                         (split(/\s+/,$Sort::External::b))[1]
                                     }
                                 );

    # 다시 열고 feed
    open $in, '<', $input_file;
    while ( my $line = <$in> ) {
        $sortex->feed( $line );
    }
    close $in;

    print " laptime time after feeding : ", tv_interval($t0), "\n";

    $sortex->finish;
    print " laptime time after finish (sorting?) : ", tv_interval($t0), "\n";

    my $output_file = "sorted_6_$output_postfix";
    open my $out, ">", $output_file;
    while ( defined( $_ = $sortex->fetch ) ) {
        print {$out} $_;
    }

    close $out;

    print "method 6 - save [$output_file]\n";
    print " total elapsed time : ", tv_interval($t0), "\n";
}
elsif ( $method == 7 ) {            # Sort::External, GRT;
    print "method 7 - use Sort::External, GRT(sprintf) [$input_file]\n";
    my $t0 = [ gettimeofday ];

    # GRT 변환을 위해서는 일단 freq 를 알아야 함
    my %freq = ();
    open my $in, '<', $input_file;
    while ( my $line = <$in> ) {
        my $key = (split /\s+/, $line)[0];
        $freq{$key}++;
    }
    close $in;

    print " laptime time after loading, counting : ", tv_interval($t0), "\n";

    my $sortex = Sort::External->new();

    open $in, '<', $input_file;
    while ( my $line = <$in> ) {
        chomp($line);
        my ($key, $num) = split /\s+/, $line;

        # encode for GRT
        my $sortkey = (~ sprintf("%04d", $freq{$key}) ) .
                         sprintf("%05d", $key) .
                         sprintf("%04d", $num);

        $sortex->feed( $sortkey );
    }
    close $in;

    print " laptime time after feeding : ", tv_interval($t0), "\n";

    $sortex->finish;
    print " laptime time after finish (sorting?) : ", tv_interval($t0), "\n";

    my $output_file = "sorted_7_$output_postfix";
    open my $out, ">", $output_file;
    while ( defined( $_ = $sortex->fetch ) ) {
        # decode for GRT
        my $key = substr( $_, 4, 5 ) + 0;
        my $num = substr( $_, 9 ) + 0;
        print {$out} $key, "\t", $num, "\n";
    }

    close $out;

    print "method 7 - save [$output_file]\n";
    print " total elapsed time : ", tv_interval($t0), "\n";
}
elsif ( $method == 8 ) {            # Sort::External, GRT, pack;
    print "method 8 - use Sort::External, GRT(pack) [$input_file]\n";
    my $t0 = [ gettimeofday ];

    # GRT 변환을 위해서는 일단 freq 를 알아야 함
    my %freq = ();
    open my $in, '<', $input_file;
    while ( my $line = <$in> ) {
        my $key = (split /\s+/, $line)[0];
        $freq{$key}++;
    }
    close $in;

    print " laptime time after loading, counting : ", tv_interval($t0), "\n";

    my $sortex = Sort::External->new();

    open $in, '<', $input_file;
    while ( my $line = <$in> ) {
        chomp($line);
        my ($key, $num) = split /\s+/, $line;

        # encode for GRT
        my $sortkey = (~ pack('n', $freq{$key}) ) .
                         pack('n', $key) .
                         pack('n', $num);

        $sortex->feed( $sortkey );
    }
    close $in;

    print " laptime time after feeding : ", tv_interval($t0), "\n";

    $sortex->finish;
    print " laptime time after finish (sorting?) : ", tv_interval($t0), "\n";

    my $output_file = "sorted_8_$output_postfix";
    open my $out, ">", $output_file;
    while ( defined( $_ = $sortex->fetch ) ) {
        # decode for GRT
        my ( undef, $key, $num ) = unpack('n3', $_);
        print {$out} $key, "\t", $num, "\n";
    }

    close $out;

    print "method 8 - save [$output_file]\n";
    print " total elapsed time : ", tv_interval($t0), "\n";
}
elsif ( $method == 9 ) {            # Sort::External, GRT;
    my $mem = $ARGV[1] || 8;

    print "method 9 - use Sort::External, GRT(sprintf), Memory Size($mem MB) [$input_file]\n";
    my $t0 = [ gettimeofday ];

    # GRT 변환을 위해서는 일단 freq 를 알아야 함
    my %freq = ();
    open my $in, '<', $input_file;
    while ( my $line = <$in> ) {
        my $key = (split /\s+/, $line)[0];
        $freq{$key}++;
    }
    close $in;

    print " laptime time after loading, counting : ", tv_interval($t0), "\n";

    my $sortex = Sort::External->new( mem_threshold => $mem * (1024**2));

    open $in, '<', $input_file;
    while ( my $line = <$in> ) {
        chomp($line);
        my ($key, $num) = split /\s+/, $line;

        # encode for GRT
        my $sortkey = (~ sprintf("%04d", $freq{$key}) ) .
                         sprintf("%05d", $key) .
                         sprintf("%04d", $num);

        $sortex->feed( $sortkey );
    }
    close $in;

    print " laptime time after feeding : ", tv_interval($t0), "\n";

    $sortex->finish;
    print " laptime time after finish (sorting?) : ", tv_interval($t0), "\n";

    my $output_file = "sorted_9_mem_${mem}MB_$output_postfix";
    open my $out, ">", $output_file;
    while ( defined( $_ = $sortex->fetch ) ) {
        # decode for GRT
        my $key = substr( $_, 4, 5 ) + 0;
        my $num = substr( $_, 9 ) + 0;
        print {$out} $key, "\t", $num, "\n";
    }

    close $out;

    print "method 9 - save [$output_file]\n";
    print " total elapsed time : ", tv_interval($t0), "\n";
}

1.2. 메모리에 다 불러와서 정렬

일단 파일 전체를 메모리에 읽어들인 후 정렬하여 파일로 기록하는 코드:

    # 통채로 읽고
    my @array = <$in>;

    # 각 키의 빈도수를 먼저 카운트한 후
    my %freq = ();
    foreach my $line ( @array ) {
        my $key = (split /\s+/, $line)[0];
        $freq{$key}++;
    }

    # 정렬하고
    my @sorted =
        map { $_->[1] }
        sort { $freq{$b->[0]} <=> $freq{$a->[0]} or $a->[0] <=> $b->[0] }
        map { [ (split /\s+/, $_)[0], $_ ] }
        @array;

    # 파일에 저장

실행결과는 다음과 같음

순차 파일

[gypark@www perlstudy_1473]$ ./sort.pl 11
method 1 - in-memory sort. [input_seq.txt]
 laptime time after loading file : 1.730617
 laptime time after counting : 4.001903
 laptime time after sorting : 13.373383
method 1 - save [sorted_1_seq.txt]
 total elapsed time : 14.21391

사용메모리: 약 745M

랜덤 파일

[gypark@www perlstudy_1473]$ ./sort.pl 12
method 1 - in-memory sort. [input_rnd.txt]
 laptime time after loading file : 1.725655
 laptime time after counting : 4.212954
 laptime time after sorting : 40.480208
method 1 - save [sorted_1_rnd.txt]
 total elapsed time : 41.319748

사용메모리: 약 820M

파일을 읽어 배열에 넣는데 1.7초, 그 배열원소 3백만개를 순회하며 키를 뽑아내어 빈도수를 재는 데 2.3초 정도 걸리는 건 비슷하나, 그 다음 정렬할 때 차이가 많이 난다. 순차 파일의 경우 같은 키에 해당하는 원소들이 이미 정렬된 채로 모여 있어서 그런 듯.

(여담으로, 위 테스트를 처음에는 윈도우7이 깔린 컴퓨터에서 하려고 했는데, 파일을 읽는 데에만 십수분이 걸려도 끝나지 않았다 -_-;; Perl/StringConcatenationBenchmark에서도 얘기가 나왔었지만 윈도우에서 메모리를 realloc 으로 계속 늘려나갈 때 문제가 있어서 그런 게 아닐까 짐작함)

문제는 메모리 사용량이다. 25MB 짜리 텍스트 파일을 읽어 배열에 저장할 때 400MB 이상을 쓰게되고, 정렬을 위해서 배열이 하나 복사되면서 두 배가 된다. 라인 수를 7백만개로 늘렸을 경우 내 테스트 환경에서는 순차 파일은 2GB를 간당간당하게 쓰면서 40초 정도 끝났는데, 랜덤 파일은 디스크에 스왑을 하게되는 듯 끝날 기미가 안 보여서 포기했음.

1.3. 키 별로 개별 파일에 저장 후 병합

메모리가 부족해서 통채로 읽을 수 없으니, 할 수 없이 디스크를 쓰기로 한다.

기본 컨셉은, 하나의 키에 해당하는 라인들만 뽑아내어 파일 하나에 저장하는 식으로 분리를 한 후, 빈도수가 높은 (즉 라인수가 많은) 키의 파일들부터 읽어서 하나의 파일에 기록하는 식.

    my %freq = ();
    open my $in, '<', $input_file;
    while ( my $line = <$in> ) {
        my $key = (split /\s+/, $line)[0];
        $freq{$key}++;

# 한 라인을 읽을 때마다 매번 그 라인에 해당하는 키 파일을 열고 거기에 덧붙인 후 닫음
        open my $tmp, '>>', $key;
        print {$tmp} $line;
        close $tmp;
    }
    close $in;

    open my $out, ">", $output_file;
    foreach my $key ( sort { $freq{$b} <=> $freq{$a} or $a <=> $b } keys %freq ) {
# 정렬한 키 순서대로 키 파일을 읽어서 최종 결과물에 덧붙임
        open my $tmp, '<', $key;
        while ( my $line = <$tmp> ) {
            print {$out} $line;
        }
        close $tmp;
        unlink $key;
    }
    close $out;

실행 결과:

[gypark@www perlstudy_1473]$ ./sort.pl 21
method 2 - open-close in each iteration. [input_seq.txt]
 laptime time after loading, counting, splitting : 132.328214
method 2 - save [sorted_2_seq.txt]
 total elapsed time : 134.268979

사용메모리: 약 10M

[gypark@www perlstudy_1473]$ ./sort.pl 22
method 2 - open-close in each iteration. [input_rnd.txt]
 laptime time after loading, counting, splitting : 1081.486577
method 2 - save [sorted_2_rnd.txt]
 total elapsed time : 1089.66655

사용메모리: 약 10M

메모리는, 쓸래야 쓸 일이 없다. 항상 한 라인씩 처리하기 때문에 10MB를 넘지 않는다.

순차 파일과 랜덤 파일 둘 다 정렬하고 최종 파일에 기록하는 건 몇 초 걸리지 않는데, 입력을 읽으며 키 파일들을 만드는 데 시간의 차이가 크게 난다. 어차피 3백만 번 오픈,클로즈를 꼬박꼬박 하는 건 마찬가지인데 이렇게 차이가 나는 건, 순차 파일의 경우는 한번 열었던 파일을 다시 열게 되니까 이 때는 버퍼 캐시 등의 도움으로 오버헤드가 줄어들기 때문으로 생각됨.

1.4. open 횟수를 줄이려는 시도

3백만 라인을 읽는 동안 매번 파일을 열고,닫는 건 너무 오버헤드가 크다. 이걸 줄여볼 요량으로, 어떤 키가 처음 나타날 때 그 키에 해당하는 파일을 열고, 그 다음부터는 계속 연 채로 두기로 한다.

    my %freq = ();

# 각 키에 해당하는 파일 핸들들의 해시
    my %fh = ();

    open my $in, '<', $input_file;
    while ( my $line = <$in> ) {
        my $key = (split /\s+/, $line)[0];
        $freq{$key}++;

# 어떤 키가 처음 나오면 그 때 열고
        if ( not exists $fh{$key} ) {
            open $fh{$key}, '>', $key;
        }
# 열린 파일 핸들을 계속 사용
        print {$fh{$key}} $line;
    }
    close $in;

# 나머지는 앞 섹션과 동일

실행 결과:

[gypark@www perlstudy_1473]$ ./sort.pl 31
method 3 - open-close once. [input_seq.txt]
Failed to load 'autodie::exception'.
This may be a typo in the 'autodie->exception_class' method,
or the 'autodie::exception' module may not exist.

 Can't locate autodie/exception.pm:   Too many open files at (eval 105) line 2, <$_[...]> line 1917511.
 at /home/gypark/perl5/perlbrew/perls/perl-5.14.2/lib/5.14.2/Fatal.pm line 1250, <$_[...]> line 1917511.
        Fatal::throw('autodie', 'function', 'CORE::open', 'args', 'ARRAY(0xa0997f8)', 'pragma', 'autodie',

'errno', 'Too many open files', ...) called at (eval 19) line 114
        main::__ANON__('GLOB(0xa0997b8)', '>', 1020) called at ./sort.pl line 108

안타깝게도... 시스템에서 한 프로세스가 동시에 열 수 있는 파일의 갯수에는 제한이 있다. 이 시스템에서는 1024로 설정되어 있고, 수정하려면 /etc/security/limits.conf에서 해 줄 수 있긴 하다. 윈도우에서는 2048개 정도인 듯 한데 수정하는 방법을 알아내지 못 했다. (구글링해보면 말이 다 다름)

한군님이 데이타 사이즈를 줄여서 테스트한 게 있는데, 거기에서는 매번 오픈-클로즈 할 때에 비해 속도가 절반으로 줄어들었다고 한다.

1.5. FileCache 모듈 사용

그러면 현재 열려 있는 파일 핸들의 갯수를 계속 주시하다가 한계를 넘을 것 같으면 기존의 핸들을 닫아야 한다. 이걸 자동으로 해 주는 게 이

FileCache 모듈이다. 이걸 사용해 보았다.

# 이 모듈은 심볼릭 레퍼런스 기능을 쓰기 때문에 strict 에서 제외시켜야 한다.
    no strict 'refs';

    my %freq = ();
    my %fh = ();
    open my $in, '<', $input_file;
    while ( my $line = <$in> ) {
        my $key = (split /\s+/, $line)[0];
        $freq{$key}++;

# print 하기 전에 cacheout 을 불러 주면
# 핸들이 없다면 생성해주고, 있으면 그냥 반환해주고, 닫혔다면 다시 열어서 반환해준다.
# 그리고 파일 이름을 "키번호.txt"의 형식으로 짓게 했는데, 그냥 "키번호"로 이름을 지었더니
# 키가 0인 경우 이게 표준입력의 핸들과 같은 수치가 되어 버려서 그런지 에러가 나더라.

        $fh{$key} = cacheout "$key.txt";
        print {$fh{$key}} $line;
    }
    close $in;

# 그냥 close 를 해도 될 것 같긴 한데, 모듈 문서에서 뭐라뭐라 하길래 거기서 권유하는 cacheout_close 를 사용
# 처음에는 close를 하지 않았다가 큰 낭패를 봤다. 본문에서 자세히 얘기함
    cacheout_close $_ foreach ( values %fh );

# 병합 과정은 앞에서와 동일

순차 파일

[gypark@www perlstudy_1473]$ ./sort.pl 41
method 4 - use cacheout. [input_seq.txt]
 laptime time after loading, counting, splitting : 17.825475
method 4 - save [sorted_4_seq.txt]
 total elapsed time : 19.576668

랜덤 파일

[gypark@www perlstudy_1473]$ ./sort.pl 42
method 4 - use cacheout. [input_rnd.txt]
 laptime time after loading, counting, splitting : 891.26132
method 4 - save [sorted_41_rnd.txt]
 total elapsed time : 893.901962

순차 파일은 매우 빠르다! 메모리에 전부 불러오는 경우와 비교해도 몇 초 차이나지 않는다. 게다가 8573개의 파일을 여는 데에도 전혀 문제가 없다. 메모리 사용량은 13MB 정도였다.

그에 비해 라인이 랜덤하게 섞여 있을 경우는 크게 느려진다. 매번 오픈하는 두번째 경우와 비교할 때 1081초에서 891초로 20% 정도 줄기는 했으나 그래도 꽤나 걸린다.

순차 파일은 한 번 나왔던 키는 연달아 나온 후 더 이상 나오지 않으니까, 다른 파일을 열기 위해서 기존의 핸들을 닫고 나면 다시 열 일이 없다. 즉 기존의 핸들을 닫고 새 핸들을 여는 걸 키의 갯수만큼만 수행하면 된다. (최대 8573번이고, 실제론 동시에 여러 핸들을 열 수 있으니 이보다 줄어들 것이다) 그러나 랜덤 파일은 아까 닫았던 핸들을 다시 열어야 되는 경우가 계속 생기니까, 장기적으로는 매번 open-close 하는 것과 비슷해질 것이다. 따라서 이 결과는 납득할 수 있다.

어쨌거나 매번 오픈하는 것에 비해 시간을 단축할 수 있다.

1.5.1. 핸들을 제 때 닫지 않아서 생기는 문제

여기서 내가 테스트 중에 상당히 곤혹스러운 일이 있었는데, 처음 시도할 때는, 분할이 끝난 직후에 키 파일들에 대한 파일 핸들을 닫지 않았다. FileCache가 관리하는 핸들을 수동으로 close해도 괜찮을까 걱정이 되었고, 모듈 문서에서 "가능하긴 하지만 어쩌고 저쩌고"하길래 그랬던 것이다. 그랬더니만 정렬된 결과 파일이 앞의 방법들과 비교해서 달라지는 문제가 생겼다.

순차 파일을 정렬했을 경우, 일부 키들이 통채로 사라져버렸다
랜덤 파일을 정렬했을 경우, 일부 키들의 마지막 라인이 사라졌다

분할 직후에 일시정지하도록 수정한 후, 생성된 키 파일들을 봤더니 크기가 0이었다. 즉 print 가 제대로 되지 않은 것이다. 그리고 이렇게 크기 0인 파일을 병합하게 되니, 최종 결과에 그 키에 해당하는 라인들이 나타나지 않는다.

상당히 당혹스러운 현상이고 원인도 알 수 없어서 한참을 고민했다. 그런데 병합이 끝나고 프로그램이 종료된 다음에 크기가 0인 파일들을 다시 확인하려 했더니, 그 파일들이 그제서야 제대로 저장이 되어 있더라. 그제서야 이게 print 자체는 수행이 되었는데 그게 디스크에 반영이 늦게 되는 문제란 걸 알았다. 디스크에 반영이 안 된 상태로 병합 루프에서 직접 open을 하여 읽으니 읽을 데이타가 없는 것이다. (이런 경우 OS 차원에서 동기화해줘야 되는 것 같기도 한데?)

그래서 부랴부랴 cacheout_close()를 써서 핸들을 전부 닫고 병합을 진행하도록 하였다. 그러고나니 결과가 제대로 나왔다. (그나마도 처음엔 close할 생각은 아예 안 들었고 print 직후에 꼬박꼬박

IO::Handle 모듈을 써서 파일 핸들에 flush()를 시켜줬다. 그랬더니 결과는 정상으로 나오지만 시간이 1.5배 정도로 늘어났었다)

1.6. exists 검사와 cacheout을 같이 쓰는 경우

앞에 "open 횟수를 줄이려는 시도" 섹션에서는, 파일핸들이 존재하는지 아닌지를 해시를 써서 검사했다. 즉 해시에 핸들이 존재하면, 따로 open을 시도하지 않고 곧바로 print한다.

# 어떤 키가 처음 나오면 그 때 열고
        if ( not exists $fh{$key} ) {
            open $fh{$key}, '>', $key;
        }
# 열린 파일 핸들을 계속 사용
        print {$fh{$key}} $line;

그리고 바로 앞 섹션에서는, 매번 프린트하기 전에 cacheout을 불러서 핸들을 새로 받아온다 (그게 이미 열려있는 핸들일 수도 있고, 모듈이 새로 열어준 핸들일 수도 있지만)

        $fh{$key} = cacheout "$key.txt";
        print {$fh{$key}} $line;

이 두 가지를 섞어서 다음과 같이 하면 어떻게 될까.

# 해시에 핸들이 존재하지 않을 경우에는 cacheout을 써서 받아옴
        if ( not exists $fh{$key} ) {
            $fh{$key} = cacheout "$key.txt";
        }
        print {$fh{$key}} $line;

얼핏 보면 두 방법의 장점만 취합한 좋은 방법 같지만, 함정이 있다. 오픈 파일의 갯수가 한계에 걸려서 기존 핸들의 일부를 FileCache모듈이 닫아버렸을 때, 여전히 저 %fh 해시에는 그 키가 남아 있다. 따라서 exists 검사는 통과하지만, 실제 핸들은 닫혀 있는 상태에서 print 를 시도할 것이다.

실제 결과를 보면,

순차 파일

[gypark@www perlstudy_1473]$ ./sort.pl 51
method 5 - use cacheout (maybe error with random sequence). [input_seq.txt]
 laptime time after loading, counting, splitting : 5.53795
method 5 - save [sorted_5_seq.txt]
 total elapsed time : 7.270632

순차 파일은 아주 빠르다! 매번 cacheout 검사를 하지 않고 필요할 때만 부르니 훨씬 빨라진다.

그러나 랜덤하게 섞인 데이타를 가지고 수행하면:

랜덤 파일

[gypark@www perlstudy_1473]$ ./sort.pl 52
print() on closed filehandle 1828.txt at ./sort.pl line 185, <$_[...]> line 157.
print() on closed filehandle 8.txt at ./sort.pl line 185, <$_[...]> line 161.
print() on closed filehandle 294.txt at ./sort.pl line 185, <$_[...]> line 184.
...

이렇게 무수히 많은 경고가 뜬다. 이미 닫힌 핸들에 대해 print를 시도하기 때문이다. 예상한 결과다. 어째서 순차 파일에는 이런 경고가 뜨지 않는가? 그것도 충분히 짐작 가능하지만, 한번 닫은 핸들에 다시 기록을 시도할 일이 없기 때문이다.

저 경고를 무시하고 끝까지 진행하면 어떻게 될까? 혹시 경고는 뜨지만 실제 write는 제대로 되지 않을까 하는 생각에 warnings 프라그마를 끄고 실행해보았더니, 실행은 순차파일때와 동일하게 7초여만에 끝났지만, 정렬결과는... 3백만 라인 중 9453라인만 남아 있고 나머지는 다 사라져 버렸다.

혹시나 싶어서 exists 대신에 defined로 검사를 해보기도 했다. 전혀 소용없었다.(FileCache 모듈이 어떤 핸들을 닫을 경우 저 변수값도 undef으로 바꿔주지 않을까 한 것인데, 사실 말이 안 되는게 fh 해시에 들어있는 값은 레퍼런스도 아니고 단순한 스트링이다. 그러니 그 자체가 바뀔 리가 없다)

검사를 tell($fh{$key}) == -1과 같이 해보기도 했다. tell은 닫힌 파일핸들에 대해 수행하면 경고를 띄우면서 -1을 반환하는 것을 이용한 것이다. 즉 핸들이 닫혔는지를 모듈에 맡기지 않고 수동으로 검사해주는 것인데, 정렬 결과는 제대로 나왔으나 시간은 더 오래 걸렸다. (947초)

그러니 그냥 핸들을 사용하기 전에 cacheout 을 꼬박꼬박 불러주는 것이 제일 낫다고 생각된다. 물론 동일한 핸들에 연달아 기록을 할 때 매번 불러줄 필요는 없겠고, 다른 핸들을 한참 사용하다가 이 핸들을 간만에 사용하게 되는 시점에 한번씩 불러주면 될 것이다.

1.7. Sort::External 사용

열심히 많은 양의 데이타를 정렬하는 방법을 궁리하긴 했지만, 사실 메모리에 한번에 올릴 수 없는 양의 데이타를 정렬하는 것에 대해서는 이미 이론이나 구현이 많이들 연구되어 있고... CPAN 모듈 중에도 없을 리가 없다.

aer0님이 또 하나를 찾아서 알려주셨다.

Sort::External

이 모듈은 메모리에서 정렬을 하다가 메모리가 부족하면 파일에 캐시로 저장하는 과정을 반복하면서 대용량의 데이타를 정렬한다.

사용법은 일단 객체를 하나 생성한 후에, feed()로 정렬할 아이템을 넣어주고, finish()로 정렬을 완료시킨 후, fetch()로 정렬된 아이템을 순서대로 가져온다.

1.7.1. 정렬용 비교 함수를 제공

앞 섹션들에서 정렬하는 기준이 첫째는 "키의 빈도수가 높은 것"이고, 빈도수가 같은 키의 경우는 "키 값이 작은 것" 순이었다. 이걸 그대로 비교 루틴을 만들어줬다.

    my %freq = ();

# 정렬에 사용되는 익명 서브루틴을 정의할 때, $a 와 $b 대신에 $Sort::External 패키지의 a와 b를 써야 한다.
    my $sortex = Sort::External->new(
                        sortsub => sub {
                                         $freq{(split(/\s+/,$Sort::External::b))[0]}
                                         <=>
                                         $freq{(split(/\s+/,$Sort::External::a))[0]}
                                                        or
                                         (split(/\s+/,$Sort::External::a))[0]
                                         <=>
                                         (split(/\s+/,$Sort::External::b))[0]
                                     }
                                 );

    while ( my $line = <$in> ) {
        my $key = (split /\s+/, $line)[0];
        $freq{$key}++;

# $sortex 객체에 각 라인을 입력으로 공급
        $sortex->feed( $line );
    }

# 입력이 끝났으면 finish()호출
    $sortex->finish;

# fetch()로 하나씩 가져와서 저장
    while ( defined( $_ = $sortex->fetch ) ) {
        print {$out}  $_, "\n";
    }

이렇게 했더니, 정렬 결과에 상당히 많은 라인이 누락되었다. 그리고 아래 결과에서도 나오지만 중간중간 랩타임을 재보면, feed과정에서는 시간이 꽤 걸리고 finish는 수 초 내외로 끝나는 걸로 봐서, feed가 다 끝나고 finish를 할 때 정렬을 하는 게 아니라 feed를 받을 때 꼬박꼬박 정렬을 해 주는 것 같다.

따라서 일단 한번 데이타를 주욱 읽고 키 별 빈도수를 다 구한 후에 다시 데이타를 feed로 입력해야 한다.

# 일단 freq 계산을 먼저 해야 함
    my %freq = ();
    while ( my $line = <$in> ) {
        my $key = (split /\s+/, $line)[0];
        $freq{$key}++;
    }

# 입력데이타를 다시 열고 feed
    open $in, '<', $input_file;
    while ( my $line = <$in> ) {
        $sortex->feed( $line );
    }
    close $in;

# 이하는 동일

이제는 누락된 라인은 없는데, 다른 방법에 비해서 딱 한 번, 키 292에 일련번호 353부터 357까지 다섯 개의 라인의 위치가 바뀌어있었다. (같은 292키에 해당하는 구간에서 다른 1800대 일련번호가 있는 곳에 끼어 있었음)

이건 아마도 정렬하던 내용이 메모리와 디스크 캐시 사이에서 이동하면서 생긴 게 아닌가 싶고, 어쨌거나 이걸로 알 수 있는 건 Sort::External이 제공하는 정렬은 stable sort가 아니다라는 점.

따라서 이제는 키의 빈도수, 키 값 이 두 가지에 이어서 일련번호까지도 정렬 기준으로 추가해야 한다.

    my $sortex = Sort::External->new(
                        sortsub => sub {
                                         $freq{(split(/\s+/,$Sort::External::b))[0]}
                                         <=>
                                         $freq{(split(/\s+/,$Sort::External::a))[0]}
                                                        or
                                         (split(/\s+/,$Sort::External::a))[0]
                                         <=>
                                         (split(/\s+/,$Sort::External::b))[0]
# 정렬 기준이 하나 더 추가됨
                                                        or
                                         (split(/\s+/,$Sort::External::a))[1]
                                         <=>
                                         (split(/\s+/,$Sort::External::b))[1]
                                     }
                                 );

이제는 정렬 결과가 다른 방법들과 완전히 동일해졌다. 실행 시간은

순차 파일

[gypark@www perlstudy_1473]$ ./sort.pl 61
method 6 - use Sort::External. [input_seq.txt]
 laptime time after loading, counting : 3.167748
 laptime time after feeding : 20.112696
 laptime time after finish (sorting?) : 21.309754
method 6 - save [sorted_6_seq.txt]
 total elapsed time : 38.807948

랜덤 파일

[gypark@www perlstudy_1473]$ ./sort.pl 62
method 6 - use Sort::External. [input_rnd.txt]
 laptime time after loading, counting : 3.327495
 laptime time after feeding : 93.334164
 laptime time after finish (sorting?) : 98.381735
method 6 - save [sorted_6_rnd.txt]
 total elapsed time : 123.500077

순차 파일의 경우, cacheout 을 쓰며 분할 후 병합했던 방법보다 느리지만 그래도 충분히 쓸 만 하게 빠르다.

랜덤 파일의 경우, 훨씬 빨라진다. 여기서도 순차 파일에 비해서는 세 배 정도 느려지는데, 아마도 미리 정렬된 구간이 있느냐 없느냐의 차이일 거라고 생각된다.

1.7.2. 펄 내장 sort 사용 (GRT, sprintf)

정렬을 하려면 모든 원소들을 한번씩은 짝지어서 비교를 해야 한다. 따라서 latex equation

만큼의 비교를 해야 하는데, 데이타가 3백만 개니까 4조5천만 번 비교를 해야 한다......는 물론 과장이다. 저건 정말 비효율적인 알고리즘을 썼을 때 얘기고, 보통은 그보다 훨씬 빠르다.

현제 테스트셋을 가지고 Sort::External은 몇 번 비교를 할까를 잠깐 측정해 봤는데 (sortsub 익명 서브루틴에다가 count를 증가시키도록 추가), 순차 파일의 경우 6백40만번, 랜덤 파일의 경우는 5천1백만번 정도 비교를 하더라. latex equation

이 약 6천4백만이니까, 얼추 거기에 맞게 떨어진다.

암튼 5천만 번 비교를 하는데, 그때마다 매번 각 원소를 split, 게다가 정렬 기준이 세 가지라서 원소당 세 번씩 총 여섯 번 해야 한다. (익명 서브루틴 안에서 변수를 써서 split은 원소당 한 번씩 할 수도 있었겠다) 아무래도 너무 낭비 같다.

따라서, 정렬할 대상을 일단 Guttman Rosler Transform을 써서 변환하고, 정렬이 끝난 후 원래 모습으로 다시 변환하도록 해 보았다. GRT에 대해서는 Perl/SchwartzianTransform에 간단히 나와 있지만, 정렬할 대상 앞에 정렬 기준이 되는 값을 고정 길이 문자열로 삽입한 후에, Perl의 내장 sort함수를 쓸 수 있도록 하는 것이다. (내장 sort는 기본적으로 문자열 비교를 한다)

# 이젠 sortsub 를 따로 만들어 줄 필요는 없다
    my $sortex = Sort::External->new();

    while ( my $line = <$in> ) {
        chomp($line);
        my ($key, $num) = split /\s+/, $line;

# 키의 빈도수를 4자리
# 키 값을 5자리
# 키의 일련번호를 4자리
# 그 뒤에 정렬할 대상인 $line 자체가 또 들어와야 하지만, 어차피 $key와 $num이 있으면
# 라인은 그대로 구성할 수 있으니까 굳이 덧붙여주지 않았다.

        my $sortkey = (~ sprintf("%04d", $freq{$key}) ) .   # 키 빈도수는 내림차순으로 정렬해야 하므로, 비트를 반전시켰음
                         sprintf("%05d", $key) .
                         sprintf("%04d", $num);

        $sortex->feed( $sortkey );
    }

# 정렬 후 출력
    while ( defined( $_ = $sortex->fetch ) ) {
# 정렬된 원소에서 원래 데이타를 만들 수 있는 $key 와 $num 부분을 뽑아내어 그것만 출력한다
        my $key = substr( $_, 4, 5 ) + 0;
        my $num = substr( $_, 9 ) + 0;
        print {$out} $key, "\t", $num, "\n";
    }

처음에는 어차피 $line 자체에 일련번호가 있으니까 상관없겠다 싶어서 빈도수-키값-라인자체의 형태로 구성해서 정렬을 했는데, sort가 수 정렬이 아니라 문자열 정렬을 하기 때문에 다음과 같이 정렬을 해 버리더라:

그래서 위 코드처럼 다시 수정했다.

이제 실행해보면,

순차 파일

[gypark@www perlstudy_1473]$ ./sort.pl 71
method 7 - use Sort::External, GRT(sprintf) [input_seq.txt]
 laptime time after loading, counting : 3.264783
 laptime time after feeding : 18.273631
 laptime time after finish (sorting?) : 18.35904
method 7 - save [sorted_7_seq.txt]
 total elapsed time : 29.397259

랜덤 파일

[gypark@www perlstudy_1473]$ ./sort.pl 72
method 7 - use Sort::External, GRT(sprintf) [input_rnd.txt]
 laptime time after loading, counting : 3.504307
 laptime time after feeding : 23.121355
 laptime time after finish (sorting?) : 23.309957
method 7 - save [sorted_7_rnd.txt]
 total elapsed time : 35.480231

순차 파일의 경우 39초에서 29초로 단축되었다. 역시 효과가 꽤 있다.

랜덤 파일의 경우... 123초에서 35초로 단축되었다!! 비교하는 횟수가 순차 파일에 비해서 8배 정도 많다보니 비교함수의 속도 차이가 미치는 영향도 크다.

1.7.3. 펄 내장 sort 사용 (GRT, pack)

이왕 이렇게 단축한 거, 조금 더 해보자.

앞 섹션의 경우 정렬 원소를 13자리 문자열로 만들었다. 그런데 세 가지 정렬 기준이 다 2만을 넘지 않는 정수들이므로, 각각 2바이트 short int 에 담을 수 있다. Perl의 자료형을 C처럼 다루기 위해서 Perl/Pack을 쓴다. pack,unpack은 언제 봐도 헷갈리지만, 다행히

Sort::External::Cookbook 문서에서 친절하게 예를 보여준다. 정말 맘에 드는 모듈이다.

    while ( my $line = <$in> ) {
        chomp($line);
        my ($key, $num) = split /\s+/, $line;

# pack 의 인자 'n'은 network byte order short 를 의미한다.
# 키 빈도수 2바이트
# 키 값 2바이트
# 일련번호 2바이트로 압축한다.
        my $sortkey = (~ pack('n', $freq{$key}) ) .   # 역시 내림차순 정렬해야 하므로 비트 반전
                         pack('n', $key) .
                         pack('n', $num);

        $sortex->feed( $sortkey );
    }

# 출력할 때
    while ( defined( $_ = $sortex->fetch ) ) {
# unpack 으로 세 필드를 분리한 후 뒤의 두 가지만 사용한다.
        my ( undef, $key, $num ) = unpack('n3', $_);
        print {$out} $key, "\t", $num, "\n";
    }

이제 13바이트 문자열 정렬을, 6바이트 문자열 정렬로 바꾸었다 (아스키 문자로 구성된 게 아니니 문자열..이라고 부르긴 뭣하지만)

순차 파일

[gypark@www perlstudy_1473]$ ./sort.pl 81
method 8 - use Sort::External, GRT(pack) [input_seq.txt]
 laptime time after loading, counting : 3.056234
 laptime time after feeding : 16.980159
 laptime time after finish (sorting?) : 16.990444
method 8 - save [sorted_8_seq.txt]
 total elapsed time : 27.515224

랜덤 파일

[gypark@www perlstudy_1473]$ ./sort.pl 82
method 8 - use Sort::External, GRT(pack) [input_rnd.txt]
 laptime time after loading, counting : 3.429468
 laptime time after feeding : 21.588868
 laptime time after finish (sorting?) : 21.600361
method 8 - save [sorted_8_rnd.txt]
 total elapsed time : 32.706688

음... 이건 sprintf를 쓴 것에 비해서 그렇게 큰 효과를 보지는 못했다.

어쨌거나, 정리하면

순차 파일을 정렬할 때는 수작업으로 분할 후 병합하는 게 더 빠르다. 이미 각 키별로는 다 정렬되어 있기 때문에 분할된 파일들만 순서를 바꿔 합쳐주면 그만이기 때문이다.
랜덤 파일을 정렬할 때는 계속 분할 파일들을 open-close하는 오버헤드가 발생한다. 이 상황에서는 Sort::External을 써서 메모리와 디스크를 같이 쓰면서 정렬시키는 쪽이 훨씬 빨라진다.
그리고 top으로 관찰해봤을 때, 세 가지 방법 다 약 30MB 정도의 메모리를 차지하였다.

1.8. Radix sort

Perl 내장 sort를 사용하기 위해서 GRT변환을 하다보니, 모든 라인이 다 동일한 길이(13 또는 6바이트)가 되었다. 정렬데이타가 모두 동일한 길이라면,

기수_정렬(

Radix_sort)이라는 걸출한 알고리즘이 있다. 이걸 쓰면 어떨까 하고 시도해보았다.

소스 코드를 이리저리 수정하여 시도하면서 각각의 소스와 그때의 출력 결과를 제대로 저장을 해 두지 않은 터라 말로만 간단히 얘기하면:

일단 데이타를 읽어서 빈도수 카운팅을 한 후, 다시 읽으면서 Perl/Pack을 써서 6바이트 문자열로 만들고 이 문자열들을 배열에 넣은 후, Sort::Radix 모듈을 써서 정렬

: 이렇게 했더니 메모리는 한 700MB를 사용했고, 빈도수 카운팅에 3초, 다시 읽으면서 배열을 구성하는데 10초 (여기가 은근히 걸린다), 정렬하는데 45초, 파일에 기록하는데 7초 정도 걸리면서 총 65초 정도 소요

애초에 메모리에 올릴 수 없는 대용량 데이타 정렬을 테스트하는 건데 배열을 만드는 건 무리가 있다 싶다. 그래서 각 라인을 pack으로 6바이트로 줄인 것을, 하나의 스트링 안에 다 담았다. 이러면 스트링 자체는 6*3백만 = 18MB 짜리가 된다. 그리고 소트 과정에서 각 자리를 기준으로 정렬할 때마다 매번 원본과 동일한 크기의 공간이 필요하다. 그래서 동일 크기의 스트링을 하나 더 만든 후에 데이타를 왔다갔다하게 하였다. 저 위키피디아에 있는 C 소스코드와 비슷한데, C의 배열을 쓰지 않고 Perl의 스트링 하나를 커다랗게 잡은 후 substr 을 써서 각 원소에 접근하게 한 것

: 메모리는, 잘 기억은 안 나지만 50MB 정도 썼던 것 같다. 그리고 시간은 40~50초 정도 걸렸었다. 여기서도 역시 커다란 스트링을 구성하는 과정에서 10초 정도가 걸려 버린다.

아무리 pack으로 압축을 해도 메모리에서 다룰 수 없을 정도로 데이타의 양이 더 많아질 수 있으므로, 기수 정렬을 다시 파일을 대상으로 하도록 해 보았다. 아무리 각 라인의 길이가 고정되어 있다고는 하나, 파일을 매번 seek로 오가면서 특정 위치의 6바이트의 데이타를 뽑아 또다른 파일에 (여기서도 같은 크기의 파일 두 개가 필요) 다시 특정 위치에 집어넣어야 되는데 이건 너무 비효율적이다. 그래서 File::Map 모듈을 써서 memory-mapped 파일을 구성한 후, 위에서와 같이 파일에 매핑된 스트링을 대상으로 substr을 사용하였다. (seek를 쓰는 거에 비해서 얼마나 효율적인지가 궁금한데 비교해보지 못했음)

: 메모리는 40MB 이내로 사용을 했고, 시간은 의외로 파일을 사용했음에도 큰 차이가 나지 않았다. 아마도 메모리가 여유가 있는 상황이었기 때문에 마지막으로 flush하기 전까지는 계속 메모리만 사용을 했던 게 아닌가 싶음. 이 테스트를 하려면 정말로 메모리에 담을 수 없을만큼 큰 데이타셋을 가지고 해야 되지 않을까 싶다.

어쨌거나 어떻게 해도 Sort::External보다 좋은 성능을 내지는 못했다. 특히 정렬할 대상을 pack을 써서 변환하는 시간이 10초 정도 고정적으로 들어가는 게 문제. Sort::External을 쓸 때도 변환을 하긴 했는데, 이 때는 각 라인을 변환하자마자 곧바로 feed()에 넣어 정렬을 시켜버렸기 때문에 정확한 비교를 할 수 없었음.

아예 처음부터 정렬대상을 저렇게 pack된 상태로 만들어 놓고 비교를 해봐야겠다.

1.9. 결과 요약

각 섹션에 나온 결과를 한 눈에 보면,

전체 데이타 갯수 300만개. 파일 크기는 25MB
키 분류 가짓수 8573개. 분포는 지수분포
많이 나타난 키 순으로 정렬

                            데이타가 키 별로 뭉쳐 있는 경우         데이타가 랜덤하게 섞인 경우
----------------------------------------------------------------------------------------------------
* 메모리에서 정렬                                      메모리 800MB 사용
                                        14초                                    41초

----------------------------------------------------------------------------------------------------
* 키 별로 분할 저장 후 병합                        이하 전부 메모리 10~13MB 사용

1) 한 라인 읽을때마다                   134초                                  1089초
   open, close                 

2) 계속 open 해 두기                               파일 오픈 갯수 제한에 걸림                    
                                  제한에 걸리지 않을 정도로 키 가짓수가 적을 경우는 크게 빨라짐

3) cacheout 사용                        20초                                    894초

4) 2와 3결합                             7초                                      7초
                                                                       그러나 정렬 결과는 잘못됨

----------------------------------------------------------------------------------------------------
* Sort::External 사용                              이하 전부 메모리 30MB 사용                 

1) 비교 함수를 제공                     39초                                    123초

2) GRT 변환,sprintf,13자리              29초                                     35초

3) GRT 변환,pack,6자리                  28초                                     33초

현재까지는 Sort::External과 GRT변환(sprintf)를 결합한 게 제일 좋아 보인다. pack을 쓴 GRT변환은 조금 더 빨라지긴 하지만 pack은 익숙하지 않은 사람이 쓰기에는 까다롭다.

2. Comments

우왕 짱이심다... :)

-- aero 2012-10-31 3:44 pm

더불어 내용이 FileCache때문에 시작한건데 이제 그건 그냥 일부가 되어버렸으니 위키타이틀 제목을 BigDataSort 또는 BigFileSort 정도로 바꾸는게 낫지 않을까요? 요즘 하도 빅데이터 드립들이 많아서 이 좋은 내용들을 널리 보게하기 위해 검색에 의한 유입수를 늘이는데도 그게 좋을듯요 :)

-- aero 2012-11-1 9:11 am

: 어제부터 그 생각을 하고 있는데 한 번 제목을 정했다 바꾸면 이래저래 불편한게 많아서(이게 위키가 엄청 수동식이라서요 ^^;)... 이 페이지는 그냥 두고 새로 만들어 옮겨야겠어요. 어쨌거나 이번에도 가르침 많이 받았습니다 :-)
-- Raymundo 2012-11-1 9:33 am

좋은내용 감사합니다. sample data 생성부분 코드도 좀 추가해주실수 있을까요??

-- yongbin 2012-11-4 12:23 pm

: "테스트 데이타를 생성하는 데 사용한 코드" 섹션을 추가했습니다 :-)
-- Raymundo 2012-11-4 1:48 pm

컴퓨터분류

마지막 편집일: 2024-9-1 10:20 pm (변경사항 [d])
1806 hits | Permalink | 변경내역 보기 [h] | 페이지 소스 보기