Mempercepat Operasi Input / Output Teks di FreePascal

March 29, 2006 at 8:31 pm | Posted in ACM Contest, Code Samples | 12 Comments

By: Mpu Gondrong

Penjurian program dalam kontes ACM sepenuhnya menggunakan mesin. Secara sederhana setiap program yang dikirim akan diuji dengan serangkaian input untuk kemudian dicek apakah output yang dihasilkan sudah sesuai. Penyusunan peringkat program terbaik didasarkan pada waktu eksekusi yang tercepat. Secara teknis program penjurian menggunakan NetJudge, berjalan di atas Linux, menggunakan prosesor Pentium III dan memory 1024 MByte.

Mengingat pentingnya waktu dalam penjurian, kita akan melihat bagaimana sebenarnya unjuk kerja dari Free Pascal dalam menangani teks. Dalam uji coba digunakan prosesor Intel Pentium 4 2,80GHz dan memory 2048 MByte. Sedangkan untuk file teks yang digunakan berupa angka ganjil antara 1 s/d 999999 (500.000 baris). Untuk mengukur waktu program berjalan digunakan time yang tersedia di kebanyakan Linux.

Dalam Free Pascal untuk membaca Input dan Output cukup menggunakan Readln dan Writeln. Ketika program dijalankan sistem operasi akan mengaktifkan 3 file descriptor, yaitu Input, Output dan Error yang masing-masing bernilai 0, 1 dan 2. Dengan fasilitas pengalihan tujuan (redirector) maka input, output, dan error ini bisa diarahkan dari / ke file, misalnya <input atau >output.

Kita lihat pertama-tama contoh program sederhana dalam bahasa Pascal dan C untuk membaca dan menulis string berupa angka. Untuk Pascal digunakan kompiler Free Pascal 2.0.1, dan untuk C dengan GCC v4.0.0. Optimasi pada kompiler untuk GCC dengan ‘-O2’ dan FPC dengan ‘-OG’. Kernel Linux yang digunakan Linux v2.6.12 dan glibc v2.3.5.

#include <stdio.h>
int main()
{
  int angka, hasil;
  char buf[4*1024];
  do {
    hasil = scanf("%d", &angka);
    if (hasil==EOF || angka==0) break;
    printf("%d\n", angka);
  } while (1);
}

program Test_Baca_Tulis;
var
  I: Integer;
begin
  repeat
    Readln(I);
    if I = 0 then Break;
    Writeln(I);
  until False;
end.

Sebagai contoh untuk penghitungan waktu dan operasi input maupun output yaitu seperti di bawah. Program yang dicontohkan adalah cat yang kurang cocok untuk perbandingan kita karena terlalu cepat.

[oguds@gobang acm]$ time cat < input.txt > output.txt real 0m0.012s user 0m0.001s sys 0m0.011s

Secara rata-rata dibutuhkan 0,303 detik untuk GCC dan 1,772 detik untuk FPC, atau hampir 6x lebih lambat versi Pascal ketimbang C. Tidaklah heran bila program Pascal secara default akan anjlok dalam ranking bila dibandingkan dengan program C. Hasil yang tidak jauh berbeda juga didapat bila program dicompile menggunakan Borland Kylix v3.0. Sama-sama memble dan sama sekali tidak kece.

Ada Apa Sebenarnya ?

Penelusuran lebih lanjut kita lakukan. Baik Free Pascal, sebagai produk Open Source, maupun Kylix (komersial) sama-sama menyertakan kode sumber untuk semua unitnya sehingga dapat diteliti secara mendalam. Ternyata dalam Free Pascal (juga Kylix) biang kerok yang memperlambat operasi penulisan adalah adanya flush secara berkala setiap terjadi Writeln yang efeknya sangat membuat lambat.

Flush ini pada dasarnya berguna, yaitu mengusahakan agar data tersimpan secara langsung, dibanding bila ditampung dulu dalam buffer untuk disimpan belakangan ketika file ditutup atau menurut kehendak sistem operasi. Ketika terjadi kecelakaan, misalnya sistem macet atau mati listrik, data yang terbuang tidak banyak. Namun pemakaian yang berlebihan dan tidak pada tempatnya, seperti untuk keperluan kontes program, justru akan merugikan.

