Fastest way to merge millions of files

Question

There are 81 million files (!) stored in one directory on a remote machine. All files end in ".paintedHaploDiversity". I would like to merge those files into one called allOutputs_3.5 in the parent directory. More specifically, each file contains two or three lines. The first line is a header that I can ignore. Among the remaining one or two lines, one of them has the value 2 in the fourth column. For each file, I want to copy the whole line where there is a 2 in the second column and add to it the filename (excluding the extension ".paintedHaploDiversity"). I refer to this filename as "simID".

For information, the remote machine runs on MAC OS X 10.11.6 (15G22010). It is a simple destkop. There is hence no network involved (outside my ssh command to reach the remote machine).

I first tried

for f in *;
do
   simID=${f%.paintedHaploDiversity}
   awk -v simID=${simID} 'NR>1{if ($4==2) {printf simID"\t"; print}}' $f >> ../allOutputs_3.5
done

but it was very slow. I estimated the time required to months or even years! Then, I tried

awk 'FNR==1{simID=substr(FILENAME, 1, length(FILENAME)-22)}FNR>1{if ($4==2) {printf simID"\t"; print}}' * >> ../allOutputs

but it does not seem any faster. Just as a speed test, I also considered

find . -exec cat '{}' ';' > out

but it is again very slow. Thinking that maybe the issue might come from the regex expansion *, I tried to loop through each file by reproducing their name through two C style loops.

for ((bigID=1; bigID <= 9 ;++bigID)); do
   for ((rep=1; rep <= 9000000 ;++rep)); do
      awk -v simID=3.5.${bigID}_${rep} 'NR>1{if ($4==2) {printf simID"\t"; print}}' 3.5.${bigID}_${rep}.paintedHaploDiversity >> ../allOutputs_3.5
   done
done

The process is now quite a bit faster but it would still take months to run! Finally, I figured, I might as well remove the lines where the the second column is not equal to 2 only later on (probably with a sed command) and do

for ((bigID=1; bigID <= 6 ;++bigID)); do
   for ((r=1; r <= 9000000 ;++r)); do
      printf "3.5_${bigID}_${r}\t"  >> ../allOutputs_3.5
      tail -n +2 3.5_${bigID}_${r}.paintedHaploDiversity >> ../allOutputs_3.5
   done
done

The process now is expected to take about two weeks. That starts to be reasonable. I am still wondering what is causing this process to be so slow and whether it can be improved.

I suppose the bottleneck is likely the disk IO. Or is it the filesystem that takes a lot of CPU time? Is the process so slow because there are so many files in the same directory and it requires searching through a binary tree of files at every iteration of the loop? How can it be improved? Should I try writing the process in c++?

If it helps here is the output of top -o MEM while the last command (the one using printf and tail) was running

Processes: 254 total, 3 running, 12 stuck, 239 sleeping, 1721 threads                            03:12:40
Load Avg: 2.04, 1.79, 1.60  CPU usage: 0.84% user, 4.33% sys, 94.81% idle
SharedLibs: 85M resident, 11M data, 10M linkedit.
MemRegions: 42324 total, 4006M resident, 63M private, 230M shared.
PhysMem: 14G used (2286M wired), 10G unused.
VM: 753G vsize, 535M framework vsize, 1206153(0) swapins, 2115303(0) swapouts.
Networks: packets: 413664671/284G in, 126210468/104G out.
Disks: 1539349069/12T read, 1401722156/7876G written.

