I, too, have been wondering that. On a high level, a linker does these things:

- Read in objects file and parse linking information (needed symbols etc)

- Do some in-memory calculations - resolving symbols and some other stuff. Simple graph theory. Is there any need for more than O(n log n) runtime?.

- Write out object files

I don't think anything should take so long. No caching needed. I read the series on linkers by gold's author, where significant speedups were claimed. And also, that object-oriented C++ was the right approach to software architecture. I strongly disagree with that second point and didn't understand too much from the article series to be honest. So I am not surprised at all that there are today even much faster linkers.