Algorithmic Efficiency - Memory


Often, it is possible to make an algorithm faster at the expense of memory. This might be the case whenever the result of an 'expensive' calculation is cached rather than recalculating it afresh each time. The additional memory requirement would, in this case, be considered additional overhead although, in many situations, the stored result occupies very little extra space and can often be held in pre-compiled static storage, reducing not just processing time but also allocation and deallocation of working memory. This is a very common method of improving speed, so much so that some programming languages often add special features to support it, such as C++'s 'mutable' keyword.

The memory requirement of an algorithm is actually two separate but related things:-

  • The memory taken up by the compiled executable code (the object code or binary file) itself (on disk or equivalent, depending on the hardware and language). This can often be reduced by preferring run-time decision making mechanisms (such as virtual functions and run-time type information) over certain compile-time decision making mechanisms (such as macro substitution and templates). This, however, comes at the cost of speed.
  • Amount of temporary "dynamic memory" allocated during processing. For example, dynamically pre-caching results, as mentioned earlier, improves speed at the cost of this attribute. Even the depth of sub-routine calls can impact heavily on this cost and increase path length too, especially if there are 'heavy' dynamic memory requirements for the particular functions invoked. The use of copied function parameters (rather than simply using pointers to earlier, already defined, and sometimes static values) actually doubles the memory requirement for this particular memory metric (as well as carrying its own processing overhead for the copying itself. This can be particularly relevant for quite 'lengthy' parameters such as html script, JavaScript source programs or extensive freeform text such as letters or emails.

(See also sections Choice of instruction or data type and Avoiding costs concerning deliberate 'stretching' of data structures to force them to have a fixed length, which then becomes a multiple of 2, 4, 8 etc.)

Read more about this topic:  Algorithmic Efficiency

Other articles related to "memory":

Program Counter - Hardware Implementation
... in which the CPU places the value of PC on the address bus to send it to the memory ... The memory responds by sending the contents of that memory location on the data bus ... computer model, in which executable instructions are stored alongside ordinary data in memory, and handled identically by it) ...
Memory Management
... Memory management is the act of managing computer memory ... The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and freeing it for reuse when no longer needed ... methods have been devised that increase the effectiveness of memory management ...
Time Immemorial
... Time immemorial is a phrase meaning time extending beyond the reach of memory, record, or tradition, indefinitely ancient, "ancient beyond memory or record" ... same as time out of mind, "a time before legal history and beyond legal memory." In 1275, by the first Statute of Westminster, the time of memory was limited to the reign of ... In 1832, time immemorial was re-defined as "Time whereof the Memory of Man runneth not to the contrary." The plan of dating legal memory from a fixed time was ...

Famous quotes containing the word memory:

    Vashtar: So it’s finished. A structure to house one man and the greatest treasure of all time.
    Senta: And a structure that will last for all time.
    Vashtar: Only history will tell that.
    Senta: Sire, will he not be remembered?
    Vashtar: Yes, he’ll be remembered. The pyramid’ll keep his memory alive. In that he built better than he knew.
    William Faulkner (1897–1962)

    Men like my father cannot die. They are with me still, real in memory as they were in flesh, loving and beloved forever. How green was my valley then.
    Philip Dunne (1908–1992)

    The true art of memory is the art of attention.
    Samuel Johnson (1709–1784)