Main.hs 9.16 KB
Newer Older
Simon Marlow's avatar
Simon Marlow committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
{-
// This is adapted from a benchmark written by John Ellis and Pete Kovac
// of Post Communications.
// It was modified by Hans Boehm of Silicon Graphics.
//
// 	This is no substitute for real applications.  No actual application
//	is likely to behave in exactly this way.  However, this benchmark was
//	designed to be more representative of real applications than other
//	Java GC benchmarks of which we are aware.
//	It attempts to model those properties of allocation requests that
//	are important to current GC techniques.
//	It is designed to be used either to obtain a single overall performance
//	number, or to give a more detailed estimate of how collector
//	performance varies with object lifetimes.  It prints the time
//	required to allocate and collect balanced binary trees of various
//	sizes.  Smaller trees result in shorter object lifetimes.  Each cycle
//	allocates roughly the same amount of memory.
//	Two data structures are kept around during the entire process, so
//	that the measured performance is representative of applications
//	that maintain some live in-memory data.  One of these is a tree
//	containing many pointers.  The other is a large array containing
//	double precision floating point numbers.  Both should be of comparable
//	size.
//
//	The results are only really meaningful together with a specification
//	of how much memory was used.  It is possible to trade memory for
//	better time performance.  This benchmark should be run in a 32 MB
//	heap, though we don't currently know how to enforce that uniformly.
//
//	Unlike the original Ellis and Kovac benchmark, we do not attempt
// 	measure pause times.  This facility should eventually be added back
//	in.  There are several reasons for omitting it for now.  The original
//	implementation depended on assumptions about the thread scheduler
//	that don't hold uniformly.  The results really measure both the
//	scheduler and GC.  Pause time measurements tend to not fit well with
//	current benchmark suites.  As far as we know, none of the current
//	commercial Java implementations seriously attempt to minimize GC pause
//	times.
//
//	Known deficiencies:
//		- No way to check on memory use
//		- No cyclic data structures
//		- No attempt to measure variation with object size
//		- Results are sensitive to locking cost, but we dont
//		  check for proper locking

class Node {
	Node left, right;
	int i, j;
	Node(Node l, Node r) { left = l; right = r; }
	Node() { }
}

public class GCBench {

	public static final int kStretchTreeDepth    = 18;	// about 16Mb
	public static final int kLongLivedTreeDepth  = 16;  // about 4Mb
	public static final int kArraySize  = 500000;  // about 4Mb
	public static final int kMinTreeDepth = 4;
	public static final int kMaxTreeDepth = 16;

	// Nodes used by a tree of a given size
	static int TreeSize(int i) {
	    	return ((1 << (i + 1)) - 1);
	}

	// Number of iterations to use for a given tree depth
	static int NumIters(int i) {
                return 2 * TreeSize(kStretchTreeDepth) / TreeSize(i);
        }

72
	// Build tree top down, assigning to older objects.
Simon Marlow's avatar
Simon Marlow committed
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
	static void Populate(int iDepth, Node thisNode) {
		if (iDepth<=0) {
			return;
		} else {
			iDepth--;
			thisNode.left  = new Node();
			thisNode.right = new Node();
			Populate (iDepth, thisNode.left);
			Populate (iDepth, thisNode.right);
		}
	}

	// Build tree bottom-up
	static Node MakeTree(int iDepth) {
		if (iDepth<=0) {
			return new Node();
		} else {
			return new Node(MakeTree(iDepth-1),
					MakeTree(iDepth-1));
		}
	}

	static void PrintDiagnostics() {
		long lFreeMemory = Runtime.getRuntime().freeMemory();
		long lTotalMemory = Runtime.getRuntime().totalMemory();

		System.out.print(" Total memory available="
				 + lTotalMemory + " bytes");
		System.out.println("  Free memory=" + lFreeMemory + " bytes");
	}

	static void TimeConstruction(int depth) {
		Node    root;
		long    tStart, tFinish;
		int 	iNumIters = NumIters(depth);
		Node	tempTree;

		System.out.println("Creating " + iNumIters +
				   " trees of depth " + depth);
		tStart = System.currentTimeMillis();
		for (int i = 0; i < iNumIters; ++i) {
			tempTree = new Node();
			Populate(depth, tempTree);
			tempTree = null;
		}
		tFinish = System.currentTimeMillis();
		System.out.println("\tTop down construction took "
				   + (tFinish - tStart) + "msecs");
		tStart = System.currentTimeMillis();
                for (int i = 0; i < iNumIters; ++i) {
                        tempTree = MakeTree(depth);
                        tempTree = null;
                }
                tFinish = System.currentTimeMillis();
                System.out.println("\tBottom up construction took "
                                   + (tFinish - tStart) + "msecs");
		
	}

	public static void main(String args[]) {
		Node	root;
		Node	longLivedTree;
		Node	tempTree;
		long	tStart, tFinish;
		long	tElapsed;


		System.out.println("Garbage Collector Test");
		System.out.println(
			" Stretching memory with a binary tree of depth "
			+ kStretchTreeDepth);
		PrintDiagnostics();
		tStart = System.currentTimeMillis();

		// Stretch the memory space quickly
		tempTree = MakeTree(kStretchTreeDepth);
		tempTree = null;

		// Create a long lived object
		System.out.println(
			" Creating a long-lived binary tree of depth " +
  			kLongLivedTreeDepth);
		longLivedTree = new Node();
		Populate(kLongLivedTreeDepth, longLivedTree);

		// Create long-lived array, filling half of it
		System.out.println(
                        " Creating a long-lived array of "
			+ kArraySize + " doubles");
		double array[] = new double[kArraySize];
		for (int i = 0; i < kArraySize/2; ++i) {
			array[i] = 1.0/i;
		}
		PrintDiagnostics();

		for (int d = kMinTreeDepth; d <= kMaxTreeDepth; d += 2) {
			TimeConstruction(d);
		}

		if (longLivedTree == null || array[1000] != 1.0/1000)
			System.out.println("Failed");
					// fake reference to LongLivedTree
					// and array
					// to keep them from being optimized away

		tFinish = System.currentTimeMillis();
		tElapsed = tFinish-tStart;
		PrintDiagnostics();
		System.out.println("Completed in " + tElapsed + "ms.");
	}
} // class JavaGC
-}

