WireCell / wire-cell-toolkit

Toolkit for Liquid Argon TPC Simulation and Reconstruction
https://wirecell.github.io/
Other
7 stars 20 forks source link

`BlobGrouping` scales badly with increasing number of blobs #177

Open brettviren opened 2 years ago

brettviren commented 2 years ago

The BlobGrouping flow graph node performs the merging of channels to produce the blobs' "measures" ("merged wires" in WCP terms).

In comparing the speed of BlobDepoFill (#175) it was found that BlobGrouping slows down considerably with more activity in the event.

Hopefully a better algorithm can be invented.

brettviren commented 2 years ago

Part of the problem has to do with use of IndexedGraph. It's ability to map from node object to node descriptor makes for brief code, but leads to extra computation. Using directly the unindexed cluster graph and a local custom index where needed brings about a 5x speed up (see #175).

The faster code still uses the same algorithm which is a recursive neighbors iteration over s-b-w-c. The w-c iteration could be avoided as w's IWire holds directly their channel idents allowing b-chid graph to be made and later satisfied with a chid-c lookup which can be built during the initial iteration.

Another possibility is to convert the s-b-w-c graph into a directed one and a DFS visit could collect s-b-c without the walk going "up" the wrong branch (eg from w->c->w).