What is the overhead of Virtual Memory?
One major overhead of virtual memory is that virtual pages that are being used in the current computation have to
be loaded in physical memory, which usually means also transferring
out another page back on disk. Since this is costly, you want to avoid
doing it too often. Hence an important concept is the locality of
programs: though a program may have to use considereable space, you
try to organize the program so that only a much smaller part of memory
is used at any time, a smaller part that evolves only slowly.

THis concerns the code being executed, but also the data used. And
data is often orders of magnitude larger than the code. So, a program
handling large amounts of data will often be organized so as to
improve the locality of the data organisation in memory (but this depends also on what the code does with the data). As a
consequence, too naive a use of classical textbook algorithms may result in
very slow programs, because of too many page faults.

I guess there are tools to analyze the locality of programs, or to
optimize them to improve it. A specific example is the design of
garbage collectors, which have developed various techniques to improve
data locality by reorganizing the information, and which are of course
design to explore the memory in a very local way, for example by
looking in priority at pages the main program has already loaded in
physical memory.

Programs with bad locality spend too much time loading pages compared
to actual computing time. This is called thrashing.