Regarding marking direct parents as uninteristing I found the answer myself: This wouldn't help much. For 99% of the cases if you visit the direct parent of the commit X then you would have visited the commit X itself one step before. And you would have stopped your walk at commit X. Therefore you will nearly never reach the direct parents of commit X.