XKCD Comic; memory and pointers

You can basically say that everything a computer reads and does is stored as memory. Whether's it's RAM (random-access memory) that a program is currently using, or part of the ROM (read-only memory), the computer is using memory.

But in order for a computer to first use memory, it has to allocate space in its memory for storage. Basically, the computer looks for a bit of its memory that is completely unused then says "this spot is now used by X program" so it is marked as "used." Then, the program can write to it as normal.

As a good example, let's say you have a game of tic-tac-toe that's coordinate-based. So the top left square is {0,0}, the top right is {2,0}, and the bottom right is {2,2}. If you were to use OOP for this, then you'd have 12 bytes allocated for each square:

class Square {
    Square(int coord_x, int coord_y) {
        X = coord_x;
        Y = coord_y;
        Owner = 0;

    int X;  // 4 bytes: X coord
    int Y;  // 4 bytes: Y coord
    int Owner;  // 4 bytes: 0=Empty, 1=X, 2=O

void main() {
    // Each of these lines allocates a Square*, which is a pointer to a Square object. These are each 4 bytes.
    Square* TL = new Square(0,0);
    Square* TM = new Square(1,0);
    Square* TR = new Square(2,0);
    Square* ML = new Square(0,1);
    Square* MM = new Square(1,1);
    Square* MR = new Square(2,1);
    Square* BL = new Square(0,2);
    Square* BM = new Square(1,2);
    Square* BR = new Square(2,2);

Now the computer has a total of 9 (4 + 4 + 4 + 4) = 144 bytes of data stored in the RAM. (Of course, you have to know that data this size will rarely be stored by a program; there are far more variables and data stored than just these 9 Square objects. Error handling, Kernel stuff, etc., are all added; when running this program, approximately 196K is allocated--1,361 times* what we estimated.)

So now that the memory is allocated (each time when a Square* is intialized, another 16 bytes is allocated), values are stored into it. First the pointer to the object is stored (which is mostly random; you can see in the table below that they basically follow no rhyme or reason). Next, the constructor, Square(int,int), is called and stores the values of 0 and 0 (or others, depending on which we've called) in X and Y, as well as the value of 0 in Owner. Once we've hit the end of the program, if we were to map out the known memory, it would look something like this:

Memory Table

The unfortunate but unavoidable problem with memory allocation is that it's slow. As mentioned by StealthEye here, one of the biggest problem with the MergeSort sorting algorithm (and consequently many other sorting algorithms) is the fact that arrays often have to be copied and data has to be allocated to serve the algorithm. If you were to do something to the effect of this pseudocode, the first example would be much quicker than the second.

Example 0:
x = new array[50];
for (i = 0; i < 50; i++) {
    x[i] = i;

Example 1:
x = new array[0];
for (i = 0; i < 50; i++) {
    x.alloc(1); // Allocate another space
    x[i] = i;

In any case where speed matters and you can get rid of an allocation, do so. Even if it takes you a little bit longer than usual to write the code, you and your users will both save time in the processing time.

So what's new for you? ;)

Next Post Previous Post