// macro that increments index, sets variables for the next stage, and
// gotos the label indexed by the current character
#define next(c, lc, iw) cnt = (c); lcnt = (lc); in_word = (iw); idx++; goto *(jmp_arr[(int)str[idx-1]]);
int main(int argc, char** argv)
{
/* test string */
char* str = argv[1];
/* normally this would be done as a sort of partial evaluation, but i can't for example generate an optimized function at runtime in C */
void** jmp_arr;
jmp_arr = malloc(sizeof(char)*256);
int i;
for (i = 0; i < 256; i++)
{
switch ((char)i)
{
case '\n':
jmp_arr[i] = &&newline;
break;
case ' ':
jmp_arr[i] = &&whitespace;
break;
default:
jmp_arr[i] = &&character;
break;
}
}
// null character points to exit label
jmp_arr[0] = &&terminate;
int cnt = 0;
int lcnt = 1;
bool in_word = false;
int idx = 0;
// jump to label for first char
goto *(jmp_arr[(int)str[0]]);
// macro that increments index, sets variables for the next stage, and
// gotos the label indexed by the current character
#define next(c, lc, iw) cnt = (c); lcnt = (lc); in_word = (iw); idx++; goto *(jmp_arr[(int)str[idx-1]]);
int main(int argc, char** argv)
{
/* test string */
char* str = argv[1];
/* normally this would be done as a sort of partial evaluation, but i can't for example generate an optimized function at runtime in C */
void** jmp_arr;
jmp_arr = malloc(sizeof(char)*256);
int i;
for (i = 0; i < 256; i++)
{
switch ((char)i)
{
case '\n':
jmp_arr[i] = &&newline;
break;
case ' ':
jmp_arr[i] = &&whitespace;
break;
default:
jmp_arr[i] = &&character;
break;
}
}
// null character points to exit label
jmp_arr[0] = &&terminate;
int cnt = 0;
int lcnt = 1;
bool in_word = false;
int idx = 0;
// jump to label for first char
goto *(jmp_arr[(int)str[0]]);
OP, you don't handle whitespace, fool. Also, you know that switch internally builds its own jump table*, right? You're just manually building a jump table that you assign WITH ANOTHER JUMP TABLE. Look up Duff's Device if you really want to do what you're trying to do.
* Get of my back, L.A. Calculus
Name:
Anonymous2013-08-08 0:55
>>6
But the jump table is created in an initialization phase. If c wasn't crap, you could generate it at compile time and store it statically in the executable, like in lisp. But that doesn't stop you from doing it with a preprocessor.
Name:
Anonymous2013-08-08 1:06
>>6
The point is partially evaluating the part of the problem that is statically known. It's difficult to do this in C, (it would require piecing together machine code by hand, compiling and loading code from another program at runtime, or using C macros)
so I just did it in the same chunk of code.
And since it works, it quite obviously handles whitespace.
>>7
Yeah, I didn't feel like hacking that in, but the lisp version compiles the jump table into a function.
Name:
Anonymous2013-08-08 1:08
I'm still the only one with the parallel solution.
Name:
Anonymous2013-08-08 1:08
Copyright (C) All years. Richard Marx Stalin.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>;.
#include <stdio.h>
main(){
system("wc");
}
Name:
Anonymous2013-08-08 1:13
>>7
If C was like Lisp, it wouldn't be C, and you wouldn't be using it for your shootout. Furthermore, your program fails on anything nontrivial because it requires the tested data to be passed in with the arguments, instead of reading from a file or from stdin or something. This means that passing in large datasets is impossible, which means that it spectacularly fails when I try to benchmark it against any other solution.
>>5 >>15
>Write the fastest program that counts the number of words and lines in a string.
Name:
Anonymous2013-08-08 1:31
>>11
I don't think we are talking about the same thing, and I don't understand what reasoning you are using. Are you suggesting that I was suggesting that the input file would be compiled into the binary of wc?
Name:
Anonymous2013-08-08 1:41
>>19
You were suggesting that you want to do something like
The bit you missed is that the switch table already does that for you and allows better compiler optimization for the specific use case you're describing. I pointed that out. You complained that your favorite language could do this better, and complained that you couldn't do a 1:1 translation from your favorite language into C. I chided you for that, and pointed out at the same time a completely different issue, which is that the program you posted can't work on large datasets. This is a completely separate issue than your flawed attempt at optimization through jump tables.
It's not his program, and that's just an implementation detail, not a problem with the algorithm itself. I didn't feel like reading up on how to do file i/o in C because I have better things to do.
Also, no the input file should not be compiled into the binary. The point of the jump table is optimizing for the problem in a way significantly better than GCC will do with a simple switch table.
Name:
Anonymous2013-08-08 1:48
>>21 I didn't feel like reading up on how to do file i/o in C because I have better things to do
So you are obviously unfamiliar with C, but you choose to start a shootout thread by posting a C snippet? You're obviously not too busy to man fopen; man fgetc, because you're on /prog/ being defensive. I can understand starting a shootout thread, but why would you do so in a language you don't know when you clearly have written the program already in a language you DO know?
Name:
Anonymous2013-08-08 1:56
>>22
I felt like re-writing it in C, and the algorithm is intact. It's not really a big deal.
>>23
Sure, whatever. But you should know that as written the algorithm is just a hamfisted way of using Duff's Device, without any of the associated speed.
Name:
Anonymous2013-08-08 2:07
>>24
I don't see how it's related to Duff's Device at all.
The algorithm jumps through threaded code, like a direct-threaded forth interpreter.
The point still stands, that while c provides a switch statement, you cannot specify which of the implementations to use for the switch table. Some implementations provide faster access but with more memory usage. If you build the jump table yourself, you can use a design that will give you the best benefit for the application you have in mind. You can do better than the compiler at this level, because the compilers at this time aren't aware of your intent.
Furthermore, I'm not the writer of that lisp program you twat. Go back to reddit, where you can collect material on posters and ``chide'' them on irrelevant bullshit.
>>22,23
What is the matter with you? Is it really that satisfying to go online and try attacking the credibility of others? I'd rather you invest energy in contributing something insightful or original instead. You confuse familiarity with a set of standard functions with prowess.
>>17-18
sum is bugged for futures resolving on other CPUs so a fully parallel extension of this is broken right now. It should be alright as it is.
I could just produce the algorithm Steele talked about but that would be boring.
Name:
Anonymous2013-08-08 2:38
>>28
Oh, I didn't notice it was supposed to be a parallel algorithm. That's pretty cool then, state machines aren't parallel at all, so yours would win eventually.
>>27 Is it really that satisfying to go online and try attacking the credibility of others?
No, not really. But it is more irksome to see ignorant code go by unchallenged than it is to challenge it. I'd rather you invest energy in contributing something insightful or original instead.
And I suggest you go volunteer to spend your time curing world hunger. We are both wasting our time on /prog/ - don't pretend to have any kind of high ground. You confuse familiarity with a set of standard functions with prowess.
I do not. I simply note that unfamiliarity with such simple concepts as basic i/o precludes prowess, especially in a program ostensibly designed to be efficient.
>>29 Oh, I didn't notice it was supposed to be a parallel algorithm.
That's the bait.
It is parallel, but only where you see an @-sigil. As it is it just does line count and word counts separately, so I lied about the speed. A proper version would go deeper and would be faster for long enough strings.
Name:
Anonymous2013-08-08 2:56
>>30
I am familiar with i/o, I just don't use C often enough to remember how to do file i/o when I occasionally use it.
>>33
If you're reading byte-by-byte or if the maximum chunk size is too small to dispatch to another thread without overhead killing you. The latter is probably true on many systems, but if you can avoid copying Steele's algorithm is still faster.
>>38
That's what I mean: each chunk (not necessarily what the OS gives you) can be done in its own thread and counted/summed in log time, so read time isn't a problem if you can avoid copying after the initial read-in of any given substring. mmap works well here if you have an O(1) size operation.