ISA-tools/graph2tab — pull request #4 by afaulconbridge (2012-07-06 15:48:21+00:00)
Title: Cache startNodes

For laying out large tabular files with many start nodes (thousands or more) and little structure, I have found the performance to be quite poor. This change improves performance on large graphs, in some cases by orders of magnitude.

The change is in code that deals with identifying the starting nodes i.e. those without any inputs.

Without this optimization, each time the start nodes are required it does a loop over all nodes and try to add nodes without any inputs to the TreeSet startNodes - and every time after the first, they are already in the set. The start nodes are stored but this store is not used as a cache.

With this optimization, this loop is only done one during initialization and the start nodes are cached for future use. The overall effect is to change an approximately O(n * n*log(n)) performance into O(1)