Monday, February 6, 2012


Link List facts in modern computer system 

This question has been bugging me for the last few days. Why would anyone use a linked-list instead of arrays? I argue that linked lists have become irrelevant in the context of a modern computer system. I have asked around a few colleagues and I include their counter arguments and my rebuttal for your reference. Please point out if I am missing something.

Lists have several disadvantages that did not exist in traditional systems:

1.They reduce the benefit of out-of-order execution. 

Out-of-order execution gains a lot of benefit by parallelizing independent memory accesses. Accesses in linked lists are dependent as the address of each node is only known after the current element has been loaded into the cache. This effectively eliminates the benefit of out-of-order executing when traversing the list. 

2. They throw off hardware pre-fetching

Most processors today employ hardware pre-fetchers. Hardware pre-fetchers are good at pre-fetching regular data such as arrays but they are unable to pre-fetch linked data structures.

<    3.They reduce DRAM and TLB locality

Linked lists spread data elements all over the memory. Consecutive elements can be in different DRAM pages. Since modern DRAMs take 3x more cycles to fetch random memory locations, each memory access of a linked list is potentially more expensive (Explained in my post on What every programmer should know about the DRAM memory). For the same reason, a more dispersed memory footprint requires more pages to be brought into the DRAM memory which increases the usage of physical memory. Lastly, if the list is dispersed across more pages, there are a larger number of TLB misses with a list.

      4. They cannot leverage SIMD.

In operations like lookup, multiple elements of an array can be compared to a value using a single SIMD instruction. Since elements in a linked list have to be fetched one at a time, it is unable to use the power-efficient SIMD model.

      5.     They are harder to send of GPUs. 

Today’s GPUs have a different memory address space than the CPU. Thus, when sending a data over to the GPU, all pointers have to convert from one memory space to the other. Linked lists have lots of pointers which makes it considerable expensive to send then to the GPU. Note: This advantage will go away once GPUs share the virtual memory with the CPU. When I gave the above reasons to my colleagues, they gave me some counter arguments about why linked lists are better.
Below are their list and my rebuttal to each point

<1.    Re-sizable Linked lists can be sized dynamically.

  My argument: Array with amortized doubling has solved this problem.

<2.   Different element types Linked lists are superior to arrays as they allow each node to be of a   different type.

My argument: I agree except that this property is rarely exploited.

<3. Cheaper insertions at the ends it is cheaper to insert an element at the head or tail of a list.

 My argument: Arrays can be used with a head and tail pointers and buffers at both ends for faster insertions.

<4.Cheaper insertions in the middle in ordered lists, inserts are often needed in the middle of the data structure. A link list insert is cheaper as on average it requires traversing only 1/2 of the list, finding the right spot, and inserting the node. Inserting in an array seems expensive because it requires traversing half of the array to find the insertion point and then shifting the other half of the array to make space for the incoming element.

My argument: The analysis is naive. Arrays are actually faster. Improved memory-level parallelism, locality, pre-fetching, and the ability to use SIMD far offsets the fact that arrays requires 2x the operations.

<5.  Pointers in the middle we can have jump pointers to make list accesses faster.
     
      My argument: This is called a hash table, not a list.
Do you have any other arguments that support the linked lists?


Saturday, September 17, 2011

C storage classes



The "storage class" of a variable determines whether the item has a "global" or "local" lifetime. C calls these two lifetimes "static" and "automatic." An item with a global lifetime exists and has a value throughout the execution of the program. All functions have global lifetimes.
Automatic variables, or variables with local lifetimes, are allocated new storage each time execution control passes to the block in which they are defined. When execution returns, the variables no longer have meaningful values.
C provides the following storage-class specifiers:

storage-class-specifier:
auto
register
static
extern
typedef


Items declared with the auto or register specifier have local lifetimes. Items declared with the static or extern specifier have global lifetimes.
Since typedef and __declspec are semantically different from the other four storage-class-specifier terminals, they are discussed separately. For specific information on typedef, see Typedef Declarations. For specific information on __declspec, see Extended Storage-Class Attributes.
The placement of variable and function declarations within source files also affects storage class and visibility. Declarations outside all function definitions are said to appear at the "external level." Declarations within function definitions appear at the "internal level."
The exact meaning of each storage-class specifier depends on two factors:
  • Whether the declaration appears at the external or internal level
  • Whether the item being declared is a variable or a function
