Optimasi Kode C (Contoh Kasus)

Dalam mengkode program, seringkali kita dihadapkan oleh problem optimasi terhadap rutin-rutin tertentu dalam program. Adapun tujuan optimasi sendiri diantaranya adalah 1) memperoleh footprint yang sekecil mungkin, dan 2) waktu eksekusi rutin yang secepat mungkin (biasanya sebagai implikasi dari footprint yang kecil), dengan tetap menjamin semantik rutin. Optimasi terhadap rutin ini sangatlah vital misalnya rutin dalam operasi real-time atau rutin yang berada di ISR (Interrupt Service Routine) yang keduanya menuntut kode yang time-constrained.

Sebagai contoh adalah requirement sederhana untuk memetakan 16 nilai x dalam y dengan ketentuan berikut:

x 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
y=f(x) 0 8 16 24 64 72 80 88 128 136 144 152 192 200 208 216


Problem tersebut muncul saat kita ingin menempatkan 8-bit data (kanal x) di lokasi yang ditandai dengan nilai y. Misalnya, MSB data untuk kanal 15 akan berada di lokasi 0, sedangkan kanal 3 akan berada di lokasi 192. Framing data dalam pengkanalan TDM membutuhkan rutin ini.

Problem sederhana di atas dapat dipecahkan setidaknya dengan dua cara:
1) menggunakan if-then-else untuk memetakan x di nilai y yang diinginkan;
2) menggunakan rumus aritmetika

Kedua solusi tersebut dinyatakan dalam fungsi func2 dan func1 di program terlampir di bawah. Kedua solusi memberikan hasil yang sama (semantik). Namun, dua catatan yang penting adalah:
1) func1 menghasilkan footprint kode yang jauh lebih kecil dari func2 (31 Byte dibandingkan 290 Byte)
2) func1 menghasilkan waktu eksekusi yang lebih cepat dari func2 (116 us dibandingkan 302 us, untuk 1000 loop)

Jelas, sebaiknya kita menggunakan rutin/fungsi func1 daripada func2 dalam program kita. Masih banyak teknik optimasi yang bisa diterapkan ke dalam program/aplikasi kita untuk mencapai kode yang kecil dan waktu eksekusi yang cepat (MIPS yang besar). Anda perlu mengeksplorenya lebih lanjut.

/* Mapping x to y, with this logic:
    for use in16-chans framing
    x=15 14 13 	12 11 10 9  8   7   6   5   4    3   2   1    0
    y= 0  8  16 24 64 72 80 88 128 136 144 152 192 200 208 216
   This program maps x to y=f(x) using both if-then-else and arithmetic routines

    @2009 eko didik widianto
 */
#include <stdio.h>
#include <sys/time.h>

#define NUM_TEST 1000

struct timeval start, end;

int func1(int x) {
	return 	8* (27-((x & 0xc)*2+(x & 0x3)));
}

int func2(int x) {
	switch (x &0xc) {
		case 	0x0:	return 216 - 8*(x %  4);
		case 	0x4:	return 152 - 8*(x %  4);
		case 	0x8:	return 88- 8*(x %  4);
		case 	0xc:	return 24- 8*(x %  4);
	}

}

int main(int argc, char *argv[]) {
	int i, x, y;
	int time_elapsed;

	gettimeofday(&start, (struct timezone *) 0);
	for (i=0; i<NUM_TEST; i++) {
		for (x=0;x<16;x++) {
			y=func1(x);
		}
	}
	gettimeofday(&end, (struct timezone *) 0);
	time_elapsed = (1000000*end.tv_sec + end.tv_usec) - 
                      (1000000*start.tv_sec + start.tv_usec) ;
	printf("Time elapsed for function 1 = %d us\n",time_elapsed);

	gettimeofday(&start, (struct timezone *) 0);
	for (i=0; i<NUM_TEST; i++) {
		for (x=0;x<16;x++) {
			y=func2(x);
		}
	}
	gettimeofday(&end, (struct timezone *) 0);
	time_elapsed = (1000000*end.tv_sec + end.tv_usec) - 
                            (1000000*start.tv_sec + start.tv_usec) ;
	printf("Time elapsed for function 2 = %d us\n",time_elapsed);
	return 0;
}

