Thursday, January 05, 2006

A cry for help.

I need to improve the performance of my computation of the empirical distribution function. It is so deadly slow that, by my computations, the simulations I am currently running will take around 5 years to complete. I am programming in Fortran 90, and my edf subroutine (for scalar-valued arguments) looks something like this:

function edf_s(t,x)
! data in x, t is scalar
real(kind=8), dimension(:), intent(in) :: x
real(kind=8), intent(in) :: t
real(kind=8) :: edf_s
integer :: n,m,i

m = size(x)
edf_s = count(x<=t)/dble(m)

end function edf_s
Any ideas? I compute values of the edf probably close to a million times for each iteration in my simulation (I'm bootstrapping).

Google has failed me. I can't remember the last time that happened.

Update: Ha, ha, ha, ha! Guess what! This routine is just fine. Each iteration (at the smallest sample size, mind you) calls it not a million times, but a frickin' 740 million times! Conclusion: the problem is elsewhere. I now return you to your normally scheduled blogreading.

Update 2: Moving from the function as it appears above to a lookup table has taken the time required for one iteration from 228 s to 13 s. That's considerable improvement, but still very slow. I'm still working on it: thanks for all the useful suggestions y'all have made in the comments and via email.

8 comments:

Liz Miller said...

Yay!!!

Angry Professor said...

Well, not yay. I reduced the number of function calls to 250 million, but that's still mind-bogglingly high. I'm trying something completely different, that will probably chew up my entire day and fail at the end. Grr.

Anonymous said...

The problem may not only be elsewhere -- do you have any timings on calls to this function?

I wrote the equivalent routine in matlab:

function y = edf_s(t,x);

y = sum(x <= t)/length(x);

and, with x of length 1000 it would take about 14 hours to call 740 million times on my powerbook. Could count be a really inefficient routine?

I am probably not the first person to suggest this to you, but you might really want to look in to Matlab. So much easier to write, debug and profile!

Cheers.

ps - I have always thought that statistics is just adding and dividing.

Angry Professor said...

anonymous, I did time the function. It's very, very fast. Because matlab is an interpreted language, it can never be as fast as fortran, which is optimized for these kinds of numerical problems. I used to do everything in matlab, and I went back to fortran.

I've reprogrammed the calling routine to use a lookup table. I'll let you know how it goes.

Angry Professor said...

travis, thanks for all your good thoughts. Because the table keys are ordered and because the values of t to be searched are also ordered, I don't actually have to search at all, but just increment the key index every so often.

I started to do the (ordered) table as a binary search, but realized that if I attacked the table with the ordered values of t then that was unnecessary.

I'm not sure how to speed things up any further, but it would be nice to see each iteration down around 1-2 s. I think that's a pipe dream, though.

Anonymous said...

holy crap my mind exploded

Anonymous said...

Are you still looking for suggestions on this?

Angry Professor said...

Always. Sorry I was out of town when your comment was posted.