Macfeteria

พอดีว่าผมอ่านเรื่อง Locality of reference แล้วมันน่าสนใจ มันเป็น topic เกี่ยวกับการ optimize ของ memory access ว่าเราจะเขียนโปรแกรมยังไงให้การเข้าถึง memory นั้นเร็วที่สุด ( ถ้าหากเราเข้าถึงเร็วมันก็หมายถึงว่า โปรแกรมของเราก็เร็วขึ้นด้วย ) โดยปกติแล้วในภาษา c/c++ เมื่อเราเขียนข้อมูลในลักษณะของ Array นั้นตัวเลขที่อยู่ด้านซ้ายสุดจะเป็น row ส่วนตัวต่อมาจะเป็น column และวิธีการเขียนให้เพิ่มประสิทธิภาพของเรานั้น ก็ควรจะเขียนให้มันมีการเคลื่อนที่ของตำแหน่งที่จะอ่านต่อไปในลักษณะอ่านอยู่ใน memory page เดียวกัน ดูรูปประกอบ

จากภาพ ประกอบ Memory Page นั้นจะเรียงเป็นลักษณะ เหมือนลิ้นชักที่เป็นชั้นๆ (row) มันก็เหมือนกับ เมื่อเราเปิดตู้เอกสาร ที่มีหลายๆลิ้นชัก ถ้าเราจะหาเอกสารสักชิ้น ลองคิดว่าถ้าเราหาทีละชั้น โดยหยิบออกมาทีละชิ้นจนหมดชั้นนั้นแล้วค่อยไปเริ่มชั้นใหม่ เทียบกับ เปิดออกมาหนึ่งชั้นและหยิบมาหนึ่งชั้นแล้วก็ปิด หลังจากนั้นก็เปิดชั้นต่อไปแล้วก็หยิบมาตรวจอีก 1 ชิ้นแล้วก็ไปชั้นใหม่ แบบไหนเร็วกว่า

ก็แน่นอนว่า การค้นหาทีละชั้นแล้วค่อยไปหาชั้นต่อไปนั้นเร็วกว่า การเขียนโปรแกรมก็ไม่ได้ต่างอะไร เพื่อเป็นการเห็นชัดๆ ผมมีตัวอย่าง Code ภาษา C ที่ทำการคำนวนการคูณของ Matrix

ตัวอย่าง code แรก ผมทำการคำนวนโดยที่ ตำแหน่งที่ต้องเปลี่ยนบ่อยที่สุดก็คือ k และแน่นอนว่ามันเป็นตำแหน่งของ row

for ( i = 0; i < N; i++ )
{
	for ( j = 0; j < N; j++ )
	{
		 for ( k = 0; k < N; k++ )
			C[i][j] += A[i][k] * B[k][j];
	}
}

และ code ที่สอง โดยผมสลับตำแหน่งของ Loop ให้ตำแหน่งที่ต้องเปลี่ยนบ่อยที่สุดคือ j และมันก็เป็น column

for ( i = 0; i < N; i++ )
{
	for ( k = 0; k < N; k++ )
	{
		for ( j = 0; j < N; j++ )
			C[i][j] += A[i][k] * B[k][j];
	}
}

ก็อย่างที่ผมบอกไป ว่าถ้าเราเข้าถึงข้อมูลทีละชั้น (row) แล้วค่อยๆเลี่อนไปทีละอัน กับหา 1 อันแล้วเปลี่ยนชั้น (row ) อะไรจะ เร็วกว่า ก็ตอบแทบไม่ต้องคิดเลย นั่นก็คือ code อันที่สองมันย่อมเร็วกว่าแน่ๆ เอาละ งั้นเรามาลองทดสอบกันดูเลยดีกว่า ว่ามันจะเร็วกว่าจริงๆหรือ หรือว่ามันจะเร็วกว่าสักเท่าไหร่กันเชียว จากของจริงเลยดีกว่า

#include
#include 
#include 
#define MAX_ARRAY 1024
unsigned int GetTimeSnapshot()
{
	struct timeval tv;
	gettimeofday( &tv, NULL );
	return (unsigned int)(tv.tv_sec * 1000 + tv.tv_usec / 1000);
}
 
int main (int argc, char * const argv[])
{
	int array[MAX_ARRAY][MAX_ARRAY] = {0,};
 
	unsigned int x = 0, y = 0 , z = 0;
	unsigned int startTime , endTime;
 
	// Loop A
	startTime = GetTimeSnapshot();
	for ( y = 0 ; y < MAX_ARRAY ; y++)
	{
		for ( x = 0; x < MAX_ARRAY; x++ )
		{
			array[x][y] = ++z;
		}
	}
	endTime = GetTimeSnapshot();	
 
	printf("nLoop A Total time: %d", (int)endTime - startTime);
	// Loop B
	startTime = GetTimeSnapshot();
	for ( x = 0 ; x < MAX_ARRAY ; x++)
	{
		for ( y = 0; y < MAX_ARRAY; y++ )
		{
			array[x][y] = ++z;
		}
	}
	endTime = GetTimeSnapshot();	
 
	printf("nLoop B Total time: %d", (int)endTime - startTime);
	return 0;
}

จาก code ข้างบน ผลลัพธ์ของ สอง Loop นี้ทำงานเหมือนกัน แต่วิธีการต่างกัน
และผลลัพธ์จากการทำงานได้แบบนี้
Loop A Total time: 23
Loop B Total time: 6

โอ้โห จะเห็นว่า มันทำงานเร็วกว่าถึง 4 เท่า !!!
ก็สำหรับวันนี้ถ้าสงสัยอะไรก็ถามได้ใน Forum นะครับ

Download Source Code

Technorati Tags: c++, programming