Preface: I don't want to extend the current discussions, about threads etc. The subject here is a possible language extension, that might allow to simplify the construction of shareable objects, while improving performance vs. already possible workarounds, optionally adding means to allow the compiler to assure correct and safe use of such objects.

The idea is a merge of reference counting and thread synchronization, which I could not find in any other language yet (dunno about ADA in detail), but which can be implemented easily in OPL/FPC. Inspiration came from TThreadList and Interfaces.

When interface references are reference counted, then it's possible to use the RefCount for automatic locking of the related object, so that it can be used by multiple threads *only* sequentially - preventing race conditions.

Until here everything can be achieved in every class, e.g. derived from TInterfacedObject, by modifying _AddRef and _Release accordingly. But the use of the object via interface references slows down the entire procedure, due to the overhead involved in calling interface methods vs. object methods, and the maintenance of the additional interface declaration.

I have no idea about the practical impact of that overhead, so the only questions are:

1. Would it make sense, perfomance-wise, to add reference-counted classes as a new language element?

2. Could further support be added, so that the compiler can assure that references to such objects can not be stored outside the calling procedure? I.e. only local variables and parameters would be allowed to contain such references, because otherwise the object could be locked permanently.

Let me give an example, based on TThreadList. Such a list is intended to hold objects, that are for exclusive use by only one thread at the same time. The disadvantage is the locking of *all* list elements at the same time, what can either cure or create possible deadlocks. Now you may understand why I would like to have single objects, protected in a similar way. Also other organizations (pipe=FIFO, stack=LIFO...) may be desireable with *shareable objects*, i.e. objects that are *intended* for communicating data safely across thread boundaries.

Based on already available features, an IShareable interface could be designed, whose implementation must lock the object when its RefCount exceeds 1, and unlocks it again when the RefCount reaches 1 again. You may note the weak point: every class can implement that interface differently, possibly violating the implied rules. This could not happen when a refcounted *class* could not override the implementation in the base class. So let's assume that all this is implemented in a TShareableObject class, for use similar to TInterfacedObject, where nobody has to care about the implementation of the required interface-related (and here: thread/data synchronization related) methods.

Now we can assume that IShareable objects/references can be used all over the code, with no further precautions in explicit code required, that the use of the object *and* its content is always synchronized and sequentialized properly. Specific interfaces can be derived from IShareable, e.g. IShareableList,
IShareableParamsAndResult<for_whatever_purpose>.

As far as FPC is concerned, the elimination of the additional interfaces in above workaround IMO would not only increase the acceptance of this model in the design of threaded applications, but also could demonstrate that "Pascal rules!", increasing the acceptance of FPC/OPL as an outstanding compiler and language :-)

Am I too euphoric?

DoDi

To me this seems like an excellent idea.

Especially when combined with features like "parallel" loop and "future" variables (like existing in Delphi Prism), that can be implemented based on a thread pool. All this can increase performance on SMP systems by "invisibly" using threads.

-Michael

Michael Schnell wrote

To me this seems like an excellent idea.

+1

Marcos Douglas

Hello FPC,

Thursday, June 30, 2011, 4:07:22 PM, you wrote:

HPD> Now we can assume that IShareable objects/references can be used all HPD> over the code, with no further precautions in explicit code required, HPD> that the use of the object *and* its content is always synchronized and HPD> sequentialized properly. Specific interfaces can be derived from HPD> IShareable, e.g. IShareableList,
HPD> IShareableParamsAndResult<for_whatever_purpose>.

So you mean that something like:

IMyObject inherited from IShareable the compiler must add stub code on each function/procedure/property to lock the interface ?

So a function like:

function iMyObject.Increment(a: integer): integer;
begin
  a:=a+1;
end;

must be "silently modified" by the compiler to something like:

function iMyObject.Increment(a: integer): integer;
begin
  IObjectCritical.Enter;
  try
    a:=a+1;
  finally
    IObjectCritical.Leave;
  end;
end;

????????????? To me it looks extremelly overkill.

If you think in the other approach, so when interface count is higher than one enter the critical section, it could not be done IMHO because when refcount reach 2 it could happend in thread 2 while thread 1 is inside a procedure of the object which could lead to unexpected results.

Maybe I missed something ?

So you mean that something like: IMyObject inherited from IShareable the compiler must add stub code on each function/procedure/property to lock the interface ?

