CS110 Summary

Computer Architechture 一些homework和project总结。

当时不太会的东西， 但可能稍微久一点以后也不会了。

---

Homework2:

boundy case

1. 边界条件应该积极与其他人交流，不是闭门造车，效率会好点

2. 尽快确认正确性，排除正确性问题（quicksort的实现出了很多次错误）

3. 有可用的算法参考，就使用。

4. 测试应该手写case后尽快在合适的平台上测试（ubuntu），不应该嫌麻烦在macos上等死

5. 尽可能复用函数，例如 doubll_item *head = list_head(list) ，减少重复实现代码造成的误差，也避免改动花费大量时间

   quick_sort 交换指针尽量只交换其中数据，不交换指针本身

   //lo for lower index, hi for higher index
   algorithm partition(A, lo, hi) is
       pivot := A[hi]
       i := lo - 1    
       for j := lo to hi - 1 do
           if A[j] < pivot then
               i := i + 1
               swap A[i] with A[j]
       swap A[i + 1] with A[hi]
       return i + 1 
                   
   algorithm quicksort(A, lo, hi) is
       if lo < hi then
           p := partition(A, lo, hi)
           quicksort(A, lo, p - 1 )
           quicksort(A, p + 1, hi) 

补码反码

反码解决正负加减都用加法的问题

补码解决两个0（正负0）的问题

Project1.1

Horrible mistake during coding and no error messages raised:

int *num = malloc( sizeof(int) );

Caution: +1for\0

char* str = malloc( strlen(other_str) + 1 );

1. strtok() usage

   Read token by token.

   FILE* input;
   char buf[BUF_SIZE];
   
   //read buf line by line
   while(fgets(buf,sizeof(buf),input)){
     //get token separated by IGNORE_CHARS
   	token=strtok(buf,IGNORE_CHARS);
     //read until the line ends
   	while((token=strtok(NULL,IGNORE_CHARS))!=NULL){
      	
     }
   }

   Strtok_r() 使用了外置的save_ptr, 解决一些concurrence

2. strtol() usage

   translate str into long

   char *end;
   const char *str;
   
   res=strtol(str,&end,0);
   //errno out of range
   if(errno == ERANGE)return -1;

3. sprintf()

   translate number into str

   int num;
   //malloc '+1' to contain '\0' string end
   char *args=malloc(sizeof(num)+1);
   
   sprintf(args,"%d",num);

Project3 optimization of k-means

不要想自己解决这个问题，应该先去找paper看看有没有更好的算法。

Openmp 优化：手动array reduction

#pragma omp parallel
{
  int * q_private = new int[N];
  q_private[] init 0;
  
  #pragma omp for
  for (int i=0;i<N;++i){
    q_private[i] += i;
  }
  
  #pragma omp critical
  for (int i=0;i<N;++i){
    //manually add private array into saving array 
    q[i] += q_private[i];
  }
}

Simd优化

//翻intel 指令集找指令
_mm_store_pd((double*)(a+i),_mm_add_pd(_mm_load_pd((double*)(a+i),_mm_load_pd((double*)(b+i))));
//强制类型转换
//struct type can be used the same as array (a[i] ==> a+i)

Homework 7 C++ template and reference passing

Namespace and template/reference passing:

namespace __Detail{
	template <typename T>
  class link_list{
    link_list();//default constructor
    void push(link_list &new_node);//push a node;
  }
}

//constructor can not have a return specification
__Detail::link_list<T>::link_list(){
  //do something here
}

//Const parameter passing
void __Detail::link_list<T>::push(const link_list &new_node){
  head->next=new_node;
  //notice the "const link_list &new_node" here is a mark to pass the original variable to the function( a reference), not to make it a pointer
}

重载运算符

//const type &it 表示一种c++语法糖，不复制参数，也不能修改传入参数
//type& 返回类型：返回已经有的某个变量、值，不是新值，不复制值提高效率/ 可以实现 a = b = c
type& operator=(const type &it) {
	_M_node = it._M_node;
	return *this;
}

type* operator->() const {
	return &_M_node->_M_data;
}

//type& :返回一个type类型的reference(适用于已经有的某个变量、值) 不复制值，用于提高效率/ 实现(*a) 复合操作
type& operator*() const {
	return _M_node->_M_data;
}

//type&, 表示 ++a: 先令a+=1,然后返回增加后的a
type& operator++() {
	_M_node = _M_node->_M_next;
	return *this;
}

//type : 表示a++: b = a++ 先令b=a，然后a+=1
//括号中int是用于区别前置、后置的额外形参(其实是个0)，没有用处
// 与 ++a 的区别主要在于返回值是否已经+1, type& 为锦上添花，提高效率：因为返回了 *this，不需要新值，而 a++需要一个temp 所以返回type
type operator++(int) {
	iter_type tp = *this;
	_M_node = _M_node->_M_next;
	return tp;
}

c++11 auto自动类型推断

//使用type declare
__detail::__List_node_base<T> *nt = _M_head._M_next;
//使用auto，the same effect
auto nt = _M_head._M_next;

//iterator声明
__detail::__List_iterator<int> *it=new __detail::__List_iterator<int>();
//equal to
auto it = new __detail::__List_iterator<int>();

Project4 Shell implementation with c

Proj4 is a realization of shell program.

主要遇到的问题：

1. c中的string copy must be implemented with strcmp() or it is not reliable since the = is manipulation of pointer

   The copy of pointer will raise problem when editing the string but keep slient sometimes. The bug is somehow hard to find if you don’t realize this might be a reason.

2. fork() and shell machenism

   The main thread need to be exsiting until the shell is shutdown, execve() (or this series of syscall) will kill this thread after the function with no return. So we need fork() to make it a new thread run the command.

   But built-in command will be executed by main thread.

   if( isBuiltInCommand() ){
     runCommand();
   }else{
     int childPid=fork();
     if( childPid==0 ){
       //这里需要处理pipe(多重命令)
       execve(command);//This is the child thread to run this command
     }else{
       if(isBackgroundJob){
         waidpid(childPid,NULL,0);
       }else{
         backgroundJobs[num++]=childPid;//store background job's pid to track
       }
     }
   }

3. Pipe and multi-pipe

   (1) | (2) | (3)

   先判断是头/尾，然后用pipe()，redirect stdin/stdout 到fd[1]/fd[2]，把stdio传到下一个阶段。Really need patience to design.

4. Background jobs

   Multithread wake-up/ kill syntax, need some caution.