Happy tickets benchmark

| category: Testing | author: st
Tags: , , ,

Some countries have integer numbers printed on the transport tickets, for example, in ex-USSR. The ticket is "happy" when the sum of the first half of digits equals to the second one. Then you should eat it and make a wish.

Example:

123456 and 111222 are not happy tickets
123123 and 123222 are the happy tickets

The brute-force test should iterate through all number combinations and calculate the count of happy tickets.

No human-like optimization is required, it is only compiler test. The test compares compiler generated code quality, not the PC performance!

Assume, every number have 8 digits. Then the count of happy tickets is 4816030 including "00000000".

Programs

Assembler

This non-optimized simple assembler code can be a reference for other programs as the expected minimum of the generated code quality. In other words, the "minimally poor code".

; Asm : nasm -f elf64 -l happytickets.lst  happytickets.asm
; Link: ld -s -o happytickets happytickets.o

section .data
  ticket_count      dq 0
  start_time        dq 0
  stop_time         dq 0
  clock_per_msec    dq 0
  msec              dq 0
  msec_in_sec       dq 1000
  msg_result        db '. Elapsed time, msec: '
  msglen_result     equ $-msg_result
  buf               db '123546890'
  buflen            equ $-buf
  LF                db 0xA
  LFlen             equ $-LF
  timeval:
    tv_sec  dd 0
    tv_usec dd 0

section .text
  global _start

_start:
  call get_clock_per_millisecond
  call get_start_time

  ; begin calculating
  mov rbx, 0 ; store count in register
  mov r8, 10
  loop_1:
    mov r9, 10
    loop_2:
      mov r10, 10
      loop_3:
        mov r11, 10
        loop_4:
          mov r12, 10
          loop_5:
            mov r13, 10
            loop_6:
              mov r14, 10
              loop_7:
                mov r15, 10
                loop_8:
                  mov rax, r8
                  add rax, r9
                  add rax, r10
                  add rax, r11
                  sub rax, r12
                  sub rax, r13
                  sub rax, r14
                  sub rax, r15
                  jnz not_happy
                    inc rbx
                  not_happy:
                    dec r15
                jnz loop_8
                dec r14
              jnz loop_7
              dec r13
            jnz loop_6
            dec r12
          jnz loop_5
          dec r11
        jnz loop_4
        dec r10
      jnz loop_3
      dec r9
    jnz loop_2
    dec r8
  jnz loop_1

  mov [ticket_count], rbx
  ; end of calculations

  call get_stop_time

  ; elapsed time
  mov rax, [stop_time]
  sub rax, [start_time]
  mov rdx, 0                 ; load upper half of dividend with zero
  div qword [clock_per_msec] ; divide rdx:rax by value
  mov [msec], rax

  ; print results
  mov rax, [ticket_count]
  call print_number
  mov rcx, msg_result
  mov rdx, msglen_result
  call print_str
  mov rax, [msec]
  call print_number
  call print_newline

  ; exiting program
  mov rax, 1  ; the system call for exit (sys_exit)
  mov rbx, 0  ; exit with return code of 0 (no error)
  int 0x80    ; system call
  ret

;------------------------
; subroutines

get_timestamp:
  xor rax, rax
  cpuid
  rdtsc
  ret

get_start_time:
  call get_timestamp
  mov [start_time], eax
  mov [start_time + 4], edx
  ret

get_stop_time:
  call get_timestamp
  mov [stop_time], eax
  mov [stop_time + 4], edx
  ret

get_clock_per_millisecond:
  call get_start_time
  ; sleep for 1 seconds and 0 nanoseconds
  mov dword [tv_sec], 1
  mov dword [tv_usec], 0
  mov eax, 162
  mov ebx, timeval
  mov ecx, 0
  int 0x80
  ;
  call get_stop_time
  mov rax, [stop_time]
  sub rax, [start_time]
  mov rdx, 0
  div qword [msec_in_sec]
  mov [clock_per_msec], rax
  ret

