Accessing a certain address in memory

Question

Why can we access to a certain place in our memory in O(1)?

Answer 1

Memory in modern computer systems is random access, so as long as you know the address of memory you need to access, the computer can go directly to that memory location and read/write to that location.

This is opposed to some [older] systems such as tape memory where the tape had to be physically spooled to access certain areas, thus farther locations take longer time to access.

Not sure what you mean by allocate in O(1) as allocating memory is typically not O(1) when dealing with typical heap on every day computers.

Answer 2

Quick answer: You can't!

The system's main memory, the chips on the board, can however be addressed with a direct access. Just give the correct address and the bus will return the memory at that location (likely in a block).

Once you get into the CPU however memory access is very different. There are several caches, several cores with caches, and possibly other CPUs with caches. Though accessing main memory can be done directly, it is slow, that is why we have all these caches. But this now means that inside the CPU the memory isn't directly accessible.

When the CPU needs to access memory it thus goes into a lookup mode. It also has a locking system to share memory between the caches correctly. Different addresses will actually take different periods of time to access, depending on whether you are reading or writing, and where the most recent cache of that memory resides. This is something known as NUMA (non-uniform memory access). While the time complexity here is probably bound by a constant (so possibly/technicall O(1)) it probably isn't what most people are thinking of as constant time.

It gets more complicated than this. The CPU provides page tables for memory so that the OS can provide virtual memory to the applications (that is, it can partition the address spaces) and load memory on demand. These tables are map-like structures. When you access memory the CPU decides if the address you want is loaded, or if the OS has to retrieve it first. These maps are a function of the total memory size, so are not linear time, though very likely amortized constant time. (If you're running a virtual machine you can add another layer of tables on top here -- one reason why VMs run slightly slower).

This is just a brief overview. Hopefully enough to give you the impression that memory access isn't really constant time and depends on many things. Keep in mind however that so much optimization is employed at these levels that a high-level C program will likely appear to have constant time access.

Answer 3

Why can you access in O(1)? Because memory access is by address. If you know the address you want to access, then the hardware can go directly to it and fetch whatever is there in a single operation.

As for allocations being O(1), I'm not sure that is always the case. It is up to the OS to allocate a new block of memory, and the algorithm that it uses to do that may not necessarily be O(1) in all cases. For instance, if you request a large block of memory and there is no contiguous block large enough to satisfy the request, the OS may do things like page out other data or relocate information from other processes so as to create a large enough contiguous block to satisfy the request.

Though if you want to take an extremely simplified view of allocation as being "returning the address of the first byte of available memory" then it's easy to see why that could be an O(1) operation. The system just needs to return the address of the last allocated byte + 1, so as long as it tracks what the last allocated byte is after every allocation and as long as you assume an unlimited memory space, then computing the next free address is always O(1).

Answer 4

That depends on the computing model that you use, in the Turing machine model, neither operation is O(1), in the random access model, access is O(1), which, since that is the case for most modern hardware using RAM makes that model useful. I assume you are using a model that for the sake of simplicity also allows O(1) allocation as a close approximation to most modern implementations on a machine that is under light memory usage load.