Priority Queues/Timing and Performance/Old - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:45:10Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:45, 9 October 2019
Line 16:		Line 16:
	* Loop over a "large" number of statistical trials. The average access time over all the trials is reported.		* Loop over a "large" number of statistical trials. The average access time over all the trials is reported.

	Link on git.charlesreid1.com: https://charlesreid1.com~~:3000~~/cs/java/src/master/priority-queues/Timing.java		Link on git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/priority-queues/Timing.java

	Class contents:		Class contents:

Admin at 09:33, 25 June 2017

2017-06-25T09:33:50Z

← Older revision		Revision as of 09:33, 25 June 2017
Line 134:		Line 134:

	Bug was fixed, as per above, and trend was still holding, so possibility 1 is likely.		Bug was fixed, as per above, and trend was still holding, so possibility 1 is likely.

	~~=Flags=~~

	~~{{StacksQueuesFlag}}~~
	~~[[Category:Queues]]~~
	~~[[Category:Priority Queues]]~~
	~~[[Category:Java]]~~
	~~[[Category:CS]]~~
	~~[[Category:Data Structures]]~~
	~~[[Category:Timing]]~~
	~~[[Category:Performance]]~~

Admin: Admin moved page Priority Queues/Timing and Performance to Priority Queues/Timing and Performance/Old

2017-06-25T04:28:56Z

Admin moved page Priority Queues/Timing and Performance to Priority Queues/Timing and Performance/Old

← Older revision	Revision as of 04:28, 25 June 2017
(No difference)

Admin: /* Results discussion */

2017-06-20T03:10:59Z

Results discussion

← Older revision		Revision as of 03:10, 20 June 2017
Line 118:		Line 118:

	[[Image:PriorityQueueTiming_SortedRetry.png\|500px]]		[[Image:PriorityQueueTiming_SortedRetry.png\|500px]]

			I discovered that the code was using the exact same same key-value object for each add operation in the code timed above. The timing results were for a best case scenario. Once this was fixed, I re-ran and got the following results:

			[[Image:PriorityQueueTiming_Sorted3.png\|500px]]

			The trend is still not very clear. This means, Hypothesis 1 is also likely - that we're looking at an operation that, relative to the overhead involved, is relatively cheaper, so that the linear increase in an O(N) operation is gradual enough to be nearly constant.

	===Results discussion===		===Results discussion===
Line 124:		Line 130:

	Two possibilities:		Two possibilities:
	* Built-in doubly-linked list access operations are just so damn fast that most of the time spent to retrieve an item is on function overhead, which is O(1), so what we're actually seeing is not an O(N) increase in cost but a LARGE O(1) + SMALL O(N) increase.		* Built-in doubly-linked list access operations are just so damn fast that most of the time spent to retrieve an item is on function overhead, which is O(1), so what we're actually seeing is not an O(N) increase in cost but a LARGE O(1) factor + a SMALL O(N) increase.
	* Bug in the timing code that's causing measured times to be sub-linear.		* Bug in the timing code that's causing measured times to be sub-linear.

	~~Hypothesis 2 is likely - I discovered that the code~~ was ~~using the exact same same key-value object for each add operation in the code timed~~ above~~. The timing results were for a best case scenario. One this was fixed~~, ~~I re-ran~~ and ~~got the following results:~~		Bug was fixed, as per above, and trend was still holding, so possibility 1 is likely.

	~~[[Image:PriorityQueueTiming_Sorted3.png\|500px]]~~

	~~The~~ trend is still ~~not very clear. This means~~, ~~Hypothesis~~ 1 is ~~also~~ likely ~~- that we're looking at an operation that, relative to the overhead involved, is relatively cheaper, so that the linear increase in an O(N) operation is gradual enough to be nearly constant~~.

	=Flags=		=Flags=

Admin: /* Results discussion */

2017-06-19T19:17:21Z

Results discussion