Menjalankan program menghasilkan:

#> ./mapping
Time elapsed for function 1 = 116 us
Time elapsed for function 2 = 302 us
#> ./mapping
Time elapsed for function 1 = 116 us
Time elapsed for function 2 = 303 us
#> ./mapping
Time elapsed for function 1 = 116 us
Time elapsed for function 2 = 301 us
#> ./mapping
Time elapsed for function 1 = 116 us
Time elapsed for function 2 = 301 us
#> ./mapping
Time elapsed for function 1 = 116 us
Time elapsed for function 2 = 302 us

Dengan ‘objdump -d mapping‘ menghasilkan kode assembly x86 (snap untuk func1 dan func2 saja) berikut:

08048368 :
 8048368:       55                      push   %ebp
 8048369:       89 e5                   mov    %esp,%ebp
 804836b:       8b 45 08                mov    0x8(%ebp),%eax
 804836e:       83 e0 0c                and    $0xc,%eax
 8048371:       8d 14 00                lea    (%eax,%eax,1),%edx
 8048374:       8b 45 08                mov    0x8(%ebp),%eax
 8048377:       83 e0 03                and    $0x3,%eax
 804837a:       01 c2                   add    %eax,%edx
 804837c:       b8 1b 00 00 00          mov    $0x1b,%eax
 8048381:       29 d0                   sub    %edx,%eax
 8048383:       c1 e0 03                shl    $0x3,%eax
 8048386:       5d                      pop    %ebp
 8048387:       c3                      ret    

