O comando grep falha com erro de falta de memória

Se você olhar o código da implementação GNU degrep para saber o que acontece quando invocado como grep -Fxvf file1 file2, você verá:

1. lê todo o conteúdo da file1memória
2. desduplica as linhas dessa lista usando uma tabela hash (para a qual são necessários alguns bytes extras de memória por linha, embora essa memória seja recuperada após a desduplicação)¹.
3. em seguida, ele compila uma árvore de padrões usando o algoritmo Aho – Corasick (o mesmo Aho do ain awke o mesmo algoritmo usado no original fgrepnos anos 70), de modo a minimizar o número de comparações quando se trata de procurar linhas correspondentes em o assunto.

3 acontece mesmo quando -Fcombinado com -xo qual, para que mais do que algumas strings correspondam, provavelmente seria muito mais eficiente usar uma tabela hash (e, ironicamente, uma foi construída apenas no estágio 2).

É provável que a última parte 3 consuma mais CPU e exija mais memória.

Correndo:

base64 -w 1000 /dev/urandom | head -n 10000 |
  \time -f %MKiB grep -Fvxf - /dev/null

E variando 10.000, vejo que ele aloca cerca de 96 bytes de RAM para cada byte do arquivo de padrão, então seriam 18GiB para seu arquivo de 200MiB.

Observando isso gdb, vemos que ele aloca a struct trie(64 bytes) para a maioria, se não para todos os bytes no arquivo de padrão, pelo menos.

grepnormalmente é usado para procurar uma string ou regexp ou uma pequena lista de strings ou regexps em entradas de tamanho arbitrário, não foi projetado para comparar arquivos.

Para isso, use uma tabela hash como faria em awkou perlcom:

awk '!file1_processed {hash[$0]; next}
     ! ($0 in hash)' file1 file1_processed=1 file2

É o caminho a seguir. Isso só precisa armazenar todo o conteúdo file1na memória (mais a sobrecarga da tabela hash). E a correspondência file2é apenas uma pesquisa na tabela hash.

Para arquivos já classificados, usar commseria ainda mais eficiente.

Agora, olhando para outras grepimplementações, podemos encontrar ou construir no GNU/Linux:

$ () { \time -f '%MKiB %E' grep -Fvxf $1 $1; } =(base64 -w 1000 /dev/urandom | head -n 20000)
Command exited with non-zero status 1
1918504KiB 0:04.01

$ () { \time -f '%MKiB %E' busybox grep -Fvxf $1 $1; } =(base64 -w 1000 /dev/urandom | head -n 20000)
Command exited with non-zero status 1
24644KiB 0:15.55

$ () { \time -f '%MKiB %E' toybox grep -Fvxf $1 $1; } =(base64 -w 1000 /dev/urandom | head -n 20000)
Command exited with non-zero status 1
22892KiB 0:00.11

$ () { \time -f '%MKiB %E' ast-open-grep -Fvxf $1 $1; } =(base64 -w 1000 /dev/urandom | head -n 20000)
Command exited with non-zero status 1
48416KiB 0:21.90

$ () { \time -f '%MKiB %E' heirloom/grep/grep_su3 -Fvxf $1 $1; } =(base64 -w 1000 /dev/urandom | head -n 20000)
Command exited with non-zero status 1
805476KiB 0:13.58

O GNU e o baú de ferramentas herdado (do OpenSolaris provavelmente baseado no original fgrep) usam muita memória, mas são "relativamente" rápidos. busybox e ast-open usam menos memória, mas são muito mais lentos, possivelmente usando um algoritmo mais burro .

Toybox' é muito rápido (embora ainda significativamente mais lento que a awkabordagem) sem usar muita memória (pouco acima do tamanho de file1). Ele usa uma espécie de tabela hash grosseira em que o "hash" é o primeiro byte da string, portanto, embora faça comparações simples, ele só precisa comparar com a lista de strings para as quais o primeiro byte é o mesmo, que em o caso de strings aleatórias codificadas em base64, como em meus testes, significa que o número de comparações a serem realizadas é dividido por 64.

Se em vez de 20.000 linhas longas de 1.000 bytes de texto base64 aleatório, usarmos a saída seq -f %01000g 20000onde apenas os últimos bytes das linhas mudam, os tempos se tornam bem diferentes, com GNU/heirloom sendo de longe o mais rápido (menos de um segundo, mostrando o benefício de usar o algoritmo Aho – Corasick), busybox/ast-open/toybox aparentemente demorando uma eternidade (desisti de esperar depois de 5 minutos), toybox' ficando atrás de ast-open (não busybox que se torna o mais lento de longe²) como o o primeiro byte é sempre o mesmo, e também porque todas as comparações precisam comparar os primeiros 990+ bytes, então podemos esperar que seja cerca de 64*990 tão lento quanto para dados aleatórios.

^{¹ Ele também registra em outra tabela onde os padrões foram lidos, embora seja usado apenas ao relatar erros de regexp, portanto, é inútil para strings fixas.}

^{² Talvez porque usestrstr() para pesquisar um string dentro de um string em vez de strcmp()mesmo com -x.}

Conforme mencionado nos comentários e para responder à sua pergunta: Falha porque grep está lendo o conteúdo completo do arquivo1 e usando cada linha desse arquivo como um padrão de texto estático para pesquisar/corresponder no arquivo2

Embora isso funcione em princípio, é muito ineficiente quando você deseja obter linhas iguais em ambos os arquivos.

Conforme sugerido, use:comm

comm -23 <(sort file2) <(sort file1)

Isso comparará o conteúdo classificado e as linhas de saída exclusivas do arquivo2 (-2 suprime as linhas exclusivas do arquivo1 e -3 suprime as linhas comuns aos dois arquivos).

(ou classifique os dois arquivos antes de passá-los para o comando comm)