> Python 2.7.13
> 4000000
> real    0m11.104s
> user    0m9.736s
> sys    0m0.516s

Python 2.7.13
4000000

real    0m20,490s
user    0m16,934s
sys    0m0,570s
>   d[line.rstrip("\n")]=1

Убираем вездесущий rstrip и получаем ускорение раза в полтора на ровном месте:
>     for line in f1:
>        d[line]=1

real    0m13,029s
user    0m9,299s
sys    0m0,527s

Или заменяем на однострочник:
% time python -c 'import sys;h=set(open(sys.argv[1]));sys.stdout.writelines(l for l in open(sys.argv[2]) if l not in h)' <(seq 1000000000000 1000005000000|shuf) <(seq 1000003000000 1000009000000|shuf) |wc -l

real    0m10,557s
user    0m7,168s
sys    0m0,442s