?

Log in

No account? Create an account
brad's life [entries|archive|friends|userinfo]
Brad Fitzpatrick

[ website | bradfitz.com ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

bowling statistics [Dec. 17th, 2000|07:51 pm]
Brad Fitzpatrick
[Tags|, ]

I knew this program I'm writing would take a ton of CPU, but I guess I didn't think realize how much it. What I'm doing is calculating bowling statistics over all possible games. Last time I went bowling I got it in my head to do this and I can't stop thinking about what the three-dimensional graph of [x=balls thrown, y=score, z=occurences] must look like.

I wrote it in Perl initially but it was way too slow so I rewrote it in C. In C it takes 43 seconds to compute the incredible small subset of the larger problem... in Perl that same subset takes 4 minutes and 10 seconds. Stupid Perl. :-)

If I disable the prints to stdout, the time of the C program drops to 10 seconds. On Kenny (the P3-933) it runs in 4 seconds.

Solving the entire problem is going to take approximately (50**6) times longer because right now I'm running it assuming only 4 frame game.

I need to think of way of a new way to solve the problem by breaking the game up into separate parts which don't interfere with the rest of the game (i.e. sets of open frames following an open frame).

Or, I need to make the program start at arbitrary points and run it on all four computers in here while I sleep. That's kinda hard to do right now because of how it's written (using recursion) ... An iterative solution might be faster, and more easily parallelizable, but it's harder to think about.

I guess I'll graph what I have so far, and then think about this later.

Also, I decided to use glib for the C port, but I don't like it much ... g_list_append appears to be O(n). But then again, so is strcat .... :-/
LinkReply

Comments:
[User Picture]From: jurann
2000-12-20 03:37 pm (UTC)

Re: g_list_append

Word of advice from the field: "Standard Library" means "Made for Idiots with Room For Mistakes". In the industry, if you need some library to work a certain way, it's usually not very tough to write it in a simple, efficient manner, just make sure there are no possibilities of data error. Error checking is the biggest cause for slowdown in stdlibs... And they wouldn't really be standard without it. General rule of thumb: if you need it done right, right away, best do it yourself unless you know of a library that does it EXACTLY the way you want already. Since that's a rarity, it's best to just optimize your own routines for getting stuff done. Yeah, it's boring, yeah, it's simplistic, but yeah, it's damn effective.

BTW - Sorry to hear about your trouble with Perl, the program shouldn't be running that slowly IMHO. Worst case scenario I've seen Perl run at about 50% the speed of a compiled C program unless the Perl code was not written with speed optimization in mind, or some dynamic of the Perl interpreter was left out of (or left in) the coding. Making fast Perl code pretty much requires sleeping with the demon, but she's good in bed and you'll be happy to come back to her. ;) I do almost all of my development in Perl these days, it's just one of the best trade-offs of development speed to execution speed. And you can do some loopy stuff with Perl! Anyway, I'm praising too much, so I'll go now. Good luck with your project. =)
(Reply) (Parent) (Thread)
[User Picture]From: bradfitz
2000-12-20 11:37 pm (UTC)

Re: g_list_append

I do 99.4% of my development in Perl lately too....

The particular program I was writing I knew Perl would suck at... it was just math in loops.

(Reply) (Parent) (Thread)
[User Picture]From: jurann
2000-12-21 01:09 pm (UTC)

Re: g_list_append

Awesome, Perl rules.

Too true about the math loops, Perl's not very handy for pure-math applications since it treats all variables as strings internally, and math work in Perl requires a little extra process overhead (well, exponentially more depending on the size of your loops) to handle them effectively. Blah. C makes sense, it makes perfect sense.

So what's with this BML stuff LJ uses? I never heard of it until yesterday, when my boss and I looked it up on Google based on the file extensions on LJ. Interesting, I was responsible for a similar project at CourtLink which we termed the "token-parser". That project was 100% Perl, and was damnfast in mod_perl on Apache. But how does BML link into the webserver? Is it an API, module, Perl script, eh? I'm asking to make conversation and because I'm too lazy right now to look it all up. Plus it gives you a chance to be witty and say stuff. =) Thanks!
(Reply) (Parent) (Thread)
[User Picture]From: bradfitz
2000-12-21 05:01 pm (UTC)

Re: g_list_append

http://www.bradfitz.com/bml/

Uses Apache's Action directive... running as a set of FastCGI processes now...
(Reply) (Parent) (Thread)