Benchmark of linear search and binary search, implemented in Fortran.

log

./main.x
 checking consistency ...
   lnr   bin cmp
     1     1   T
     2     2   T
     3     3   T
     3     3   T
     4     4   T
     6     6   T
     0     0   T
     0     0   T
 Benchmarking N =           10
time used for linear_search:   0.000044ms per loop
time used for binary_search:   0.000041ms per loop
Consistency of result: T

 Benchmarking N =          100
time used for linear_search:   0.000237ms per loop
time used for binary_search:   0.000060ms per loop
Consistency of result: T

 Benchmarking N =         1000
time used for linear_search:   0.002180ms per loop
time used for binary_search:   0.000081ms per loop
Consistency of result: T

 Benchmarking N =        10000
time used for linear_search:   0.021975ms per loop
time used for binary_search:   0.000146ms per loop
Consistency of result: T

 Benchmarking N =       100000
time used for linear_search:   0.219085ms per loop
time used for binary_search:   0.000134ms per loop
Consistency of result: T

Makefile

FC = gfortran
FFLAGS = -O3 -fbounds-check -Wall -Wextra -ffree-form -ffree-line-length-none

test: main.x
	./$<

main.x: main.f90
	$(FC) -o $@ $^ $(FFLAGS)

clean:
	rm -rf *.o *.x *.mod

searching_benchmark.f90

module foo
    implicit none
    integer, parameter :: q = selected_real_kind(10)

    contains

    subroutine cumsum(A, B)
        implicit none

        real(q), intent(in)  :: A(:)
        real(q), intent(out) :: B(:)

        integer :: N, i
        real(q) :: s

        N = size(A)

        s = A(1)
        B(1) = s

        do i = 2, N
            s = s + A(i)
            B(i) = s
        enddo
    end subroutine


    function binary_search(A, v) result(ret)
        real(q), intent(in) :: A(:)
        real(q), intent(in) :: v
        integer :: ret

        integer :: l, m, r
        integer :: N

        N = size(A)
        l = 0
        r = N + 1

        do while (l+1 /= r)
            m = (l + r) / 2
            if (A(m) <= v) then
                l = m
            else
                r = m
            end if
        enddo

        ret = mod(r, N+1)
    end function binary_search


    subroutine benchmark(N, nrep_)
        integer, intent(in) :: N
        integer, intent(in), optional :: nrep_

        real(q), allocatable :: A(:)
        real(q), allocatable :: B(:)
        integer :: nrep, i
        integer :: ret_lnr(5)
        integer :: ret_bin(5)

        real(q) :: timing_beg, timing_end

        if (.not. present(nrep_)) then
            nrep = 1000
        else
            nrep = nrep_
        end if

        allocate(A(N), B(N))
        call random_number(A)
        A(N/2-1:N/2+1) = 0.0
        call cumsum(A, B)

        print *, "Benchmarking N = ", N

        call cpu_time(timing_beg)
        do i = 1, nrep
            ret_lnr(1) = whichtohop(B, B(1))
            ret_lnr(2) = whichtohop(B, B(n/3))
            ret_lnr(3) = whichtohop(B, B(n/2))
            ret_lnr(4) = whichtohop(B, B(n*2/3))
            ret_lnr(5) = whichtohop(B, B(n))
        enddo
        call cpu_time(timing_end)

        print '("time used for linear_search: ", F10.6, "ms per loop")', 1000 * (timing_end - timing_beg) / nrep

        call cpu_time(timing_beg)
        do i = 1, nrep
            ret_bin(1) = binary_search(B, B(1))
            ret_bin(2) = binary_search(B, B(n/3))
            ret_bin(3) = binary_search(B, B(n/2))
            ret_bin(4) = binary_search(B, B(n*2/3))
            ret_bin(5) = binary_search(B, B(n))
        enddo
        call cpu_time(timing_end)

        print '("time used for binary_search: ", F10.6, "ms per loop")', 1000 * (timing_end - timing_beg) / nrep
        print '("Consistency of result: ", L1, /)', ALL(ret_lnr == ret_bin)

        deallocate(A, B)
    end subroutine benchmark


    subroutine correctness_check
        real(q) :: A(6)

        integer :: i_linear, i_binary

        A = [1.0, 2.0, 4.0, 5.0, 5.0, 6.0]

        print *, "checking consistency ..."
        print '(2A6,A4)', "lnr", "bin", "cmp"

        i_linear = whichtohop(A, 0.0_q); i_binary = binary_search(A, 0.0_q); print '(2I6,L4)', i_linear, i_binary, i_linear == i_binary
        i_linear = whichtohop(A, 1.0_q); i_binary = binary_search(A, 1.0_q); print '(2I6,L4)', i_linear, i_binary, i_linear == i_binary
        i_linear = whichtohop(A, 2.0_q); i_binary = binary_search(A, 2.0_q); print '(2I6,L4)', i_linear, i_binary, i_linear == i_binary
        i_linear = whichtohop(A, 3.0_q); i_binary = binary_search(A, 3.0_q); print '(2I6,L4)', i_linear, i_binary, i_linear == i_binary
        i_linear = whichtohop(A, 4.0_q); i_binary = binary_search(A, 4.0_q); print '(2I6,L4)', i_linear, i_binary, i_linear == i_binary
        i_linear = whichtohop(A, 5.0_q); i_binary = binary_search(A, 5.0_q); print '(2I6,L4)', i_linear, i_binary, i_linear == i_binary
        i_linear = whichtohop(A, 6.0_q); i_binary = binary_search(A, 6.0_q); print '(2I6,L4)', i_linear, i_binary, i_linear == i_binary
        i_linear = whichtohop(A, 7.0_q); i_binary = binary_search(A, 7.0_q); print '(2I6,L4)', i_linear, i_binary, i_linear == i_binary
    end subroutine correctness_check


    function whichtohop(A, v) result(ret)
        real(q), intent(in) :: A(:)
        real(q), intent(in) :: v
        integer :: ret

        real(q) :: lower, upper
        integer :: i
        integer :: N

        N = size(A)
        ret = 0
        lower = 0
        upper = 0

        do i = 1, N
            if (i == 1) then
                lower = 0
                upper = A(i)
            else
                lower = upper
                upper = A(i)
            end if

            if (lower <= v .and. v < upper) then
                ret = i
                exit
            end if
        enddo
    end function whichtohop
end module foo

program main
    use foo
    implicit none

    call correctness_check
    call Benchmark(10)
    call Benchmark(100)
    call Benchmark(1000)
    call Benchmark(10000)
    call Benchmark(100000)
end program