Tag Info

28

Storing local variables on a stack is an implementation detail – basically an optimization. You can think of it this way. When entering a function, space for all local variables is allocated somewhere. You can then access all variables, since you know their location somehow (this is part of the process of allocation). When leaving a function, the space is ...

26

Having y on the stack doesn't physically prevent x from being accessed, which, as you pointed out, makes computer stacks different from other stacks. When a program is compiled, the positions of variables in the stack are also predetermined (within the context of a function). In your example, if the stack contains an x with a y "on top of" it, then the ...

21

I can see why you're confused. The diagram is a bit confusing, and may actually be incorrect. First off, let's think about why a kernel needs a memory allocator below the level of pages. This is probably already stuff that you mostly know, but I'll go through it for completeness. Pages are the typical "unit" of memory operations. When a user-space ...

16

The subject you're describing often goes under the names computer architecture, computer systems, computer organization and design, and the like. One example is Elements of computing systems, based on a course From Nand to Tetris originating in the Hebrew University. The Amazon page on the book links to other popular textbooks on the topic. Generally ...

15

The entries of a hash table are stored in an array. However, you have misunderstood the application of the modulo operator to the hash values. If the hash table is stored in an array of size $n$, then the hash function is computed modulo $n$, regardless of how many items are currently stored in the table. So, in your example, if you were storing ...

14

To provide a concrete example of how a compiler manages the stack and how values on the stack are accessed, we can look at visual depictions, plus code generated by GCC in a Linux environment with i386 as the target architecture. 1. Stack frames As you know, the stack is a location in the address space of a running process that is used by functions, or ...

9

