The Computer Language
Benchmarks Game

binary-trees Fortran Intel program

source code

! -*- mode: f90 -*-
!
! $Id: binarytrees.1.ifc.code,v 1.16 2017/03/26 06:56:54 igouy-guest Exp $ ; $Name:  $
!
! The Computer Language Shootout Benchmarks
! http://benchmarksgame.alioth.debian.org/

! 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
     integer :: item
     type(treeNode), pointer :: left
     type(treeNode), pointer :: right
  end type treeNode

contains

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

    allocate(node)
    node = treeNode(item, 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(item, depth, node)
    integer, intent(in) :: item
    integer(kind=short), intent(in) :: depth
    type(treeNode), pointer :: node

    type(treeNode), pointer :: left, right

    nullify(left, right)

    if (depth > 0) then
       call BottomUpTree(item, depth - 1_short, left)
       call BottomUpTree(item, depth - 1_short, right)
    end if
    call NewTreeNode(left, right, item, 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(0, stretchDepth, stretchTree)
  write(*,"(2(a,i0))") "stretch tree of depth ", stretchDepth,  &
       tab//" check: ", ItemCheck(stretchTree)

  call BottomUpTree(0, maxDepth, longLivedTree)
  
  do depth = minDepth, maxDepth, 2
     iterations = 2**(maxDepth - depth + minDepth)
     check = 0
     do i = 1, iterations
        call BottomUpTree(i, 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
Intel(R) Fortran Intel(R) 64 Compiler for applications running on Intel(R) 64, Version 17.0.1.132 Build 20161005
Copyright (C) 1985-2016 Intel Corporation.  All rights reserved.
FOR NON-COMMERCIAL USE ONLY


Sun, 26 Mar 2017 01:32:06 GMT

MAKE:
/usr/local/src/intel/bin/ifort -O3 -xHost -qopenmp -static-intel -ip -lapr-1 binarytrees.f90 -o binarytrees.ifc_run
rm binarytrees.f90
0.26s 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