print_number:
  mov rbx, buf + buflen - 1
  mov rcx, buflen
  mov rdi, 10
  next_digit:
    mov rdx, 0
    div rdi
    add rdx, 48 ; '0' ASCII code
    mov [rbx], dl
    dec rbx
  loop next_digit

  mov rcx, buf
  mov rdx, buflen
  call print_str
  ret

print_newline:
  mov rcx, LF
  mov rdx, LFlen
  call print_str
  ret

print_str:
  mov rax, 4
  mov rbx, 1
  int 0x80
  ret

Pascal

The program should be compiled with FreePascal, Delphi and other.

program HappyTickets;

{$IFDEF FPC}
{$MODE DELPHI} // Required for FPC
{$ELSE}
{$APPTYPE CONSOLE} // required for Delphi
{$ENDIF}

uses
  SysUtils, DateUtils;

var
  n1, n2, n3, n4, n5, n6, n7, n8: {$IFDEF FPC}0..9{$ELSE}integer{$ENDIF};
  TicketsCount: longint; // Required for FPC that uses int16 instead of int32 for integer type in some cases (see notes)
  d1, d2: TDateTime;
begin
  TicketsCount := 0;
  d1 := Now;
  for n1 := 0 to 9 do
    for n2 := 0 to 9 do
      for n3 := 0 to 9 do
        for n4 := 0 to 9 do
          for n5 := 0 to 9 do
            for n6 := 0 to 9 do
              for n7 := 0 to 9 do
        for n8 := 0 to 9 do
                  if n1 + n2 + n3 + n4 = n5 + n6 + n7 + n8 then
                  {$IFDEF FPC}
            TicketsCount := TicketsCount + 1; // Inc may be slower in FPC
          {$ELSE}
            Inc(TicketsCount);
          {$ENDIF}
  d2 := Now;
  writeln('Found ', TicketsCount, ' tickets. Elapsed time, msec: ', DateUtils.MilliSecondsBetween(d1, d2));
end.

To compile from command line with FPC

fpc -O2 -Cr- HappyTickets.pas

To compile from command line with Delphi 7

dcc32 -$O+ -$R- -$Q- -$I- -$C- -$D- happytickets.pas

To compile from command line with Delphi DX 10 (other XE version should be compiled too)

dcc32 -CC -VT -NSSystem -$O+ -$R- -$Q- -$I- -$C- -$D- happytickets.pas...dcc64 -CC -VT -NSSystem -$O+ -$R- -$Q- -$I- -$C- -$D- happytickets.pas

Comments

In FPC 3.0.0 64bits/Linux :

  • changing the type of n1-n8 from 0..9 to longint increases the time by 10%
  • changing the type of n1-n8 from 0..9 to integer doubles the time!!

In Delphi Inc() is faster until you turn on Overflow checking. See example.

About longint type requirement. With the integer type the FPC optimizer seems to replace type with shortint (16-bits) and I see 31902 instead of 4816030 in my configuration.

In Delphi XE 10 changing the type of n1-n8 from 0..9 to integer decreases the time by 60%.

C

The program will compile with GNU C, MSVC and Borland C.

#include <stdio.h>
#include <time.h>

int main()
{
  unsigned char n1, n2, n3, n4, n5, n6, n7, n8;
  long int tickets_count = 0;
  clock_t t1, t2;  // forward declaration to prevent MS VC 14.0 error
  double msec;
  t1 = clock();
  for (n1 = 0; n1 < 10; n1++)
    for (n2 = 0; n2 < 10; n2++)
      for (n3 = 0; n3 < 10; n3++)
        for (n4 = 0; n4 < 10; n4++)
          for (n5 = 0; n5 < 10; n5++)
            for (n6 = 0; n6 < 10; n6++)
              for (n7 = 0; n7 < 10; n7++)
                for (n8 = 0; n8 < 10; n8++)
          if (n1 + n2 + n3 + n4 == n5 + n6 + n7 + n8)
            tickets_count++;
  t2 = clock();
  msec = (double)(t2 - t1) / ((double)CLOCKS_PER_SEC / 1000);
  printf("Found %ld tickets. Time elapsed: %.0f msec\n", tickets_count, msec);
  return 0;
}

