Tests and benchmark results

DEM test 00

[ wmv2/avi | mpeg4/avi | flash | mpeg4 (8.8 Mb) ];
1126 time steps. Calculation took about 8 minutes (7:41).

DEM test 01

[ wmv2/avi | mpeg4/avi | flash | mpeg4 (14 Mb) ].

Non-intersection enforcement

Video: [ wmv2/avi | mpeg4/avi | flash | mpeg4 (6.4 Mb)]; 793 time steps. Calculation took about 8 minutes.

kd-tree-1 (interactions reported up to eight times), ver. 2009_06_03, mean on 4 runs and 11 steps (50-60), on an Intel E2180 at 2GHz,

N	d	CPU time per step	Selected pairs	Collisions	Resident (approx.)
50,000	0.1	211 ms	3,299,379	351,523	9 Mb
100,000	0.1	434 ms	5,842,521	702,811	17 Mb
500,000	0.1	2,261 ms	35,809,497	3,841,143	82 Mb
1,000,000	0.1	4,194 ms	78,895,265	7,659,655	144 Mb
5,000,000	0.1	18,885 ms	518,701,177	30,216,540	558 Mb

kd-tree-2 (interactions reported once), ver. 2009_06_09, mean on 4 runs and 11 steps (50-60), on an Intel E2180 at 2GHz,

N	d	CPU time per step	Selected pairs	Collisions	Resident (approx.)
50,000	0.1	297 ms	277,806	148,575	18 Mb
100,000	0.1	620 ms	565,180	291,294	35 Mb
500,000	0.1	3,288 ms	3,008,004	1,530,082	193 Mb
1,000,000	0.1	6,153 ms	6,005,570	3,075,764	353 Mb
5,000,000	0.1	24,205 ms	30,379,341	15,926,885	1.5 Gb

kd-tree-2, ver. 2009_08_12, mean on 4 runs and 11 steps (50-60), on an Intel i7-975 at 3.33GHz,

N	d	CPU time per step	Selected pairs	Collisions	malloc() total
50,000	0.1	155 ms	278,442	148,584	17.65 Mb
100,000	0.1	323 ms	563,863	291,061	35.51 Mb
500,000	0.1	1,734 ms	3,008,814	1,530,232	180.68 Mb
1,000,000	0.1	3,223 ms	6,010,489	3,076,452	361.36 Mb
5,000,000	0.1	12,000 ms	30,380,502	15,926,302	1.78 Gb
10,000,000	0.1	30,631 ms	60,738,048	32,012,398	3.57 Gb
20,000,000	0.1	100,690 ms	123,789,734	64,905,343	7.14 Gb
30,000,000	0.1	251,705 ms	185,861,947	97,678,602	10.71 Gb