# C - 12 seconds #

I decided to port my Scala answer to C, to see how much more performance I could get.

It's more or less the same approach (build an open hash table on `a`), except that I skip the step where I build the initial array, and iterate from the hash table directly (for some reason I could never get this approach to perform in Scala - I suspect JVM inlining was to blame).

I didn't bother with threads, as it's a pain to do portably.

The code is:

 #include <stdlib.h>
 #include <stdio.h>
 #include <stdint.h>
 #include <string.h>

 // Should be 37% occupied with 50m entries
 #define TABLE_SIZE 0x8000000
 #define MASK (TABLE_SIZE - 1)
 #define BUFFER_SIZE 16384
 #define END_OF_FILE (-1)
 #define DEFAULT_VALUE (-1)

 typedef struct Row {
 int32_t a;
 int32_t b;
 int32_t t;
 } Row;

 int32_t hash(int32_t a) {
 return a * 428916315;
 }

 void insert(Row * table, Row row) {
 long loc = hash(row.a) & MASK; // Entries are hashed on a
 long inc = 0;
 while (inc <= TABLE_SIZE) {
 loc = (loc + inc) & MASK;
 inc++;
 if (table[loc].a == DEFAULT_VALUE) {
 table[loc] = row;
 break;
 }
 }
 }

 int readChar(FILE * input, char * buffer, int * pos, int * limit) {
 if (*limit < *pos) {
 return buffer[(*limit)++];
 } else {
 *limit = 0;
 *pos = fread(buffer, sizeof(char), BUFFER_SIZE, input);
 if (*limit < *pos) {
 return buffer[(*limit)++];
 } else return END_OF_FILE;
 }
 }

 void readAll(char * fileName, Row * table) {
 char* buffer = (char*) malloc(sizeof(char) * BUFFER_SIZE);
 int limit = 0;
 int pos = 0;
 
 FILE * input = fopen(fileName, "rb");
 
 int lastRead;
 Row currentRow;
 uint32_t * currentElement = &(currentRow.a);
 
 // As with the Scala version, we read rows with an FSM. We can
 // roll up some of the code using the `currentElement` pointer
 while (1) {
 switch(lastRead = readChar(input, buffer, &pos, &limit)) {
 case END_OF_FILE:
 fclose(input);
 return;
 case ' ':
 if (currentElement == &(currentRow.a)) currentElement = &(currentRow.b);
 else currentElement = &(currentRow.t);
 break;
 case '\n':
 insert(table, currentRow);
 currentRow.a = 0;
 currentRow.b = 0;
 currentRow.t = 0;
 currentElement = &(currentRow.a);
 break;
 default:
 *currentElement = *currentElement * 10 + (lastRead - '0');
 break;
 }
 }
 //printf("Read %d", lastRead);
 }

 int main() {
 Row* table = (Row*) malloc(sizeof(Row) * TABLE_SIZE);
 memset(table, 255, sizeof(Row) * TABLE_SIZE);
 
 readAll("test.file", table);
 
 // We'll iterate through our hash table inline - passing a callback
 // is trickier in C than in Scala, so we just don't bother
 for (size_t i = 0; i < TABLE_SIZE; i++) {
 Row * this = table + i;
 if (this->a != DEFAULT_VALUE) {
 // Lookup entries `that`, where `that.a == this.b`
 long loc = hash(this->b) & MASK;
 long inc = 0;
 while (inc <= TABLE_SIZE) {
 loc = (loc + inc) & MASK;
 inc++;
 Row * that = table + loc;
 if ((this->b == that->a) && (0 <= that->t - this->t) && (that->t - this->t < 100)) {
 // Conditions are symmetric, so we output both rows
 printf("%d %d %d\n", this->a, this->b, this->t);
 printf("%d %d %d\n", that->a, that->b, that->t);
 }
 else if (that->b == DEFAULT_VALUE) break;
 }
 }
 }
 
 free(table);
 return 0;
 }

Compile with:
 
 gcc -std=c99 -O3 -m64 filter.c

And run with:

 ./a.out

The location of the test file is hard-coded as "test.file".

Once again, reading the data takes up most of the time (just under 9 seconds). Matching takes the rest of the time.

Again, it'll be interesting to see how this fares against Scott Leadley's answer, which uses the same language but a different strategy. Scott is joining on T, which in principle means he'll have more to join against, but again, joining on T gives better cache locality.