Hmm... it seems to me that whenever any article is posted that claims "X is faster than C", there are immediately 40 replies saying "Well, the author's C is horrible. If I wrote that, it would be much different."
Okay, as someone who has NOT been programming in C 8 hours a day for years on end, I would actually like to see somebody do this -- to show me what GOOD C looks like.
So if someone wouldn't mind, could you take his C code and show me the improved version? This would really help me understand. (And I don't just mean an example where one line could be improved; I'm talking abou the whole thing.)
Ok, I pledge to re-write this properly and to benchmark the current implementation vs a nice one. I'll post the results. I need something to get my mind off things and this is as good as any. It will take at least until Monday (it is my sons birthday tomorrow).
Compiled with "gcc -pipe -Wall -O3 -fomit-frame-pointer -std=c99 -pthread" on my Mac, it's about twice as fast at the blog author's version.
Time spent:
coding: 30 minutes
bugfixing: 30 minutes
I have a feeling there is some kind of catch in the description of the algorithm in terms of implementing the output, but I for the life of me could not grok whether they wanted me to parse the entry into these three pieces or not...
EDIT to add: The only optimization I made was inlining the tightly-called "subst" function, did it without any profiling (so the optimization process literally took about 30 seconds:). Before inlining this version was still about 15% faster than the blog author's one.
Thank you! It was indeed a nice little fun exercise. It is interesting the bugs that I made by being tired and not reading the task carefully/not thinking clearly (yesterday was a bit of a long and stressy day):
1) My initial understanding was that I do need to reverse the order, yet somehow after re-reading the article I understood the order does not need to change, and the "reverse" in the name is some kind of jargon. This is quite stupid, and probably not worth mentioning, if only to prove I was tired :)
2) missing that the first iteration of the "business logic" code in my case happens before anything is filled in. Crash.
3) forgetting about the "\n"s - with rather funny "partially correct" output effect.
Ok, I looked at your code. What you really should do (before coding up the solution) is to look at the problem specification. Other than that I like the 'direct' approach, it isn't quite as fast as what I cooked up but yours is a lot shorter.
Thanks! yes, this goes to show the perils of coding after a 12h work day on Friday :-). This affected the use of fgets() I/O (I understood you have to call the line-buffered routines based on their description)
There already is an efficient multithreaded C version on the shootout site. I don't know if that's what people would consider good production code, but at least it isn't laughably bad.
On my 64-bit MBP, this program does not terminate - at least not within the 3 minutes I allowed it to run. (the blog article's one completes within 4 seconds, so I thought 60-fold slack is enough).
I know it works on Ubuntu 64-bit. :-) Just that it appears to be hanging on MacOS 64-bit. The algorithms like this one should hardly have such a catastrophic failure - that's why I am curious if someone else can replicate it hanging on MacOS.
BTW, on 8-core Ubuntu box with 32Gb RAM, my silly half-an-hour hack from yesterday - http://stdio.be/revseq.c - still outperforms this one and completes in 60% of time. So I am getting more and more convinced that either I did not get the spec right while writing it.. Or that I should submit it :-)
EDIT: If you have a chance to give it a whirl alongside, could be fun to compare your results with mine...
Okay, as someone who has NOT been programming in C 8 hours a day for years on end, I would actually like to see somebody do this -- to show me what GOOD C looks like.
So if someone wouldn't mind, could you take his C code and show me the improved version? This would really help me understand. (And I don't just mean an example where one line could be improved; I'm talking abou the whole thing.)