TheDeveloperBlog.com


Temporal Locality: Improve Performance

Temporal locality enhances performance. It tells us whether memory locations in a program are likely to be accessed again in the near future. A method has high temporal locality if it is called repeatedly in a short period of time.

Memory Hierarchy

Tip: With this principle in mind, we can develop effective optimizations for many programs.

Tip 2: One way to optimize a program is to increase its temporal locality. This helps certain programs.


Example. Think of a program that reads in 1000 files, generates a report for each file, and then writes 1000 output files. You could have this program read in one file, generate a report, and then write an output file. This is repeated 1000 times.

Program outline with low temporal locality

Read data file
Generate output
Write output file

Read data file
Generate output
Write output file

Read data file
Generate output
Write output file

Program outline with higher temporal locality

Read data file
Read data file
Read data file

Generate output
Generate output
Generate output

Write output file
Write output file
Write output file

How can you change the program as described above to have more temporal locality? One thing you could try is to read in all the data files. Then you could generate all 1000 outputs. And finally you could write all 1000 output files.


Discussion. Why would increasing temporal locality in this way improve performance? First, file IO is probably a large part of the total time required. If you read or write files in a tight loop, the file system cache will anticipate this better.

And: This will lead to less wait time when requesting a file be read in from the disk.

By increasing temporal locality in this way, the code itself will be more likely to be in the cache. So it will execute faster as well. Improving temporal locality here increases the effectiveness of caches on the hardware.

Windows File Cache

Note: A realistic example of using temporal locality in this way is hard to demonstrate.

But: My experience with a program supports this idea. I found that improving temporal locality for the output files helped.

Benchmark

Summary. Compiler theory describes all storage locations (processor caches, RAM, hard disks) as memory. Computers have a distinct memory hierarchy. With temporal locality, caches can better anticipate a program's next actions.