fts
Apple のリファレンスを眺めているとディレクトリ走査でパフォーマンスを考慮するなら fts を使うのがいいと出ていた。
File-System Performance Guidelines: Iterating Directory Contents
上記内の Traversing Directories in BSD に記述あり。
調べてみたところ fts というのは BSD系OSで使われているディレクトリ走査用のライブラリのようだ。
fts_open - Linuxの手で行なうページ
(特徴)
・サブディレクトリを含むファイルとディレクトリの一覧を取得できる
・パス名の他、stats構造体を取得できる
・ソートが可能(比較関数を渡すことができる)
サブディレクトリも再帰的にリストアップできるので従来からある readdir系のライブラリよりも使い勝手が良い。また fts ではパス名だけでなく stats構造体も取得できるのでファイルサイズを計算する場合にわざわざ stats関数を呼び出す必要がない。
以下、1ファイル/ディレクトリ毎に取得できる構造体 FTSENT の内容:
typedef struct _ftsent { u_short fts_info; /* flags for FTSENT structure */ char *fts_accpath; /* access path */ char *fts_path; /* root path */ u_short fts_pathlen; /* strlen(fts_path) */ char *fts_name; /* file name */ u_short fts_namelen; /* strlen(fts_name) */ short fts_level; /* depth (-1 to N) */ int fts_errno; /* file errno */ long fts_number; /* local numeric value */ void *fts_pointer; /* local address value */ struct ftsent *fts_parent; /* parent directory */ struct ftsent *fts_link; /* next file structure */ struct ftsent *fts_cycle; /* cycle structure */ struct stat *fts_statp; /* stat(2) information */ } FTSENT;※ man fts(3) より転載
実装例
こんな感じ。
#include <sys/types.h> #include <sys/stat.h> #include <fts.h> - (IBAction)fts { int size = 0; FTS* fts; FTSENT *entry; char* paths[] = { [[self path] cStringUsingEncoding:NSUTF8StringEncoding], NULL }; fts = fts_open(paths, 0, NULL); while ((entry = fts_read(fts))) { if (entry->fts_info & FTS_DP || entry->fts_level == 0) { // ignore post-order continue; } if (entry->fts_info & FTS_F) { size += entry->fts_statp->st_size; } } fts_close(fts); }再帰コードが要らないのでスッキリして簡単。fts_openで渡すパスは配列で渡す必要がある。また通常だと取得リスト内にディレクトリが2回現れる(pre-order と post-order)ので重複させたくない場合は上記コードのように2回目に出現するタイミング(post-order)を無視するようにしている(entry->fts_info & FTS_DP)。また fts_open の引数で渡したディレクトリ自身がリストに含まれないようにトップレベルのディレクトリ(etnry->fts_level==0 のケース)も無視している。ファイルサイズは FTSENT構造体の持つ fts_statp 経由で簡単に取得できる。
fts_open の第3引数にはソート用の比較関数を渡すことができる。
FTS *fts_open(char * const *path_argv, int options, int (*compar)(const FTSENT **, const FTSENT **));例えば名前順に一覧を取得したい場合は
fts = fts_open(paths, 0, cmpare);として compare関数を用意してやる。
int cmpare(const FTSENT **a, const FTSENT **b) { return (strcasecmp((*a)->fts_name, (*b)->fts_name)); }
他の方法との比較
ファイルサイズ計算の方法は fts 以外には readdir と stats の組み合わせの他、NSFileManager を使う方法がある。これらの方法と fts を使う場合の計3つの方法についてかかる時間の比較をやってみた。
条件
下記のテストデータ(ディレクトリ、ファイル)を作成し、rootディレクトリ配下のファイルサイズを計算するのにかかった時間を実機で計測した。
条件:ディレクトリ数 10x10x10、ファイル数 10x10x10、1ファイルのサイズ 1024バイト 実機: iPhone 3GS / iOS 4.2.1 (root) |--00 | |--00 | | |--00 | | | |--file-00 | | | |--file-01 | | | : | | | |--file-09 | | |--01 | | : | | | |--01 : :
ソース
readdir を使った場合のソース。
int countStdlib; int sizeStdlib; void countdir(const char* path) { DIR* dir = opendir(path); struct dirent* ent; struct stat buf; char newPath[4096]; if (dir) { for(;;) { if ((ent = readdir(dir)) == NULL) { break; } strcpy(newPath, path); strcat(newPath, "/"); strcat(newPath, ent->d_name); if (ent->d_type == DT_DIR) { if (strcmp(ent->d_name, ".") && strcmp(ent->d_name, "..")) { countdir(newPath); } } else { // file stat(newPath, &buf); sizeStdlib += buf.st_size; countStdlib++; } } } closedir(dir); } - (IBAction)stdlib { countStdlib = 0; sizeStdlib = 0; countdir([[self path] cStringUsingEncoding:NSUTF8StringEncoding]); }
NSFIleManager を使った場合のソース。
- (IBAction)cocoa { int count = 0; int size = 0; NSFileManager* fileManager = [NSFileManager defaultManager]; NSError* error = nil; NSString* path = [self path]; for (NSString* filename in [fileManager enumeratorAtPath:[self path]]) { NSDictionary* attributes = [fileManager attributesOfItemAtPath:[path stringByAppendingPathComponent:filename] error:&error]; if ([[attributes objectForKey:NSFileType] isEqualToString:NSFileTypeRegular]) { count++; size += [[attributes objectForKey:NSFileSize] intValue]; } } }
結果
fts 6.6秒 readdir 8.5秒 NSFileManager 40.6秒fts が一番速いが readdirとの差はそれほど大きくない。readdir の遅れ 2秒近くは関数の再帰処理と stats関数で呼び出し回数が増えている分のオーバヘッドと思われる。NSFileManager はオブジェクトの生成によるオーバヘッドが大きく予想通り他の2つと比べてかなり遅い。
ファイルサイズの取得処理を除いて単純な一覧取得だけに絞って実行してみると次のようになる。
fts 1.3秒 (FTS_NOSTAT オプション) readdir 1.1秒 NSFileManager 11.0秒全体的にかなり時間が短縮できることから stats実行の処理が比較的重いことが分かる。
考察
fts は readdir とほぼ同じパフォーマンスを持ちながら、readdirよりも簡潔にコードを記述できる。また標準で stats情報の取得やソート処理が行えるなど高機能である。fts が使える処理系(iOS含む)であればこちらを利用する方が何かと便利だろう。NSFileManager は他の2つに比べると速度性能でかなり劣る。ただ cocoaで記述できるメリットもあるので対象データ量が少ない場合であればこれを使うのも悪くはない。
なお性能が同程度となるともう一つ気になるのはメモリのフットプリント。Instrumentsを使いシミュレータ上でのメモリの変化を調べてみたところ次のようになった。
(1) fts
770KB→934KB (+164KB)
(2) readdir
762KB→934KB(+172KB)
(3) NSFileManager
1MB → 27MB(+26MB)
fts と readdir はほとんど変わらず、両方共にメモリの利用量は多く無い。一方 NSFileManager の場合は NSString の生成コストが大きくかなりのメモリを消費している。
おまけ:fts ソート時の性能
先のケースではソートを行っていなかった。パス名でのソート処理を入れた時の時間を計測してみた。
: fts = fts_open(paths, 0, cmpare); : } int cmpare(const FTSENT **a, const FTSENT **b) { return (-strcasecmp((*a)->fts_name, (*b)->fts_name)); // パス名降順 }
結果は 6.6秒とソート未指定時と変わらない。念のためパス内容を NSLog で出して確認してみたがちゃんとパス名降順で一覧が取得できてる。これは速いな。
サンプル
GitHub からどうぞ。
ftsSample at 2011-03-07 from xcatsan/iOS-Sample-Code - GitHub
実行するとボタンの載った画面が現れる。
"setup directories" をタップするとテスト用のディレクトリ/ファイルが生成される。これは数十秒かかるがインストール後の最初の一回だけの実行で良い。
BSD fts .... fts によるファイルサイズ計算
stdlib ... readdir を使ったファイルサイズ計算
Cocoa ... NSFileManager を使ったファイルサイズ計算
参考情報
fts_open
ftsでファイル階層を取得する。: Xo式 実験室(labo.xo-ox.net)
FreeBSDのlsを読む fts(3)でlsを作ってみよう~。 - ボクノス
Recursive read directory - verzeichnis rekursiv auslesen - dirent - GIDForums
Manpage of READDIR
dirent
Responses
Leave a Response