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];
}
Hello everybody,
I am writing this post because I've just finished my first C project after a long time. It is a clone of the UNIX wc (Word Count). Right now, the program can only compute the number of words and rows. I haven't implemented the flags like -l, -w etc that wc has.
Feel free to give me tips on how to write better C code and to become a better programmer
When I was at NASA, their C coding required everything to be explicit. So
`if(!w_cnt || !r_cnt)
return NULL_PTR;
`
was wrapped in real brackets.
I was also told not to use ternery operators.
But that's NASA specific things.
Another NASA specific thing was to declare all variables at the top of a function instead of scattering declarations throughout. I see you've put them after the argument checks, so actually I think that lives up to that spirit.
I suppose that you mean wrapping in curly-braces, for explicit syntax?
if (cond) {
return val;
}
Also, there is only one instance of ternary operator in ANSI C:
cond ? succ() : fail();
This ternary syntax does not appear in main.c
"NULL_PTR" is a rather bold choice for an integer error status. I see where it’s coming from. It’s not wrong, but there are conventions for naming things.
You should also be making use of stderr to output any error message or anything that is not your expected output.
wc(1) is a Posix standard utility and you should have purchased the spec and keep one eye on the spec while implementing something like this. So far it is one cut above "Hello World".
Unix exit value 0 should indicate success. Posix system calls always return 0 on success. ANSI C library calls as well. For user-defined functions, you don’t have access to the "errno" variable, so you do what you gotta do.
Speaking of exit values, it’s also a good convention to explicitly use "exit()" rather than "return()" from main(). It’s exactly the same result. I recommend a book on standard C programming. I haven’t read a standards spec in 30 years.
Personally, I'd make the NULL_PTR error message a bit more specific. "Memory Error" is quite general. The real issue is that specific invalid arguments were passed in.
Now since this may live in it's own module and not be a public function, that could be fine. But if it's ever expanded, you'll want callers to know what specifically went wrong to help debugging.
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.
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;
Hello everybody, I am writing this post because I've just finished my first C project after a long time. It is a clone of the UNIX wc (Word Count). Right now, the program can only compute the number of words and rows. I haven't implemented the flags like -l, -w etc that wc has. Feel free to give me tips on how to write better C code and to become a better programmer
Seems pretty good.
When I was at NASA, their C coding required everything to be explicit. So
`if(!w_cnt || !r_cnt) return NULL_PTR; `
was wrapped in real brackets.
I was also told not to use ternery operators. But that's NASA specific things.
Another NASA specific thing was to declare all variables at the top of a function instead of scattering declarations throughout. I see you've put them after the argument checks, so actually I think that lives up to that spirit.
I suppose that you mean wrapping in curly-braces, for explicit syntax?
Also, there is only one instance of ternary operator in ANSI C: This ternary syntax does not appear in main.c"NULL_PTR" is a rather bold choice for an integer error status. I see where it’s coming from. It’s not wrong, but there are conventions for naming things.
You should also be making use of stderr to output any error message or anything that is not your expected output.
wc(1) is a Posix standard utility and you should have purchased the spec and keep one eye on the spec while implementing something like this. So far it is one cut above "Hello World".
Unix exit value 0 should indicate success. Posix system calls always return 0 on success. ANSI C library calls as well. For user-defined functions, you don’t have access to the "errno" variable, so you do what you gotta do.
Speaking of exit values, it’s also a good convention to explicitly use "exit()" rather than "return()" from main(). It’s exactly the same result. I recommend a book on standard C programming. I haven’t read a standards spec in 30 years.
Personally, I'd make the NULL_PTR error message a bit more specific. "Memory Error" is quite general. The real issue is that specific invalid arguments were passed in.
Now since this may live in it's own module and not be a public function, that could be fine. But if it's ever expanded, you'll want callers to know what specifically went wrong to help debugging.
Also, for some reason the "standard" in C return values is 0 for success.