No. The object is locked as long the code holds the reference to it.

DoDi

Hello FPC,

Thursday, June 30, 2011, 9:42:36 PM, you wrote:

> So you mean that something like: > > IMyObject inherited from IShareable the compiler must add stub code on > each function/procedure/property to lock the interface ?

HPD> No. The object is locked as long the code holds the reference to it.

In that case read my note at the end of the e-mail, I think it could not be done in that way.

No other thread can have a reference to the same object, and consequently cannot call its methods.

_AddRef:
   if RefCount > 0 then
     EnterCriticalSection(myCS);

This will block any other thread in the attempt to get another reference, until the thread owning myCS has left the critical section.

DoDi

While I do think that a "kind of reference counting" for locking/unlocking critical sections in fact is a great idea that definitely is worth considering, it might be possible, that the standard reference counting done by the compiler is not usable for that and the compiler would need to be equipped with a new feature on that behalf.

Thinking about that for just a few minutes I have not been able to come up with a definition of where exactly the compiler is supposed to increment/decrement the thread-reference-count. Can you ?

-Michael

Hmm, when the first reference is stored in a global variable, as was my intention, what happens to the refcount when a method is invoked immediately from that reference?

var ShareObj: ISomething;
...
ISomething.DoSomething;

Would a function (property getter...) help, that returns the reference, instead of a simple variable? I'm a bit clueless right now :-(

Thanks for the hint anyway :-)

DoDi

Hans-Peter Diettrich wrote

The idea is a merge of reference counting and thread synchronization, which I could not find in any other language yet (dunno about ADA in detail), but which can be implemented easily in OPL/FPC. Inspiration came from TThreadList and Interfaces.

Could there be a fully lockable object class?

I mean an class which (when locked) none of its
methods/properties/variables can be read/called/altered from outside except, of course, by the locking object itself.

Such a beast would deserve many coding efforts, which are unlikely to be ever taken. It's much simpler to control existing references to an object, since every use of an object deserves an object reference. No woman - no cry ;-)

DoDi

Thinking about that for just a few minutes I have not been able to come up with a definition of where exactly the compiler is supposed to increment/decrement the thread-reference-count. Can you ?

My intention was to just use *existing* refcounting procedures, whose functionality and implementation is known both useful and correct. They only had to be applied to a new object (sub)type, in addition to Interfaces.

Also reference counting occurs by object, not by thread. Thread blocking is handled by the related critical section, and consequently deserve no ads.

DoDi

Hans-Peter Diettrich wrote

Such a beast would deserve many coding efforts, which are unlikely to be ever taken. It's much simpler to control existing references to an object, since every use of an object deserves an object reference.

In a double-linked list (or a treeview kind of structure), a simplified Attach() procedure looks like below:

     FNextSibling := AParent.FNextSibling;
     AParent.FNextSibling := Self;
     FPrevSibling := AParent;
     FParent := AParent.FParent;
     if FNextSibling = nil then FParent.FLastChild := Self
     else FNextSibling.FPrevSibling := Self;

Now, in this piece of code we have the following 9 variables (each one a node object):

FNextSibling
FNextSibling.FPrevSibling
FParent
AParent
FParent.FLastChild
AParent.FNextSibling
AParent.FParent
FPrevSibling
Self

In a multi-core multi-threaded platoform, I simply cannot see (other than locking the whole object) how any amount of interlocking or critical sections (or whatever) can guarantee that none of these 9 variables (nodes) will not be altered/deleted while we're in Attach() procedure.

And, the problem isn't just the Attach() procedure, any thread (running on a different core) that reads any property (such as FirstChild, LastChild, NextSibling, Parent, PrevSibling etc.) of this node object cannot be guaranteed to get valid values.

BTW, the problem --as I see it-- isn't limited to double-linked lists; any object that that gets shared across threads running on different cores will have similar problems; it's just that nodes in double-linked lists (or treeviews) highlight the problem better than anything else I can think of right now.

No woman - no cry ;-)

Is that similar to "no pain, no gain" ;)

2011/7/1 Adem :

In a multi-core multi-threaded platoform, I simply cannot see (other than locking the whole object) how any amount of interlocking or critical sections (or whatever) can guarantee that none of these 9 variables (nodes) will not be altered/deleted while we're in Attach() procedure.

