# What does “map” mean?

I have encountered the term many times, in various CS education materials:

1. L2 CS162 (UC Berkeley):

Memory-mapped I/O

2. L4 CS162 (UC Berkeley):

Memory mapped files

3. L24 CS61 (UC Berkeley):

“Memory mapped I/O”: Device control/data registers mapped to CPU address space

4. Even, after googling "mapping", I got the article Map_(higher-order_function), but it wasn't very clear to me.
5. Even more, tried to understand the meaning in the context of bitmap by reading the Wikipedia article:

A bit array is a mapping from some domain (almost always a range of integers) to values in the set {0, 1}

I'm not sure, but in the context above it sounds to me about data conversion.

6. Later after reading a CS book, I found only this paragraph but it didn't explain the meaning of "mapping" for me:

Memory Mapping Linux (along with other forms of Unix) initializes the contents of a virtual memory area by associating it with an object on disk, a process known as memory mapping.

7. I got also MapReduce as a search result: where map is explained as "an idiom in parallel computing where a simple operation is applied to all elements of a sequence, potentially in parallel".

I'm still confused about the term. Can anyone explain what does "map" mean in the contexts I mentioned?

So, there are two distinct uses of the word "map", that I'll unpack here.

1. The first is very generic, where map means "to associate," particularly by way of a function. If we say "$f$ maps each $x$ to $2x$", then we're saying $\forall x \ldotp f(x) = 2x$.

This usage includes "memory mapped IO:" there is a (conceptual) function associating each piece of memory with a particular IO action. Nobody actually ever writes out the function, but it is indeed there: for each piece of mapped memory, there's some IO associated with it. Maybe a part of a disk, maybe a hardware register on a peripheral, etc.

Likewise, bit arrays (and arrays in general) fall into this: each index has a single element associated with it (at any given time), so an array is effectively an encoding of a finite-domain function.

2. In functional programming and derivatives (such as MapReduce), map refers to applying a transformation across a structure.

The original map comes from Lisp, where it referred to the function that took another function and a list, and returned the result of applying the function to each element of that list.

But, this phenomenon is quite general. In Haskell, a data structure that admits such an operation is called a functor, and the operation is called fmap (for historical reasons, to avoid conflicts with the list map).

These all are related through the concept of a Functor from category theory, which is an abstraction of structures admitting a "map" operation.

• (Typo in the Functor link name - too little to suggest an edit.) – Mat Jan 4 '18 at 12:17
• Very clear and excellent explanation. However I didn't understand what does 'finite function' mean. – Kais Jan 4 '18 at 15:26
• @Kais 'finite function' is most commonly used for a function for which no element is mapped to infinity. I guess jmite wanted to highlight that arrays are basically functions mapping the set of (valid) indices to the contained values. – Michael Hoff Jan 4 '18 at 16:02
• The two uses are really just aspects of the same thing. The map function returns a result where each element is associated with the corresponding element of the input. The distinction is that the first use describes an existing relationship, while the second refers to an operation that creates the relationship. – Barmar Jan 4 '18 at 16:41
• Typo: Fucntor – Barmar Jan 4 '18 at 16:42

In the following I am going to be less than accurate in a number of ways, sacrificing technical accuracy to provide a basic understanding. It is obvious that you have read a number of technical sources and the very technicalness of the material is making it difficult for you to understand what is a fairly basic and simple concept.

In simple terms the most common use of the word map is to describe a relationship between the things in two different sets. This may be a mathematical function or it may be some other kind of representation and mechanism. The most common that comes immediately to mind is the street map.

A street map is a picture of a particular terrain or area in the real world in which the lines and drawings and words written on the map correspond to actual physical streets and buildings. There is a one to one relationship between the representation of the terrain that is pictured in the street map and the actual terrain.

Looking further we can also see that a street map is a representation of the actual terrain. The actual terrain has objects and details and dynamic processes which the street map does not depict. The street map is an abstract representation of the actual terrain and what is depicted in the street map is only what is needed to fulfill its purpose, to provide a navigational aid for the real terrain.

A number of the examples in the question involve creating a representation with supporting mechanisms so that a person can use the representation and the mechanism translates the person's actions into what is needed for the underlying functionality that is hidden by the facade of the representation.

Memory mapped file I/O allows a programmer to think of a file as a large area of memory, to use a memory representation of a real file. The programmer does not think of the file as a file but instead thinks of it as a large area of memory. The memory mapped file I/O functionality takes care to make sure that when the programmer references a particular memory offset that the corresponding data in the file is accessed.

