Filter a large file quickly
C, ~ 7 4.1 seconds

Radix sort on T, then walk through the array looking for matches.

It is fast because it is cache friendly.  The radix sort reasonably so, and the final walk very.  I have to check each row against about 100 others, but they are all adjacent in the cache.

Added: I no longer have to check each row against a scan of 100 other rows.  A small table of counts of low order bits of b's in the window suffices to eliminate most instances of this scan.

Now about 1/2 time parsing, 1/3 time sorting, 1/6 time doing the actual matching.

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;sys/mman.h&gt;
#include &lt;fcntl.h&gt;

// B = # of bits per radix pass
// R = # of radix passes
#define B 9
#define R 3
#define M ((1&lt;&lt;B)-1)
#define MAXN 50000000

int count[R][1&lt;&lt;B];

typedef struct {
  int a,b,t,print;
} entry;

entry A[MAXN];
entry C[MAXN];

// Sized to fit well in L1 cache
unsigned char bcount[16384];

int main(int argc, char *argv[]) {
  FILE *f = fopen(argv[1], "r");
  fseek(f, 0, SEEK_END);
  int size = ftell(f);
  fclose(f);

  int fd = open(argv[1], O_RDONLY);
  const char *p = (const char*)mmap(0, size, PROT_READ, MAP_SHARED, fd, 0);
  const char *endp = p + size;

  // parse, insert into array
  int n = 0;
  while(p &lt; endp) {

    // parse line
    int a = 0;
    while(*p != ' ') {
      a *= 10;
      a += *p - '0';
      p++;
    }
    p++;
    int b = 0;
    while(*p != ' ') {
      b *= 10;
      b += *p - '0';
      p++;
    }
    p++;
    int t = 0;
    while(*p != '\n') {
      t *= 10;
      t += *p - '0';
      p++;
    }
    p++;

    // insert it
    if(n == MAXN) {
      printf("too many elements\n");
      exit(1);
    }
    A[n].a = a;
    A[n].b = b;
    A[n].t = t;
    n++;

    // compute counts for radix sort
    count[0][t&amp;M]++;
    count[1][(t&gt;&gt;B)&amp;M]++;
    count[2][t&gt;&gt;2*B]++;
  }

  // accumulate count entries
  for(int r = 0; r &lt; R; r++) {
    for(int i = 0; i &lt; M; i++) {
      count[r][i+1]+=count[r][i];
    }
  }

  // radix sort, 3 rounds
  for(int i = n-1; i &gt;= 0; i--) {
    C[--count[0][A[i].t&amp;M]] = A[i];
  }
  for(int i = n-1; i &gt;= 0; i--) {
    A[--count[1][(C[i].t&gt;&gt;B)&amp;M]] = C[i];
  }
  for(int i = n-1; i &gt;= 0; i--) {
    C[--count[2][A[i].t&gt;&gt;2*B]] = A[i];
  }

  // Walk through array (now sorted by T) and find matches.
  // We maintain a window of T values that might match.
  // To facilitate finding matches within that window, bcount
  // keeps track of a count of how many b's in that window
  // have the given low 14 bits.
  int j = 0;
  for(int i = 0; i &lt; n; i++) {
    int a = C[i].a;
    int t = C[i].t;
    while(C[j].t &lt;= t - 100) {
      int x = C[j].b &amp; 16383;
      if(bcount[x] != 255) bcount[x]--;
      j++;
    }
    if(bcount[a &amp; 16383] &gt; 0) {
      // somewhere in the window is a b that matches the
      // low 14 bits of a.  Find out if there is a full match.
      for(int k = j; k &lt; i; k++) {
        if(a == C[k].b)
          C[k].print = C[i].print = 1;
      }
    }
    int x = C[i].b &amp; 16383;
    if(bcount[x] != 255) bcount[x]++;
  }
  for(int i = 0; i &lt; n; i++) {
    if(C[i].print)
      printf("%d %d %d\n", C[i].a, C[i].b, C[i].t);
  }
}