Weird runtime behavior

Announcements, comments, ideas, feedback, and "How do I... ?" questions
Post Reply
aginis
Posts: 2
Joined: Sat Dec 31, 2011 6:25 pm

Weird runtime behavior

Post by aginis » Sat Mar 31, 2012 11:43 am

I've noticed a weird behavior when i run my solutions:
if i run the solution twice in a row the second run is much faster.
I assume this is due to some sort of caching, can anyone explain it to me?

which time should i use when timing my solutions?
Thanks!

ldesnogu
Posts: 17
Joined: Wed Jan 11, 2012 10:04 am

Re: Weird runtime behavior

Post by ldesnogu » Sat Mar 31, 2012 11:58 am

aginis wrote:I've noticed a weird behavior when i run my solutions:
if i run the solution twice in a row the second run is much faster.
I assume this is due to some sort of caching, can anyone explain it to me?
If you use an interpreted language (Python for instance) then the time to load the interpreter in the second run would be close to 0 under any well-behaved OS thanks to caching as you correctly guessed. But I'd expect the difference to be rather small and certainly much less than 1s.
which time should i use when timing my solutions?
I'd say you can keep the fastest, but any way the difference should not be that large unless your program is so fast that any way you're well below the one minute threshold.
Image

aginis
Posts: 2
Joined: Sat Dec 31, 2011 6:25 pm

Re: Weird runtime behavior

Post by aginis » Sat Mar 31, 2012 1:46 pm

Got it Thanks!

User avatar
kenbrooker
Posts: 129
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Weird runtime behavior

Post by kenbrooker » Tue Jan 22, 2019 6:45 am

I've noticed from time to time in the past that my RunTimes have counterintuitively increased rather than decreased.
In checking out the RoseCode WebSite, via their Problem #1, I have experienced it again and,
even in this very simple, straightforward example, I can't figure out -- Why?

Here's the (self-explanatory?) Java code for a first, totally naive algorithm with
Median RunTime = 0.57 Secs with the
Median in Range 0.562 to 0.578 --

Code: Select all

/*
Problem #1

Find a Prime 

Prime numbers are numbers that are only divisible by 1 and themselves. 
The first prime number is 2. 
The 10000th is 104729.

Find the 78200th prime number.
--------------------------------------------------------------------------------------------------------------------
OUTPUT:

   p = 995909

RunTime = 0.57 Secs (Median in Range 0.562 to 0.578) 
--------------------------------------------------------------------------------------------------------------------
*/
			
class aRoseCode1Proc
{
	boolean IsPrime(int i)
	{
		if(i < 2) return false;
		if(i == 2) return true;
		else if(i % 2 == 0) return false;

		boolean	prime = true;

		for(int j = 3; j <= Math.sqrt(i); j=j+2)	//3 & 5 & 7 fall through!
			if (i % j == 0) prime = false; 		

		return prime;			
	}
}

class aRoseCode1		 		
{
public static void main(String args [ ])
{
	double start = System.currentTimeMillis();

	System.out.println();

	aRoseCode1Proc IP = new aRoseCode1Proc();

	int count = 0;

	for(int p = 2; p <= 1000000; p++)
	{
		if(IP.IsPrime(p)) count++;
		
		if(count == 78200)
		{
System.out.println("   p = " +p);
			break;
		}
	}
System.out.println();
	
	double finish = System.currentTimeMillis();
System.out.println("RunTime = " + (finish - start)/1000 + " Secs");					
} 
}
And here's the "All New and Improved" code wherein all I changed, expecting a speedup,
was to limit the main for-loop to odd numbers, cutting the domain in half, and
limiting the IsPrime function accordingly, expecting a speedup, but the
Median RunTime = 0.615 Secs with the
Median in Range 0.609 to 0.625 --

Code: Select all

/*
Problem #1

Find a Prime 

Prime numbers are numbers that are only divisible by 1 and themselves. 
The first prime number is 2. 
The 10000th is 104729.

Find the 78200th prime number.
--------------------------------------------------------------------------------------------------------------------
OUTPUT:

   p = 995909

RunTime = 0.615 Secs (Median in Range 0.609 to 0.625)  
--------------------------------------------------------------------------------------------------------------------
*/
			
class aRoseCode1bProc
{
	boolean IsPrime(int i)
	{
		//if(i < 2) return false;
		//if(i == 2) return true;
		//else if(i % 2 == 0) return false;

		boolean	prime = true;

		for(int j = 3; j <= Math.sqrt(i); j += 2)	//3 & 5 & 7 fall through!
			if (i % j == 0) prime = false; 		

		return prime;			
	}
}