Selain itu buffer teks yang disediakan untuk operasi file sangat kecil, yaitu 256 byte. Namun untuk sistem operasi modern seperti Linux hal ini tidak banyak pengaruhnya, karena pada dasarnya setiap operasi file sudah dioptimalkan agar berjalan cepat dengan buffer internal yang memadai. Meski begitu, Free Pascal menyediakan fungsi SetTextBuf untuk mengganti buffer tersebut.

Perbaikan Tahap 1

Berikut perbaikan program untuk masalah flush dan buffer file tersebut. Untuk hal ini masih digunakan fungsi-fungsi pembacaan teks yang disediakan FPC.

program Test_Baca_Tulis;
uses
  Dos;
const
  MaksBuf = 4 * 1024;
var
  I: Integer;
  BufBaca, BufTulis: array[0..MaksBuf-1] of Char;
begin
  SetTextBuf(Input, BufBaca, MaksBuf);
  SetTextBuf(Output, BufTulis, MaksBuf);
  with TextRec(Output) do
    FlushFunc := nil;
  repeat
    Readln(I);
    if I = 0 then Break;
    Writeln(I);
  until False;
  Flush(Output);
end.

Terjadi peningkatan hampir 4x lebih cepat, yaitu kini waktu eksekusi menjadi 0,407 detik, meskipun juga masih lebih lambat ketimbang versi C yang masih orisinil. Sayangnya cara ini tidak berlaku untuk Kylix yang tetap saja loyo.

Perbaikan Tahap 2

Perbaikan berikutnya yaitu dengan membuat sendiri rutin pembaca file teks. Untuk membaca input cukup dengan membaca dari descriptor 0 dan untuk menulis output dengan menulis ke descriptor 1. Operasi file dilakukan langsung melalui fungsi dari sistem operasi, yaitu fdRead dan fdWrite. Fungsi ini ada di unit Linux (untuk FPC = 2.0). Konvensi pergantian baris yang digunakan sesuai untuk Unix / Linux yaitu #10.

program BacaTulisAngka;
uses
  OldLinux;
const
  MaksBuf = 1024 * 4;
type
  TPString = ^ShortString;
var
  IdxTulis, IdxBaca: Integer;
  BufBaca, BufTulis: array[0..MaksBuf] of Char;

procedure ReadStr(var Value: ShortString);
var
  I, J: Integer;
begin
  I := IdxBaca;
  while I <= MaksBuf do begin
    if BufBaca[I] = #0 then begin
      Dec(I, IdxBaca);
      if (I > 0) then
        Move(BufBaca[IdxBaca], BufBaca[0], I);
      J := fdRead(0, BufBaca[I], MaksBuf-I-1);
      if J=0 then begin
        Value := '';
        Break;
      end;
      BufBaca[I+J] := #0;
      IdxBaca := 0;
    end
    else if BufBaca[I] = #10 then begin
      Move(BufBaca[IdxBaca], Value[1], I-IdxBaca);
      Value[0] := Chr(I-IdxBaca);
      Inc(I);
      Break;
    end
    else Inc(I);
  end;
  IdxBaca := I;
end;

procedure WriteStr(Value: ShortString);
begin
  if (Value='') or (IdxTulis + Length(Value) >= MaksBuf-1) then begin
    BufTulis[IdxTulis] := #10;
    fdWrite(1, BufTulis[1], IdxTulis);
    IdxTulis := 0;
  end;
  TPString(@BufTulis[IdxTulis])^ := Value;
  BufTulis[IdxTulis] := #10;
  Inc(IdxTulis, Length(Value) + 1);
end;

function ReadInt: Integer;
var
  S: String[20];
  I: Integer;
begin
  ReadStr(S);
  Val(S, Result, I);
  if I <> 0 then Result := 0;
end;

procedure WriteInt(Value: Integer);
var
  J: Integer;
begin
  if IdxTulis > MaksBuf-20 then begin
    BufTulis[IdxTulis] := #10;
    fdWrite(1, BufTulis[1], IdxTulis);
    IdxTulis := 0;
  end;
  Str(Value, TPString(@BufTulis[IdxTulis])^);
  J := Ord(BufTulis[IdxTulis]) + 1;
  BufTulis[IdxTulis] := #10;
  Inc(IdxTulis, J);
