Fastest way -- Appending a line to a file only if it does not already exist

Few suggested improvements:

1. Try using awk instead of grep so that you can both detect the string and write it in one action;
2. If you do use grep don't use a Bash loop to feed each potential match to grep and then append that one word to the file. Instead, read all the potential lines into grep as matches (using -f file_name) and print the matches. Then invert the matches and append the inverted match. See last pipeline here;
3. Exit as soon as you see the string (for a single string) rather than continuing to loop over a big file;
4. Don't call the script millions of times with one or just a few lines -- organize the glue script (in Bash I suppose) so that the core script is called once or a few times with all the lines instead;
5. Perhaps use multicores since the files are not dependent on each other. Maybe with GNU Parallel (or you could use Python or Ruby or Perl that has support for threads).

Consider this awk for a single line to add:

$ awk -v line=line_to_append 'FNR==NR && line==$0{f=1; exit} 
                              END{if (!f) print line >> FILENAME}' file

Or for multiple lines:

$ awk 'FNR==NR {lines[$0]; next} 
       $0 in lines{delete lines[$0]} 
       END{for (e in lines) print e >> FILENAME}' lines file

Some timings using a copy of the Unix words file (235,886 lines) with a five line lines file that has two overlaps:

$ echo "frob
knob
kabbob
stew
big slob" > lines
$ time awk 'FNR==NR {lines[$0]; next} 
   $0 in lines{delete lines[$0]} 
   END{for (e in lines) print e >> FILENAME}' lines words
real    0m0.056s
user    0m0.051s
sys 0m0.003s
$ tail words
zythum
Zyzomys
Zyzzogeton
frob
kabbob
big slob

Edit 2

Try this as being the best of both:

$ time grep -x -f lines words | 
       awk 'FNR==NR{a[$0]; next} !($0 in a)' - lines >> words
real    0m0.012s
user    0m0.010s
sys     0m0.003s

Explanation:

1. grep -x -f lines words find the lines that ARE in words
2. awk 'FNR==NR{a[$0]; next} !($0 in a)' - lines invert those into lines that are NOT in words
3. >> words append those to the file

Turning the millions of passes over the file into a script with millions of actions will save you a lot of overhead. Searching for a single label at each pass over the file is incredibly inefficient; you can search for as many labels as you can comfortably fit into memory in a single pass over the file.

Something along the following lines, perhaps.

awk 'NR==FNR { a[$0]++; next }
    $0 in a { delete a[$0] }
    1
    END { for (k in a) print k }' strings bigfile >bigfile.new

If you can't fit strings in memory all at once, splitting that into suitable chunks will obviously allow you to finish this in as many passes as you have chunks.

On the other hand, if you have already (effectively) divided the input set into sets of 10-30 labels, you can obviously only search for those 10-30 in one pass. Still, this should provide you with a speed improvement on the order of 10-30 times.

This assumes that a "line" is always a full line. If the label can be a substring of a line in the input file, or vice versa, this will need some refactoring.

If duplicates are not valid in the file, just append them all and filter out the duplicates:

cat myfile mynewlines | awk '!n[$0]++' > mynewfile

This will allow appending millions of lines in seconds.

If order additionally doesn't matter and your files are more than a few gigabytes, you can use sort -u instead.

Have the script read new lines from stdin after consuming the original file. All lines are stored in an associative array (without any compression such as md5sum).

Appending the suffix 'x' is targeted to handle inputs such as '-e'; better ways probably exist.

#!/bin/bash
declare -A aa
while read line; do aa["x$line"]=1; 
done < file.txt
while read line; do
  if [ x${aa[$line]} == x ]; then
    aa[$line]=1;
    echo "x$line" >> file.txt
  fi
done