5 Replies - 9034 Views - Last Post: 09 October 2012 - 07:03 AM

#1 Kakerergodt  Icon User is offline

  • D.I.C Head

Reputation: 87
  • View blog
  • Posts: 201
  • Joined: 01-May 12

Question regarding optimization of code

Posted 23 August 2012 - 10:58 AM

I've just started on a course, where, among the subjects discussed is optimization of code/algorithms.
We've started out easy by optimizing a bit of code to find the highest number in an array, one of the most efficient(but "ugliest") way to do it was to use a sentinel so as to avoid the comparison test in the for-loop.

I tried optimizing the code on my own and found that this code snippet:
	
public static int max(int[] a)
	{
		int m = 0;
		int maxvalue = a[m];

		try
		{
			for(int i = 1; ;i++)
			{
				if(a[i] > maxvalue)
				{
					m = i;
					maxvalue = a[m];
				}
			}
		}
		catch(ArrayIndexOutOfBoundsException e){}
		return m;
	}


..were nearly as fast as the fastest my professor demonstrated in the lecture, only much more "readable".
What I'm wondering is, is it "bad" form to use a try/catch block in this way? Not intending it to catch something that might go wrong, but catching something that is expected to go wrong every time the code is run, for the sake of efficiency.

Is This A Good Question/Topic? 0
  • +

Replies To: Question regarding optimization of code

#2 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1155
  • View blog
  • Posts: 2,534
  • Joined: 05-May 05

Re: Question regarding optimization of code

Posted 23 August 2012 - 12:03 PM

I think that's a bad practice, and should probably be avoided if the speed up isn't significant. If the array was expected to be really big (where an extra 1 or 2 byte code instructions per conditional check would make a difference) and your trying to squeeze every last bit of performance out the code, then perhaps it's not such a bad idea. After all, the point is make things faster.
Was This Post Helpful? 0
  • +
  • -

#3 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7803
  • View blog
  • Posts: 13,197
  • Joined: 19-March 11

Re: Question regarding optimization of code

Posted 16 September 2012 - 08:40 PM

Missed this when it was originally posted, but there are two ways of looking at the question.
From a style standpoint, it's ugly. It's a non-standard usage that forces the person maintaining the code to stop and think about the implications, meaning it costs time (= money) every time someone has to look at it. That's bad - developer time is usually more expensive, all things considered, than running time. Optimizing for speed over readability is usually a bad bet.

From a speed standpoint, it looks like this might be a slight win in huge loops that do very little - this is based on some quick tests I've run. These tests are probably not the most informative, it's just something I threw together when I saw this questions. Code is below in the spoiler tags.

Basically, the "without comparison" thread generally outperformed the "with comparison" thread by about 20% on my machine - except when sometimes the "with" thread outperformed it by 50%. I don't know why that is, it happened maybe once in ten runs.

That performance gain - 20%! - is probably going to be completely swamped as soon as you put any actual code in those loops, though. Conditional evaluations are pretty cheap, all in all.
Then you have to remember that you're creating an Exception object each time you hit the end of that array in your optimized version. That takes time, too, but not a lot - about a microsecond on my machine, and you're only doing it once per loop, so that's going to fall right out of the calculations.

So all in all, it looks to me like this optimization is a bit of a wash. It might save some trivial amount of time, but it'll cost you in the long run, in time and in increased number of bugs. But yes, it will probably save some real and calculable amount of time.


The test code for loops with and without comparison, if anyone wants to kibbitz it:

Spoiler

Was This Post Helpful? 1
  • +
  • -

#4 rfs02  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 26
  • View blog
  • Posts: 70
  • Joined: 30-September 12

Re: Question regarding optimization of code

Posted 05 October 2012 - 12:48 PM

From my test (code below), checking for length is actually much faster than using a try/catch. Let me know what the results are on your machine.

public class FindMax {
	
	public static void main(String[] args) {
		
		int values[] = { 1, 4, 5, 9, 10, 5, 4 };
		long startTime = System.currentTimeMillis();
		
		for (int i=0; i<100000; i++)
			maxNoTry(values);
		
		long noTryTimestamp = System.currentTimeMillis();
		
		for (int i=0; i<100000; i++)
			max(values);
				
		long endTime = System.currentTimeMillis();
		
		System.out.println("  No try/catch: " + (noTryTimestamp - startTime));
		System.out.println("With try/catch: " + (endTime -noTryTimestamp));
	}
	
	
	public static int max(int[] a)
	{
		int m = 0;
		int maxvalue = a[m];

		try
		{
			for(int i = 1; ;i++)
			{
				if(a[i] > maxvalue)
				{
					m = i;
					maxvalue = a[m];
				}
			}
		}
		catch(ArrayIndexOutOfBoundsException e){}
		return m;
	}

	public static int maxNoTry(int[] a)
	{
		int m = 0;
		int maxvalue = a[m];

		for(int i = 1; i < a.length;i++)
		{
			if(a[i] > maxvalue)
			{
				m = i;
				maxvalue = a[m];
			}
		}

		return m;		
	}
}


Was This Post Helpful? 0
  • +
  • -

#5 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1400
  • View blog
  • Posts: 3,108
  • Joined: 05-April 11

Re: Question regarding optimization of code

Posted 09 October 2012 - 06:04 AM

View Postrfs02, on 05 October 2012 - 07:48 PM, said:

From my test (code below), checking for length is actually much faster than using a try/catch. Let me know what the results are on your machine.

public class FindMax {
	
	public static void main(String[] args) {
		
		int values[] = { 1, 4, 5, 9, 10, 5, 4 };
		long startTime = System.currentTimeMillis();
		
		for (int i=0; i<100000; i++)
			maxNoTry(values);
		
		long noTryTimestamp = System.currentTimeMillis();
		
		for (int i=0; i<100000; i++)
			max(values);
				
		long endTime = System.currentTimeMillis();
		
		System.out.println("  No try/catch: " + (noTryTimestamp - startTime));
		System.out.println("With try/catch: " + (endTime -noTryTimestamp));
	}
	
	
	public static int max(int[] a)
	{
		int m = 0;
		int maxvalue = a[m];

		try
		{
			for(int i = 1; ;i++)
			{
				if(a[i] > maxvalue)
				{
					m = i;
					maxvalue = a[m];
				}
			}
		}
		catch(ArrayIndexOutOfBoundsException e){}
		return m;
	}

	public static int maxNoTry(int[] a)
	{
		int m = 0;
		int maxvalue = a[m];

		for(int i = 1; i < a.length;i++)
		{
			if(a[i] > maxvalue)
			{
				m = i;
				maxvalue = a[m];
			}
		}

		return m;		
	}
}



If you increase the size of the array, then the example with try-catch should be a little faster I think :)
Was This Post Helpful? 0
  • +
  • -

#6 rfs02  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 26
  • View blog
  • Posts: 70
  • Joined: 30-September 12

Re: Question regarding optimization of code

Posted 09 October 2012 - 07:03 AM

Actually.. I did some additional testing, and you are right - the breakeven (on my computer) is when the string length is around 50k chars.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1