Isn't the use of pointer variables a memory overhead?

Question

In languages like C and C++, while using pointers to variables we need one more memory location to store that address. So isn't this a memory overhead? How is this compensated? Are pointers used in time critical low memory applications?

Answer 1

Actually, the overhead does not really lie in the extra 4 or 8 bytes needed to store the pointer. Most times pointers are used for dynamic memory allocation, meaning that we invoke a function to allocate a block of memory, and this function returns to us a pointer which points to that block of memory. This new block in and of itself represents a considerable overhead.

Now, you don't have to engage in memory allocation in order to use a pointer: You can have an array of int declared statically or on the stack, and you can use a pointer instead of an index to visit the ints, and it is all very nice and simple and efficient. No memory allocation needed, and the pointer will usually occupy exactly as much space in memory as an integer index would.

Also, as Joshua Taylor reminds us in a comment, pointers are used to pass something by reference. E.g., struct foo f; init_foo(&f); would allocate f on the stack and then call init_foo() with a pointer to that struct. That's very common. (Just be careful not to pass those pointers "upward".) In C++ you might see this being done with a "reference" (foo&) instead of a pointer, but references are nothing but pointers that you may not alter, and they occupy the same amount of memory.

But the main reason why pointers are used is for dynamic memory allocation, and this is done in order to solve problems that could not be solved otherwise. Here is a simplistic example: Imagine you want to read the entire contents of a file. Where are you going to store them? If you try with a fixed-size buffer, then you will only be able to read files that are not longer than that buffer. But by using memory allocation, you can allocate as much memory as necessary to read the file, and then proceed to read it.

Also, C++ is an object-oriented language, and there are certain aspects of OOP like abstraction that are only achievable using pointers. Even languages like Java and C# make extensive use of pointers, they just don't allow you to directly manipulate the pointers, so as to prevent you from doing dangerous stuff with them, but still, these languages only begin to make sense once you have realized that behind the scenes everything is done using pointers.

So, pointers are not only used in time-critical, low-memory applications, they are used everywhere.

Answer 2

So isn't this a memory overhead?

Sure, an extra address (generally 4/8 bytes depending on processor).

How is this compensated?

It is not. If you need the indirection necessary for pointers, then you get to pay for it.

Are pointers used in time critical low memory applications?

I haven't done much work there, but I would assume so. Pointer access is an elementary aspect of assembly programming. It takes trivial amounts of memory and pointer operations are speedy - even in the context of these sorts of applications.

Answer 3

I don't quite have the same spin on this as Telastyn.

System globals in an embedded processor might be addressed with specific, hard-coded addresses.

Globals in a program will be addressed as an offset from a special pointer that points to the place in memory where globals and statics are stored.

Local variables appear when a function is entered and are addressed as an offset from another special pointer, often called the "frame pointer". This includes the arguments to the function. If you are careful about the pushes and pops with the stack pointer, you can do away with the frame pointer and access local variables straight from the stack pointer.

So you pay for the indirection of pointers whether you're striding through an array or just grabbing some unremarkable local or global variable. It's just based on a different pointer, depending on what kinda variable it is. Code that is compiled well will keep that pointer in a CPU register, rather than reloading it each time it's used.

Answer 4

Yes, of course. But it's a balancing act.

Low memory applications would typically be constructed bearing in mind the trade-off between the overhead of a few pointer variables compared to the overhead of what would be a massive program (that must be stored in memory, remember!) if pointers could not be used.

This consideration applies for all programs, because nobody wants to build a horrid, unmaintainable mess with duplicated code left right and centre, that's twenty times larger than it needs to be.

Answer 5

In languages like C and C++, while using pointers to variables we need one more memory location to store that address. So isn't this a memory overhead?

You assume that the pointer needs to be stored. That is not always the case. Every variable is stored at some memory address. Say you have a long declared as long n = 5L;. This allocates storage for n at some address. We can use that address to do fancy things like *((char *) &n) = (char) 0xFF; to manipulate parts of n. The address of n isn't stored anywhere as an extra overhead.

How is this compensated?

Even if pointers are explicitly stored (e.g. in data structures such as lists), the resulting data structure is often more elegant (simpler, easier to understand, easier to handle, etc) than an equivalent data structure without pointers.

Are pointers used in time critical low memory applications?

Yes. Devices that use micro-controllers often contain very little memory but the firmware might use pointers for handling interrupt vectors or buffer management, etc.

Answer 6

Having a pointer definitely consumes some overhead, but you can see the upside too.Pointer is like index. In C you can use complex data structures like string and structures due to pointers only.