← Older revision		Revision as of 19:17, 19 June 2017
Line 127:		Line 127:
	* Bug in the timing code that's causing measured times to be sub-linear.		* Bug in the timing code that's causing measured times to be sub-linear.

	Hypothesis 1 is ~~out~~ - the code was using the same key-value ~~pair in~~ each add operation in the code timed above. The timing results were for a best case scenario.		Hypothesis 2 is likely - I discovered that the code was using the exact same same key-value object for each add operation in the code timed above. The timing results were for a best case scenario. One this was fixed, I re-ran and got the following results:

			[[Image:PriorityQueueTiming_Sorted3.png\|500px]]

			The trend is still not very clear. This means, Hypothesis 1 is also likely - that we're looking at an operation that, relative to the overhead involved, is relatively cheaper, so that the linear increase in an O(N) operation is gradual enough to be nearly constant.

	=Flags=		=Flags=

Admin: /* Priority queue timing class */

2017-06-19T19:14:33Z

Priority queue timing class

← Older revision		Revision as of 19:14, 19 June 2017
Line 32:		Line 32:

	// Tests		// Tests
	public static void main(String[] args) {		public static void main(String[] args) {
	sorted_timing();		sorted_timing();
	}		}
Line 45:		Line 45:
	StringBuffer sb = new StringBuffer();		StringBuffer sb = new StringBuffer();

	sb.append("N, Walltime Add (ms), Walltime Rm Min (ms)\n");		sb.append("N, Walltime Add (us), Walltime Rm Min (us)\n");

	int ntrials = ~~200~~;		int ntrials = 1000;
	Random r = new Random();		Random r = new Random();

	// Loop over values of N		// Loop over values of N
	for(int N = ~~(int)(5E3)~~; N <= ~~(int)(5E5)~~; N+=~~2500~~) {		int start = 50000;
			int skip = 50000;
			int MAX = 1000000;
			for(int N = start; N <= MAX; N+=skip) {

	Tim add_tim = new Tim();		Tim add_tim = new Tim();
Line 57:		Line 60:

	// Trials counter is always k for Kafka		// Trials counter is always k for Kafka
	for(int k = 0; k<ntrials; k++) {		for(int k = 0; k<ntrials; k++) {
	// Each trial is a different sequence of random numbers,		// Each trial is a different sequence of random numbers,
	// but the sequence matches between tests of different collection types		// but the sequence matches between tests of different collection types
	SortedPriorityQueue<Integer> q = new SortedPriorityQueue<Integer>();		SortedPriorityQueue<Integer> q = new SortedPriorityQueue<Integer>();
	~~Integer key = new Integer( r.nextInt() );~~
	~~Integer val = new Integer( r.nextInt() );~~

	add_tim.tic();		add_tim.tic();
	for(int i=0; i<N; i++) {		for(int i=0; i<N/2; i++) {
			Integer key = new Integer( r.nextInt() );
			Integer val = new Integer( r.nextInt() );
	q.add(key,val);		q.add(key,val);
	}		}
Line 71:		Line 74:

	rm_tim.tic();		rm_tim.tic();
	for(int i=0; i<N; i++) {		for(int i=0; i<N/4; i++) {
	q.removeMin();		q.removeMin();
	}		}
	rm_tim.toc();		rm_tim.toc();

			add_tim.tic();
			for(int i=N/2; i<N; i++) {
			Integer key = new Integer( r.nextInt() );
			Integer val = new Integer( r.nextInt() );
			q.add(key,val);
			}
			add_tim.toc();

			rm_tim.tic();
			for(int i=N/4; i<N; i++) {
			q.removeMin();
			}
			rm_tim.toc();

	}		}

			// Normalized for trials, not for container size N
	sb.append( String.format("%d, ",N) );		sb.append( String.format("%d, ",N) );
	sb.append( String.format("%.3f, ", add_tim.elapsedms()/ntrials) );		sb.append( String.format("%.3f, ", 1000*add_tim.elapsedms()/ntrials) );
	sb.append( String.format("%.3f ", rm_tim.elapsedms()/ntrials) );		sb.append( String.format("%.3f ", 1000*rm_tim.elapsedms()/ntrials) );
	sb.append("\n");		sb.append("\n");
	}		}

Admin: /* Results discussion */

2017-06-19T18:39:12Z

Results discussion

