Lecture 1.2 (Program Performance)

Dept. of Information Systems Hanyang University

Program Performance

Program performance is the amount of computer memory and time needed to run a program.

• How is it determined?

1. Analytically

   • performance analysis
   • example: profiling

프로파일링 또는 성능 분석은 프로그램의 시간 복잡도 및 공간, 특정 명령어 이용, 함수 호출의 주기와 빈도 등을 측정하는 동적 프로그램 분석의 한 형태이다

2. Experimentally

   • performance measurement
   • 예를 들어서 cpu speed, mhz 같이 computer speed 는 computer performance 를 측정하는데 좋은 요인이 될 수 있다.

Criteria for Measurement

• Space

  • amount of memory program occupies
    • usually measured in bytes,KB or MB

• Time

  • execution time

    • usually measured by the number of executions

Space Complexity

Space complexity is defined as the amount of memory a program needs to run to completion.

• Why is this of concern?

  • We could be running on a multi-user system where programs are allocated a specific amount of space.

  • We may not have sufficient memory on our computer.

  • There may be multiple solutions,each having different space requirements.

  • The space complexity may define an upper bound on the data that the program can handle.

Components of Program Space

Program space = Instruction space + data space + stack space

Following is a quick diagram and comparison with the standard diagram we learned in c, with heap and stack.

<- 나중에 그릴 예정.

Instruction space

• The instruction space is dependent on several factors.

  • the compiler that generates the machine code

  • the compiler options that were set at compilation time

    • if you are curious, you could check by entering 'gcc --help' in your terminal

  • the target computer

  See Figure2.1 –which one takes the least amountof instruction space?

Data space

• very much dependent on the computer architecture and compiler

• The magnitude of the data that a program works with is another factor

Data type	Data size(in bytes)
char	1
short	2
int	4
long	4
float	4
double	8
long double	10
pointer	2

Choosing a “smaller” data type has an effect on the overall space usage of the program.

Choosing the correct type is especially important when working with arrays.

• How many bytes of memory are allocated with each of the following declarations?

double a[100];

int maze[rows][cols];

당연한 질문? 800byte, 4 rows colums

Environment Stack Space

Every time a function is called, the following data are saved on the stack.

1. the return address
   • Where to return after the end of function call
2. the values of all local variables and value formal parameters
   • formal parameters: the thing in the declaration part of the function.
3. the binding of all reference and const reference parameters
   • I guess this is talking about the reference within the function.

What is the impact of recursive function calls on the environment stack space?

Bad Use of recursive function can cause too much use of stack space. So you should be careful to use recursive function, only if needed.

An example

Lets take a look at our swap funcion example again.

void swap(int &n1, int &n2)
{
    temp = n1;
    n1 = n2;
    n2 = temp;
}

int main(void)
{
    int a =2;   //line1
    int b = 3;  //line2
    swap(a, b);     //line3
    cout <<a<<" "<<b<<endl; //line4
    return 0;   //line 5
}

Instructions, such as int a =2 or cout<<~~~ would be in instruction space.

Datas, such as constant 2 or 3 would be in Data space.

In the stack space,

• First there would be the return address, line 4 for the program to come back to main program.

• Second, there would be local variables temp that stores the value of n1.

• Third, there would be binding of reference parameters, with n1 and n2. (Not sure if I'm right with this)

Space Complexity Summary

Given what you now know about space complexity, what can you do differently to make your programs more space efficient?

• Always choose the optimal(smallest necessary) data type

• Study the compiler.

  • Compiler can tell you about the space and time complexity. Consider using '-O' option. Or 'time' command to find out about the time took.

• Learn about the effects of different compilation settings.

• Choose non-recursive algorithms when appropriate.

READ & Understand 2.2.2 Examples

Time Complexity

Time complexity is the amount of computer time a program needs to run.

Why do we care about time complexity?

• Some computers require upper limits for program execution times.

• Some programs require a real-time response.

  • If in case, response is slow, the computer thinks you are a user responding and cuts the connection. "You are not a computer, a user!"

• If there are many solutions to a problem, typically we’d like to choose the quickest.

How do we measure?
세개의 방법이 있다!!
1. Count a particular operation - operation counts
2. Count the number of steps - step counts
3. Asymptotic complexity
- 점근적인. Something like lim -> goes to infinity.

Running Example: Insertion Sort

You could see the visuals here

for (int i = 1; i < n; i++) // n is the number of elements in array

{

// insert a[i] into a[0:i-1]

    int t = a[i];

    int j;

    for (j = i - 1; j >= 0 && t < a[j]; j--)
    //t< a[j] comparison could be the particular operation

        a[j + 1] = a[j]; 
    
    a[j + 1] = t;

}

Operation Count

Count a particular operation!

• Pick an instance characteristic ... n, n = the number of elements in case of insertion sort.
• Determine count as a function of this instance characteristic.

So what is an instance characteristic?

An instance characteristic is a measure(typically with integer value) of the magnitude of an instance of the problem.
It's essentially a function whose domain is a set of problems and whose range is the set of nonnegative integers.

Following is the source code of insertion sort with only the instance characteristic.

사실 말이 어렵지만 그냥 직관적으로 하나의 작업을 골라서 그걸 통해서 O(n)을 만드는 느낌인듯?

//counts only comparisons
for (int i = 1; i < n; i++)
    for (j = i - 1; j >= 0 && t < a[j]; j--)
        a[j + 1] = a[j];

How many comparisons are made?

The number of compares depends on a[]s and t as well as on n.

• Worst case count = maximum count
• Best case count = minimum count
• Average count

Worst Case Operation Count

for (j = i - 1; j >= 0 && t < a[j]; j--) 
    a[j + 1] = a[j];

• a = [1,2,3,4] and t = 0 ⇒ 4 compares
• a = [1,2,3,4,...,i] and t = 0 ⇒ i compares

for (int i = 1; i < n; i++)
    for (j = i - 1; j >= 0 && t < a[j]; j--)
        a[j + 1] = a[j];

total compares = 1+2+3+...+(n-1) = (n-1)n/2

READ Examples 2.7~2.18

Step Count

Count the number of steps!

• The operation-count method omits accounting for the time spent on all but the chosen operation

• The step-count method count for all the time spent in all parts(steps) of the program

• A program step is loosely defined to be a syntactically or semantically meaningful segment of a program for which the execution time is independent of the instance characteristics.

  • step count에서도 다 세는 건 아니고, loosley defined 한 의미있는 step들만 센다.

  • 100 adds,100 subtracts,1000 multiples can be counted as one step.

  • However,n add scan not be counted as one step.

//s/e: steps/execution                  //s/e frequency
for(int i=1; i<n; i++)                  //1     n-1  
{
    //insert a[i] into a[0:i-1]         
    int t = a[i];                       //1     n-1
    int j;                              //0     0
    for(j = i-1; j>=0 && t<a[j];j--)    //1     (n-1)n/2
        a[j+1] =a[j];                   //1     (n-1)n/2
    a[j+1] = t;                         //1     n-1
}                                      

int j; is not counted as meaningful step.

Frequency는 아마도 실시하는 횟수인듯.

Total step counts
= (n-1) + 0 + 0 + (n-1) + 0 + (n-1)n/2 + (n-1)n/2 + (n-1) + (n-1)

=n^2 +3n–4

READ Examples 2.19~2.22

TIL

이제 종창맨 귀여움 알것같다.