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.11.1 20231117
Mon, 04 Mar 2024 20:10:34 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)
rm binarytrees.f90
2.86s 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