Competitive/Collaborative Programming Class

Continuum of a Program

If you look a program, you will see data and code -- logical. Have you ever thought about their interrelationships?

The choice of data structure predestines some of the code. The choice of some code predestines some data structures. In fact, the two could be perceived as opposite ends of a continuum. When you design/implement a program, you choose what to do. Consider that choice a slider on a scale. It can be heavy data structure and lighter code or the other way around.

Programs can be optimized for speed or for data usage (usually these goals are diametrically opposed).

Here are 3 different implementations that produce the same result:

Nested If Statements

if (1 == i)
 { total = total + 17; }
else if (2 == i)
 { total = total + 29; }
else if (3 == i)
 { total = total + 99; }

Case Statement

switch (i)
 { // switch
 case 1: total = total + 17; break;
 case 2: total = total + 29; break;
 case 3: total = total + 99; break;
 } // switch
 

Array Implementation

 int ary[4] {0, 17, 29, 99};


 total = total + ary[i];
 

        movq    %rsp, %rbp      #,
        .cfi_def_cfa_register 6
        cmpl    $1, -8(%rbp)    #, i
        jne     .L2     #,
        addl    $17, -4(%rbp)   #, total
        jmp     .L3     #
.L2:
        cmpl    $2, -8(%rbp)    #, i
        jne     .L4     #,
        addl    $29, -4(%rbp)   #, total
        jmp     .L3     #
.L4:
        cmpl    $3, -8(%rbp)    #, i
        jne     .L3     #,
        addl    $99, -4(%rbp)   #, total
.L3:
        movl    $0, %eax        #, D.2060
        leave
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:

        movq    %rsp, %rbp      #,
        .cfi_def_cfa_register 6
        movl    -8(%rbp), %eax  # i, tmp60
        cmpl    $2, %eax        #, tmp60
        je      .L4     #,
        cmpl    $3, %eax        #, tmp60
        je      .L5     #,
        cmpl    $1, %eax        #, tmp60
        jne     .L2     #,
.L3:
        addl    $17, -4(%rbp)   #, total
        jmp     .L2     #
.L4:
        addl    $29, -4(%rbp)   #, total
        jmp     .L2     #
.L5:
        addl    $99, -4(%rbp)   #, total
.L2:
        movl    $0, %eax        #, D.2057
        leave
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:  

        movq    %rsp, %rbp      #,
        .cfi_def_cfa_register 6
        movl    $0, -32(%rbp)   #, ary
        movl    $17, -28(%rbp)  #, ary
        movl    $29, -24(%rbp)  #, ary
        movl    $99, -20(%rbp)  #, ary
        movl    -8(%rbp), %eax  # i, i.0
        cltq
        movl    -32(%rbp,%rax,4), %eax  # ary, D.2054
        addl    %eax, -4(%rbp)  # D.2054, total
        movl    $0, %eax        #, D.2055
        leave
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:

Here are some code segments to perform the same task. Look at them.

#define LEFT 0
#define RIGHT 1

#define NORTH 0
#define EAST  1
#define SOUTH 2
#define WEST  3

/* direction is left or right */
.
.
.
if (NORTH == curMove)
   if (LEFT == direction)
      nextMove = WEST;
   else
      nextMove = EAST;
else
if (EAST == curMove)
   if (LEFT == direction)
      nextMove = NORTH;
   else
      nextMove = SOUTH;
else
if (SOUTH == curMove)
   if (LEFT == direction)
      nextMove = EAST;
   else
      nextMove = WEST;
else
if (WEST == curMove)
   if (LEFT == direction)
      nextMove = SOUTH;
   else
      nextMove = NORTH;

#define LEFT 0
#define RIGHT 1

#define NORTH 0
#define EAST  1
#define SOUTH 2
#define WEST  3

/* direction is left or right */
.
.
.
switch (curMove)
 { // switch
   case NORTH: 
        if (LEFT == direction)
           nextMove = WEST;
        else
           nextMove = EAST;
        break;
   case EAST: 
        if (LEFT == direction)
           nextMove = NORTH;
        else
           nextMove = SOUTH;
        break;
   case SOUTH: 
        if (LEFT == direction)
           nextMove = EAST;
        else
           nextMove = WEST;
        break;
   case WEST: 
        if (LEFT == direction)
           nextMove = SOUTH;
        else
           nextMove = NORTH;
        break;
 } // switch

#define LEFT 0
#define RIGHT 1

#define NORTH 0
#define EAST  1
#define SOUTH 2
#define WEST  3

int next[4][2];

next[NORTH][LEFT]  = WEST;
next[NORTH][RIGHT] = EAST;
next[EAST][LEFT]   = NORTH;
next[EAST][RIGHT]  = SOUTH;
next[SOUTH][LEFT]  = EAST;
next[SOUTH][RIGHT] = WEST;
next[WEST][LEFT]   = SOUTH;
next[WEST][RIGHT]  = NORTH;

/* direction is left or right */
.
.
.
nextMove = next[curMove][direction];

#define LEFT 0
#define RIGHT 1

#define NORTH 0
#define EAST  2
#define SOUTH 4
#define WEST  6

int next[8];

next[NORTH + LEFT]  = WEST;
next[NORTH + RIGHT] = EAST;
next[EAST  + LEFT]  = NORTH;
next[EAST  + RIGHT] = SOUTH;
next[SOUTH + LEFT]  = EAST;
next[SOUTH + RIGHT] = WEST;
next[WEST  + LEFT]  = SOUTH;
next[WEST  + RIGHT] = NORTH;

/* direction is left or right */
.
.
.
nextMove = next[curMove + direction];

#define LEFT  3
#define RIGHT 1

#define NORTH 0
#define EAST  1
#define SOUTH 2
#define WEST  3

/* direction is left or right */
.
.
.
nextMove = (curMove + direction) MOD 4;

Above are five different ways of doing the same thing. Consider the code.

Realize that computers (cpus) tend to have many common features even though they do differ in implementation. Here are some of the features that are common but differ in size:

• Number of registers
• cache size
• combined cache vs. separate data/code cache
• cache sizes
• virtual memory implementation
• page sizes
• pipelining/prefetch
• number of cores
• number of processors
• number of caches

Reducing size of code and data after compilation increases the probability that the code/data will be in cache (dramatically improving runtime. Branching can destroy performance by not using prefetch or clearing a pipeline.