CSC352 Homework 2 2013 Solution

--D. Thiebaut (talk) 15:07, 4 October 2013 (EDT)

---

Source Code

Main Applet

/*
 * MainAppletThreaded.java  
 * D. Thiebaut
 * 
 * Packing rectangles.
 * This applet attempts to pack a collection of rectangles into a large 
 * rectangle of area mainW x mainH.
 * In this very crude implementation, the original collection of rectangles
 * to pack is in rectsToPlace of type RectangleCollection1.  This object simply
 * creates a collection of random rectangles which it sorts by area, the largest
 * first, the smallest last. 
 * When this applet is run in its current form, it first displays it displays a blank window.
 * Every time the user presses Enter, a new rectangle is taken from the collection and
 * positioned (if possible ) on the screen.   It takes a lot of clicking on ENTER to pack
 * the window.
 * A better approach is to call keyPressed() in draw() (which is currently commented out).
 * This way a rectangle is added every time draw() is called: much faster.  But still not
 * as fast as we might want to go.  The solution is to do something like what is in Homework 2!
 */
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Random;
import java.util.concurrent.ConcurrentLinkedQueue;

import processing.core.PApplet;



public class MainAppletThreaded extends PApplet {
	static boolean firstTime = true;
	LineSet lines = null;
	int N	  = 20000; 			// number of rectangles to pack
	int mainW = 1200;
	int mainH = 1000;
	long longMainW = mainW;
	long longMainH = mainH;
	float scaleFactor = 1.0f;
	final int border = 25;
	final int rectColor = 0xFFA069D6;
	final int rectOutline = 0xFF000000;
	final int bigRectColor = 0xFFBFB730;
	long startTime, endTime;
	
	ArrayList<Rectangle> placedRects = null;
	RectangleCollection2 rectsToPlace = null;
	boolean debug = false;
	ConcurrentLinkedQueue<Rectangle> queue = null;  
	
	public void setup() {
		//--- define the geometry of the applet window ---
		size(mainW + 2 * border, mainH + 2 * border);
		smooth();
		
		//--- create the queue for communication with thread ---
		queue = new ConcurrentLinkedQueue<Rectangle>();
		
		//--- create N random rectangles ---
		placedRects = new ArrayList<Rectangle>();
		rectsToPlace = new RectangleCollection2();		
		ArrayList<Integer> geometry = rectsToPlace.initRandomAndSetGeometry( N );
		
		//--- define geometry of the "real" large rectangle to pack.
		longMainW = geometry.get( 0 );
		longMainH = (long) ( geometry.get( 1 ) * 1.03f); // allow for 3% inefficiency
		scaleFactor = Math.min( ( 1.0f / longMainW ) * mainW, ( 1.0f / longMainH ) * mainH );
		scaleFactor = scaleFactor / 1.1f / 1.1f;

		PackingThread2 thread = new PackingThread2( queue, longMainW, longMainH, rectsToPlace );
		//lines = thread.getLines();   // this is just if we are interested in drawing the lines at some point...
		thread.start();
		frameRate(20);
		startTime = System.currentTimeMillis();
	}

	public void draw() {

		if ( queue.isEmpty() )
			return;
		
		//pushMatrix();
		translate(border, border);
		scale( scaleFactor );
		
		//--- display frame the very first time----
		if ( firstTime ) {
			background( 0xffffffff );
			fill( bigRectColor );
			stroke( bigRectColor );
			rect(0, 0, longMainW, longMainH);
			firstTime = false;
		}

		//--- set drawing attributes ---
		fill( rectColor );
		stroke( rectOutline );
		this.strokeWeight(3);

		while ( ! queue.isEmpty() ) {
			Rectangle r = queue.poll();
			placedRects.add( r );
			r.draw( this );
		}
				
		//popMatrix();
		
		//--- display some status information at the top of the frame ---
		stroke( 0xffffffff );		 // all white
		fill( 0xffffffff );
		rect( 0, 0, 400, border-1 ); // erase previous caption
		fill( 0xff000000 );  // black text
		text( String.format( "%d/%d --  %s", 
				placedRects.size(),	N, timeFormat( System.currentTimeMillis()-startTime ) ), 
			  border, border/2 );
	}

	private String timeFormat(long l) {
		if ( l < 1000 ) return String.format( "0.%03d sec", l );
		int s 	= (int) ( l / 1000 );
		int ms 	= ( int ) ( l % 1000 );
		int m 	= (int) ( s / 60 );
		if ( m == 0 )
			return String.format( "%02d.%03d sec", s, ms );
		s 		= (int) ( s % 60 );		
		return String.format( "%02d:%02d.%03d min", m, s, ms );
	}

	public void keyPressed() {
		System.out.println( "Keypressed not implemented..." );
		if ( key=='+' || key =='=' ) 
			scaleFactor = scaleFactor * 1.10f;
		if ( key=='-' || key =='_' ) 
			scaleFactor = scaleFactor / 1.10f;
	}

}

Thread

/**
 * PackingThread2
 * D. Thiebaut
 * This thread uses Packer to packs as fast as it can, in a while loop,
 * all the rectangles in a RectangleCollection. 
 * It enqueues them all in a nonblocking queue that is read by the draw()
 * thread, which draws the rectangles on the applet.
 * 
 */
import java.util.Iterator;
import java.util.concurrent.ConcurrentLinkedQueue;

public class PackingThread2 extends Thread {
	ConcurrentLinkedQueue<Rectangle> queue = new ConcurrentLinkedQueue<Rectangle>();
	RectangleCollection2 rectsToPlace;
	Packer packer = null;
	Iterator<Rectangle> it;
	
	/**
	 * The thread.  When it starts, it is give the queue to communicate with the applet
	 * draw() function
	 * @param queue: the concurrentLinkedQueue
	 * @param mainW: the width of the applet (will be passed to Packer)
	 * @param mainH: the height of the applet
	 * @param rectsToPlace: the collection of rectangles to place
	 */
	PackingThread2( ConcurrentLinkedQueue<Rectangle> queue, int mainW, int mainH,
					RectangleCollection2 rectsToPlace ) {
		this.queue = queue;	
		this.rectsToPlace = rectsToPlace;
		packer =  new Packer(mainW, mainH);
		
	}
	
	/**
	 * The thread.  When it starts, it is give the queue to communicate with the applet
	 * draw() function
	 * @param queue: the concurrentLinkedQueue
	 * @param mainW: the width of the applet (will be passed to Packer)
	 * @param mainH: the height of the applet
	 * @param rectsToPlace: the collection of rectangles to place
	 */
	public PackingThread2(ConcurrentLinkedQueue<Rectangle> queue,
			long longMainW, long longMainH, RectangleCollection2 rectsToPlace ) {
		this.queue = queue;	
		this.rectsToPlace = rectsToPlace;
		packer =  new Packer(longMainW, longMainH);	
	}

	/**
	 * run(): takes all the rectangles one by one, passes them to packer, and if they can be
	 * packed, enqueues them in the queue to pass to draw()
	 */
	public void run() {
		it = rectsToPlace.iterator();
		while ( it.hasNext() ) {
			//--- get a new rectangle from the collection.  The next largest in the collection ---
			Rectangle rectangle = it.next();
			
			//--- if none is returned, we're done packing ---
			if (rectangle == null)
				break;
	
			//--- if packer can pack it, it will set its coordinates to the correct location where   ---
			//--- it should go.  We keep track of it in placedRects.  Otherwise it will return false.---
			if (packer.pack(rectangle) )
				queue.add( rectangle );
		}
	}

	/**
	 * pass the lines back to the applet so that they can be displayed along with the rectangles
	 * @return
	 */
	public LineSet getLines() {
		return packer.lines;
	}
}

Question 1

When the number of rectangles is small enough, the rectangles and the queue can both fit in the heap without any trouble. When the number of rectangles becomes large, however, the heap may run out of space. In this case you have to allocate more heap space to your application. In Eclipse, this is done by going into the Run Configurations menu for your applet, click on the (x)= Argument tab, and in the VM argument box, enter a couple switches of the form:

     -Xms1g -Xmx2g

Here the switches represent the following quantities:

• -Xms<size> set initial Java heap size
• -Xmx<size> set maximum Java heap size
• -Xss<size> set java thread stack size

where the size can be expressed as follows: 64m for 64 megabytes, or 1g for 1 gigabytes.

I picked 1 gigabyte for the initial heap size, and 2 gigabytes for the max heap size because my desktop sports 12 GB and can handle the extra request on memory. You would pick lower values on a laptop. Don't max it to be equal to the size of the RAM in your laptop, otherwise your java program will compete with all the other apps on your laptop, including the OS, and the heap will be thrown to disk, making your program terribly slow suddenly.

Question 2

My program ran fine. If I wanted to make it crash or hang, I would have to stress it in several possible ways:

• There are 2 threads: the drawing thread and the packing thread. Could the drawing thread starve? Yes if I make the packing thread very slow, maybe forcing it to sleep after enqueueing each rectangle. But that would result in slow animation. Not a crash.
• I could try to stress the use of the heap. Two ways to do that: try to pack a huge number of rectangles, decrease the max size of the heap, and make the drawing thread slow. Using -Xmx64m, for example, 1000000 rectangles, and selecting a slow frameRate, say 1 frame/sec should do the trick.

If my program had been hanging, then I would help it by making the producer slower by forcing it to sleep every few rectangles enqueued (every 10, or 100 maybe). I could also increase the heap size. Of I could try to make the draw function faster by making sure it doesn't redraw all the rectangle every time it is called, but just the new ones.

Question 3

for large numbers of rectangles the packing is faster than the drawing. So the packer will always fill the queue to capacity. A good size queue would be one that never gets emptied by draw() until the end of the display of all N rectangles.

Question 4

Emily got some good numbers that I am copying below:

*                  rects/sec       rects/sec
*     size limit   frameRate(10)   frameRate(60)
*          1          19.45          115.52
*          5          59.87          343.20
*         10         109.32          549.37
*         50         473.19          558.25
*        100         600.40          575.31          
*        500         573.20          591.01
*       1000         602.78          650.29
*

Question 5 (Optional)

Here's Emily's answer:

*    We could get some improvement by using several threads. The
*    threads could operate by each packing a portion of the
*    rectangles in a portion of the screen. For example, with two
*    PackThreads, each would have its own packer that packs its own
*    RectangleCollection1 (with half the total number of rectangles)
*    in half the screen. It gets more complicated if there are more
*    than two rectangles - they will not always be able to divide up
*    the screen evenly(four is easy, five is trickier) and so on.