Chapter 4. Precious memory: Space efficiency

 

This chapter covers

  • Writing space-efficient classes
  • Comparing the memory requirements of common data structures, including arrays, lists, and sets
  • Assessing trade-offs between performance and memory footprint
  • Exploiting memory locality to improve performance

Sometimes, programmers need to store their data in as little space as possible. Contrary to intuition, this rarely happens because the device they’re targeting comes with little memory. Rather, it happens because the amount of data is huge. For example, video games are a type of software that often pushes the limits of the hardware. No matter how many GB of memory the next console boasts, soon games will run out of it and start packing data in weird ways.

In this chapter, assume your water-management program will deal with millions, perhaps even billions of containers, and you want to keep as many of them as possible in main memory. Clearly, you’ll want to shrink the memory footprint of each container as much as possible. On the other hand, you don’t need to worry about the memory that temporary local variables use because they live only the short time span of a method call.

For each implementation in this chapter, you’ll compare its memory footprint with the one of Reference, discussed in chapter 2. In the meantime, recall the fields used in that class:

4.1. Gently squeezing    [Memory1]

4.2. Plain arrays    [Memory2]

4.3. Forgoing objects    [Memory3]

4.4. The black hole    [Memory4]

4.5. Space-time trade-offs

4.6. And now for something completely different

4.7. Real-world use cases

4.8. Applying what you learned

Summary

Answers to quizzes and exercises

Further reading