Created By Tee

int comparison vs double comparison

April 1st, 2008

เมื่ออาทิตย์ที่แล้ว ได้ไปเถียงกับ postdoc ที่ค่อนข้างมั่นใจในตัวเอง และปากดีพอตัว เค้าเป็น super expert ใน statistic แต่ในเรื่องเขียนโปรแกรมเนี่ยผมว่าไม่ค่อย expert(แต่เก่งพอตัวแหละ) ประเด็นมีอยู่ว่า มี function นึงที่ expensive สุด ๆ และถูก call บ่อยโคตร ๆ เพราะฉะนันสมควรต่อการ optimize มาก postdoc ต้องการให้ผมเขียน array ของจำนวนเต็มโดยใช้ Library ที่มีอยู่แล้วด้วยซึ่งมันดั๊นรับได้แต่ double แต่ว่ามี method เท่ๆ แบบ inverse และ decomposition แทบทุกแบบ (point เค้าก็ดีนะ) ผมก็เถียงกลับไปว่า (จะบ้าหรอ)double comparison เนี่ยช้ากว่า integer comparison สุด ๆ และ fancy matrix operation เนี่ยไม่มีความหมายในปัญหาที่เรากำลังทำ (ถ้ารู้ assembly งู ๆ ปลา ๆ ก็จะรู้ว่า int comparison เนี่ย CMP หนึ่งอัน double comparison เนี่ย ทั้ง CMPSS JUMP MOV RET และอื่น ๆ อีกมากมาย)

แล้ว postdoc คนนั้นก็พยายาม disprove ผมด้วยการเขียน code ดังนี้

	
int main(int argc, char** argv)
{
  int n = 100000;
  int m = 100000;
	
  cout << n << \" \" << m << endl;
	
  /*
  int x1 = 0;
  int x2 = 1;
  */
	
  double x1 = 0;
  double x2 = 0;
	
  for( int i= 0;i< n;i++ )
    for( int j= 0;j< m;j++ )
      //      bool yes = ( x1 == x2 );
      bool yes = ( fabs(x1-x2)<0.5 );
	
  return 0;
}

compile ด้วย gcc/g++ O2 แล้วเค้าก็ time ปรากฏว่า มันเท่ากัน…. การเขียนแบบนี้เป็นการแสดงถึงความไม่เข้าใจว่า compiler มันทำบ้าอะไรกับ code
แน่นอนมันต้องเท่ากันสิ ด้วยเหตุผลว่า O2มัน optimize code แล้วสิ่งแรก ๆ ที่มันทำคือ เอาของที่ไม่ได้เกี่ยวกับ index ของ loop ออกจาก loop
Before

  for( int i=0;i< n;i++ )
    for( int j=0;j< m;j++ )
      //      bool yes = ( x1 == x2 );
      bool yes = ( fabs(x1-x2)< 0.5 );

After

//      bool yes = ( x1 == x2 );
bool yes = ( fabs(x1-x2)< 0.5 );
  for( int i=0;i< n;i++ )
    for( int j=0;j< m;j++ )
      {//do nothing;}

และสิ่งต่อไป(หรือก่อนหน้านี่ก็เป็นไปได้)ที่มันจะทำคือ เอา variable ที่ compute แล้วไม่เคยไปสร้าง side effect กับอะไรเลยออกไป
Even better

//do nothing since it's not gonna be used

cout กับ n m ยังอยู่นะเพราะมันมี side effect เพื่อเป็นการตอบกลับไปผมก็แสดงพลัง hack ด้วยการ abuse compiler ด้วย code ต่อไปนี้

int main(int argc, char** argv)
{
	
  int size = 100000000;
  int* array = new int[size];
  int* endofarray = &(array[size-2]);
  int* pointer = array;
  /*
  double* array = new double[size];
  double* endofarray = &(array[size-2]);
  double* pointer = array;
  */
  bool yes=true;
  for( ;pointer< endofarray;pointer++ ){
    //cout << (*pointer) << endl;
    yes &= (*pointer)==(*(pointer+1));
    //yes &= fabs((*pointer)-(*(pointer+1)))<0.5;
	
  }
  cout << yes << endl;
  return 0;
}

ถ้าเพิ่งเรียน c หรือ c++ อ่านแล้วอาจจะบอกได้ว่าเขียนไร(วะ) ไอ้บ้า แต่สรุปคือ ผมทำให้ program assume input ไม่ได้(ขอ chunk ของ memory แล้วไม่ได้ initialize most of the time คุณจะได้ 0 มา), เอาของออกจาก loop ไม่ได้เพราะ ของใน loop เกี่ยวกับ index ใน loop, และ cout เพื่อทำให้ yes มี side effect แล้วก็ compile ด้วย O2 แล้วก็ run…ปรากฏความต่างอย่างน้อย 2 เท่าระหว่าง int comparison และ double comparison (ยังไม่ได้เอา over head ออกนะเนี่ย)

เรื่องนี้สอนให้รู้ว่า…จำไว้ว่า code ที่เขียนกับ code ที่ compile เนี่ยมันไม่เหมือนกันนะจ้ะ

Entry Filed under: Uncategorized