The Computer Language
24.06 Benchmarks Game

binary-trees Classic Fortran program

source code

! -*- mode: f90 -*-
!
! $Id: binarytrees.ifc,v 1.5 2017/03/27 06:27:17 igouy-guest Exp $ ; $Name:  $
!
! The Computer Language Benchmarks Game Benchmarks
! https://salsa.debian.org/benchmarksgame-team/benchmarksgame/

! contributed by Steve Decker
! based on the C version by Kevin Carson
! compilation:
!    gfortran -O3 -fomit-frame-pointer -funroll-loops binarytrees.f90
!
! This implementation does not need TR15581
!
! *reset*

module b_tree
  implicit none
  save

  integer, parameter :: short = selected_int_kind(1)

  type treeNode
     type(treeNode), pointer :: left
     type(treeNode), pointer :: right
  end type treeNode

contains

  subroutine NewTreeNode(left, right, node)
    type(treeNode), target, intent(in) :: left, right
    type(treeNode), pointer :: node

    allocate(node)
    node = treeNode(left, right)
  end subroutine NewTreeNode

  recursive function ItemCheck(tree) result (check)
    type(treeNode), pointer :: tree
    integer :: check

    if (.not. associated(tree%left)) then
       check = 1
    else
       check = 1 + ItemCheck(tree%left) + ItemCheck(tree%right)
    end if
    deallocate(tree)
  end function ItemCheck

  recursive subroutine BottomUpTree(depth, node)
    integer(kind=short), intent(in) :: depth
    type(treeNode), pointer :: node

    type(treeNode), pointer :: left, right

    nullify(left, right)

    if (depth > 0) then
       call BottomUpTree(depth - 1_short, left)
       call BottomUpTree(depth - 1_short, right)
    end if
    call NewTreeNode(left, right, node)
  end subroutine BottomUpTree
end module b_tree

program binarytrees
  use b_tree
  implicit none

  integer(kind=short), parameter :: minDepth = 4_short
  character,           parameter :: tab = achar(9)

  integer :: i, iterations, check
  integer(kind=short) :: N, depth, maxDepth, stretchDepth
  character(len=2) :: argv
  type(treeNode), pointer :: stretchTree => null(), longLivedTree => null(),  &
                             tempTree => null()

  call get_command_argument(1, argv)
  read (argv, "(i2)") N

  maxDepth = max(minDepth + 2_short, N)

  stretchDepth = maxDepth + 1_short
  call BottomUpTree(stretchDepth, stretchTree)
  write(*,"(2(a,i0))") "stretch tree of depth ", stretchDepth,  &
       tab//" check: ", ItemCheck(stretchTree)

  call BottomUpTree(maxDepth, longLivedTree)
  
  do depth = minDepth, maxDepth, 2
     iterations = 2**(maxDepth - depth + minDepth)
     check = 0
     do i = 1, iterations
        call BottomUpTree(depth, tempTree)
        check = check + ItemCheck(tempTree)
     end do
     write(*,"(2(i0,a),i0)") iterations, tab//" trees of depth ", depth,  &
          tab//" check: ", check
  end do

  write(*,"(2(a,i0))") "long lived tree of depth ", maxDepth,  &
       tab//" check: ", ItemCheck(longLivedTree)
end program binarytrees
    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
Fortran Compiler Classic
2021.12.0 20240222


 Mon, 03 Jun 2024 19:31:17 GMT

MAKE:
mv binarytrees.ifc binarytrees.f90
~/intel/oneapi/compiler/latest/bin/ifort -O3 -march=ivybridge -ipo -static -static-intel binarytrees.f90 -o binarytrees.ifc_run
ifort: remark #10448: Intel(R) Fortran Compiler Classic (ifort) is now deprecated and will be discontinued late 2024. Intel recommends that customers transition now to using the LLVM-based Intel(R) Fortran Compiler (ifx) for continued Windows* and Linux* support, new language support, new language features, and optimizations. Use '-diag-disable=10448' to disable this message.
ipo: warning #11021: unresolved __ehdr_start
        Referenced in libc.a(dl-support.o)
ld: /home/dunham/intel/oneapi/compiler/2024.1/lib/libifcoremt.a(for_close_proc.o): in function `for__close_proc':
for_close_proc.c:(.text+0x1df): warning: Using 'dlopen' in statically linked applications requires at runtime the shared libraries from the glibc version used for linking
rm binarytrees.f90

0.29s to complete and log all make actions

COMMAND LINE:
 ./binarytrees.ifc_run 21

PROGRAM OUTPUT:
stretch tree of depth 22	 check: 8388607
2097152	 trees of depth 4	 check: 65011712
524288	 trees of depth 6	 check: 66584576
131072	 trees of depth 8	 check: 66977792
32768	 trees of depth 10	 check: 67076096
8192	 trees of depth 12	 check: 67100672
2048	 trees of depth 14	 check: 67106816
512	 trees of depth 16	 check: 67108352
128	 trees of depth 18	 check: 67108736
32	 trees of depth 20	 check: 67108832
long lived tree of depth 21	 check: 4194303