Memory mapped device I/O allows a device programming interface to be simplified by writing to memory addresses or reading from memory addresses. These writing and reading actions are translated by the underlying memory mapped device I/O functionality into the actual device specific actions needed to carry out the requested service or action.

A bit map is a set of bits which provide a one to one correspondence to the values of some other set. For example the CreateFile() function of the Win32 API has several bit map arguments that are used to indicate different kinds of file attributes. Specific bits in a bit map correspond to a specific file behavior such as "Open as Read Only" or "Always Create New Empty File". Special constants are provided which are combined using binary bit operations to specify the actual arguments. See CreateFile function and the example source code at Opening a File for Reading or Writing.

• Great explanation. However concerning the Memory mapped file I/O, is it an alternative to standard file i/o (fopen, fgetc ..)? is the performance advantage due to the nature of RAM faster access compared to Disks? – Kais Jan 4 '18 at 15:01
• @Kais Memory Mapped File I/O (MMF) is an alternative to using standard file API calls. There may or may not be a performance advantage to using MMF. It really depends on how well the mechanics of MMF fits the way you are using the file contents as well as how large the file is. MMF I/O pages areas of the file into memory in large blocks. You can do something similar with file API and make a significant performance difference. With standard file API I/O there tends to be a lot of copying between memory buffers from kernel space to user space that is often bypassed with MMF. – Richard Chambers Jan 4 '18 at 15:44
• @Kais not sure what you are asking. Copying data from one memory location to another takes time and CPU cycles so reducing copying of data improves performance when accessing data. The file I/O is general purpose and internally does its own caching and paging of file contents however typically the size of the memory buffers is smaller than what is used with Memory Mapped File I/O. The file API tends to be oriented towards favoring I/O of smallish chunks rather than large blocks. Sequential access tends to be favored with a look ahead within the file I/O stack and kernel. – Richard Chambers Jan 4 '18 at 16:05
• @Kais so if you can provide a hint to the file I/O API then you can improve the performance of your application that is using the file I/O API when the file I/O is a performance bottleneck. And using Memory Mapped File I/O may also help especially with mostly sequential access and operations that are within a single MMF page size. See the material and links at this URL about low level I/O with GNU C gnu.org/software/libc/manual/html_node/… which describes some of the GNU lower level mechanics. – Richard Chambers Jan 4 '18 at 16:15
• @Kais I have seen significant performance improvements with the C Standard Library file API by using the setbuf() function to set a large file I/O buffer. Anything you can do to reduce accessing the storage device tends to be a bonus. For disk drives reducing the number of seeks can make a big difference however there are a number of influences that you can't do much about such as how data is organized on disk platters, rotation speed of the platters, head movement speed, caching of data, how well cache hits reduce going to the electro-mechanical disk, etc. – Richard Chambers Jan 4 '18 at 17:16

Mapping is simply the process of associating one unit of data with another unit of data. The intent of mapping is to allow simplified access to the mapped data. For example, in classic IBM-compatible systems, the memory address 0xB8000 was mapped to the video memory of the video card. Writing to this memory would update the contents of the screen, and reading from it would retrieve the contents of the screen. File mapping, device mapping, and even data-structure mapping (typically called a Map, HashMap, or Dictionary), are all ways of associating one unit of data with another unit of data.

Mapping has two primary benefits. The first is that mapping reduces the complexity of accessing the associated device or file. For example, file mapping and device mapping allow you to treat those devices as if they were just plain memory. Instead of learning various I/O ports, data commands, and so on, you get one simple interface that is just as natural and obvious as writing to RAM.

The second benefit is that it can reduce memory requirements. For example, a Map<Integer, SomeDataType> can produce a "sparse array", which is useful where you want an array that will mostly contain invalid/unused data, and can be accessed in near-linear time. This can be far more efficient than a linked list (where it takes O(n) time to access the n-th element).

Mapping is primarily used as an abstraction to hide complicated algorithms/functions from the developer so they can focus on the task of implementing the program. Note that mapping may not always be as efficient, in terms of processing time, as accessing the device or file directly, but is always less complicated than doing so (e.g. the mapping reduces the amount of specialized code the developer must write to access the data).

• Thanks for the explanation. However I didn't understand what does "sparse array" mean, and how it is more efficient. – Kais Jan 4 '18 at 20:55
• @Kais A sparse array is a list that consists of mostly zero values. Instead of storing all the values in memory, a sparse array only stores the non-zero values in memory. By doing this, it is more efficient than simply allocating all the memory at once. Sparse arrays should typically be about 75% empty in order save space. Virtual memory often works this way as well, where the OS only stores "dirty" pages of memory, as well as file systems that allow you to store only sectors of non-zero values. – phyrfox Jan 4 '18 at 22:18