To compile from command line with GNU C

gcc happytickets.c -O2 -o happytickets

To compile from command line with Microsoft VC++ (change paths if need)

set PATH=C:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\bin;C:\Program Files (x86)\Microsoft Visual Studio 9.0\Common7\IDE;%PATH%set LIB=C:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\lib;C:\Program Files\Microsoft SDKs\Windows\v6.0A\Libset INCLUDE=C:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\includecl.exe /O2 happytickets.c

To compile from command line with Borland C (change paths if need)

set PATH=C:\Borland\BCC55\Bin;%PATH%bcc32.exe -O2 -I"C:\Borland\BCC55\Include" -L"C:\Borland\BCC55\Lib" happytickets.c

C#

The program will compile with Mono and Microsoft.NET.

using System;

namespace HappyTickets
{
  class Entry
  {
    public static void Main (string[] args)
    {
      byte n1, n2, n3, n4, n5, n6, n7, n8;
      int tickets_count = 0;
      DateTime d1 = DateTime.Now;
      for (n1 = 0; n1 < 10; n1++)
    for (n2 = 0; n2 < 10; n2++)
      for (n3 = 0; n3 < 10; n3++)
        for (n4 = 0; n4 < 10; n4++)
          for (n5 = 0; n5 < 10; n5++)
        for (n6 = 0; n6 < 10; n6++)
          for (n7 = 0; n7 < 10; n7++)
            for (n8 = 0; n8 < 10; n8++)
              if (n1 + n2 + n3 + n4 == n5 + n6 + n7 + n8)
            tickets_count++;
      DateTime d2 = DateTime.Now;
      int msec = (int)d2.Subtract(d1).TotalMilliseconds;
      Console.WriteLine("Found {0} tickets. Time elapsed: {1} msec", tickets_count, msec);
    }
  }
}

To compile with Mono from command line

mcs happytickets.cs -optimize

To compile with Microsoft .NET 4 from command line

rem set PATH=C:\Windows\Microsoft.NET\Framework\v4.0.30319;%PATH%set PATH=C:\Windows\Microsoft.NET\Framework64\v4.0.30319;%PATH%csc.exe happytickets.cs -optimize

Rust

use std::time::Instant;

fn main() {
  let mut tickets_count: u32 = 0;
  let start = Instant::now();
  for n1 in 0..10 {
    for n2 in 0..10 {
      for n3 in 0..10 {
        for n4 in 0..10 {
          for n5 in 0..10 {
            for n6 in 0..10 {
              for n7 in 0..10 {
                for n8 in 0..10 {
                  if n1 + n2 + n3 + n4 == n5 + n6 + n7 + n8 {
                    tickets_count = tickets_count + 1;
                  }
                }
              }
            }
          }
        }
      }
    }
  }
  let elapsed = start.elapsed();
  println!("Found {} tickets. Time elapsed: {} ms", tickets_count, elapsed.as_millis());
}

To install and compile on Linux Ubuntu

$ sudo apt install rustc$ rustc happytickets.rs -C opt_level=3 -o happytickets

Golang

package main

import (
  "fmt"
  "time"
)

func main() {
  var tickets_count int = 0
  var t1 = time.Now()
  for n1 := 0; n1 < 10; n1++ {
    for n2 := 0; n2 < 10; n2++ {
      for n3 := 0; n3 < 10; n3++ {
        for n4 := 0; n4 < 10; n4++ {
          for n5 := 0; n5 < 10; n5++ {
            for n6 := 0; n6 < 10; n6++ {
              for n7 := 0; n7 < 10; n7++ {
                for n8 := 0; n8 < 10; n8++ {
                  if n1 + n2 + n3 + n4 == n5 + n6 + n7 + n8 {
                    tickets_count++
                  }
                }
              }
            }
          }
        }
      }
    }
  }
  var t2 = time.Now()
  var diff = t2.Sub(t1)
  fmt.Printf("Found %d tickets. Time elapsed: %d msec\n",
    tickets_count, diff.Nanoseconds() / int64(time.Millisecond))
}

To compile on Linux Ubuntu

$ go build happytickets.go

Results

Series 1

  • HP ProBook 6550b, Intel(R) Core(TM) i5 CPU M 520, RAM 8 GB
  • Ubuntu 14.04 64 bits Linux 3.16.0-60-generic
Compiler Average time (for 10 runs), msec
NASM 2.10.09 64 bits 240
Free Pascal Compiler version 2.6.4 [2014/04/20] for x86_64 355
Free Pascal Compiler version 3.0.0 [2015/12/05] for x86_64 332
gcc version 4.8.4 (Ubuntu 4.8.4-2ubuntu1~14.04) 116
Mono C# compiler version 3.2.8.0 260

As we can see, FPC 3.0 looks about 7% better. Unfortunately, I cannot run Delphi test because of Linux so the results of your series are welcome.

Series 2

The results was gracefully provided by Norbert Saint Georges (tetrasys.fi).

  • Intel(R) Core(TM)i7 CPU 920 \@2.67GHz
  • Win7 64bits
Compiler Average time (for 10 runs), msec
Pascal Code Typhon v 5500 32bits 371
Lazarus V1.4.4 Free Pascal Compiler v2.6.4 32bits 302
Lazarus V1.6.0 Free Pascal Compiler v3.0.0 32bits 260
Delphi 7 32bits 400 (with 0..9 type)
RemObject Oxygene 8.1.85.1801 (Pascal-like) 168
MS Visual C++ V10.0 64bits 205

Series 3

  • VirtualBox VM on Intel(R) Core(TM) i5-3470 CPU 3,2 GHz, 4 cores (2 cores for VM), RAM for VM 2 GB
  • Windows Server 2012 64 bits
Compiler Average time (for 10 runs), msec
Delphi 7 32 bits 155 (215 with 0..9 type)
Delphi XE 10.1 32 bits 187
Delphi XE 10.1 64 bits 203
Free Pascal Compiler version 2.6.4 [2015/07/11] for i386 189
Microsoft (R) Visual C# Compiler version 4.0.30319.33440 64bits 117
Microsoft (R) Visual C# Compiler version 4.0.30319.33440 32bits 125
Borland C++ 5.5.1 for Win32 188
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 15.00.21022.08 for 80x86 125

Series 4

The results was gracefully provided by Steven Chesser (Delphi group in Facebook).

  • Dell M4800, Intel(R) Core(TM) i7-4900MQ CPU \@2.8GHz
  • Win7 64bits
Compiler Average time (for 10 runs), msec
Delphi XE8 32bits 193 (with 0..9 type)
Delphi XE8 64bits 201 (with 0..9 type)
Delphi XE10 Seattle 32bits 181 (with 0..9 type)
Delphi XE10 Seattle 64bits 202 (with 0..9 type)
Delphi 7 32bits 203
Free Pascal Compiler version 3.1.1 32bit 232
Free Pascal Compiler version 3.1.1 64bits 151

Notes. FPC 3.1.1 32bit with -O3 option: 210 msec. FPC 3.1.1 64bit with -O3 option: 154 msec.

Series 5

The results was gracefully provided by OBones (nzn.fr.delphi newsgroup).

  • Intel Core i7 870 @ 2.93GHz, RAM 8 GB
  • Windows 7 x64
Compiler Average time (for 10 runs), msec
Delphi XE7 32bits 303 (with 0..9 type)
Delphi XE7 64bits 374 (with 0..9 type)
Free Pascal Compiler version 2.6.4 32bit 260
Free Pascal Compiler version 2.6.4 64bits 240

Series 6 (2022-01-24)

  • HyperV VM on Intel(R) Core(TM) i7-9850H CPU @ 2.60GHz 2.59 GHz 6 cores (4 cores for VM), RAM for VM 16 GB
  • Ubuntu 20.04 LTS 64 bits
Compiler Average time (for 10 runs), msec
ASM 125
C# .NET 6 115
GCC 9.3.0 35
Rust 1.53.0 35
Go 1.17.6 linux/amd64 134