08048388 :
 8048388:       55                      push   %ebp
 8048389:       89 e5                   mov    %esp,%ebp
 804838b:       83 ec 1c                sub    $0x1c,%esp
 804838e:       8b 45 08                mov    0x8(%ebp),%eax
 8048391:       83 e0 0c                and    $0xc,%eax
 8048394:       89 45 f8                mov    %eax,-0x8(%ebp)
 8048397:       83 7d f8 04             cmpl   $0x4,-0x8(%ebp)
 804839b:       74 5f                   je     80483fc
 804839d:       83 7d f8 04             cmpl   $0x4,-0x8(%ebp)
 80483a1:       7f 0b                   jg     80483ae
 80483a3:       83 7d f8 00             cmpl   $0x0,-0x8(%ebp)
 80483a7:       74 1a                   je     80483c3
 80483a9:       e9 f0 00 00 00          jmp    804849e
 80483ae:       83 7d f8 08             cmpl   $0x8,-0x8(%ebp)
 80483b2:       74 7e                   je     8048432
 80483b4:       83 7d f8 0c             cmpl   $0xc,-0x8(%ebp)
 80483b8:       0f 84 aa 00 00 00       je     8048468
 80483be:       e9 db 00 00 00          jmp    804849e
 80483c3:       8b 45 08                mov    0x8(%ebp),%eax
 80483c6:       89 c2                   mov    %eax,%edx
 80483c8:       81 e2 03 00 00 80       and    $0x80000003,%edx
 80483ce:       89 55 f0                mov    %edx,-0x10(%ebp)
 80483d1:       83 7d f0 00             cmpl   $0x0,-0x10(%ebp)
 80483d5:       79 0a                   jns    80483e1
 80483d7:       ff 4d f0                decl   -0x10(%ebp)
 80483da:       83 4d f0 fc             orl    $0xfffffffc,-0x10(%ebp)
 80483de:       ff 45 f0                incl   -0x10(%ebp)
 80483e1:       8b 45 f0                mov    -0x10(%ebp),%eax
 80483e4:       8d 14 c5 00 00 00 00    lea    0x0(,%eax,8),%edx
 80483eb:       b8 d8 00 00 00          mov    $0xd8,%eax
 80483f0:       89 c1                   mov    %eax,%ecx
 80483f2:       29 d1                   sub    %edx,%ecx
 80483f4:       89 4d fc                mov    %ecx,-0x4(%ebp)
 80483f7:       e9 a4 00 00 00          jmp    80484a0
 80483fc:       8b 45 08                mov    0x8(%ebp),%eax
 80483ff:       89 c2                   mov    %eax,%edx
 8048401:       81 e2 03 00 00 80       and    $0x80000003,%edx
 8048407:       89 55 ec                mov    %edx,-0x14(%ebp)
 804840a:       83 7d ec 00             cmpl   $0x0,-0x14(%ebp)
 804840e:       79 0a                   jns    804841a
 8048410:       ff 4d ec                decl   -0x14(%ebp)
 8048413:       83 4d ec fc             orl    $0xfffffffc,-0x14(%ebp)
 8048417:       ff 45 ec                incl   -0x14(%ebp)
 804841a:       8b 45 ec                mov    -0x14(%ebp),%eax
 804841d:       8d 14 c5 00 00 00 00    lea    0x0(,%eax,8),%edx
 8048424:       b8 98 00 00 00          mov    $0x98,%eax
 8048429:       89 c1                   mov    %eax,%ecx
 804842b:       29 d1                   sub    %edx,%ecx
 804842d:       89 4d fc                mov    %ecx,-0x4(%ebp)
 8048430:       eb 6e                   jmp    80484a0
 8048432:       8b 45 08                mov    0x8(%ebp),%eax
 8048435:       89 c2                   mov    %eax,%edx
 8048437:       81 e2 03 00 00 80       and    $0x80000003,%edx
 804843d:       89 55 e8                mov    %edx,-0x18(%ebp)
 8048440:       83 7d e8 00             cmpl   $0x0,-0x18(%ebp)
 8048444:       79 0a                   jns    8048450
 8048446:       ff 4d e8                decl   -0x18(%ebp)
 8048449:       83 4d e8 fc             orl    $0xfffffffc,-0x18(%ebp)
 804844d:       ff 45 e8                incl   -0x18(%ebp)
 8048450:       8b 45 e8                mov    -0x18(%ebp),%eax
 8048453:       8d 14 c5 00 00 00 00    lea    0x0(,%eax,8),%edx
 804845a:       b8 58 00 00 00          mov    $0x58,%eax
 804845f:       89 c1                   mov    %eax,%ecx
 8048461:       29 d1                   sub    %edx,%ecx
 8048463:       89 4d fc                mov    %ecx,-0x4(%ebp)
 8048466:       eb 38                   jmp    80484a0
 8048468:       8b 45 08                mov    0x8(%ebp),%eax
 804846b:       89 c2                   mov    %eax,%edx
 804846d:       81 e2 03 00 00 80       and    $0x80000003,%edx
 8048473:       89 55 e4                mov    %edx,-0x1c(%ebp)
 8048476:       83 7d e4 00             cmpl   $0x0,-0x1c(%ebp)
 804847a:       79 0a                   jns    8048486
 804847c:       ff 4d e4                decl   -0x1c(%ebp)
 804847f:       83 4d e4 fc             orl    $0xfffffffc,-0x1c(%ebp)
 8048483:       ff 45 e4                incl   -0x1c(%ebp)
 8048486:       8b 45 e4                mov    -0x1c(%ebp),%eax
 8048489:       8d 14 c5 00 00 00 00    lea    0x0(,%eax,8),%edx
 8048490:       b8 18 00 00 00          mov    $0x18,%eax
 8048495:       89 c1                   mov    %eax,%ecx
 8048497:       29 d1                   sub    %edx,%ecx
 8048499:       89 4d fc                mov    %ecx,-0x4(%ebp)
 804849c:       eb 02                   jmp    80484a0
 804849e:       eb 06                   jmp    80484a6
 80484a0:       8b 45 fc                mov    -0x4(%ebp),%eax
 80484a3:       89 45 f4                mov    %eax,-0xc(%ebp)
 80484a6:       8b 45 f4                mov    -0xc(%ebp),%eax
 80484a9:       c9                      leave
 80484aa:       c3                      ret

2 Komentar to “Optimasi Kode C (Contoh Kasus)”

  1. wow keren.. ini dia yg ku cari..😛

  2. mantab ulasan ini….good share

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: