As countless questions/answers have noted in the past, LaTeX requires you to compile at least twice when there are references, TOC/LOF, etc. Many of these situations have been documented in the answer to What are the situations where you have to compile a document more than once?
Efforts at avoiding this extra step have been successful in select, very specific cases, such as How can I avoid compiling twice? Yet, it is a practice that we take as a given today, simply developing scripts and macros to automate this process enough to ease the pain.
The answer to [this question about moving to the previous page] alludes to memory constraints of early computers being central to the reasons why TeX was originally built the way it was. Information that might be needed later is simply stowed away in any number of auxiliary files, and referred to as the next pass was made. Once a page is "complete", it is forgotten by the compiler.
I have often thought: Given the advancements in computer processing and memory capabilities, is it possible/realistic/planned for LaTeX to maintain more of the document in memory to avoid having to compile multiple times?
Keeping the entire document in memory would take a lot of memory, and perhaps some very large documents could not go this route (maybe it would have to be an optional behavior). But it seems that many aspects of typesetting would benefit from this sort of enhanced compilation.
I realize this gets to the heart of what (La)TeX is and how it was built. It is not a simple patch; it likely requires a rewrite of the whole core (or does it?). There are certainly other issues that surround this as well (Would this actually reduce compilation time?); I'd be delighted for a reference to another place that discusses this or related issues. (Has this been thought about for LaTeX3?)