Re: [fpc-devel] Improving Ref Counting
peter green wrote: surely this also means 1: there has to be rtti for every field in every class so the compiler can follow the paths from the class That's almost required, not only for classes but for all data types that contain references (pointers) to managed objects. It's not necessarily RTTI where such information resides, the compiler (Delphi, at least) already maintains such tables for fields with reference counted data types. These tables are used in the Initialize and Finalize procedures of every data structure. 2: you can't safely cast between classes and untyped pointers or integers (because those refs would be invisible to the gc) It's a matter of the compiler specific handling of managed objects. Remember that dynamic strings (AnsiString), arrays etc. and their casts already have to be handled by the compiler. You'll encounter no problems with pointers as long as the objects are kept alive by references which GC recognizes. Consider an AnsiString and an PChar into the string, then the pointer will become invalid when the string is moved or destroyed. Likewise a pointer to an object will become invalid when the object is destroyes. These are situations which you'll have to consider already, even without GC. 3: the GC can't work with pointers to things for every class GC doesn't have to know about pointer types, it's sufficient to determine that an object at an address (pointer value) is referenced and consequently is alive. When such an object has fields with further references, then GC certainly must know about the data type of the object. That's why managed objects usually have a somewhat fixed standard layout, so that GC can find the class type and layout of the object from e.g. the VMT pointer. Alternatively managed objects can have an additional (hidden) reference to the layout information, stored before the begin of the object. Such a preamble also is used by classic memory managers, though with different contents, so that the MM can return the memory to the free memory pool when the object is free'd with e.g. FreeMem, Dispose or Destroy. At this level GC and traditional MM are not very different ;-) DoDi ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
RE: [fpc-devel] Improving Ref Counting
-Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of DrDiettrich Sent: 01 March 2005 07:33 To: FPC developers' list Subject: Re: [fpc-devel] Improving Ref Counting Jamie McCracken wrote: A GC needs to trace an object's references to see if anything still points to it. How else can it decide whether an object is no longer in use? GC starts from known alive object references, in static or local variables, and follows the references in these objects to further objects. Unused objects never occur in this search, so they need no special marking or other treatment. http://lists.freepascal.org/mailman/listinfo/fpc-devel surely this also means 1: there has to be rtti for every field in every class so the compiler can follow the paths from the class 2: you can't safely cast between classes and untyped pointers or integers (because those refs would be invisible to the gc) 3: the GC can't work with pointers to things for every class ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
Jamie McCracken wrote: A GC needs to trace an object's references to see if anything still points to it. How else can it decide whether an object is no longer in use? GC starts from known alive object references, in static or local variables, and follows the references in these objects to further objects. Unused objects never occur in this search, so they need no special marking or other treatment. Imagine objects represented as tiles, tied together by reference ropes. Lift one living tile, and all other living tiles will follow. The tiles without references from living tiles will be left on the floor. GC does nothing but lift the known alive tiles, and then sweeps the garbage from the floor. The references in static and local variables are known to live, their location is the only thing that a garbage collector has to know. It's very expensive. getmem is quite expensive, and you need it for every reference this way. Okay then use Tlist with preallocation of say half a dozen references - that should be efficient for 99% of cases for an individual object's references. Do you realize how much memory consume your suggestions? Talking abojects, each one increased by a list of references? I agree that there exist only few references to most objects, perhaps less than 2 references in average, but the management of the according lists will cost either time (getmem/freemem) or space (preallocation). DoDi ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
On 28 feb 2005, at 12:26, Jamie McCracken wrote: FPC uses an platform independent method. The C++ ABI isn't used. But it could be used on platforms that have a fairly stable and standardised C++ ABI (windows and Linux mainly). Other platforms can use the current FPC generic method as a fallback. FPC could use that trick on (pretty much?) any platform. It doesn't have to be compatible with the official C++ abi of that platform (just like the current technique isn't either). It just isn't implemented yet. Jonas ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
Jonas Maebe wrote: On 28 feb 2005, at 12:26, Jamie McCracken wrote: FPC uses an platform independent method. The C++ ABI isn't used. But it could be used on platforms that have a fairly stable and standardised C++ ABI (windows and Linux mainly). Other platforms can use the current FPC generic method as a fallback. FPC could use that trick on (pretty much?) any platform. It doesn't have to be compatible with the official C++ abi of that platform (just like the current technique isn't either). It just isn't implemented yet. Yes thats right which is why I think its best to optimise its implementation in the various RTLs (the Linux RTL could use the C++ ABI or something else depending on which is faster etc). jamie. Jonas ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
On 28 feb 2005, at 13:14, Jamie McCracken wrote: FPC could use that trick on (pretty much?) any platform. It doesn't have to be compatible with the official C++ abi of that platform (just like the current technique isn't either). It just isn't implemented yet. Yes thats right which is why I think its best to optimise its implementation in the various RTLs (the Linux RTL could use the C++ ABI or something else depending on which is faster etc). It's not the RTL that contains these tables, it's the compiler that generates them. Using a specific ABI (table layout) is only required to be compatible with such tables generated by other compilers, I doubt there are many (if any) speed differences among them. Jonas ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
Jamie McCracken wrote: A GC needs to trace an object's references to see if anything still points to it. How else can it decide whether an object is no longer in use? GC starts from known alive object references, in static or local variables, and follows the references in these objects to further objects. Unused objects never occur in this search, so they need no special marking or other treatment. Imagine objects represented as tiles, tied together by reference ropes. Lift one living tile, and all other living tiles will follow. The tiles without references from living tiles will be left on the floor. GC does nothing but lift the known alive tiles, and then sweeps the garbage from the floor. The references in static and local variables are known to live, their location is the only thing that a garbage collector has to know. It's very expensive. getmem is quite expensive, and you need it for every reference this way. Okay then use Tlist with preallocation of say half a dozen references - that should be efficient for 99% of cases for an individual object's references. Do you realize how much memory consume your suggestions? Talking aboX-MozillaX-Mozilla-Status: 0009jects, each one increased by a list of references? I agree that there exist only few references to most objects, perhaps less than 2 on average, but the management of the according lists will cost either time (getmem/freemem) or space (preallocation). DoDi ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
circular refs should also be done if applicable) 6) Whenever an exception is thrown, wait until its either handled or fully propagated and then perform some garbage collection. (traverse the single linked list of all managed objects and for each object check whether anything that references it is still valid and delete if appropriate). I also thought immediately what Uberto already said: how do you recognize a valid/invalid reference without accessing memory that is invalid in the mean time. Also note that the list of references must be a dynamically size structure, incurring getmem and size-change overhead on a simple assignment. I doubt performance would improve, specially since the edge of this problem (the worst 90%) can be taken off by simply disabling try...finally generation in places where they are unlikely to happen. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
Marco van de Voort wrote: circular refs should also be done if applicable) 6) Whenever an exception is thrown, wait until its either handled or fully propagated and then perform some garbage collection. (traverse the single linked list of all managed objects and for each object check whether anything that references it is still valid and delete if appropriate). I also thought immediately what Uberto already said: how do you recognize a valid/invalid reference without accessing memory that is invalid in the mean time. How does a GC do this? It would have the same problem? Also note that the list of references must be a dynamically size structure, incurring getmem and size-change overhead on a simple assignment. yes a single linked list is a very efficient dynamically sized structure and much cheaper than try..finally or using Tlist. I doubt performance would improve, specially since the edge of this problem (the worst 90%) can be taken off by simply disabling try...finally generation in places where they are unlikely to happen. Is there a real failsafe way of doing that? jamie. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
Marco van de Voort wrote: a valid/invalid reference without accessing memory that is invalid in the mean time. How does a GC do this? It would have the same problem? A GC manages all memory, local variable allocation inclusive. IOW, the way a GC does it, is not possible in a mixed environment. Are you saying it would be a managed pointer then which is allocated on the heap? (I had assumed the pointer would be on the stack and the object in the heap) Also note that the list of references must be a dynamically size structure, incurring getmem and size-change overhead on a simple assignment. yes a single linked list is a very efficient dynamically sized structure and much cheaper than try..finally or using Tlist. It's very expensive. getmem is quite expensive, and you need it for every reference this way. Okay then use Tlist with preallocation of say half a dozen references - that should be efficient for 99% of cases for an individual object's references. I doubt performance would improve, specially since the edge of this problem (the worst 90%) can be taken off by simply disabling try...finally generation in places where they are unlikely to happen. Is there a real failsafe way of doing that? Nothing is failsafe. However e.g. in RTL string routines exceptions shouldn't occur unless memory is exhausted, in case it doesn't matter much anyway. What about all other non string exceptions that can occur between creation and destruction of the ansistring? Multithreaded environments too? jamie. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
I also thought immediately what Uberto already said: how do you recognize a valid/invalid reference without accessing memory that is invalid in the mean time. How does a GC do this? It would have the same problem? A GC dont' try to recognize a valid/invalid reference, it is invoked to free unused memory, which it assume point to valid memory. Anyway I still don't understand the goal of this discussion. Do you want to add some managed object in fpc? OK, but I suggest to start studing how GC works in Java, Python and dotnet. As for me I'd rather ask for not managed Interfaces in Delphi (fpc ones are ok). Bye Uberto ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
Uberto Barbini wrote: I also thought immediately what Uberto already said: how do you recognize a valid/invalid reference without accessing memory that is invalid in the mean time. How does a GC do this? It would have the same problem? A GC dont' try to recognize a valid/invalid reference, it is invoked to free unused memory, which it assume point to valid memory. A GC needs to trace an object's references to see if anything still points to it. How else can it decide whether an object is no longer in use? Anyway I still don't understand the goal of this discussion. Do you want to add some managed object in fpc? OK, but I suggest to start studing how GC works in Java, Python and dotnet. I dont want a full blown GC just a way to speed up ref counting so that it can be used elsewhere. As for me I'd rather ask for not managed Interfaces in Delphi (fpc ones are ok). You already have them in Iunknown, ansistrings and variants. Its all a question of making them faster cause they are dog slow atm. jamie. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
A GC needs to trace an object's references to see if anything still points to it. How else can it decide whether an object is no longer in use? Yes, this is right, but it hasn't to decide if reference are valid or invalid. Moreover also the simpliest GC techniques (mark'n'swift) are quite slow and are usually running in a low priority thread in background. I dont want a full blown GC just a way to speed up ref counting so that it can be used elsewhere. Good luck, may you success where everyone else failed! ;) As for me I'd rather ask for not managed Interfaces in Delphi (fpc ones are ok). You already have them in Iunknown, ansistrings and variants. Its all a question of making them faster cause they are dog slow atm. I wish them NOT managed, you cannot free a interface in Delphi. Anyway, why you're saying that refcount is slow? Do you have any benchmark? If I recall you mentioned try..finally as the bottleneck, but AFAIK modern cpu should do it almost with zero overhead, differently from try..except. Bye Uberto Bye Uberto ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
05-02-27 12.35, skrev Jamie McCracken följande: Hi, Rather than continuing the GC stuff which seems fruitless I thought it might be better to improve what we have with ref counting (whilst taking a leaf out of the GC book as well). A more simplictic alternative could be to have objects (declared to be managed) managed in the same way as ansistrings. This would be easy to implement since the ansistring facilty could be reused. Also a block of memory could be declared to be managed in this way. Drawback for objects is that they could not refere to other objects in a circular manner, so this has to be handled manually. This feature could be especially useful for functions which returns objects or memory chuncks of arbitrary size like bitmaps. Olle ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
A more simplictic alternative could be to have objects (declared to be managed) managed in the same way as ansistrings. This is exactly what delphi do with interfaces, the result is an orrible mess, and passing them as parameters a nightmare. Refcounted objects are possible, python used them till version 2.x, but I don't think they should stay in pascal. Bye Uberto ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
05-02-27 13.47, skrev Uberto Barbini följande: A GC needs to trace an object's references to see if anything still points to it. How else can it decide whether an object is no longer in use? Yes, this is right, but it hasn't to decide if reference are valid or invalid. Moreover also the simpliest GC techniques (mark'n'swift) are quite slow and are usually running in a low priority thread in background. Afaik the simplest GC's need to have exclusive access to the heap and stack, so it cant be run in parallell with ordinary processing. Olle ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
[ Charset ISO-8859-1 unsupported, converting... ] Marco van de Voort wrote: circular refs should also be done if applicable) 6) Whenever an exception is thrown, wait until its either handled or fully propagated and then perform some garbage collection. (traverse the single linked list of all managed objects and for each object check whether anything that references it is still valid and delete if appropriate). I also thought immediately what Uberto already said: how do you recognize a valid/invalid reference without accessing memory that is invalid in the mean time. Another possibility is for the exception handling to Null the pointers on the stack if its not handled in the current subroutine. And that will have to be guarded in a try..finally, so we are back ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
On Sunday 27 February 2005 15:29, Peter Vreman wrote: Why are you looking at GC/Refcounting when the problem is the try..finally? It is better to rewrite the try..finally code using the C++ ABI for exception handling. +1 and it'd be benefical to all applications. Bye Uberto ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
Uberto Barbini wrote: On Sunday 27 February 2005 15:29, Peter Vreman wrote: Why are you looking at GC/Refcounting when the problem is the try..finally? It is better to rewrite the try..finally code using the C++ ABI for exception handling. +1 and it'd be benefical to all applications. Using the C++ ABI the overhead is almost zero. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
05-02-27 19.16, skrev Uberto Barbini följande: Thats a possibility, but then you do not win anything by running it in a thread. It could as well be run when a memory allocation is done, and then as a subroutine. No, because the background thread get more time slices during idle moments and none at all during intense computations. GC have to release the control as fast as possible and be able to resume the job where it left it. What I ment was that simple GC's is all-or-nothing, so if it is interupted, all work it has done so far is spoiled. But OK, it is better to attempt to do a collect during idle time. True parallell GC's exists, but they are then not simple. Do you mean in SMP systems? No I mean those which work incrementally. Afaik these also need to lock everytning when they do their increment, but that the increment is small in time. So OK it is not true parallell. Olle ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
Peter Vreman wrote: Why are you looking at GC/Refcounting when the problem is the try..finally? It is better to rewrite the try..finally code using the C++ ABI for exception handling. Where do you see improvements in the C++ ABI? Or even differences? Windows implements this ABI, and every language should use it in the intended way. Perhaps FPC implements a different method on other systems? DoDi ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
Jamie McCracken wrote:
Rather than continuing the GC stuff which seems fruitless I thought it
might be better to improve what we have with ref counting (whilst taking
a leaf out of the GC book as well).
A reasonable attempt.
2) Have a single linked list that contains references to all managed
objects (ansi strings, variants etc)
A pointer to the next object could be part of every managed object.
3) Each managed object also has a single linked list that contains
addresses of all pointers that reference it.
Now you replace an simple reference counter by a list of pointers?
What a waste of memory and runtime :-(
Consider what will happen with every assignment to a (managed) string
variable.
5) dec ref count means removing the pointer's address from that list.
When that list is empty the object is freed. (a check for eliminating
circular refs should also be done if applicable)
A check for circular references is just what GC never has to do. That's
why GC can execute in linear time. It also cannot be determined when a
check for circular references is required, as soon as more than one
object has to be managed. This means that this check must be run very
often, with low probability that it will find discardable object
clusters.
6) Whenever an exception is thrown, wait until its either handled or
fully propagated and then perform some garbage collection. (traverse the
single linked list of all managed objects and for each object check
whether anything that references it is still valid and delete if
appropriate).
This requires that it's known which objects are in/valid - how that?
Your ideas are not bad at all, so let me refine your model:
{Notes:
object in the following text means *managed* object.
A client object contains a reference to a server object.
}
1) Every object is accompanied by a list of references to other objects.
This list is required for the maintenance of the reference lists. The
list can become part of the RTTI, as a list of offsets to reference
fields in the objects of the same type.
2) All objects include an pointer to the next object. (Your 2).
3) Every object has a list of client objects (it is the list header).
A reference (list record) consists of an pointer to the referenced
object, and of an pointer to the next reference to the same (server)
object. (Your 3)
4) Subroutines include a list of references to managed objects. This
list is used to determine which references become invalid, after normal
or abnormal exit from a subroutine. (Your 6)
This list can be optimized by allocating all such variables in a
contiguous stack area, to eliminate linked-list management overhead.
Subroutine parameters must be managed similarly, but they can't be
reordered. The lists are static, part of the subroutine signature.
Now let's replace (3) by this:
5) Non-local variables are collected in another list of references.
and, oh wonder, we have all what's required to implement a GC!
In your model the reference lists (3) must be updated with every
assignment to a reference variable, and after exit from a subroutine.
Adding a reference (inc ref) doesn't cost much, but removing a reference
(dec ref) from the linked list can become expensive.
In a mark/sweep GC an additional mark bit in every object is required.
There exist enough usable bits, e.g. the low bits in every object
reference. In the first pass (mark) the list of static (non-local)
variables is examined, and all referenced objects are marked (alive).
Then the active subroutine list (stack) is traversed, and all referenced
objects are marked. Finally the list of all objects is traversed and
split into a life and an unknown list. Every marked object is put
into the life list, and all objects that it references are marked
alive as well. In a simple implementation the remaining unknown object
list can be traversed until it contains no more alive members. More
sophisticated algorithms may do that recursively, where recursion is
limited by the number of yet unmarked objects. The key point is the
linear traversal of the lists, without searches. In the final pass
(sweep) the mark bits in the life list are cleared, and it becomes
(is) the list of all remaining objects (2), and the objects in the
unknown list are discarded.
This may sound complicated, but all that happens in linear time. When
swapping will occur during GC, the same will occur in your model, when
the reference lists are updated. Now it should be clear why frequent
updates of the management information should be avoided.
I'm not perfect, any comments on above are appreciated.
DoDi
___
fpc-devel maillist - fpc-devel@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
Why are you looking at GC/Refcounting when the problem is the try..finally? It is better to rewrite the try..finally code using the C++ ABI for exception handling. Where do you see improvements in the C++ ABI? Or even differences? Windows implements this ABI, and every language should use it in the intended way. Perhaps FPC implements a different method on other systems? FPC uses an platform independent method. The C++ ABI isn't used. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Improving Ref Counting
You can finalize it, so that it releases all private resources. That's common practice in a GC environment. But then you are responsible when the interfaced object is referenced from one of the still remaining references, and it fails to act properly due to the missing resources. I wish I could use an interface exactly how I could use an object (create..try..finally..free). But that it's another topic. Anyway, why you're saying that refcount is slow? Do you have any benchmark? If I recall you mentioned try..finally as the bottleneck, but AFAIK modern cpu should do it almost with zero overhead, differently from try..except. Please separate the overhead in normal operation from the overhead in exception handling. I agree, but the ratio between try..finally without and with raised exception is something about 1/1, and often an exception break the loop anyway. IMHO from a performance pov only try..finally without exception matters. At least if you're not Chad! (pun to the author of Indy ;))) We had a lengthy thread about exception handling in a Delphi group there's one on Borland groups years ago, too. In normal operation a Try block requires to push and pop some pointers, comparable to the argument handling of a subroutine call. The invocation of the Finally code may cost a few extra cycles, because it has to be executable both in normal and abnormal program flow. The Exception code executes only when an exception occurs, so it does not add any time penalty in normal operation. Consequently one should eliminate chances for exceptions, not try/except/finally blocks ;-) My experiences and that lengthy discussion differs here: in delphi try ... finally ... end; is almost negible, without exception raised at least. I've no data here but with or without the block the time is quite the same. try ... except ...end; instead is really really really slow. with kylix the times were a bit higher but restoring after a exception was faster. I want to crono fpc now! ;)) Bye Uberto ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