Hash-table usually do waste space. Many algorithms do, since time-space trade-offs are common, but they usually hide it better :). Like other algorithms, hash-tables do it to get better time performance. The first point is that you try to avoid collisions in your hash-table, because that keeps the access time cost constant (but collisions are usually ...

9

There are two special registers: ESP (stack pointer) and EBP (base pointer). When a procedure is invoked the first two operations are usually push ebp mov ebp,esp The first operation saves the value of the EBP on the stack, and the second operation loads the value of the stack pointer into the base pointer (to access the local variables). ...

9

You are confused because the local variables stored in stack are not accessed with the access rule of stack: First In Last Out, or just FILO. The thing is that the FILO rule applies to function call sequences and stack frames, rather than to local variables. What is a stack frame? When you enter a function, it is given some amount of memory on the stack, ...

8

Network latency is orders of magnitude too high for a remote server to usefully share its RAM directly, even if you could cobble together a virtualization layer to make it work. However, today's network speeds are high enough that remote RAM based key/value stores like memcached can compete favorably with hammering a local database due to insufficient local ...

7

Heap allocators typically call a system call to reserve a region of pages and then dole out chunks of that to new, malloc, and other higher-level calls. The system call on Unix used to be brk and sbrk, but implementations sometimes use mmap as well. I think windows uses VirtualAlloc, but it's not totally clear to me. A good resource for this is Wikipedia's ...

6

The idea underneath the slab allocator is that the operating system needs specific but somewhat standard data structures (for example the process PCB, semaphores, file metadata etc) that suggest the memory usage that is necessary for them. The slab allocator algorithm provides stocks of memory areas whose dimensions and initialization are optimized for ...

5

This is really a question about memory allocators and doesn't have much to do with operating systems. "Memory control block" does seem to be a DOS specific term for a node in a free list. I'm not aware of any broadly used term for those nodes. They are usually just called "free blocks" or "unallocated blocks" or some such. An operating system kernel ...

5

Short answer, summarizing the other answers: It is done by the operating system. Simple (early) operating systems assigned fixed size areas for code, data, stack + heap (with the idea that the stack and heap grew towards each other). Early Unix systems had a space for the stack and an area for data, used also by the heap (which could be extended with the ...

5

RAM is cleared after each power cycle. The power-up value of cells depends on the technology. Static RAM content is usually random (there is no preference between 0 and 1, but the same chip may present similar patterns after each power-up). Dynamic RAM has the value corresponding to empty capacitors in the RAM array, which usually corresponds to ones, but ...

4

First there is the answer already given by André Souza Lemos. The data need not be destroyed. It is usually sufficient to mark the corresponding space as unused in some table, so that the system will no longer try to read it: it considers that there is nothing stored there. But the data is often still there, often fairly easy to find, even when some key ...

4

Deleting is not necessarily destroying data. It can be done (much faster, indeed) by making it inaccessible. You can do it by erasing critical information from the data structures that are used to index the data you want to delete. How exactly this is done depends on how the storage device is organized (formatted).

4

According to https://lwn.net/Articles/211505/, what you imagine should be done by the OS, is already done: Since Linux is a virtual memory system, fragmentation normally is not a problem; physically scattered memory can be made virtually contiguous by way of the page tables. There are limits to this, as hardware devices may request contiguous hardware ...

4

The way you access the array affects performance. It depends on how the matrix is represented and stored in memory. Often a matrix is stored in row-major order, so that consecutive elements of a row are contiguous in memory. Reading memory in contiguous locations is faster than jumping around among locations. As a result, if the matrix is stored in row-...

4

There are many ways to implement local variables by a language runtime system. Using a stack is a common efficient solution, used in many practical cases. Intuitively, a stack pointer sp is kept around at runtime (in a fixed address, or in a register -- it does really matter). Assume that every "push" increments the stack pointer. At compile time, the ...

4

Row-major order stores the rows of the array one after another in memory. That is, the array a d g j b e h k c f i l is stored as a d g j b e h k c f i l To determine the address of an element in this list, we need to know how many elements come before it. For element $[I,J]$, this is the number of complete rows above row $I$ times the length of a ...

4

Yes, it is certainly possible. It really depends if you want it enough to pay the price in terms of complication. First of all, I would strongly recommend that your array should have negative indices: a[-1], a[-2], and so on. This will be good because the stack grows downwards, and if you adopt this convention then you will not need to move all your ...

3

Quick note, sizeof(char) is defined to be 1. So you can just simplify to malloc(1). The real answer however is quite boring. Your program has what's so called undefined behavior. In C (and C++), if you make an error like this the result is undefined. This could mean that your program will crash right as you trigger the bug. But it doesn't necessarily crash. ...

3

"Local variable" is a concept in the source language. Some target languages have the concept (e.g. virtual machines with dictionary-based scopes), but many do not. Since you're using Java, let's look at the JVM. A local variable cannot be accessed by other methods (e.g. you can't pass a variable by reference like you can in C++ or Fortran), and cannot be ...

3

There is no single standard implementation of JavaScript, so if you want to know what happens in a particular implementation, you should use your web search skills, focusing your efforts on that particular implementation. That said, a cursory web search reveals two main points: Arrays can be implemented simply as associative arrays (also known as hash ...

3

A good way to look at hash tables is like a lookup table with infinite index range (well, not really infinite, you're still constrained by the value limit of the key you're using). Lets say you're trying to store some specific values of sqrt(x) in a lookup table where X is an integer, it would go something like this: [1] = 1 [3] = 1.732 [10000] = 100 This ...

3

The easiest idea is to think of variables as fix names for addresses in memory. Indeed, some assemblers display machine code that way ("store value 5 in address i", where i is a variable name). Some of these addresses are "absolute", like global variables, some are "relative", like local variables. Variables (i.e. addresses) in functions are relative to ...

3

what would the worst-case complexity be if it didn't have to copy over $n$ items? If it only needed to allocate a buffer with size $O(n)$ when resizing, would that be considered to run $O(1)$ or $O(n)$ time? This depends on what you mean by "allocate a buffer with size $O(n)$" and how much time that takes. Unfortunately, there isn't a standard answer for ...

3

In your second example, you allocate space for a PrimeSet object and initialise it, then you call the countPrimeNumbers function. The PrimeSet object still exists, it still occupies memory, it probably allocated more memory, and all that memory is still occupied but not accessible. That’s a memory leak: Memory that is occupied but unusable.

2

To answer your question 1, the short answer is yes. The long answer is when an executable is linked, there are also fields in the executable header (For Unix and Unix-Like operating systems, it's ELF. Windows uses PE32/64 for 32-bit and 64-bit.) that determine the initial size of the static data area, the stack, and the heap. For your question 2, the ...

Only top voted, non community-wiki answers of a minimum length are eligible