Talk:Overlay (programming)

From Wikipedia, the free encyclopedia

[edit] About that merge

I reverted the changes to this article, but I left standing the change of Overlays to a redirect, and I'm about to remove the mergefrom tag from here. There was really nothing in the other article worth saving and a fair share of what it had to say was misleading. Atlant 17:21, 13 July 2006 (UTC)

I thought my merge was cleaner. Why not restore the many wiki links that you reverted? Which is clearer:

Mine: This operation is similar to virtual memory, but is not fully automatic or transparent to the programmer in the same way; instead, the overlay strategy...

Revert: This operation is similar to virtual memory, but is not usually not fully-automatic or transparent to the programmer; instead, the overlay strategy...

Shouldn't this be a compsci stub like I had it? I think you may want to go back and pick and choose the reverts you're not happy with, it is not all junk. — RevRagnarok ^{Talk Contrib Reverts} 17:37, 13 July 2006 (UTC)

The biggest problem with your merge was the overall tone. It immediately dove into the multi-pass compiler stuff, and that's only a small corner of the much larger world of overlays and what they're used for. I'd be happy to do another edit of this article, comparing your diffs, but I haven't got the time right now, and the revised article was just too far off base. Maybe this evening...

Atlant 17:45, 13 July 2006 (UTC)

[edit] Physical? Or virtual?

I'm a new wikipedian so please don't be too harsh if I'm breaking some rules. I did my homework reading through the help pages but still...

I'd like to change the article referring to Overlays because, in my opinion, the association with Virtual Memory concept is not appropriate. More, the "virtual address space" in the first sentence is wrong. It should be quite the opposite, physical memory, that I would accept.

Virtual address space is an abstract concept representing the collection of memory locations in a system with a certain number of address lines. For example, the virtual address space of a CPU with 16-bit address bus is 64K (65536) locations.

I'm open to discussions, but I think this is a better definition of Overlays.

--- Overlaying is a programming method that allows programs to be larger than the CPU's main program memory (or whatever block of memory the CPU is supposed to draw its instruction from, in case not all main memory is available at a certain moment, or not all memory is available for that program).

This method assumes dividing a program into self-contained machine code object blocks (called "overlays") not bigger than the maximum block of available program memory. The overlays are supposed to be loaded (from external memory or support where the program resides) into the CPUs main memory in order to be executed.

Embedded systems would normally use overlays because of the limitation of physical memory (internal memory for systems-on-chip). ---

Adsp 12:56, 18 January 2007 (UTC)

I'm sorry, but if you insist on "physical memory", you would be wrong. Overlays were widely used in systems that had, say, 16-bit virtual address spaces but had larger physical address spaces (for example, 22-bits). What such overlays allowed was the running of programs larger than 64K. For example, using overlays, I personally wrote a program that was about 1.5 Meg in size and still "fit" within the 64K virtual address space of a PDP-11.

Where it gets confusing is that overlays are not necessarily swapped to and from the backing storage (e.g., disk). Systems that have large amounts of physical memory will often store many or all of the overlays in physical memory, swapping them in and out of the virtual address space as needed. This process (of exchanging virtual->physical address mappings) is obviously orders of magnitude faster than swapping information to/from the disk and in such a system, you could change overlays tens or hundreds of times per second with very little performance penalty.

Be careful that you're not confusing virtual memory with virtual address space.

Atlant 13:32, 18 January 2007 (UTC)

Yes, I'm afraid I have to insist. What is the difference between virtual memory and virtual address space, then? Oh, if you mean virtual memory is a technique also known as virtual memory addressing of a contiguous space known as virtual address space, then yes, they are different. But the key concept here is virtual. And you use virtual as physical. It is physical because it does exist.

What you describe in your 16-bit / 22-bit example is more like paging. And what you call physical space in that example is actually external memory and you will use an I/O operation to select the page, which actually means that the external memory is more like a peripheral. It's external anyway, as opposed to main memory, what you actually call virtual memory (which is not virtual at all since the processor can fetch code from that memory).

I don't have a problem with memory overlays (but I want to stress external memory), it doesn't matter where they are stored (yes, it might be faster loading from external memory than from disk). But the essential idea is that they are loaded in CPU's main memory, which is physical, no doubt.

I'm not sure when the concept of virtual memory came around, but I suspect it was after the PDP-11 episode of paging (and by the way, I have done that too, on some advanced Spectrum with more than 64K memory, I don't remember what the name was). And I suspect that virtual memory was associated with CPUs that had plenty of address lines (like 32-bit machines) but memory was expensive enough to prevent physical population of the whole space (and still is, only supercomputers have 4 GB main memory, I think).

