Comparative Bench of 4 search tree structures

ComparativeBench.java

package oss.alphazero.util.ds2.adhoctests;

import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
import java.util.concurrent.ConcurrentSkipListSet;
import java.util.concurrent.TimeUnit;

import oss.alphazero.util.ds2.STF;
import oss.alphazero.util.ds2.SplayTree;
import oss.alphazero.util.ds2.SplayTreeMap;
import oss.alphazero.util.ds2.STF.TreeFactory;

/**
 * @date:  Feb 11, 2012
 */
@SuppressWarnings("unused")
public class ComparativeBench {

	public static void main(String [ ] args) {
		benchAgainstSplayTreeMap ();
	}
	
	private static final int iters = 20;
	private static final int seqlen = 128;
	private static final TreeFactory<Integer> splayTreeFactory = new STF.TreeFactory.SplayTrees<Integer>();
	private static final TreeFactory<Integer> jdkTreeSetFactory = new STF.TreeFactory.TreeSets<Integer>();

	public static final void benchAgainstSplayTreeMap() {
		class Datastruct {
			public Datastruct(Set<Integer> ds, String info) {
				this.ds = ds;
				this.info = info;
			}
			final Set<Integer> ds;
			final String 	info;
		}
		
		int degree = 16; // for the STF 
		Datastruct stf_treeset = new Datastruct(new STF<Integer>(degree, jdkTreeSetFactory),   "STF<TreeSet>");
		Datastruct stf_splaytree = new Datastruct(new STF<Integer>(degree, splayTreeFactory), "STF<SplayTree>");
		Datastruct splaytree = new Datastruct(new SplayTree<Integer>(), "SplayTree");
		Datastruct jdkTreeSet = new Datastruct(new TreeSet<Integer>(), "TreeSet (JDK)");
		
		Datastruct[] subjects = new Datastruct[]{
				jdkTreeSet,
				stf_treeset,
				splaytree,
				stf_splaytree,
		};
		
		// run forever
		int loop = 0;
		for(;;){
			boolean doDelete = ++loop%4 == 1;
			if(!doDelete) 
				System.out.format("adding %d linear sequences of length: %d\n", iters, seqlen);
			for(Datastruct ds : subjects){
				benchTree(ds.ds, doDelete, ds.info);
			}
			System.out.println ();
		}
	}
	
	public static final Random random = new Random(System.currentTimeMillis());
	public static final int randint() {
		int lim = Integer.MAX_VALUE-seqlen;
		int v = random.nextInt(lim-1);
		return v;
	}
	
	public static final void benchTree(Set<Integer> t, boolean remove, String dstype) {
		final String OP = remove ? "DEL" : "ADD";
		final long start = System.nanoTime();
		
		// actual mods to the tree
		int mods = 0;
		// actual ops on tree 
		int ops = 0;
		// cnt is number of items in tree can be used for assert against t.size()
		int cnt = 0;
		
		// depending on remove flag, add or insert 
		// a quantity of items to tree
		// adds are pretty much iters*seqlen 
		// removes start small but as cnt gets large, they approach add cnt
		// so tree size starts growing fast and then gently increases as remove 
		// counts increase and offset the adds.
		
		for(int i=0; i<iters; i++){
			final int key = randint();
			if(remove){
				// try deleting random sequence
				// we need to try a large set of numbers
				// so ops >> mods but ops are still lookups in tree
				for(int j=0; j<seqlen*200; j++){
					if(t.remove(randint())){
						cnt--;
						mods ++;
					}
					ops ++;
				}
			}
			else {
				// inserts of random sequence
				// if seqlen > 1 then favors lists and splaytrees, etc
				for(int j=0; j<seqlen; j++){
					// pick random n and add sequence n->n+seqlen 
					if(t.add(key+j)){	
						cnt++;
						mods ++;
					}
					ops ++;
				}
			}
		}
		final long delta = System.nanoTime() - start;
		
		double dmods = mods;
		double dops = ops;
		double modspers = dmods/delta * TimeUnit.SECONDS.toNanos(1);
		double opspers = dops/delta * TimeUnit.SECONDS.toNanos(1);
		
		System.out.format(
				"delta(ns):%10d | [%s] ops:%8d | mods:%5d | ops/sec:%9.0f | mods/sec:%9.0f | " +
				"tot-size:%7d [struct:%8s]\n", 
				
				delta, OP, ops, mods, opspers, modspers, t.size(), dstype
			);

//		System.out.format("%s mods:%4d delta:%10d ops/sec:%8.0f size:%8d [tree:%s]\n", OP, mods, delta, modspers, t.size(), t.getClass().getSimpleName());
	}
}