diffにかかる時間

diff コマンドに要する時間を調査してみました．

diffコマンド

二つのテキストファイルを比較し，違いを抽出するプログラムです

調査結果

16M行

16M行 (16*1024*1024行)のファイル同士の比較．
1行11バイト(改行を含む)

不一致行割合 と diff時間 (16M行ファイル)

不一致行割合 と diff時間 (16M行ファイル)

不一致行の割合に対して，diff時間が単調に増加しました．

64M行

不一致行割合 と diff時間 (64M行ファイル)

不一致行の割合に対して，diff時間が単調に増加しました．

不一致行なし

ファイル行数 と diff時間

両ファイルに全く違いが無い場合．
64M行でも，1秒未満．

測定環境

比較対象ファイル

比較対象ファイルの1個目は，以下のプログラム(C言語)で作成

#include <stdio.h>
#include <stdlib.h>
void main(int argc, char **argv){
        int i,max=100;
        if( 1<argc ){
                max = atoi(argv[1]);
        }
        for(i=0; i<max; i++){
                printf("%10d\n", rand());
        }
}

比較対象ファイルの2個目は，以下のプログラム(Python)で作成

import sys
n = 0
if 1< len(sys.argv):
        n = int(sys.argv[1])
i=0
with open('a.txt') as f:
        for line in f:
                if 0<n and i % n == 0:
                        print(int(line)+1)
                else:
                        sys.stdout.write(line)
                i += 1

ベンチマークを繰り返すシェルスクリプト

gcc a.c
./a.out `echo 64*1024*1024|bc` > a.txt
for i in 4 8 16 32 64 128
do
        echo ${i}
        python3 a.py ${i} > b.txt
        echo ${i}.x
        /usr/bin/time diff a.txt b.txt > /dev/null 2> result.${i}.txt
        for((j=0; j<9; j++))
        do
                echo ${i}.${j}
                /usr/bin/time diff a.txt b.txt > /dev/null 2>> result.${i}.txt
        done
done

集計するシェルスクリプト

grep elapsed result.* | sed 's/result./result. /' | sed 's/.txt/ .txt/' | sed 's/elapsed/ elapsed/' | sort -n -k 2 -r > all.txt

実行環境

CPU: Intel Core i7-3770 CPU @ 3.40GHz, clock rate 3.4 GHz (fixed)
HDD: Hitachi Deskstar 7K1000.C (1TB)
OS: Ubuntu 20.04.3 LTS, desktop, Linux 5.15.25
Memory: 16 GB