In conclusion, overlays are not so much about virtual and physical memory, it's about main memory, the overlay has to be loaded into CPUs main memory in order to be executed.
--Adsp 19:41, 18 January 2007 (UTC)

No, and your confusion between the concepts of virtual memory and virtual address space really suggests that you need to learn more about all of this before you start editing this article. So let's get definitional:

• The virtual address space is that set of addresses that the machine can simultaneously specify using its various addressing modes (and without manipulating any memory-mapping hardware). For simple machines that have a Von Neuman architecture, that's usually a single space of about the same size as the width of the registers, so 16 bits on the PDP-11, 32 bits on a VAX, Power(PC), or SPARC, and 64 bits on Alphas, UltraSPARCs, and the latest POWER chips. For Harvard architecture machines, there can be multiple virtual address spaces, for example, one for code, one for data, and on more baroque architectures such as the 8051, a few more thrown in just for confusion.

• The physical address space is that set of addresses that can be passed to the memory system and responded to.

• Virtual memory is memory that can be accessed by the processor but is not necessarily all physically present in physical memory at all times. It doesn't matter how big the virtual address space is compared to the physical address space although most interesting cases are machines that have virtual address spaces bigger (sometimes, much bigger) than the physical address space. Generally speaking, the magic that happens behind the scene to make all virtual accesses succeed (page faulting and the like) is all completely transparent to the user's program.

Overlays are a completely orthogonal concept. They are a way to manipulate memory that replaces portions of the virtual address space so that machines with a limited virtual address space can run humongous programs too. Generally speaking, overlays only turn upon machines with small virtual address spaces (such as the PDP-11 or PDP-8).

Atlant 20:38, 18 January 2007 (UTC)

You got "definitional" and to be honest there is nothing wrong in the way you explain the concepts (I didn't understand why "simultaneously", but there we are). But there is nothing conceptually different from the way I defined them (which is in fact pretty much a copy of the definition given in Wikipedia's virtual memory). You gave concepts a different outlook (which is not wrong in itself) but it proves nothing, you don't contradict the definitions I gave and you claim are wrong (because I still "need to learn more about all of this before editing" YOUR article). I think you should better re-read virtual memory and primary storage and main memory and especially paging. Because this is what you describe as overlaying from your PDP-11 experience. Maybe you called it overlaying at that time, because there was no virtual memory or paging concepts at that time.
Only by diverting the main subject towards von Neuman and Harvard won't scare me off. I know probably more than you do about those (and hardware architecture in general, I would say) since you confuse such a basic concept as main memory, defined by von Neuman.

Now, look again at your last paragraph in this talk. You believe overlaying will only be used on "machines with small virtual address spaces (such as the PDP-11 or PDP-8)". This is completely wrong and this is where your confusion comes from. Overlays are used in embedded systems (systems-on-chip) where the CPU is a 32-bit RISC and there is only some 100K or less of internal memory available in the system (and there is huge flash memory external).

If you keep saying that I'm wrong, please point out explicitly where I'm wrong before giving me your definitions and send me to read more. And return to the main subject, your definition of overlay in the main article. You say "bigger than the amount of virtual address space", I say main memory. Do you still keep to your "virtual"?

--Adsp 11:36, 19 January 2007 (UTC)

I refined my initial proposal and I intend to move towards replacing the actual main article (which I believe is wrong for the reasons above) with the following one as a basis for future collaborative expansion. I'm open to discussion if anyone believes that some of the actual article should be merged into the one I propose.

---

