Any experienced coders that could help with a bit of optimization?

[pzt]

Hey guys, this may be a bit much to ask, but here goes nothing.

for one of my final assignments at uni we were asked to write a program to implement a memory management algorithm. Needless to say my program is working perfectly,
but also part of the assignment (our last chapter was on optimization) was the shortest most optimized code gets the best grade in the class.

My program as far as i know is pretty streamlined for what it does, but I was wondering if any of you guys could maybe look at it and see if I could cut back somewhere. Like for example I would like to get rid of some of the small methods like bestFit but I can't really figure out a way to so far that passes my test cases.

any help is greatly appreciated! (if not thats cool to i know it is alot of code to look over, just a little challenge i suppose)

If you dont wanna help just rage and ill take down the post, just looking for a few tips maybe that could help me shorten it.

import java.util.*;public class BuddySystem{	public static void execute(Memory memory, String[] processes){				ArrayList<Process> allProcesses = new ArrayList<Process>();		ArrayList<Integer> processMemory = new ArrayList<Integer>();		ArrayList<Integer> memoryTime = new ArrayList<Integer>();		allProcesses.add(new Process(0, 1024, false));		int processCount = 0;				//----------------------------------------------------------------------------------------------------------------------		//							first split up the strings and add them too the block object		//----------------------------------------------------------------------------------------------------------------------				for(int i = 0; i < processes.length; i++){			String [] splitProcess = processes[i].split(",");			processMemory.add(Integer.parseInt(splitProcess[0]));			memoryTime.add(Integer.parseInt(splitProcess[1]));		}							//----------------------------------------------------------------------------------------------------------------------		//											Execute the main while loop		//----------------------------------------------------------------------------------------------------------------------						while(!processMemory.isEmpty() || occupiedBlocksExist(allProcesses)){													//while pending requests / occupied blocks in memory								for(int i = 0; i < allProcesses.size(); i++){				if(allProcesses.get(i).getOccupied()){																			//if there is an occupied block					allProcesses.get(i).reduceTime();																			//decrease the time by 1					if(allProcesses.get(i).getTime() == 0){																		//if the occupied blocks time is 0						memory.deallocate(allProcesses.get(i).getProcess());													//remove the block						allProcesses.get(i).setOccupied(false);																	//that spot is no longer occupied						allProcesses.get(i).setProcess(0);																		//mark the process as 0 so we know its done						allProcesses = reAllocate(allProcesses);																//reallocate the memory to recreate larger blocks					}				}			}			for(int i = 0; i < processMemory.size(); i++){				int pendingRequest = processMemory.get(i), processTime = memoryTime.get(i);				int bestFit = bestFit(pendingRequest), startPosition = 0;				boolean canBeAllocated = false;								for(int x = 0; x < allProcesses.size(); x++){					if(allProcesses.get(x).getProcessMemory() >= bestFit && !allProcesses.get(x).getOccupied()){						canBeAllocated = true;						startPosition = x;						break;					}				}				if(canBeAllocated){					boolean availableHole = false;					while(!availableHole){						if(allProcesses.get(startPosition).getProcessMemory() == bestFit){							availableHole = true;							processCount++;							allProcesses.get(startPosition).setProcess(processCount);							allProcesses.get(startPosition).setTime(memoryTime.get(0));							allProcesses.get(startPosition).setOccupied(true);							int start = findStart(startPosition, allProcesses);							memory.allocate(processCount, processTime, start, bestFit);							processMemory.remove(0);																			//remove the process's memory from the beginning of the processMemory array list							memoryTime.remove(0);																				//remove the process's time from beginning of the memoryTime array list							i--;						}						else{							allProcesses.get(startPosition).setSize(allProcesses.get(startPosition).getProcessMemory()/2);							allProcesses.add(startPosition + 1, new Process(0, allProcesses.get(startPosition).getProcessMemory(), false));						}					}				}				else{					break;				}			}		}	}				//----------------------------------------------------------------------------------------------------------------------	//											Connect blocks back together not in use	//----------------------------------------------------------------------------------------------------------------------			public static ArrayList<Process>  reAllocate(ArrayList<Process> allBlocks){		for(int x = 0; x < allBlocks.size()-1; x++){			if(allBlocks.get(x).getProcessMemory() == allBlocks.get(x+1).getProcessMemory()){				if(!allBlocks.get(x).getOccupied() && !allBlocks.get(x+1).getOccupied()){					allBlocks.remove(x+1);					allBlocks.get(x).setSize(allBlocks.get(x).getProcessMemory()*2);					x = -1;				}				else{					x++;				}			}		}		return allBlocks;	}		//----------------------------------------------------------------------------------------------------------------------	//											Find out if there are occupied blocks	//----------------------------------------------------------------------------------------------------------------------		public static boolean occupiedBlocksExist(ArrayList<Process> occBlocks){		for(int x = 0; x < occBlocks.size(); x++){			if(occBlocks.get(x).getOccupied()){				return true;			}		}		return false;	}			//----------------------------------------------------------------------------------------------------------------------	//													Find the best fit	//----------------------------------------------------------------------------------------------------------------------		public static int bestFit(int processMemory){		int temp = 1024, minSize = 32;		int bestFit = 0;		while(temp >= minSize){			if( processMemory > temp/2){				bestFit = temp;				break;			}			else if( processMemory == temp/2){				bestFit = temp/2;				break;			}			else{				temp = temp/2;			}		}		return bestFit;	}		//----------------------------------------------------------------------------------------------------------------------	//										Figure out where to place the new block	//----------------------------------------------------------------------------------------------------------------------		public static int findStart(int location, ArrayList<Process> list){		int start = 0;		for(int x = 0; x < location; x++){			start += list.get(x).getProcessMemory();		}		return start;	}	}	class Process {		int trueValue, process, time;		boolean occupied;				public Process( int currentProcess, int processMemory, boolean isOccupied){			process = currentProcess;			trueValue = processMemory;			occupied = isOccupied;		}				void setOccupied(boolean occ){			occupied = occ;		}				boolean getOccupied(){			return occupied;		}				int getProcessMemory(){			return trueValue;		}				void setSize(int processMemory){			trueValue = processMemory;		}				int getProcess(){			return process;		}				void setProcess(int incomingProcess){			process = incomingProcess;		}				void reduceTime(){			time--;		}				int getTime(){			return time;		}				void setTime(int memoryTime){			time = memoryTime;		}	}

thanks again for any help!

[Vitalius]

I'd love to know enough about this to help you, but sadly, I don't. However, I think Glenwing may be able to, if he feels like it.

[pzt]

Hey thanks for the response! and no worries, I know its a big bite of code, most people may not have time to look over, but thought maybe if i could actually cut it down i might win

[WanderingFool]

Well the shortest doesn't always mean most optimized (of course it can...but there are sometimes optimizations that require more complex code to save time later).

 

Anyways, there really is a lot to read through...so on a quick read through I can mention a few things:

1) Initializing variables inside loops.  While compilers could optimize the code, it is not always guaranteed. 

for(int i = 0;....for(int i = 0;....

What a compiler _might_ do is create room twice, for the variable i....again this could depend on the compiler though....same can be said about variables inside any loops though, as they might add a slight processing of each new "instance"....which that said any decent compiler would prevent that from happening.

 

2) In the strictest definition ++i is faster than i++, but again even a horrible compiler should optimize it. (Just something to keep an eye on...if all optimizations by the compiler are turned off then ++i is faster than i++)

 

3) Your best fit function...I haven't read too carefully but depending how many times the loop is run it could be optimized more (There is overhead to do this optimization...not sure how much).

	public static int bestFit(int processMemory){		int temp = 1024, minSize = 32;		int bestFit = 0;                int tempCompare = temp * 0.5; //In theory 0.5 * val is quicker than val / 2 but the compiler usually optimizes it though		while(temp >= minSize){			if( processMemory > tempCompare){ //We are almost neutral...only cost extra is the creation of tempCompare				bestFit = temp;				break;			}			else if( processMemory == tempCompare){				bestFit = tempCompare;				break;			}			else{				temp = temp/2;                                tempCompare = temp * 0.5; //I can't recall how slow assignments are...but 1 extra assignment.  The extra addition here gets cancelled out by the first if statement compare, so assuming an assignment takes less time than division then this should be faster.			}		}		return bestFit;	}

4) The only other thought I have is when you used x = -1; x--; would seem more efficient (although again compiler optimizations should fix it for you)

[MrSuperb]

public static int bestFit(int processMemory){

int temp = 1024, minSize = 32;

while(temp >= minSize){

temp = temp/2;

if( processMemory > temp){

return temp * 2;

}

else if( processMemory == temp){

return temp;

}

}

return 0;

}

[MrSuperb]

public static int bestFit(int processMemory){		int temp = 512, minSize = 32;		while(processMemory <= temp || temp < minSize)  temp = temp/2;		return temp * 2 ;}

this should work aswell

[laxer]

Well the shortest doesn't always mean most optimized (of course it can...but there are sometimes optimizations that require more complex code to save time later).

 

I have to agree, code length is never a good indicator of code quality.

 

Honestly, if I were you: Write the cleanest easiest to understand code and let the compiler do all the work optimizing.

 

What are you using to compile Javac/GCJ? Give yourself a good read on compilers: http://www.excelsior-usa.com/jetcs00007.html, http://stackoverflow.com/questions/1503479/how-to-see-jit-compiled-code-in-jvm, etc

 

Even the best optimized code will give minimal improvement. If there is big improvement to have it is going to be through algorithm optimization not code optimization.

 

With that said, your algorithms are not very complex with the worst as far as I can see being < O(n^2)

 

What hardware will the tests be ran on? You may gain performance by compiling for that specific hardware. (Read up on: http://en.wikipedia.org/wiki/Just-in-time_compilation)

 

Honestly, if you want faster code forget java and go with something that is not emulated... IE C or some variant there of. (I know not possible at this point but, just a good thing to keep in mind)

 

Sorry I am not too knowledgeable in Java or the compilers for it. The last course I took that asked for java was some 3 years ago. Now days all my profs want code in C/C#/C++/Python/Perl/Haskel/PHP or whatever they fancy at the time of the assignment.

 

I might be able to give you a more detailed answer in a few days but, like you I have finals this week and a lack of time. (It'll probably be too late at that point but, thought I would offer)