In fact suppose you want to pass a variable by reference then its easy to maintain a pointer rather than replicating the whole structure and synchronizing changes between them(even for copying them you will need pointer ). How would you deal with non contiguous memory allocations and de-allocations without pointer ?

Even your normal variables have an entry in symbol table that stores address where your variable is pointing towards. So, I don't think it creates much overhead in terms of memory(just 4 or 8 bytes) . Even languages like java use pointers internally(reference), they just don't let you to manipulate them as it will make JVM less secure.

You should use pointers only when you have no other choice like missing data-types, structures(in c) as using pointers may be lead to errors if not handled properly and are comparatively harder to debug.

Answer 7

So isn't this a memory overhead?

Yes.... no... maybe?

This is an awkward question because imagine the memory addressing range on the machine, and a software that needs to persistently keep track of where things are in memory in a way that can't be tied to the stack.

For example, imagine a music player where the music file is loaded on a button push by the user and unloaded from volatile memory when the user tries to load another music file.

How do we keep track of where the audio data is stored? We need a memory address to it. The program not only needs to keep track of the audio data chunk in memory but also where it is in memory. Thus we need to keep around a memory address (i.e., a pointer). And the size of the storage required for the memory address is going to match the addressing range of the machine (ex: 64-bit pointer for a 64-bit addressing range).

So it's kind of "yes", it does require storage to keep track of a memory address, but it's not like we can avoid it for dynamically-allocated memory of this sort.

How is this compensated?

Talking about just the size of a pointer itself, you can avoid the cost in some cases by utilizing the stack, e.g. In that case, compilers can generate instructions which effectively hard-code the relative memory address, avoiding the cost of a pointer. Yet this leaves you vulnerable to stack overflows if you do this for large, variable-sized allocations, and also tends to be impractical (if not outright impossible) to do for a complex series of branches driven by user input (as in the audio example above).

Another way is to use more contiguous data structures. For example, an array-based sequence might be used instead of a doubly-linked list which requires two pointers per node. We can also use a hybrid of these two like an unrolled list which stores only pointers in between every contiguous group of N elements.

Are pointers used in time critical low memory applications?

Yes, very commonly so, as many performance-critical applications are written in C or C++ which are dominated by pointer usage (they might be behind a smart pointer or a container like std::vector or std::string, but the underlying mechanics boil down to a pointer which is used to keep track of the address to a dynamic memory block).

Now back to this question:

How is this compensated? (Part Two)

Pointers are typically dirt cheap unless you're storing like a million of them (which is still a measly* 8 megabytes on a 64-bit machine).

_{* Note as Ben pointed out that a "measly" 8 megs is still the size of the L3 cache. Here I used "measly" more in the sense of total DRAM use and the typical relative size to the memory chunks a healthy usage of pointers will point to.}

Where pointers get expensive is not pointers themselves but:

1. Dynamic memory allocation. Dynamic memory allocation tends to be expensive since it has to go through an underlying data structure (ex: buddy or slab allocator). Even though these are often optimized to death, they're general-purpose and designed to handle variable-sized blocks which require that they do at least a bit of work resembling a "search" (albeit lightweight and possibly even constant-time) to find a free set of contiguous pages in memory.

2. Memory access. This tends to be the bigger overhead to worry about. Whenever we access memory allocated dynamically for the first time, there's a compulsory page fault as well as cache misses moving the memory down the memory hierarchy and down into a register.

Memory Access

Memory access is one of the most critical aspects of performance beyond algorithms. A lot of performance-critical fields like AAA game engines focus a great deal of their energy towards data-oriented optimizations which boil down to more efficient memory access patterns and layouts.

One of the biggest performance difficulties of higher-level languages which want to allocate each user-defined type separately through a garbage collector, e.g., is that they can fragment memory quite a bit. This can be especially true if not all objects are allocated at once.

In those cases, if you store a list of a million instances of a user-defined object type, accessing those instances sequentially in a loop might be quite slow since it's analogous to a list of a million pointers which point to disparate regions of memory. In those cases, the architecture wants to fetch memory form upper, slower, bigger levels of the hierarchy in large, aligned chunks with the hope that surrounding data in those chunks will be accessed prior to eviction. When each object in such a list is allocated separately, then often we end up paying for it with cache misses when each subsequent iteration might have to load from a completely different area in memory with no adjacent objects being accessed prior to eviction.

A lot of the compilers for such languages are doing a really great job these days at instruction selection and register allocation, but the lack of more direct control over memory management here can be killer (though often less error-prone) and still make languages like C and C++ quite popular.

Indirectly Optimizing Pointer Access

