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