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).

I note that ref counting is very fast without all the implicit try..finally stuff so I was wondering if it was possible to implement it without them (whilst still being able to free them even if an exception occurs).

My proposal is to do the following (its a hybrid ref count/GC):

1) Remove all implicit try..finally in ref counting.
2) Have a single linked list that contains references to all managed objects (ansi strings, variants etc)
3) Each managed object also has a single linked list that contains addresses of all pointers that reference it.
4) inc ref count means adding the pointer's address to that list
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)
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).

Im not sure if there are any corner cases where the above would not work but it does have the advantage of being very fast and very efficient memory wise. It also avoids the problem of extended lifetimes that you get with GCs. The only performance hit you will get is when an exception occurs but considering they only occur in exceptional circumstances and that exceptions are slow anyhow I dont think thats any loss. If no exceptions are thrown then no GC needs to be performed ever. Can we get away with doing this?

jamie.

If so raising an exception will freeze your application, checking some thousand hundreds of lists.
And how do you reconnaize a valid reference from an invalid one?

Bye Uberto

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.

There would be a small delay yes but Pascal is very fast so even checking many thousands of lists should only take a few milliseconds on a reasonable machine. Dont forget all GCs do this whenever garbage allocation is performed.

And how do you reconnaize a valid reference from an invalid one?

The same way a GC does?

jamie.

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.

> 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.

It's very expensive. getmem is quite expensive, and you need it for every reference this way.

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.

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

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)

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.

What about all other non string exceptions that can occur between creation and destruction of the ansistring?

Multithreaded environments too?

jamie.

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.

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! ;)

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

05-02-27 12.35, skrev Jamie McCracken följande:

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

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

05-02-27 13.47, skrev Uberto Barbini följande:

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

Another possibility is for the exception handling to Null the pointers on the stack if its not handled in the current subroutine.

jamie.

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.

What you mean with parallell? I imagine that it's protected into a critical section.
Anyway I'm not a GC expert but there's tons of stuff on GC theories and all python and Java sources to study! ;)

Bye Uberto

That is a solution yes. Or on the stack, but on termination the reference is killed, and you are back at the try..finally again

Still an dyn allocation extra. Ansistring performance is partially bound to it, and you double it.

They lead to mem leaks.

Multithreaded environments too?

Yes.

[ Charset ISO-8859-1 unsupported, converting... ]

And that will have to be guarded in a try..finally, so we are back....

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.

My proposal is to do the following (its a hybrid ref count/GC): 1) Remove all implicit try..finally in ref counting.

Already supported: {$implicitexceptions off}

Peter

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

05-02-27 14.23, 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.

True parallell GC's exists, but they are then not simple.

Olle

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.

True parallell GC's exists, but they are then not simple.

Do you mean in SMP systems?

Bye Uberto

It can also compact generations that are not in the current working set.

Using the C++ ABI the overhead is almost zero.

Out of curiosity, can you be more specific on why using C++ Application Binary Interface will reduce overhead?

Bye Uberto

05-02-27 19.16, skrev Uberto Barbini följande:

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

05-02-27 19.28, skrev Marco van de Voort följande:

If it is not in the working set it is not alive, no ?

Then it doesn't need compaction ?

Olle

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.

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

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

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

Uberto Barbini wrote

> 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.

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.

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. We had a lengthy thread about exception handling in a Delphi group, with interesting results. I don't know how exactly FPC implements Try blocks, but there shouldn't be much room for implementations very different from the Delphi (Windows) implementation.

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 ;-)

DoDi

FPC uses an platform independent method. The C++ ABI isn't used.

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.

I agree, but the ratio between try..finally without and with raised exception is something about 10000/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.

My experiences and that lengthy discussion differs here: in delphi
try ... finally ... end;
is almost negible, without exception '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

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.

jamie.

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

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.

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

Sorry, but it isn't so simple to just update the RTL. Also the compiler needs to be adapted to write exception frames (.eh_frame) sections.

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 thanX-Mozilla-Status: 0009 management of the according lists will cost either time (getmem/freemem) or space (preallocation).

DoDi

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

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

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