In general computing sense, overlaying means "replacement of a block of stored instructions or data with another" (http://www.askoxford.com/concise_oed/overlay_1?view=uk ?how to provide references?)

Overlaying is a programming method that allows programs to be larger than the CPU's main memory.

The method assumes dividing a program into self-contained object code blocks called overlays. The size of an overlay is limited according to memory constraints.

The place in memory where an overlay is loaded is called overlay region or destination region. Although the idea is to reuse the same block of main memory, multiple region systems could be defined (possibly of different sizes).

An overlay manager (possibly part of the operating system) will load the required overlay from external memory into its destination region in order to be used.

Some linkers provide support for overlays (to be extended?) http://www.gnu.org/software/binutils/manual/ld-2.9.1/html_node/ld_22.html

An embedded system would normally use overlays because of the limitation of physical memory (internal memory for a system-on-chip).

---

--Adsp 23:07, 27 January 2007 (UTC)

[edit] Overlaying is not obsolete!

Although I agree with the main idea of Sailorman2003's addition, i.e.

• the fact that overlaying is difficult to handle;
• assumes a low-level, closer to hardware point of view (not necessarily assembly language though, the linker is the important tool);
• virtual memory makes designer life much easier;

I'd like the two added paragraphs to reflect the fact that Overlaying is not an obsolete method used only before the advent of virtual memory.

Embedded systems very seldom can afford the luxury of a hardware memory manager required by any virtual memory scheme.

"Modern languages that do not allow the programmer much control over size (e.g. Java, C++, Smalltalk …)" are wonderful for applications running on desktop computers, but if the architect will avoid the Pentium for a portable music player.

--Adsp 18:45, 9 March 2007 (UTC)

Good point. Now go cite the use of overlays in such an embedded system and it'll be perfect. --Damian Yerrick (talk | stalk) 00:49, 10 March 2007 (UTC)

Just curious: in what economic environment does hardware cost more than software? You can buy a very high end system for $10,000 with all the virtual memory you can ever need; Programmers in the Northeast and West coast cost $100 per hour once all the overhead is added in. On average, the programming cost is not much less in the rest of the country. While specialized hardware does exist and still requires overlays, the embeded systems are the exception.

It is true that using a high level language like Java will have a performance cost, but with today's hardware it is well worth it for everything but special cases (e.g. drivers, operating systems...) I recently wrote a telephone billing system that rates all the call records and it handles the traffic without anhy problem. I did have to pay attention to my use of java to minimize garbage collection, but other than that, it is pure object oriented design.

That said, I do agree with the changes in the article, but think that it should mention that overlays are a very rare case at this point.--Eric 16:33, 10 March 2007 (UTC)

Embedded systems are hardly an exception. As the number of identical hardware units that run a single program reaches the millions, the cost of building the hardware begins to dwarf the cost of developing and maintaining the software, so you want to minimize hardware complexity at the cost of extra software complexity. Look at iPod and any other digital music player. When the user decides to play an MP3, the hardware loads the MP3 decoder into RAM. When the user decides to play an M4A, the hardware loads the AAC decoder into RAM. PDAs and mobile phones likewise are small enough that app-controlled code loading and unloading has its benefits. Besides, when you talk about "Northeast and West", what country are you talking about? --Damian Yerrick (talk | stalk) 16:56, 10 March 2007 (UTC)

I am talking about the US, but the same holds true for England or France as well. I am not familiar with Ipods or Cell Phones, so where are the overlays loaded from? How is memory segragated in these devices? Perhaps you should add a more detailed description of how this works and separate it from the general purpose computing that I was referring to.--Eric 20:45, 10 March 2007 (UTC)

Programmer labor is far cheaper outside the United States, Canada, Western Europe, and Japan. (See Offshore outsourcing.) The overlays would be loaded from NAND flash memory, which acts more like a disk than like a traditional ROM. --Damian Yerrick (talk | stalk) 14:17, 11 March 2007 (UTC)

I haven't gone over numbers for two years now, but no matter where you look in the world, software is more expensive than hardware edscept in the cases you mention with embeded systems. I now believe you that there are instances where overlays are needed in embeded systems, but 99% of business systems are implemented in environments where the price of VM easily pays for itself in the productivity enhancements gained.--Eric 17:49, 11 March 2007 (UTC)

But are 90% of computing devices business systems, or are they embedded systems? Take into account that video game handhelds, mobile phones, and PDAs act more like embedded systems. Even on PCs, media players store codecs in overlays so that they don't have to load in the MPEG-4 codecs while you're watching a WMV or vice versa. --Damian Yerrick (talk | stalk) 19:19, 11 March 2007 (UTC)

I am not sure what we are debating. There are orders of magnitude more programmers writing business systems than there are embeded systems. By your definition, one embeded system will be deployed in millions of cell phones. Business applications will run of a small number of computers, althought they will be complex. I still think you should add to the article and describe embededed systems in more detail. I doubt you can make a reasonable case for not using virtual memory in a business application except in very rare cuscumstances. You have made your case that overlay programming is not obsolete.--Eric 20:38, 11 March 2007 (UTC)

The fact that "There are orders of magnitude more programmers writing business systems than there are embedded systems" explains why the programmers community accepts so hard the need to write efficient code, when this means spending more programming time and paying more experienced programmers. For years we lived in a computing market where programmers have been almost encouraged to write less optimal code, or been pushed to give up refinements because the hardware advances made software improvement unnecessary. Apparently this is bound to change, see http://www.gotw.ca/publications/concurrency-ddj.htm

And yes, there are more jobs in business applications programming (or desktop as opposed to embedded systems applications), but comparing the two different markets I would say the difference is not that big. Only think about the mobile phone market (embedded) and you will understand what I'm talking about. And I suspect that the number of jobs in embedded systems will go up at a higher pace.

I agree that the article could be improved by adding more detail about how things work, but did you consider that there already is a rather exhaustive article about embedded systems?
--Adsp 11:47, 13 March 2007 (UTC)