Storage-Class Specifiers for External-Level Declarations and Storage-Class Specifiers for Internal-Level Declarations describe the storage-class-specifier terminals in each kind of declaration and explain the default behavior when the storage-class-specifier is omitted from a variable. Storage-Class Specifiers with Function Declarations discusses storage-class specifiers used with functions.



Storage-Class Specifiers for External-Level Declarations


External variables are variables at file scope. They are defined outside any function, and they are potentially available to many functions. Functions can only be defined at the external level and, therefore, cannot be nested. By default, all references to external variables and functions of the same name are references to the same object, which means they have "external linkage." (You can use the static keyword to override this. See information later in this section for more details on static.)
Variable declarations at the external level are either definitions of variables ("defining declarations"), or references to variables defined elsewhere ("referencing declarations").
An external variable declaration that also initializes the variable (implicitly or explicitly) is a defining declaration of the variable. A definition at the external level can take several forms:
  • A variable that you declare with the static storage-class specifier. You can explicitly initialize the static variable with a constant expression, as described in Initialization. If you omit the initializer, the variable is initialized to 0 by default. For example, these two statements are both considered definitions of the variable k.
    static int k = 16;
    static int k;
    
  • A variable that you explicitly initialize at the external level. For example, int j = 3; is a definition of the variable j.
In variable declarations at the external level (that is, outside all functions), you can use the static or extern storage-class specifier or omit the storage-class specifier entirely. You cannot use the auto and register storage-class-specifier terminals at the external level.
Once a variable is defined at the external level, it is visible throughout the rest of the translation unit. The variable is not visible prior to its declaration in the same source file. Also, it is not visible in other source files of the program, unless a referencing declaration makes it visible, as described below.
The rules relating to static include:
  • Variables declared outside all blocks without the static keyword always retain their values throughout the program. To restrict their access to a particular translation unit, you must use the static keyword. This gives them "internal linkage." To make them global to an entire program, omit the explicit storage class or use the keyword extern (see the rules in the next list). This gives them "external linkage." Internal and external linkage are also discussed in Linkage.
  • You can define a variable at the external level only once within a program. You can define another variable with the same name and the static storage-class specifier in a different translation unit. Since each static definition is visible only within its own translation unit, no conflict occurs. This provides a useful way to hide identifier names that must be shared among functions of a single translation unit, but not visible to other translation units.
  • The static storage-class specifier can apply to functions as well. If you declare a function static, its name is invisible outside of the file in which it is declared.
The rules for using extern are:
  • The extern storage-class specifier declares a reference to a variable defined elsewhere. You can use an extern declaration to make a definition in another source file visible, or to make a variable visible prior to its definition in the same source file. Once you have declared a reference to the variable at the external level, the variable is visible throughout the remainder of the translation unit in which the declared reference occurs.
  • For an extern reference to be valid, the variable it refers to must be defined once, and only once, at the external level. This definition (without the extern storage class) can be in any of the translation units that make up the program.

Example

The example below illustrates external declarations:
/******************************************************************
                      SOURCE FILE ONE 
*******************************************************************/
#include <stdio.h>

extern int i;                // Reference to i, defined below 
void next( void );           // Function prototype            

int main()
{
    i++;
    printf_s( "%d\n", i );   // i equals 4 
    next();
}

int i = 3;                  // Definition of i

void next( void )
{
    i++;
    printf_s( "%d\n", i );  // i equals 5
    other();
}

/******************************************************************
                      SOURCE FILE TWO 
*******************************************************************/
#include <stdio.h>

extern int i;              // Reference to i in 
                           // first source file 
