Note the following lsiting, and resulting assembly code (i686, Linux):
You might think that the function is very optimized, since it requires only two comparisons and a lookup in table per character checked?
Alas, GPC does a proper call to the real memcpy() function of complete ``v'' array on each call of function DigitValue() !!!
This makes the run twice as slow as when ``v'' array is made global (edited):
----------------------------------------------------- make test arr a=8 116.290u 0.400s 1:59.62 97.5% 0+0k 0+0io 10385pf+0w time a.out arr a=8 114.190u 0.280s 1:58.53 96.5% 0+0k 0+0io 120pf+0w 114.500u 0.210s 2:03.95 92.5% 0+0k 0+0io 120pf+0w 114.650u 0.040s 1:57.13 97.9% 0+0k 0+0io 121pf+0w 114.840u 0.020s 1:57.00 98.1% 0+0k 0+0io 120pf+0w 115.180u 0.040s 2:05.03 92.1% 0+0k 0+0io 120pf+0w 106.200u 1.390s 2:07.25 84.5% 0+0k 0+0io 120pf+0w 111.700u 0.080s 2:04.02 90.1% 0+0k 0+0io 120pf+0w make test arr a=8 glob 65.840u 0.160s 1:07.62 97.6% 0+0k 0+0io 10385pf+0w time a.out arr a=8 glob 63.610u 0.060s 1:06.63 95.5% 0+0k 0+0io 120pf+0w 63.710u 0.030s 1:05.21 97.7% 0+0k 0+0io 120pf+0w 63.620u 0.040s 1:06.02 96.4% 0+0k 0+0io 120pf+0w 63.610u 0.030s 1:05.41 97.2% 0+0k 0+0io 120pf+0w 63.840u 0.000s 1:05.15 97.9% 0+0k 0+0io 120pf+0w 63.980u 0.010s 1:05.29 98.0% 0+0k 0+0io 120pf+0w 64.000u 0.020s 1:05.19 98.2% 0+0k 0+0io 120pf+0w -----------------------------------------------------
Just FYI, making ``v'' array [0..255] of Integer (for aligned access) made it even 10s slower (probably problems with FSB and cache), instead of what is commonly said, and complete code is not a bit faster from this variant:
function DigitValue (Dig: Char): Integer; attribute (inline, const); var d : Integer; attribute (register); begin if (Dig >= '0') and (Dig <= '9' ) then DigitValue := Ord (Dig) - Ord ('0') else if (Dig >= 'a') and (Dig <= 'z') then DigitValue := Ord (Dig) - Ord ('a') + 10 else if (Dig >= 'A') and (Dig <= 'Z') then DigitValue := Ord (Dig) - Ord ('A') + 10 else DigitValue := -1 end;
... even though this code has six branches.
Is it the GNU Pascal problem or the back-end problem?
NOTE: even attribute (const) after initialization of the array didn't help to evade memcpy().
Mirsad
isvalidnumberbase.pas: ---------------------------------------------------------------------------- program isvalidnum (output);
var i, Base: Integer; OK : Boolean;
function IsValidNumberBase2 (s: String; Base: Integer): Boolean; attribute(const); var i, dv : Integer; attribute (register); b : Byte; attribute (register); function DigitValue (Dig: Char): Integer; {attribute (inline, const);} var d : Integer; attribute (register); {$if 0} {$if Low (Char) < 0} {$error "this won't work: negative Char used as index} {$endif} {$endif} v : array [0..255] of ByteInt = ( -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, -1, -1, -1, -1, -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 );
begin if (Dig >= '0') and (Dig <= 'z') then DigitValue := v[Ord (Dig)] else DigitValue := -1; end;
begin b := Base; Assert ((b >= 2) and (b <= 36), 'base out of range (2..36)'); i := 1; if s[i] = '-' then Inc (i); for i := i to Length (s) do {$define VERSION1} {$ifdef VERSION1} begin dv := DigitValue (s[i]); if (dv < 0) or (dv >= b) then Return False end; {$else} if not (DigitValue (s[i]) in [0 .. b-1]) then Return False; {$endif} Return True; end;
begin { main } OK := IsValidNumberBase2 ('010101010101101010101', 2) and not IsValidNumberBase2 ('0101010210101101010101', 2) and IsValidNumberBase2 ('0121012210101101010101', 3);
if OK then WriteLn ('OK'); end. -------------------------------------------------------------------------
isvalidnumberbase.s (edited): ------------------------------------------------------------------------- .file "isvalidnumberbase.pas" .local I .comm I,4,4 .local Base .comm Base,4,4 .local Ok .comm Ok,1,1 .section .rodata .LC0: .byte -1 . . . .byte -1 .byte -1 .byte -1 .byte 0 .byte 1 .byte 2 .byte 3 .byte 4 .byte 5 .byte 6 .byte 7 .byte 8 .byte 9 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte 10 .byte 11 .byte 12 .byte 13 .byte 14 .byte 15 .byte 16 .byte 17 .byte 18 .byte 19 .byte 20 .byte 21 .byte 22 .byte 23 .byte 24 .byte 25 .byte 26 .byte 27 .byte 28 .byte 29 .byte 30 .byte 31 .byte 32 .byte 33 .byte 34 .byte 35 .byte 36 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte 10 .byte 11 .byte 12 .byte 13 .byte 14 .byte 15 .byte 16 .byte 17 .byte 18 .byte 19 .byte 20 .byte 21 .byte 22 .byte 23 .byte 24 .byte 25 .byte 26 .byte 27 .byte 28 .byte 29 .byte 30 .byte 31 .byte 32 .byte 33 .byte 34 .byte 35 .byte 36 .byte -1 .byte -1 . . . .byte -1 .byte -1 .byte -1 .byte -1 .text .p2align 4,,15 .type Digitvalue.0,@function Digitvalue.0: pushl %ebp movl %esp, %ebp subl $296, %esp movl %ebx, -4(%ebp) leal -280(%ebp), %eax movzbl 8(%ebp), %ebx movl %ecx, -12(%ebp) movl $256, 8(%esp) movl $.LC0, 4(%esp) movl %eax, (%esp) call memcpy cmpb $47, %bl jbe .L4 cmpb $122, %bl ja .L4 movzbl %bl, %eax movsbl -280(%eax,%ebp),%eax .L5: movl -4(%ebp), %ebx movl %ebp, %esp popl %ebp ret .p2align 4,,7 .L4: movl $-1, %eax jmp .L5 .Lfe1: .size Digitvalue.0,.Lfe1-Digitvalue.0 .section .rodata.str1.1,"aMS",@progbits,1 .LC1: .string "base out of range (2..36)" .text .p2align 4,,15 .globl Isvalidnumberbase2 .type Isvalidnumberbase2,@function Isvalidnumberbase2: pushl %ebp movl %esp, %ebp pushl %edi pushl %esi pushl %ebx subl $92, %esp movl 8(%ebp), %edi movzbl 12(%ebp), %eax cmpb $1, %al seta %bl movb %al, -73(%ebp) testb %bl, %bl je .L6 cmpb $36, %al setbe %bl .L6: movl $25, -72(%ebp) leal -64(%ebp), %eax movl $25, 8(%esp) movl $.LC1, 4(%esp) movl %eax, (%esp) call memcpy leal -72(%ebp), %eax movl %eax, 4(%esp) movzbl %bl, %eax movl $1, %ebx movl $25, -68(%ebp) movl %eax, (%esp) call _p_Assert cmpb $45, 8(%edi) je .L18 .L8: movl 4(%edi), %esi cmpl %esi, %ebx jg .L9 movb $0, -74(%ebp) .p2align 4,,15 .L10: cmpb $0, -74(%ebp) je .L12 cmpl %esi, %ebx je .L9 incl %ebx .L12: movb $1, -74(%ebp) leal -24(%ebp), %ecx movzbl 7(%edi,%ebx), %eax movl %eax, (%esp) call Digitvalue.0 movl %eax, %ecx shrl $31, %ecx testb %cl, %cl movl %eax, %edx jne .L17 movzbl -73(%ebp), %eax cmpl %eax, %edx jl .L14 testl %edx, %edx js .L14 movb $1, %cl .L14: testb %cl, %cl je .L10 .L17: xorl %eax, %eax .L1: addl $92, %esp popl %ebx popl %esi popl %edi popl %ebp ret .p2align 4,,7 .L9: movb $1, %al jmp .L1 .L18: movl $2, %ebx jmp .L8 .Lfe2: .size Isvalidnumberbase2,.Lfe2-Isvalidnumberbase2 .section .rodata.str1.1 .LC2: .string "010101010101101010101" .LC5: .string "OK" .LC4: .string "0121012210101101010101" .LC3: .string "0101010210101101010101" .text .p2align 4,,15 .globl pascal_main_program .type pascal_main_program,@function pascal_main_program: pushl %ebp movl %esp, %ebp subl $136, %esp movl $21, 8(%esp) leal -32(%ebp), %eax movl $21, -40(%ebp) movl $.LC2, 4(%esp) movl %eax, (%esp) call memcpy leal -40(%ebp), %eax movl $21, -36(%ebp) movl $2, 4(%esp) movl %eax, (%esp) call Isvalidnumberbase2 testb %al, %al jne .L28 .L21: testb %al, %al jne .L29 .L23: movb %al, Ok testb %al, %al jne .L30 .L19: movl %ebp, %esp popl %ebp ret .p2align 4,,7 .L30: movl $22, 24(%esp) movl $2, 20(%esp) movl $.LC5, 16(%esp) movl $17, 12(%esp) movl $2, 8(%esp) movl $784, 4(%esp) movl $_p_Output, (%esp) call _p_Internal_Write movl _p_InOutRes, %eax testl %eax, %eax je .L19 jmp .L31 .p2align 4,,7 .L29: movl $22, -104(%ebp) leal -96(%ebp), %eax movl $22, 8(%esp) movl $.LC4, 4(%esp) movl %eax, (%esp) call memcpy leal -104(%ebp), %eax movl $22, -100(%ebp) movl $3, 4(%esp) movl %eax, (%esp) call Isvalidnumberbase2 jmp .L23 .p2align 4,,7 .L28: movl $22, -72(%ebp) leal -64(%ebp), %eax movl $22, 8(%esp) movl $.LC3, 4(%esp) movl %eax, (%esp) call memcpy leal -72(%ebp), %eax movl $22, -68(%ebp) movl $2, 4(%esp) movl %eax, (%esp) call Isvalidnumberbase2 testb %al, %al sete %al jmp .L21 .L31: call _p_CheckInOutRes .Lfe3: .size pascal_main_program,.Lfe3-pascal_main_program .data .type ctor_run_condition_14.1,@object .size ctor_run_condition_14.1,1 ctor_run_condition_14.1: .byte 0 .text .p2align 4,,15 .globl init_pascal_main_program .type init_pascal_main_program,@function init_pascal_main_program: cmpb $0, ctor_run_condition_14.1 pushl %ebp movl %esp, %ebp je .L34 popl %ebp ret .p2align 4,,7 .L34: popl %ebp movb $1, ctor_run_condition_14.1 jmp _p_DoInitProc .Lfe4: .size init_pascal_main_program,.Lfe4-init_pascal_main_program .p2align 4,,15 .globl main .type main,@function main: pushl %ebp movl %esp, %ebp subl $24, %esp movl __GPC_RTS_VERSION_20030507__, %eax movl 16(%ebp), %eax andl $-16, %esp movl %eax, 8(%esp) movl 12(%ebp), %eax movl %eax, 4(%esp) movl 8(%ebp), %eax movl %eax, (%esp) call _p_initialize call init_pascal_main_program call pascal_main_program call _p_finalize movl %ebp, %esp xorl %eax, %eax popl %ebp ret .Lfe5: .size main,.Lfe5-main .ident "GCC: (GNU) 3.2.1" -------------------------------------------------------------------------------