import Text.Printf
import System.CPUTime
import Data.IORef
import Data.Array.IO
import System.Time	( ClockTime(..) )
import Control.Monad 	( replicateM_ )
import System.IO
import System.Environment

class DeepSeq a where
  deepSeq :: a -> b -> b
  deepSeq = seq

instance DeepSeq Int

instance DeepSeq Tree where
  deepSeq Empty b = b
  deepSeq Node{left=l, right=r, i=i} b =
    deepSeq l $ deepSeq r $ deepSeq i b

treeSize i = 2^(i+1) - 1

numIters max i = 2 * treeSize max `quot` treeSize i

data Tree = Node { left, right :: Tree,  i :: Int } | Empty

makeTree 0      = Node { left = Empty, right = Empty, i = 0 }
makeTree iDepth = Node { left  = makeTree (iDepth-1),
			 right = makeTree (iDepth-1),
			 i = 0 }

data MutTree = MutNode (IORef MutTree) (IORef MutTree) Int | MutEmpty

newMutNode x = do
  l <- newIORef MutEmpty
  r <- newIORef MutEmpty
  return (MutNode l r x)

224
-- Build tree top down, assigning to older objects.
Simon Marlow's avatar
Simon Marlow committed
225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259
populate 0 node = return ()
populate iDepth (MutNode lref rref i) = do
  l <- newMutNode iDepth
  writeIORef lref l
  r <- newMutNode iDepth
  writeIORef rref r
  populate (iDepth-1) l
  populate (iDepth-1) r

ldepth MutEmpty = return 0
ldepth (MutNode l _ _) = do t <- readIORef l; ldepth t

timeConstruction max depth = do
  let iNumIters = numIters max depth
--  printf "Creating %d trees of depth %d\n" iNumIters depth
  tStart <- getCPUTime
  replicateM_ iNumIters $ do
	n <- newMutNode depth; populate depth n; touch n
  tFinish <- getCPUTime
--  printf "\tTop down construction took "
--  ptimediff stdout tStart tFinish
--  printf "\n"
  tStart <- getCPUTime
  replicateM_ iNumIters $ do
	let tempTree = makeTree depth
  	deepSeq tempTree (return ())
  	touch tempTree
  tFinish <- getCPUTime
--  printf "\tBottom-up construction took "
--  ptimediff stdout tStart tFinish
--  printf "\n"
  return ()

main = do
  args <- getArgs
260 261 262
  let
    [kLongLivedTreeDepth,
     kArraySize,
Simon Marlow's avatar
Simon Marlow committed
263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279
     kMinTreeDepth,
     kMaxTreeDepth] = map read args :: [Int]

  hSetBuffering stdout NoBuffering
--  printf "Garbage Collector Test\n"
  tStart <- getCPUTime

  -- Create a long lived object or two
--  printf " Creating a long-lived binary tree of depth %d\n" kLongLivedTreeDepth
  let longLivedTree1 = makeTree kLongLivedTreeDepth
  deepSeq longLivedTree1 (return ())

--  printf " Creating a long-lived mutable tree of depth %d\n" kLongLivedTreeDepth
  longLivedTree2 <- newMutNode kLongLivedTreeDepth;
  populate kLongLivedTreeDepth longLivedTree2

  -- Create long-lived array, filling half of it
280
--  printf " Creating a long-lived array of %d doubles\n" kArraySize
Simon Marlow's avatar
Simon Marlow committed
281 282
  array <- newArray (1,kArraySize) 0.0
  let _ = array :: IOArray Int Double
283
  sequence_ [ writeArray array i (1.0 / fromIntegral i)
Simon Marlow's avatar
Simon Marlow committed
284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301
	    | i <- [ 1 .. kArraySize `quot` 2 ] ]

  sequence_ [ timeConstruction kMaxTreeDepth d
            | d <- [ kMinTreeDepth, kMinTreeDepth+2 .. kMaxTreeDepth ] ]

  touch longLivedTree1
  ldepth longLivedTree2
  touch array

-- Utils

ptimediff :: Handle -> Integer -> Integer -> IO ()
ptimediff hout t0 t1 =
  hPrintf hout "%d.%02d" secs (psecs `quot` 10^10)
  where  (secs,psecs) = (t1 - t0) `quotRem` (10^12)

touch :: a -> IO ()
touch a = a `seq` return ()