Thursday, February 5, 2009

Ch6, Ex8

%First representation
declare
fun {NewCollector}
H in
{NewCell H|H}
end
proc {Collect C X}
H T in
{Exchange C H|(X|T) H|T}
end
fun {EndCollect C}
X|nil = @C
in
X
end

%Second representation
declare
fun {NewCollector}
H in
H|{NewCell H}
end
proc {Collect C X}
T in
{Exchange C.2 X|T T}
end
fun {EndCollect C}
X|Y = C
in
@Y = nil
X
end

%Test
local C in
C = {NewCollector}
{Collect C 1}
{Collect C 2}
{Collect C 3}
{Browse {EndCollect C}} %[1 2 3]
end

Notice that for both the implementations a collector C becomes useless once EndCollector has been called on it, I don't know if this is not supposed to happen for the actual solution.

Memory Usage: To find out memory usage of both versions of Collect we'll have to transform their body in kernel language.
%First Version
declare
proc {Collect C X}
local H in
local T in
local Tmp1 in
Tmp1 = H|(X|T)
local Tmp2 in
Tmp2 = H|T
{Exchange C Tmp1 Tmp2}
end
end
end
end
end

Memory Usage-
For Tmp1 = H|(X|T) it is (1+2)+(1+2)+m(X)= 6+m(X)
For Tmp2 = H|T it is 1+2 = 3
And assume that for Exchange operation the memory used be E0
Total Memory Used = 1+1+1+6+m(X)+1+3+E0 = 13+E0 + m(X)
13+E0 words become inactive after the call
%Second Version
declare
proc {Collect C X}
local T in
local Tmp1 in
Tmp1 = C.2 %Let this causes m0 memory
local Tmp2 in
Tmp2 = X|T
{Exchange Tmp1 Tmp2 T}
end
end
end
end


Memory Usage-
Total: 1+1+m0+1+(1+2)+m(X)+E0 = 6+m0+E0 +m(X)
and 6+m0+E0 words become inactive after the call. If m0=2(don't know for a fact though) then 8+E0 becomes inactive.

Its clear that second version will leave less work for garbage collector and will take less time allocating the memory and hence better from the performance perspective.

No comments:

Post a Comment