I got inspired by that branchless rust post a couple days ago. Tried it out here and got a ~50% speedup on a 10 million word file. (Averaged over 100 runs).
File IO was the real bottleneck, so I loaded the entire file into RAM and removed the repeated fgetc's so the actual algorithms could be compared.
word_counter elapsed time: 0.043484000 seconds
The number of words is: 10000000
The number of rows is: 221000
How does this work?
You're essentially running an edge detector over words so you can for the main loop you can do a psudo-filter over a 2-sample sliding window.
This works because isalnum returns an int which is 0 when it's not a alphanumeric character. So logically the input stream becomes _ _ _---_ _ _---_ _ -- where ___ is 0 and --- is > 0.
You can detect an edge by having a 2-sample "kernel" [1, 0] which you add with a 2-sample sliding window.
That gives us these cases:
- no-word section the result is [1, 0] + [0, 0] = [1, 0].
- a rising edge section the result is [1, 0] + [0, >0] = [1, >0]
- a word section the result is [1, 0] + [>0, >0] = [>0, >0]
- a falling edge section the result is [1, 0] + [>0, 0] = [>0, 0]
So we can use the rising edge case to increment the word count. Row count can be incremented without a conditional as well.
Resultant loop is:
uint32_t i;
unsigned char new_ch;
int prev_now[2] = {0, 0};
int PREV_IDX = 0;
int NOW_IDX = 1;
int kernel[2] = {1, 0};
int result[2] = {0, 0};
for (i = 0; i < file_size_bytes; i++){
// Update now
new_ch = data[i];
prev_now[NOW_IDX] = isalnum((unsigned char)new_ch);
// Edge detect
result[0] = prev_now[NOW_IDX] + kernel[0];
result[1] = prev_now[PREV_IDX] + kernel[1];
*w_cnt += result[0] == 1 && result[1] > 0;
*r_cnt += new_ch == '\n';
// Shift without a move operation
PREV_IDX = 1 - PREV_IDX;
NOW_IDX = 1 - NOW_IDX;
// Shift with a move operation
//prev_now[PREV_IDX] = prev_now[NOW_IDX];
}
Thanks you so much for taking the time to work with the code that I've written. As someone who is just getting back to the programming world, the C world, these concepts are brand new. As a master student in physics, I love the fact that the input stream can be seen as a signal to be analysed. It's mind-blowing to see how math can reduce the execution time by 50%. I am going to take my time to fully understand your implementation. Again, thank you so much for your time and the masterclass
File IO was the real bottleneck, so I loaded the entire file into RAM and removed the repeated fgetc's so the actual algorithms could be compared.
davidkooi@Davids-MacBook-Pro word_count % ./wc_original lorem_ipsum.txt
davidkooi@Davids-MacBook-Pro word_count % ./wc_branchless lorem_ipsum.txt How does this work?You're essentially running an edge detector over words so you can for the main loop you can do a psudo-filter over a 2-sample sliding window.
This works because isalnum returns an int which is 0 when it's not a alphanumeric character. So logically the input stream becomes _ _ _---_ _ _---_ _ -- where ___ is 0 and --- is > 0.
You can detect an edge by having a 2-sample "kernel" [1, 0] which you add with a 2-sample sliding window.
That gives us these cases:
- no-word section the result is [1, 0] + [0, 0] = [1, 0].
- a rising edge section the result is [1, 0] + [0, >0] = [1, >0]
- a word section the result is [1, 0] + [>0, >0] = [>0, >0]
- a falling edge section the result is [1, 0] + [>0, 0] = [>0, 0]
So we can use the rising edge case to increment the word count. Row count can be incremented without a conditional as well.
Resultant loop is:
uint32_t i; unsigned char new_ch;