(back to Connected Components main page)

6 Connectivity

Our largest test case, from Landis, has a volume of size 1024x1088x1088 = 1,212,153,856 voxels, 50% empty. The data file is Gfiles:p1024.gz .

Using 6 connectivity, finding the 4,539,562 components takes only 51 elapsed seconds (48 CPU seconds) on an IBM T43p laptop computer with a 2000MHz Pentium.

The components contained 20,216,828 runs, each containing an average of 30 voxels each. During the 29,978,799 times that a pair of adjacent runs were processed to combine their components, the average number of pointers followed per run was only 8.4. Also, in 14,301,533 of those cases, the pair of adjacent runs was already in the same component. The largest component had 2993 runs and a volume of 23675. Many components had only one run and two voxels.

The implementation environment was a 2GHz IBM T43p laptop with SuSE linux and gcc 4.1.0. The virtual memory used, which is a function of the space preallocated for runs and components, which was sized for this example, was only 340MB. The program's elapsed time was equal to its CPU time, which was 51 CPU seconds. Smaller examples run proportionately faster, in perhaps 0.1 seconds for a 100x100x100 universe. Very complicated cases would run more slowly.

Here is the log file, giving more stats.

***** Starting at Thu Sep 21 18:03:37 2006
*****
File: header, compiled: Sep 21 2006 18:01:44, GNU compiler 4.1.0, 
version 4.1.0 (SUSE Linux),  optimized.
nx=1024, ny=1088, nz=1088, conn=6, key=0
Cumulative CPU time thru initialization= 0
read_row, x=0, y=0
read_row, x=98, y=824
read_row, x=218, y=603
read_row, x=327, y=179
read_row, x=450, y=856
read_row, x=557, y=603
read_row, x=680, y=936
read_row, x=786, y=840
read_row, x=911, y=1017
Cumulative CPU time thru processing planes= 35.07
Cumulative CPU time thru check_tree_depth= 35.41
Cumulative CPU time thru assemble_components= 35.85
Component #0 with volume 598511357 is too large to write.
Cumulative CPU time thru sort_components= 37.14
write_components, icomp=0
write_components, icomp=218526
write_components, icomp=654262
write_components, icomp=1160404
# volume=1 components not written: 3143787
Cumulative CPU time thru for write_components= 50.81
Universe has 1024*1088*1088=1212153856 voxels.
Type of connectivity: 6
# empty voxels= 608589768, fraction= 0.502073
# runs= 20216828, average size=30.1031
# components= 4539562, average # runs/component=4.45348
# times a pair of possibly adjacent runs tested, but they didn't
overlap= 48367329
# times a pair of adjacent runs processed= 29978799
# times two adjacent runs were already in the same component= 14301533
# pointers followed when processing adjacent runs= 169890091
Average # pointers followed per run= 8.4034
# times find_root_of_run called= 59957598, average # pointers followed per 
call= 1.41683
# times update_root called= 59957598, average # pointers followed per 
call= 1.41667
# times find_roots finds a run not pointing directly to its root=0
# bytes used by one run= 12, total run storage= 4
# bytes used by one component= 16, total component storage= 4
rows1 storage= 4
Total storage used by large arrays= 12
Cumulative CPU time thru end= 50.81

26 Connectivity

Here is the log from rerunning the same dataset, but this time with 26 connectivity.

***** Starting at Sun Sep 24 19:21:56 2006
*****
File: header, compiled: Sep 21 2006 18:01:44, GNU compiler 4.1.0, 
version 4.1.0 (SUSE Linux),  optimized.
nx=1024, ny=1088, nz=1088, conn=26, key=0
Cumulative CPU time thru initialization= 0
read_row, x=0, y=0
read_row, x=86, y=856
read_row, x=193, y=472
read_row, x=278, y=227
read_row, x=397, y=788
read_row, x=502, y=723
read_row, x=601, y=114
read_row, x=717, y=10
read_row, x=803, y=210
read_row, x=923, y=1024
read_row, x=1022, y=445
Cumulative CPU time thru processing planes= 39.01
Cumulative CPU time thru check_tree_depth= 39.35
Cumulative CPU time thru assemble_components= 39.72
Component #0 with volume 603263493 is too large to write.
Cumulative CPU time thru sort_components= 40.39
write_components, icomp=116679
write_components, icomp=590866
# volume=1 components not written: 1264633
Cumulative CPU time thru for write_components= 47.28
Universe has 1024*1088*1088=1212153856 voxels.
Type of connectivity: 26
# empty voxels= 608589768, fraction= 0.502073
# runs= 20216828, average size=30.1031
# components= 1931490, average # runs/component=10.467
# times a pair of possibly adjacent runs tested, but they didn't
overlap= 85959602
# times a pair of adjacent runs processed= 70474529
# times two adjacent runs were already in the same component= 52189191
# pointers followed when processing adjacent runs= 391735956
Average # pointers followed per run= 19.3767
# times find_root_of_run called= 140949058, average # pointers followed per
call= 1.38966
# times update_root called= 140949058, average # pointers followed per 
call= 1.38961
# times find_roots finds a run not pointing directly to its root=0
# bytes used by one run= 12, total run storage= 4
# bytes used by one component= 16, total component storage= 4
rows1 storage= 4
Total storage used by large arrays= 12
Cumulative CPU time thru end= 47.28