class aRoseCode1b		 		
{
public static void main(String args [ ])
{
	double start = System.currentTimeMillis();

	System.out.println();

	aRoseCode1bProc IP = new aRoseCode1bProc();

	int count = 1;			//for 2 prime

	for(int p = 3; p <= 1000000; p += 2)
	{
		if(IP.IsPrime(p)) count++;
		
		if(count == 78200)
		{
System.out.println("   p = " +p);
			break;
		}
	}
System.out.println();
	
	double finish = System.currentTimeMillis();
System.out.println("RunTime = " + (finish - start)/1000 + " Secs");					
} 
}
This RunTime degradation is "patently absurd" behavior*** to me so,
as especially true when thinking like that...
I stand to learn a lot!

*** "behaviour" beyond our proposed
"American" Walls...
Last edited by kenbrooker on Wed Jan 23, 2019 11:20 am, edited 1 time in total.
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

LilStalker
Posts: 64
Joined: Thu Nov 03, 2016 4:32 pm

Re: Weird runtime behavior

Post by LilStalker » Tue Jan 22, 2019 12:40 pm

Such low discrepancies dont matter much. It depends on whether how much computing power your computer is allowing the program to have during running. Sometimes it will not have the maximum possible computing power and it will cause a bit higher running time.

Test the program on higher inputs, for example inputs where program will need 10 minutes, 60 minutes and so on. As long as you dont do other computationaly intensive stuff on computer meanwhile, the results will be very close.
Image

User avatar
kenbrooker
Posts: 129
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Weird runtime behavior

Post by kenbrooker » Tue Jan 22, 2019 6:13 pm

Thanks LilStalker...

I agree the discrepancies are small but they are still in the Dead Wrong Direction to my way of thinking...

As you suggest I will try longer runtimes, possibly requiring BigInteger...
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

User avatar
rayfil
Administrator
Posts: 1403
Joined: Sun Mar 26, 2006 4:30 am
Location: Ontario, Canada
Contact:

Re: Weird runtime behavior

Post by rayfil » Wed Jan 23, 2019 3:06 am

As LilStalker pointed out, the timing differences should not be considered significant. And:
with the "else if(i % 2 == 0) return false;" instruction in your IsPrime function, you were disregarding further processing of all even numbers anyway. (BTW, that instruction becomes redundant in your 'improved' version.)

You must also realize that modern computers are multi-tasking (as compared to the old ones such as the Commodore where individual programs would have the entire CPU to themselves until exit). Modern computers with operating systems such as Windows also get loaded more and more with bloated programs which tend to keep running in the background, such as AV software. This switching back and forth will take increasing amounts of the system's time and would effectively increase processing times to solve a math problem on any given computer when comparing results over the years.
When you assume something, you risk being wrong half the time.

User avatar
kenbrooker
Posts: 129
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Weird runtime behavior

Post by kenbrooker » Wed Jan 23, 2019 7:11 am

Thanks! rayfil...

"Assuming" I understand you right:

1) In the "Original" algorithm I was disregarding further processing of all even numbers, but only at the expense of first executing "else if(i % 2 == 0) return false;" for every even number, which, though relatively quick, I'm sure (You are way better at Assembly Language and Registers and Such than I am...), does take some, cumulative time, i.e. can not be executed in zero time; and,

2) I agree with you about that "else if" statement being redundant in my "Improved" version and that's why I commented it out, via "//" in Java, which isn't every language's way of designating a comment and maybe it would have been more clear (though only by "invisibility") if I had simply deleted the statement...

YIKES! There's gotta be a shorter way of saying all of the above and I thank you and LilStalker for explaining how multi-tasking and background processing can affect runtimes... This is clearly evidenced in the range of runtimes I get for each of the two versions, though with the ranges well-behavedly identical in magnitude AND, Importantly to me,
1) it isn't as if the ranges ever overlap at all; 2) the relative difference between medians is "small," but not percentage-wise (~8%); and 3) the "Original" version outperforms the "Improved" version every single time, even though I count significantly fewer "executions" (You would know a better word...) in the"Improved" version, especially thanks to not wasting any time at all on even numbers, which is the mathematical equivalent of cutting the domain in half...

To clarify, I'm not at all concerned that runtimes vary within some range; I'm only concerned about the difference in the median runtimes and, especially, the direction of that difference, i.e. Who's fastest?

For what it's worth, as LilStalker suggested, I am going to try the comparison with some longer runtimes and, to tell you the truth, I'll be left wondering either way -- If the "Original" continues to outperform the "Improved" (Why?!) OR
If at some longer runtime the "Improved" is in fact an... Improvement (and Why the switch, as a function of runtime?!)

ps - As Kurt Godel might ask -- Is "When you assume something, you risk being wrong half the time" an... Assumption?
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

User avatar
kenbrooker
Posts: 129
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Weird runtime behavior

Post by kenbrooker » Thu Jan 24, 2019 4:28 am

Final (Anti-Climactic) Report:

The "Original" and "Improved" codes find the 10 millionth prime number (179,424,673) in
3,929 and 3,928 seconds, respectively; so, at least the
"All New and Improved" code is not slower(!!) but,
it's not exactly "Improved" either; and,
still being surprised only shows
my ignorance... :(
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

Post Reply