There is no thread-safe way to write to those variables safely without blocking access to each and every object in the entire collection as demonstrated.

And, the problem isn't just the Attach() procedure, any thread (running on a different core) that reads any property (such as FirstChild, LastChild, NextSibling, Parent, PrevSibling etc.) of this node object cannot be guaranteed to get valid values.

Presently, I feel you are 100% correct. I think with a similar case, which did employ CS as a full fence barrier (mentioned around here before) I had a bidirectional (double link list) problem exacerbating any outstanding cache issues by reUsing records. Meaning - in addition to First,Last, I also maintain a Recycled chain. I have a Recycled Pointer d/l/l chain so I could recycle records and avoid re-creating them over and over, since this is an HPC transactional server component.

So instead of calling new, often the system would just take the first acquire Recycled, swap with Recycled.Next, and use the Recycled pointer. If Recycled=nil, I would create a new data ptr.

Finally, remove is designed as LIFO. Just a few thoughts on this particular issue.

Andrew Brunner wrote

2011/7/1 Adem: There is no thread-safe way to write to those variables safely without blocking access to each and every object in the entire collection as demonstrated.

Why each and every object? I thought (b)locking only those touched in the Attach() procedure (9 nodes, in my ) would be sufficient; wouldn't it?

The more objects with indiviual locks are used together, the higher the risk of deadlocks (exponential increase?) :-(

DoDi

2011/7/1 Hans-Peter Diettrich :

Adem schrieb: > > Why each and every object? I thought (b)locking only those touched in > the Attach() procedure (9 nodes, in my ) would be sufficient; wouldn't it?

Each and every element in the collection may prove difficult to protect for a general purposing. This threadsafe list would be able to use it only one thread owns the list and uses the list in its own execution thread. For general thread-safe usage any read or write access to Item.Next,Item.Previous would need to be done within the scope of the lock itself to avoid corruption. Restricing general access to Item.Next, or Item.Previous would also prove counter-productive.

The more objects with indiviual locks are used together, the higher the risk of deadlocks (exponential increase?)

I don't think anyone would suggest that in real-world design - it's just expected outcome - for describing protection required.

I personally don't use interfaces. I would create items as Objects with getters/setters to Item.Next and Item.Previous et al could be accomplished by declaring attributes as property, and thus read and write would simply request the lock and establish a complex mechanism for either read barrier or write. Performance wouldn't be ideal but items would be completely protected.

TDLList=class()
private
  FLock:TRTLCriticalSection;
end;
TDLLItem=class()
private
  FNext: TDLLItem;
  FPrev: TDLLItem;
private
  function getNextItem:TItem;
public
  constructor Create(aOwner:TDLList); reIntroduce;
public
  property Next:TItem; read getNextItem;
end;
function TDLLItem.getNextItem():TDLLItem;
begin
  EnterCriticalSection(FOwner.FLock);
  Try
     Result:=FNext;
  Finally
    LeaveCriticalSection(FOwner.FLock);
  end;
end;

After just think about the above code, you can see things aren't that simple with the DLL. Even if Next,Prev reads are protected, Another thread could come in there and request the item be deleted/destroyed.

Thread

Thread1 code
...
   itm=List.First;
   while itmnil do begin
     itm.Process;
     itm=item.Next; // good
   end;
...

Thread2 code
...

  item=List.Any; // represents any Item in the List(could be result of

iterator function)

  if isItemToBeDeleted(Item) then
    List.Delete(Item);

...

Remember, First, Next, are getters with Locking CS. And if the lock is acquired for list iterations we're really going to not be able to use the list for transactional systems, which would be one of the primary reasons why developers would use threads in the first place.

The problem here is we are never really going to be able to create "fast and efficient" code to make an object like this ptr list completely thread-safe. Meaning threading concepts must be understood before a user creates and uses a list.

But in the code above, at some point thread1 will encounter and error because List.Delete freed the Item. And even though Delete, and all item Next,Prev getter/setters were fenced, the data will eventually be corrupted for multi-threaded usage.

Another problem may be that more often then not another thread may want to acquire a new object reference. What is the status of the cMem memory manager / with/without? Can one thread create an object and be freed by another thread? What about stacks? I know you can attach events to threads using an APC queue call under windows. Using that, the owner thread could pickup that callback and create an object instance, and then a mechanism can trigger the function to return (watch out for thread lock here)

These are some questions I would raise.