← Older revision		Revision as of 18:39, 19 June 2017
Line 102:		Line 102:
	===Results discussion===		===Results discussion===

	~~To be honest, I'm at a loss to explain exactly what's happening here~~. The code appears to be spending a constant (or ~~veeeeery~~ slowly increasing) amount of time on the add operation, even though it is performing an insertion sort each time. On the other hand, the remove operations are definitely confirmed to be O(1).		The code results do not match the hypothesis. The code appears to be spending a constant (or very slowly increasing) amount of time on the add operation, even though it is performing an insertion sort each time. On the other hand, the remove operations are definitely confirmed to be O(1).

	Two possibilities:		Two possibilities:
	* Built-in doubly-linked list access operations are just so damn fast that most of the time spent to retrieve an item is on function overhead, which is O(1), so what we're actually seeing is not an O(N) increase in cost but a LARGE O(1) + SMALL O(N) increase.		* Built-in doubly-linked list access operations are just so damn fast that most of the time spent to retrieve an item is on function overhead, which is O(1), so what we're actually seeing is not an O(N) increase in cost but a LARGE O(1) + SMALL O(N) increase.
	* Bug in the timing code that's causing measured times to be sub-linear.		* Bug in the timing code that's causing measured times to be sub-linear.

			Hypothesis 1 is out - the code was using the same key-value pair in each add operation in the code timed above. The timing results were for a best case scenario.

	=Flags=		=Flags=

Admin: /* Further Results */

2017-06-19T18:32:54Z

Further Results

@@ Line 107: / Line 107: @@
 * Built-in doubly-linked list access operations are just so damn fast that most of the time spent to retrieve an item is on function overhead, which is O(1), so what we're actually seeing is not an O(N) increase in cost but a  LARGE O(1) + SMALL O(N) increase.
 * Bug in the timing code that's causing measured times to be sub-linear.
 =Flags=

Admin: /* Further Results */

2017-06-19T18:26:43Z

Further Results

← Older revision		Revision as of 18:26, 19 June 2017
Line 110:		Line 110:
	===Further Results===		===Further Results===

	~~I believe the~~ big-O behavior for add and remove operations is skewed by overhead. When looking at the lower end of the amortized cost of remove operations~~, for smaller N~~, the curve looks linear. ~~This is~~ after ~~some~~ jitter for small values of N. Here is another plot of those quantities, up to array sizes of 100,000:		The big-O behavior for add and remove operations is likely being skewed by the overhead cost of the operations - the large O(1) mentioned above. When looking at the lower end of the curves given above, for the amortized cost of remove operations, the curve looks approximately linear (contrary to the expected behavior) and the add operational cost appears to be O(1), also contrary to expectations. Both of these trends are established after jitter for small values of N. Here is another plot of those quantities, up to array sizes of 100,000.

			(Note that the number of trials was also increased from 200 to 1000.)

	[[Image:PriorityQueueTiming_Sorted3.png\|500px]]		[[Image:PriorityQueueTiming_Sorted3.png\|500px]]

			If we look exclusively at arrays of size 500,000 to 1,000,000 (intervals of 50,000), and include a corresponding increase in the number of trials from 200 to 1000, we see the behavior below:

			[[Image:PriorityQueueTiming_Sorted4.png\|500px]]

	=Flags=		=Flags=

Admin: /* Results discussion */

2017-06-19T18:21:58Z

Results discussion

← Older revision		Revision as of 18:21, 19 June 2017
Line 107:		Line 107:
	* Built-in doubly-linked list access operations are just so damn fast that most of the time spent to retrieve an item is on function overhead, which is O(1), so what we're actually seeing is not an O(N) increase in cost but a LARGE O(1) + SMALL O(N) increase.		* Built-in doubly-linked list access operations are just so damn fast that most of the time spent to retrieve an item is on function overhead, which is O(1), so what we're actually seeing is not an O(N) increase in cost but a LARGE O(1) + SMALL O(N) increase.
	* Bug in the timing code that's causing measured times to be sub-linear.		* Bug in the timing code that's causing measured times to be sub-linear.

			===Further Results===

			I believe the big-O behavior for add and remove operations is skewed by overhead. When looking at the lower end of the amortized cost of remove operations, for smaller N, the curve looks linear. This is after some jitter for small values of N. Here is another plot of those quantities, up to array sizes of 100,000:

			[[Image:PriorityQueueTiming_Sorted3.png\|500px]]

	=Flags=		=Flags=