Memory Allocation in a Fixed-Point Algorithm

Question

I need to find the fixed point of f. The algorithm is very simple:

• Given X, we calculate f (X)
• If || Xf (X) || below a certain tolerance, exit and return of X, otherwise set X to f (X) and return to 1.

I want to be sure that I do not allocate memory for a new object at each iteration

Now the algorithm is as follows:

iter1 = function(x::Vector{Float64})
    for iter in 1:max_it
        oldx = copy(x)
        g1(x)
        delta = vnormdiff(x, oldx, 2)
        if delta < tolerance
            break
        end
    end
end

Here g1(x)is a function that sets xtof(x)

But it seems that this cycle highlights a new vector in each cycle (see below).

Another way to write the algorithm is as follows:

iter2 = function(x::Vector{Float64})
    oldx = similar(x)
    for iter in 1:max_it
        (oldx, x) = (x, oldx)
        g2(x, oldx)
        delta = vnormdiff(oldx, x, 2)
        if delta < tolerance
            break
        end
    end
end

where g2(x1, x2)is the function that sets x1to f(x2).

Is the most efficient and natural way to write such an iteration problem?

Edit1: , :

using NumericExtensions
max_it = 1000
tolerance = 1e-8
max_it = 100

g1 = function(x::Vector{Float64}) 
    for i in 1:length(x)
        x[i] = x[i]/2
    end
end

g2 = function(newx::Vector{Float64}, x::Vector{Float64}) 
    for i in 1:length(x)
        newx[i] = x[i]/2
    end
end

x = fill(1e7, int(1e7))
@time iter1(x)
# elapsed time: 4.688103075 seconds (4960117840 bytes allocated, 29.72% gc time)
x = fill(1e7, int(1e7))
@time iter2(x)
# elapsed time: 2.187916177 seconds (80199676 bytes allocated, 0.74% gc time)

Edit2: copy!

iter3 = function(x::Vector{Float64})
    oldx = similar(x)
    for iter in 1:max_it
        copy!(oldx, x)
        g1(x)
        delta = vnormdiff(x, oldx, 2)
        if delta < tolerance
            break
        end
    end
end
x = fill(1e7, int(1e7))
@time iter3(x)
# elapsed time: 2.745350176 seconds (80008088 bytes allocated, 1.11% gc time)

Answer 1

,

for iter = 1:max_it
    oldx = copy( x )
    ...

oldx = zeros( N )
for iter = 1:max_it
    oldx[:] = x    # or copy!( oldx, x )
    ...

, . , , for-loops . , ,

function test()
    N = 1000000

    a = zeros( N )
    b = zeros( N )

    @time c = copy( a )

    @time b[:] = a

    @time copy!( b, a )

    @time \
    for i = 1:length(a)
        b[i] = a[i]
    end

    @time \
    for i in eachindex(a)
        b[i] = a[i]
    end
end

test()

, Julia0.4.0 Linux (x86_64),

elapsed time: 0.003955609 seconds (7 MB allocated)
elapsed time: 0.001279142 seconds (0 bytes allocated)
elapsed time: 0.000836167 seconds (0 bytes allocated)
elapsed time: 1.19e-7 seconds (0 bytes allocated)
elapsed time: 1.28e-7 seconds (0 bytes allocated)

, copy!() , [:] , (, [:]). Btw, eachindex() .

vnormdiff(), norm( x - oldx ) .. , , x - oldx.