Yeah, that's at least in part because of the stat()/lstat()-blowup.

After the first run most of the stat data will be cached in-memory anyway, but tens of thousands of unnecessary system calls hurts even with the actual data in memory...