Small Memory Software

Yet another episode of Software Engineering Radio. This time, episode 79: Small Memory Software with Charles Weir and James Noble. This episode is along the lines of the book Small Memory Software: Patterns for systems with limited memory, which is available online.

I had some problems in identifying the patterns because they are not always clearly stated. Nevertheless here are my notes on the podcast. Again, I am heavily quoting from there.

01:06 introduction

When Weir and Noble wrote the book they though it would be of minor interest and maybe even become obsolete soon. But it turned out that far from that the topic is becoming more and more mainstream.

The book is targeting for developers of any software where the memory size, be it disk or RAM, is a consideration. Most workstation applications are out of the scope because there the common practice is that there are enough resources, and if not, the user buys them. Instead small machines with little memory are the major target platform. This can be embedded systems such as Symbian phones. But it can also be any other system which is mass-produced and thus hardware costs outbalance development costs. A second and surprising domain is big machines which have to deal with huge amount of data, such as batch processing on mainframes and scientific computing systems.

07:36 overview

• small data structures: How can you reduce the memory needed for your data? (chapter 5)
• memory allocation: How do you allocate memory to store your data structures? (chapter 6)
• compression: How can you fit a quart of data into a pint pot of memory? (chapter 4)
• secondary storage: What can you do when you have run out of primary storage? (chapter 3)
• small architecture: How can you manage memory use across a whole system? (chapter 2)

09:50 small data structures

• packed data: store information dense by bit-manipulating standard data types and abstract that away.
• sharing: if you have a common information used in more than one place rather then duplicating it you just share it.
• copy on write: the illusion of every part in the system having its own modifiable data.
• multiple representations: choosing the smallest representation on the fly and abstracting this away.

15:03 memory allocation

• fixed allocation: allocate all required memory at the start of the program. This does not minimize the absolute memory footprint of the program but avoids memory-out situations and thus leads to predictable and reliable memory usage. Particular important in real-time systems because malloc takes an undefined time. Also important for tasks which may not fail.
• pooled allocation: preallocate memory and keep it in a pool, which can extend. Saves the overhead of throwing away and reallocation afterwards. Avoids memory fragmentation.
• compact memory: handle memory fragmentation. If the maximum amount of memory available to allocate if very different from the size of largest single chunk you should compact memory. Implementation needs indirect pointers. Avoid allocating small objects straight after large ones and then deallocating the large ones, because this leads to memory fragmentation. Different pools for different object sizes also helps in avoiding memory fragmentation.
• memory discard: for lots of memory allocations which need deallocation afterwards, first allocate a larger heap from which the subsequent allocations are served. In the end and at every point in time before just deallocate the single heap.
• reference counting: object counts the number of references to it. If it gets zero the object deallocates itself. Has difficulties with cycles.
• garbage collection: reclaim allocated but unused memory.

32:03 compression

• table compression: compress symbol by symbol by means of a lookup table. A known example is Huffman coding. The table can either be implicitly known or explicitly stored.
• difference encoding: at a sequence of data rather then sending the whole data all the time just list the differences. May use escaped absolute values for resynchronization. A variant of this is run-length encoding
• adaptive compression: "advanced" compression methods. The podcast refers to books from Ian H. Witten and Timothy C. Bell, e.g. Managing Gigabytes.

36:55 secondary storage

• application switching: applications can store their entire state to secondary storage and resume later. The general advice is to no all the processes at once but only the ones which are needed.
• keep your data in secondary storage and have a mechanism to load what you need.
• data files: do sequential processing according to the the pipes and filters pattern.
• packages: aka. dynamic libraries. Divine up your application in a bunch of packages and ensure you only load what you currently need.
• paging: aka. caching. You can do paging in software without hardware or OS support.

42:24 small architecture

• The simplest way to make things small is to leave stuff out.
• responsibility: components take responsibility for their memory
• memory limit: don't let components allocate more memory than some maximum, thus enforcing memory responsibility.
• small interfaces: make interfaces small so that their demands on system memory is small. For example instead of requiring a copy of a (large) memory location you can
  • (temporarily) pass over responsibility aka. ownership
  • let the supplier write directly into a buffer owned by the recipient
  • do reference counting
  • swap memory blocks.
• Captain Oates: sacrifice a component so that more important components can continue their work. In case of low-memory warning gracefully store your state in secondary storage and quit instead of fighting it.
• read-only memory: memory that is part of the code (e.g. lookup tables), constants or resource files go into (cheap) read-only memory.
• hooks: make all access to read-only memory indirect through hooks then you have got the option to update the data without having to replace the ROM.

56:40 epilogue

• topic is still current, getting more and more mainstream.
• embedded operation systems are evolving towards supporting a lot of the patterns.
• This patterns are fundamental ways of handling memories and are widely accepted and implemented.