In the most performance-critical scenarios, applications often use memory pools which pool memory from contiguous chunks to improve locality of reference. In such cases, even a linked structure like a tree or a linked list can be made cache-friendly provided that the memory layout of its nodes are contiguous in nature. This is effectively making pointer dereferencing cheaper, albeit indirectly by improving the locality of reference involved when dereferencing them.

Chasing Pointers Around

Assume we have a singly-linked list like:

Foo->Bar->Baz->null

The problem is that if we allocate all these nodes separately against a general-purpose allocator (and possibly not all at once), the actual memory might be dispersed somewhat like this (simplified diagram):

When we start chasing pointers around and access the Foo node, we start off with a compulsory miss (and possibly a page fault) moving a chunk from its memory region from slower regions of memory to faster regions of memory, like so:

This causes us to cache (possibly also page) a memory region only to access a portion of it and evict the rest as we chase pointers around this list. By taking control over the memory allocator, however, we can allocate such a list contiguously like so:

... and thereby significantly improve the speed at which we can dereference these pointers and process their pointees. So, albeit very indirect, we can speed up pointer access this way. Of course if we just stored these contiguously in an array, we wouldn't have this issue in the first place, but the memory allocator here giving us explicit control over memory layout can save the day when a linked structure is required.

_{* Note: this is a very oversimplified diagram and discussion about the memory hierarchy and locality of reference, but hopefully it's appropriate for the level of the question.}

Answer 8

So isn't this a memory overhead?

It is indeed a memory overhead, but a very small one (to the point of insignificance).

How is this compensated?

It is not compensated. You need to realize that data access through a pointer (dereferencing a pointer) is extremely fast (if I remember correctly, it uses just one assembly instruction per dereference). It is fast enough that it will be in many cases the fastest alternative you have.

Are pointers used in time critical low memory applications?

Yes.

Answer 9

If you can use indexing (eg. with a vector) and you have to save a lot of addresses (eg. for some tree structure) of the elements in the vector, you should use indexing instead of pointers. On a 64 bit machine you save 4 bytes for each pointer replaced by an index saved in unsigned int.

Answer 10

You only need the extra memory usage (4-8 bytes per pointer, typically) while you need that pointer. There are many techniques which make this more affordable.

The most fundamental technique that makes pointers powerful is that you don't need to keep every pointer. Sometimes you can use an algorithm to construct a pointer from a pointer to something else. The most trivial example of this is array arithmetic. If you allocate an array of 50 integers, you don't need to keep 50 pointers, one to each integer. You typically keep track of one pointer (the first one), and use pointer arithmetic to generate the others on the fly. Sometimes you may keep one of those pointers to a specific element of the array temporarily, but only while you need it. Once you're done, you can discard it, as long as you kept enough information to regenerate it later, if you need it. This may sound trivial, but its exactly the kind of conservation tools you'll use if you truly care about how many pointers you are keeping in memory.

In extremely tight memory situations, this can be used to minimize cost. If you are working in a very tight memory space, you usually have a good sense of how many objects you need to manipulate. Instead of allocating a bunch of integers one at a time and keeping full pointers to them, you may take advantage of your developer knowledge that you'll never have more than 256 integers in this particular algorithm. In that case, you might keep a pointer to the first integer, and keep track of an index using a char (1 byte) rather than using a full pointer (4/8 bytes). You might also use algorithmic tricks to generate some of these indices on the fly.

This kind of memory conscientiousness was very popular in the past. For example, NES games would rely extensively on their ability to cram data and generate pointers algorithmically rather than having to store them all wholesale.

Extreme memory situations can also lead one to do things like allocating all of the spaces you operate on at compile time. Then the pointer you have to store to that memory is stored in the program rather than the data. In many memory constrained situations, you have separate program and data memory (often ROM vs RAM), so you may be able to adjust the way you use your algorithm to push the pointers into that program memory.

Fundamentally, you can't get rid of all of the overhead. However, you can control it. By using algorithmic techniques, you can minimize the number of pointers you can store. If you happen to be using pointers to dynamic memory, you'll never get below the cost of keeping 1 pointer to that dynamic memory spot, because that's the bare minimum amount of information needed to access anything in that block of memory. However, in ultra-tight memory constraint scenarios, this tends to be the special case (dynamic memory and ultra-tight memory constraints tend to not appear in the same situations).

Answer 11

In many situations pointers actually save memory. A common alternative to using pointers is to make a copy of a data structure. A full copy of a data structure will be bigger than a pointer.

One example of a time critical application is a network stack. A good network stack will be designed to be "zero copy" - and to do this requires clever use of pointers.