The paper is a report for a a pair work for a laboratory course in programming. Its title is The Significance of Data Presentation to Performance.

Abstract

In this paper we studied the performance of depth-first search (DFS) with four different graph implementations. To our surprise in the tests, our bit-matrix implementation didn't perform better than the integer-matrix implementation, even though in needs 32 times less memory.

Our adjacency list implementation, where we placed the data as it is common in graph implementations, performed well in all cases, even when the graph data didn't fit to the cache. With the other list implementation there was some degradation in performance when the graph size exceeded a multiple of the L2 cache size.

When testing the influence of graph density, the performance curve of adjacency matrix implementations drew a parabolic curve indicating that performance was best with sparse and dense graphs.