1988 Reports

Performance Analysis and Improvement in UNIX File System Tree Traversal

Smith, Jonathan M.

A utility program has been developed to aid UNIX system administrators in obtaining information about mounted file systems. The program gathers the information by a traversal of the accessible nodes in the file hierarchy; without kernel-recorded path names, this is the only way to dynamically determine mount-point names. The program has had three significant versions, the second and third of which were driven by performance requirements rather than functional requirements. The original version showed a factor of 7 improvements over the performance of a naive tree traversal. The second iteration showed a factor of 10 improvements over the previous version by using extra information about the structure of the file system tree to prune unnecessary branches from the traversal. The third iteration showed another factor of 3 improvements by changing the search strategy. The performance improvements depend on an analysis described in this report. Since the program's main task is traversal of a UNIX file system tree, our experience can be generalized to other such searches.