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; }
elseif (2 == i)
{ total = total + 29; }
elseif (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];
Here are some code segments to perform the same task. Look at them.
| Nested ifs | Using case: |
|---|---|
#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
|
| Using 2D array | Using 1D array |
#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]; |
| Using clock arithmetic | |
#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.