Skip to main content
  1. Posts/
  2. Today I Learned/

CSAPP 5.4 Elimination Loop Inefficiencies

·253 words·2 mins
Jiho Kim
Author
Jiho Kim
๋‹ฌ๋ ค ๋˜ ๋‹ฌ๋ ค

๐Ÿ“ ์ƒ์„ธ ์ •๋ฆฌ
#

  • ํ•จ์ˆ˜์˜ ๋‹ค์Œ ๋ถ€๋ถ„์„ ์ตœ์ ํ™” ํ•ด๋ณด์ž.
7		for (i = 0; i < vec_length(v); i++) {
8			data_t val;
9			get_vec_element(v, i, &val);
10			*dest = *dest OP val;
11		}
  • vec_length(v)๋ฅผ ๋งค ๋ฐ˜๋ณต๋งˆ๋‹ค ํ˜ธ์ถœํ•ด์„œ ๋น„๊ตํ•˜๊ฒŒ๋œ๋‹ค.
    • ์ด๋ฅผ ์œ„์—์„œ ๋ณ€์ˆ˜๋กœ ์ €์žฅํ•˜๊ณ , ๊ทธ ๋ณ€์ˆ˜๋ž‘๋งŒ ๋น„๊ตํ•˜๋ฉด ํ•ด๋‹น ํ•จ์ˆ˜๋กœ ์ธํ•œ ๋ฐ˜๋ณต๋˜๋Š” ๊ณ„์‚ฐ์„ ์ค„์ผ ์ˆ˜ ์žˆ๋‹ค.
    • ์ด ์ตœ์ ํ™”๋ฅผ code motion ์ด๋ผ๊ณ  ํ•œ๋‹ค.
  • ์ตœ์ ํ™” ์ปดํŒŒ์ผ๋Ÿฌ๋Š” ์ด code motion์„ ์ˆ˜ํ–‰ํ•˜๋ ค๊ณ  ์‹œ๋„ํ•˜์ง€๋งŒ, ์•ž์—์„œ ๋ฐฐ์šด๊ฒƒ๊ณผ ๊ฐ™์ด ์–ด๋–ค ์˜ˆ์™ธ์‚ฌํ•ญ์ด ๋ฐœ์ƒํ• ์ง€ ๋ชจ๋ฅด๊ธฐ๋•Œ๋ฌธ์— ๊ฝค๋‚˜ ์‹ ์ค‘ํ•˜๋‹ค.
    • ํ”„๋กœ๊ทธ๋ž˜๋จธ๊ฐ€ ๋ช…์‹œ์ ์œผ๋กœ ์ˆ˜ํ–‰ํ•˜๋Š”๊ฒŒ ์ข‹์„ ์ˆ˜๋„ ์žˆ๋‹ค.
  • ๊ทน๋‹จ์ ์ธ ์˜ˆ์‹œ๋กœ, ๋‹ค์Œ์„ ๋ณด์ž.
1	/* Convert string to lowercase: slow */
2	void lower1(char *s)
3	{
4		long i;
5	
6		for (i = 0; i < strlen(s); i++)
7			if (s[i] >= `A' && s[i] <= `Z')
8				s[i] -= (`A' - `a');
9	}
10	
11	/* Convert string to lowercase: faster */
12	void lower2(char *s)
13	{
14		long i;
15		long len = strlen(s);
16	
17		for (i = 0; i < len; i++)
18			if (s[i] >= `A' && s[i] <= `Z')
19				s[i] -= (`A' - `a');
20	}
21	
22	/* Sample implementation of library function strlen */
23	/* Compute length of string */
24	size_t strlen(const char *s)
25	{
26		long length = 0;
27		while (*s != `\0') {
28				s++;
29				length++;
30		}
31		return length;
32	}
  • strlenํ•จ์ˆ˜์˜ ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ $O(N)$์ด๋ผ์„œ, $O(N^2)$๊ฐ€ ๋  ์ •๋„๋กœ ์ฐจ์ด๊ฐ€ ์กด์žฌํ•œ๋‹ค.
  • ํ•˜์ง€๋งŒ ์ด๋Š” ์ปดํŒŒ์ผ๋Ÿฌ๊ฐ€ ์ธ์‹ํ•˜๊ธฐ ์–ด๋ ค์šด ์ƒํ™ฉ์ด๊ณ , ๋”ฐ๋ผ์„œ ํ”„๋กœ๊ทธ๋ž˜๋จธ๊ฐ€ ์ง์ ‘ ๋ณ€ํ™˜์„ ์ˆ˜ํ–‰ํ•ด์ฃผ์–ด์•ผ ํ•œ๋‹ค.

โ”์งˆ๋ฌธ ์‚ฌํ•ญ
#

๐Ÿ”— ์ฐธ๊ณ  ์ž๋ฃŒ
#