void other( void )
{
    i++;
    printf_s( "%d\n", i ); // i equals 6 
}
The two source files in this example contain a total of three external declarations of i. Only one declaration is a "defining declaration." That declaration,
int i = 3;
defines the global variable i and initializes it with initial value 3. The "referencing" declaration of i at the top of the first source file using extern makes the global variable visible prior to its defining declaration in the file. The referencing declaration of i in the second source file also makes the variable visible in that source file. If a defining instance for a variable is not provided in the translation unit, the compiler assumes there is an
extern int x;
referencing declaration and that a defining reference
int x = 0;
appears in another translation unit of the program.
All three functions, main, next, and other, perform the same task: they increase i and print it. The values 4, 5, and 6 are printed.
If the variable i had not been initialized, it would have been set to 0 automatically. In this case, the values 1, 2, and 3 would have been printed. See Initialization for information about variable initialization.

Storage-Class Specifiers for Internal-Level Declarations


You can use any of four storage-class-specifier terminals for variable declarations at the internal level. When you omit the storage-class-specifier from such a declaration, the default storage class is auto. Therefore, the keyword auto is rarely seen in a C program.

1)auto Storage-Class Specifier


The auto storage-class specifier declares an automatic variable, a variable with a local lifetime. An auto variable is visible only in the block in which it is declared. Declarations of auto variables can include initializers, as discussed in Initialization. Since variables with auto storage class are not initialized automatically, you should either explicitly initialize them when you declare them, or assign them initial values in statements within the block. The values of uninitialized auto variables are undefined. (A local variable of auto or register storage class is initialized each time it comes in scope if an initializer is given.)
An internal static variable (a static variable with local or block scope) can be initialized with the address of any external or static item, but not with the address of another auto item, because the address of an auto item is not a constant.

2)The register Storage-Class Specifier

register is used to define local variables that should be stored in a register instead of RAM. This means that the variable has a maximum size equal to the register size (usually one word) and cant have the unary '&' operator applied to it (as it does not have a memory location).
	{
	  register int  Miles;
	}
Register should only be used for variables that require quick access - such as counters. It should also be noted that defining 'register' goes not mean that the variable will be stored in a register. It means that it MIGHT be stored in a register - depending on hardware and implimentation restrictions.

3)Static - Storage Class

static is the default storage class for global variables. The two variables below (count and road) both have a static storage class.


     static int Count;
     int Road;

     main()
     {
       printf("%d\n", Count);
       printf("%d\n", Road);
     }
'static' can also be defined within a function. If this is done, the variable is initalised at compilation time and retains its value between calls. Because it is initialsed at compilation time, the initalistation value must be a constant. This is serious stuff - tread with care.


     void Func(void)
     {
       static Count=1;
     }
Here is an example
There is one very important use for 'static'. Consider this bit of code.


     char *Func(void);

     main()
     {
       char *Text1;
       Text1 = Func();
     }

     char *Func(void)
     {
       char Text2[10]="martin";
       return(Text2);
     }
'Func' returns a pointer to the memory location where 'Text2' starts BUT Text2 has a storage class of auto and will disappear when we exit the function and could be overwritten by something else. The answer is to specify:


     static char Text[10]="martin";
The storage assigned to 'Text2' will remain reserved for the duration if the program.

4)Extern - storage Class

extern defines a global variable that is visable to ALL object modules. When you use 'extern' the variable cannot be initalized as all it does is point the variable name at a storage location that has been previously defined.
 	Source 1				Source 2
        --------				--------


	extern int count;			int count=5;

        write()					main()
        {					{
          printf("count is %d\n", count);	  write();
        }					}
Count in 'source 1' will have a value of 5. If source 1 changes the value of count - source 2 will see the new value. Here are some example source files.  
Source 1
Source 2

Storage-Class Specifiers with Function Declarations


You can use either the static or the extern storage-class specifier in function declarations. Functions always have global lifetimes. Microsoft Specific
Function declarations at the internal level have the same meaning as function declarations at the external level. This means that a function is visible from its point of declaration throughout the rest of the translation unit even if it is declared at local scope.
The visibility rules for functions vary slightly from the rules for variables, as follows:
  • A function declared to be static is visible only within the source file in which it is defined. Functions in the same source file can call the static function, but functions in other source files cannot access it directly by name. You can declare another static function with the same name in a different source file without conflict.
  • Functions declared as extern are visible throughout all source files in the program (unless you later redeclare such a function as static). Any function can call an extern function.
  • Function declarations that omit the storage-class specifier are extern by default.