On 19/01/2011, at 6:03 PM, john skaller wrote:
>
> So .. can anyone see any reason why *1* object should be collected?
> One? Just one???
>
Oh yeah ...
var ls = list (1,2);
var leak = ls;
var i: int;
forall i in 0 upto 20 do
println "Pre rev, rev now";
ls = rev ls;
println "Post rev";
ls = ls + rev_map (fun (x:int)=>x+1) ls;
ls = ls + rev_map (fun (x:int)=>x-2) ls;
println$ len ls;
leak = copy ls;
//ls = rev ls;
//collect();
done;
~/felix>FLX_REPORT_COLLECTIONS=1 FLX_ALLOW_COLLECTION_ANYWHERE=1
FLX_FREE_FACTOR=1.1 ./lr
[FLX_REPORT_COLLECTIONS] Collection report enabled
Pre rev, rev now
Post rev
8
Pre rev, rev now
Post rev
32
Pre rev, rev now
Post rev
128
Pre rev, rev now
Post rev
512
Pre rev, rev now
Post rev
2048
Pre rev, rev now
Post rev
8192
Pre rev, rev now
Post rev
32768
Pre rev, rev now
Post rev
131072
Actually collect
actually collected 185677 objects, still allocated 5543760 bytes
Pre rev, rev now
Actually collect
actually collected 1 objects, still allocated 9999984 bytes
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
Post rev
Actually collect
actually collected 97878 objects, still allocated 8650920 bytes
Actually collect
actually collected 56212 objects, still allocated 8650920 bytes
Match Failure
Felix location: build/debug/lib/std/list.flx 139[9]-139[16]
C++ location : ./lr.cpp 336
See that? If "rev" gets interrupted by a collection, stuff fails.
Here's rev, written entirely in Felix:
noinline fun rev[T] (x:list[T]):list[T]= {
fun aux (x:list[T]) (y:list[T]) : list[T] =
{
return
match x with
| Empty[T] => y
| Cons[T] (?h, ?t) => aux t (Cons (h, y))
endmatch
;
}
return aux x Empty[T];
}
which generates this code:
//------------------------------
//C FUNC <11660>: rev
_poly_4657t_12831 FLX_REGPARM rev(FLX_APAR_DECL _poly_4657t_12831
_i11661_v11661_x){
_poly_4657t_12831 _i11665_v11665_aux__apos_2_mv_851;
_poly_4657t_12831 x_uncurry;
_poly_4657t_12831 _i11663_v11663_y;
x_uncurry = _i11661_v11661_x;
_i11663_v11663_y = ::flx::rtl::_uctor_(0,0);
_8958:;
_i11665_v11665_aux__apos_2_mv_851 = x_uncurry;
/*begin match*/
/*match case 1:|Empty[T]*/
if(!(_i11665_v11665_aux__apos_2_mv_851.variant==0) ) goto _8959;
return _i11663_v11663_y;
/*match case 2:|Cons[T] (h, t)*/
_8959:;
if(!(_i11665_v11665_aux__apos_2_mv_851.variant==1) ) goto _8960;
/*parallel assignment*/
_i11663_v11663_y = ::flx::rtl::_uctor_(1, new(*PTF
gcp,_tt12832_ptr_map,true)
_tt12832(_tt12832((*((_tt12832*)_i11665_v11665_aux__apos_2_mv_851.data)).mem_0,
_i11663_v11663_y)));
x_uncurry = (*((_tt12832*)_i11665_v11665_aux__apos_2_mv_851.data)).mem_1;
goto _8958;
/*match failure*/
_8960:;
FLX_MATCH_FAILURE("build/debug/lib/std/list.flx",139,9,139,16);
}
Note it's a normal C function and IMHO it is correct!
If you copy and paste this into an editor, and get rid of the confusing names,
you will see the routine more clearly:
list rev(list x){
list mv;
list x_uncurry;
list y;
x_uncurry = x;
y = ::flx::rtl::_uctor_(0,0);
_8958:;
mv = x_uncurry;
if(!(mv.variant==0) ) goto _8959;
return y;
_8959:;
if(!(mv.variant==1) ) goto _8960;
y = ::flx::rtl::_uctor_(1, new(*PTF
gcp,node_ptr_map,true)node(node((*((node*)mv.data)).mem_0, y)));
x_uncurry = (*((node*)mv.data)).mem_1;
goto _8958;
_8960:;
FLX_MATCH_FAILURE("build/debug/lib/std/list.flx",139,9,139,16);
}
Clearly, there are no temporary objects here: there's exactly one allocation.
now true, if you look at the Felix program, there's a deliberate leak prior
to this operation (the end of the last loop iteration) so any collection
should collect multiple objects. Why 1?
[The bet here is: it shouldn't have collected that 1 either.. that store
is being trashed .. ]
this could easily happen if the stack bounds being scanned were off. After all
we're
right in the middle of constructing a list node.
OR it could happen if I screwed up the parity of the object's shape, that's
the "mark" bit used by the collector. The usual collection algorithm
says "mark everything as unreachable then unmark everything reachable
and everything left over is unreachable". Felix does this, but it alternates
the flag between 0 and 1. It does this because after collection, all the
remaining (reachable) objects are already flagged "reachable" so we just
redefine the flag so now their flagged "unreachable". We make sure every
new object we create is flagged "unreachable". So when we come to do
a collection, everything is *already* flagged unreachable, so we don't need
to scan all objects to mark them unreachable, we just scan the reachable
ones to mark them reachable.
If that one object allocation that triggered the collection has the flag set
with
the value just before a collection is triggered, it is the wrong value:
it breaks the invariant.
--
john skaller
skal...@users.sourceforge.net
------------------------------------------------------------------------------
Protect Your Site and Customers from Malware Attacks
Learn about various malware tactics and how to avoid them. Understand
malware threats, the impact they can have on your business, and how you
can protect your company and customers by using code signing.
http://p.sf.net/sfu/oracle-sfdevnl
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