end;

var
  I: Integer;
begin
  repeat
    I := ReadInt;
    if I=0 then Break;
    WriteInt(I);
  until False;
  WriteStr('');  // flush buffer
end.

Terjadi percepatan hampir 2x yaitu menjadi 0,242 detik. Dalam program di atas terdapat 4 fungsi yang memadai untuk operasi teks pada umumnya, yaitu ReadStr, WriteStr, ReadInt, dan WriteInt. Fungsi untuk mengubah string menjadi angka dan sebaliknya masih menggunakan fungsi standard Val dan Str.

Perbaikan Tahap 3

Khusus untuk membaca angka, fungsi standard seperti Val dan Str masih dapat digenjot lagi agar lebih cepat, yaitu dengan fungsi buatan sendiri dalam bahasa assembly. Rasa-rasanya fungsi-fungsi tersebut cukup sederhana bila dibuat dalam versi assemblynya. Karena dikhususkan untuk FPC maka program ini perlu diubah seperlunya bila dicompile menggunakan Kylix.

{$ASMMODE INTEL}
program BacaTulisAngka;
uses
  OldLinux;
const
  MaksBuf = 4 * 1024;
var
  BufBaca, BufTulis: array[0..MaksBuf] of Char;
  PosBaca, PosTulis: PChar;

function BacaBuf: Integer;
var
  D: PChar;
begin
  D := BufBaca; Result := 0;
  while PosBaca^ <> #0 do begin
    D^ := PosBaca^;
    Inc(D); Inc(PosBaca);
    Inc(Result);
  end;
  Inc(Result, fdRead(0, D^, MaksBuf-1));
  if Result = 0 then Exit;
  BufBaca[Result] := #0;
  PosBaca := BufBaca;
end;

procedure TulisBuf;
begin
  if (PosTulis <> BufTulis) then begin
    fdWrite(1, BufTulis, Integer(PosTulis)-Integer(@BufTulis));
    PosTulis := BufTulis;
  end;
end;

function BacaInt: Integer; assembler;
asm
  jmp @mulai
@baca:
  call BacaBuf
  test eax, eax
  jz @usai
@mulai:
  mov ecx, PosBaca
  xor eax, eax
  xor edx, edx
@lterus:
  mov dl, [ecx]
  cmp dl, 10
  jz @usai
  cmp dl, 0
  jz @baca
  sub dl, '0'
  lea eax, [eax+eax*4]
  add eax, eax
  add eax, edx
@lbawah:
  inc ecx
  jmp @lterus
@usai:
  inc ecx
  mov PosBaca, ecx
end;

procedure TulisInt(Value: Integer); assembler;
asm
  push ebx
  mov eax, Value
  mov edx, 10
  mov ebx, 1 // hitung banyak digit
@lp:
  cmp edx, eax
  ja @us
  lea edx, [edx+edx*4]
  add edx, edx
  inc ebx
  jmp @lp
@us:
  add ebx, PosTulis
  push ebx
  mov byte ptr [ebx], $0A
  mov ecx, 10 // lakukan konversi
@loop:
  xor edx, edx
  div ecx
  add edx, '0'
  dec ebx
  mov [ebx], dl
  test eax, eax
  jnz @loop
  pop eax
  inc eax
  mov PosTulis, eax
  sub eax, offset BufTulis
  cmp eax, MaksBuf-20
  jb @usai
  call TulisBuf
@usai:
  pop ebx
end;

var
  I: Integer;
begin
  PosBaca := BufBaca;
  PosTulis := @BufTulis;
  repeat
    I := BacaInt;
    if I=0 then Break;
    TulisInt(I);
  until False;
  TulisBuf;
end.

Hasil ini bisa dibilang cukup maksimal, yaitu 0,104 detik, meski 9x lebih lambat ketimbang cat tetapi 4x lebih cepat ketimbang versi C. Dengan hasil demikian pemrogram Pascal tidak perlu kecil hati bila berkompetisi dengan bahasa C, meski secara umum memang C lebih unggul daripada Pascal. Apa boleh buat, barangkali takdirnya memang begitu.

Demikian semoga bermanfaat. Salam.