PID    COMMAND      %CPU TIME     #TH    #WQ  #PORTS MEM    PURG  CMPRS  PGRP  PPID  STATE
0      kernel_task  42.1 1716 hrs 167/25 0    2-     1968M  0B    0B     0     0     running
366    SystemUIServ 0.4  24:42:03 5      2    345    1055M  0B    10M    366   1     sleeping
472    softwareupda 0.0  12:46:11 5      0    3760   340M   0B    18M    472   1     sleeping
54242  Sublime Text 0.0  03:55:44 12     0    237    233M   0B    68K    54242 1     sleeping
63     powerd       0.0  44:07:21 2      0    95     204M   0B    8932K  63    1     sleeping
34951  Finder       0.1  04:11:06 9      2    1665   166M   0B    68M    34951 1     sleeping
197    WindowServer 0.0  40:02:58 3      0    453    142M   0B    63M    197   1     sleeping
13248  Terminal     0.0  84:19.45 5      0    388    114M   0B    113M   13248 1     sleeping
29465  X11.bin      0.0  89:38.70 9      0    229    104M   0B    16M    29464 29464 sleeping
12372  system_insta 0.0  00:31.61 2      0    75     78M    0B    9996K  12372 1     sleeping
1588   sysmond      0.0  02:34:04 2      1    23     62M    0B    4536K  1588  1     sleeping
54245  plugin_host  0.0  00:03.88 5      0    56     51M    0B    0B     54242 54242 sleeping
554    spindump     0.0  00:36.51 2      1    164    44M    0B    33M    554   1     sleeping
20024  com.apple.GS 0.0  00:01.43 3      2    24     43M    0B    2200K  20024 1     sleeping
475    suhelperd    0.0  00:19.84 2      0    55     42M    0B    28M    475   1     sleeping
418    installd     0.0  01:21.89 2      0    69     40M    0B    12M    418   1     sleeping
57     fseventsd    0.1  13:03:20 10     0    241    39M    0B    2904K  57    1     sleeping
364    Dock         0.0  08:48.83 3      0    283    38M    0B    27M    364   1     sleeping
201    sandboxd     0.0  18:55.44 2      1    38     38M    0B    10M    201   1     sleeping
103    loginwindow  0.0  04:26.65 2      0    377    35M    0B    3400K  103   1     sleeping
897    systemstatsd 0.0  65:30.17 2      1    43     34M    0B    4928K  897   1     sleeping
367    fontd        0.0  11:35.30 2      0    77     32M    0B    5920K  367   1     sleeping
396    ScopedBookma 0.0  01:00.46 3      2    46     32M    0B    28M    396   1     sleeping
22752  cfbackd      0.4  32:18.73 9      1    84     30M    0B    0B     22752 1     sleeping
39760  Preview      0.0  00:03.75 3      0    209    29M    0B    0B     39760 1     sleeping
53     syslogd      0.0  05:33:59 4      3    186-   29M-   0B    1668K  53    1     sleeping
533    SmartDaemon  0.0  27:07.67 10     7    175    28M    128K  5192K  533   1     stuck   
388    iconservices 0.0  00:08.85 2      1    66     27M    0B    157M   388   1     sleeping
7268   diskmanageme 0.0  00:40.14 888    0    8899   27M    0B    7352K  7268  1     sleeping
513    Notification 0.0  00:46.42 3      0    245    26M    0B    9852K  513   1     sleeping
83     opendirector 0.0  19:22:12 6      5    8827   26M    0B    2444K  83    1     sleeping
557    AppleSpell   0.0  03:12.61 2      0    57     26M    0B    10M    557   1     sleeping
422    com.apple.ge 0.0  01:50.41 5      0    83     25M    0B    1680K  422   1     sleeping
397    storeaccount 0.0  00:48.41 4      0    1333   21M    0B    2248K  397   1     sleeping
87     launchservic 0.0  64:26.85 3      2    306    20M    0B    5804K  87    1     sleeping
1      launchd      0.0  26:26:23 5      4    1802   20M    0B    6532K  1     0     stuck   
222    taskgated    0.0  17:59:00 3      1    43     19M    0B    4528K  222   1     sleeping
54     UserEventAge 0.0  18:19.74 3      0    32605- 18M-   0B    2968K  54    1     sleeping
4527   com.apple.sp 0.0  00:13.01 2      0    48     17M    0B    7792K  4527  1     sleeping
79     coreduetd    0.0  05:40.06 2      0    95     17M    0B    4604K  79    1     sleepin

and here is the output of iostat

      disk0           disk1           disk2       cpu     load average
KB/t tps  MB/s     KB/t tps  MB/s     KB/t tps  MB/s  us sy id   1m   5m   15m
7.19 152  1.07     8.10   0  0.00     8.22   0  0.00  15 50 35  1.68 1.74 1.59

---

Example:

Consider the following files

file_0:

first second third fourth fifth
bbb a a 2 r

file_1:

first second third fourth fifth
f o o 2 o

file_2:

first second third fourth fifth
f r e 1 e
x xxx x 2 x

file_3:

first second third fourth fifth
a a a 2 a

The expected output is

file_0 bbb a a 2 r
file_1 f o o 2 o
file_2 x xxx x 2 x
file_3 a a a 2 a

Answer 1

You probably can cope with two single calls to the programs grep and sed. This should be pretty fast. Maybe even faster than a self-written C program.

cd dir_with_all_the_files
grep -rE '^([^ ]+ +){3}2 ' . | 
sed -En 's/^\.\/(.*)\.paintedHaploDiversity:/\1 /p' > ../allOutputs_3.5

Assumptions made:

• The header of the column to be searched isn't 2 too.
• The directory contains no subdirectories.
  _{The command may still produce correct results but has to run needlessly long.}
• The filenames contain no : or linebreaks.
• Your grep implementation supports the non-Posix -r option (usually the case).

Further improvements if your grep implementation supports it:

• Add -m1 to speed up the search.
• Try grep -P (usually not supported on Mac OS) or pcregrep. PCRE is sometimes faster. With PCRE you can also try the alternative regex '^(.*? ){3}2 '.
• --exclude-dir \* (note that * is quoted) excludes subdirectories, so that you can use the command even without above assumption.

If you want the output to be sorted by filenames (as you would get when iterating *.paintedHaploDiversity), run sort -t ' ' -k 1,1 -o allOutputs_3.5{,} afterwards.

You might as well set export LC_ALL=C to speed up grep, sort, and maybe even sed.