SudokuHelper - Example for uncoupled design via interfaces

[PeterBelow 238]

SudokuHelper is an application that acts like an electronic Sudoku grid. It supports 9x9, 12x12, and 16x16 Sudokus, both in the classic and Gosu variant, where cells can be marked to only accept even numbers. The application neither creates Sudokus itself nor provides a solver for them; it is just a more convenient way to solve a Sudoku from a magazine or other external source than doing it on paper, using pencil and eraser.

The application's main features are:

• Invalid cell values are marked in red.
• Candidate values can be added and removed from a cell. Setting a cell's value will automatically remove candidates no longer possible in other cells.
• All actions can be undone, the undo stack is only limited by available memory.
• Named marks can be set for the current undo stack state and one can later restore the stack to such a named mark.
• The complete Sudoku can be saved to file, including the undo stack, and later loaded again from such a file.

 

The project can be found on GitHub: https://github.com/PeterBelow/SudokuHelper

The code is a good example (IMO) of how to uncouple the UI from the "buisness" code using interfaces, in a kind of MVC design. It is free (public domain) without restrictions.

[Alexander Elagin 143]

Does not compile in 10.1 because of inline variables. What was the reason to use the cosmetic feature only available in the latest versions?

[PeterBelow 238]

23 hours ago, Alexander Elagin said:

Does not compile in 10.1 because of inline variables. What was the reason to use the cosmetic feature only available in the latest versions?

That code comes from the forin template that comes with newer versions of Delphi. Sorry for the inconvenience, but since I program mostly for my own use i'm not much concerned with compatibilty with older Delphi versions and simply did not notice this as a potential problem.

[MarkShark 27]

Thank you Peter!  I'm checking out your code and trying to learn some uncoupling/interface techniques.  In the HelperRegistry function I notice you use the following code to set the InternalHelperRegistry while also returning it.  Is it done this way for thread safety or is it just related to maintaining the proper refcount of the interface?

 

BTW:  Your posts through the years have been extremely helpful to me, so thanks as always! 

 

      Result := THelperRegistry.Create;
      Result._AddRef; // the call below does not increment the refcount!
      P:= InterlockedCompareExchangeObject(InternalHelperRegistry,
        TObject(Pointer(Result)), nil);
      if P <> nil then begin
        Result._Release;
        Result := InternalHelperRegistry;
      end; {if}

-Mark

[MarkShark 27]

Going to answer my own question after some research.   Looks like it's for thread safety!  Got it now, thanks.

 

[Anders Melander 1783]

35 minutes ago, MarkShark said:

Looks like it's for thread safety!

Doesn't look thread safe to me. I haven't looked at the code apart from the snippet you posted, but as far as I can see there's a race condition.

[MarkShark 27]

Anders, that may be the case.  I determined that it was for thread safety from some stack overflow posts that seemed to match the code style.  The link is https://stackoverflow.com/q/5392107/113128 and there are a number of suggestions that some of the implementation examples aren't fully safe.  It's definitely a good thing to keep in mind, thanks!

[Anders Melander 1783]

8 minutes ago, MarkShark said:

I determined that it was for thread safety from some stack overflow posts that seemed to match the code style.  The link is https://stackoverflow.com/q/5392107/113128 and there are a number of suggestions that some of the implementation examples aren't fully safe.  It's definitely a good thing to keep in mind, thanks!

Yes it does seem to come from that SO thread. The problem as I see it is that it mixes a lock free solution, that's meant to operate on pointers, with reference counted interfaces. Also I don't like the practice of creating an object and then freeing it if it's not needed anyway, but that's besides the point.

[PeterBelow 238]

10 hours ago, Anders Melander said:

Yes it does seem to come from that SO thread. The problem as I see it is that it mixes a lock free solution, that's meant to operate on pointers, with reference counted interfaces. Also I don't like the practice of creating an object and then freeing it if it's not needed anyway, but that's besides the point.

Well, interface references are  pointers, so the problem is just how to make sure the reference count stays correct, which the code does.

The singleton template the code was created from is quite old, however, predating the appearance of TMonitor by several years. There may be a cleaner way to implement this these days, but I don't like to change working code if there's no pressing reason to do so.

[Anders Melander 1783]

5 minutes ago, PeterBelow said:

Well, interface references are  pointers, so the problem is just how to make sure the reference count stays correct, which the code does.

The possible race condition I referred to has to do with the (presumably reference counted) lifetime of InternalHelperRegistry but since I haven't looked at the rest of the code there might not be a problem - for example if InternalHelperRegistry is guaranteed to stay alive elsewhere.

 

With regard to locklessnes, doesn't the instantiation of an object cause a lock in the memory manager?

[PeterBelow 238]

19 hours ago, Anders Melander said:

The possible race condition I referred to has to do with the (presumably reference counted) lifetime of InternalHelperRegistry but since I haven't looked at the rest of the code there might not be a problem - for example if InternalHelperRegistry is guaranteed to stay alive elsewhere.

 

With regard to locklessnes, doesn't the instantiation of an object cause a lock in the memory manager?

InternalHelperRegistry  is a "global" variable declared in the implementation section of the unit and will stay around for the lifetime of the application; it is set to nil in the unit finalization.

It has been some time since I last looked at the memory manager implementation, but a lock there does not protect against a race condition in the code assigning the resulting reference to a variable elsewhere.

[Anders Melander 1783]

16 minutes ago, PeterBelow said:

InternalHelperRegistry  is a "global" variable declared in the implementation section of the unit and will stay around for the lifetime of the application; it is set to nil in the unit finalization.

Got it. No race condition then.

 

1 minute ago, PeterBelow said:

It has been some time since I last looked at the memory manager implementation, but a lock there does not protect against a race condition in the code assigning the resulting reference to a variable elsewhere.

My point was that since the code instantiates an object it isn't as lockless as it appears. The locking being performed is just out of view.

A critical section would be much cheaper - and in plan view.

var
  HelperRegistryLock: TCriticalSection;
  InternalHelperRegistry: IHelperRegistry;

function HelperRegistry: IHelperRegistry;
begin
  // Once InternalHelperRegistry has been assigned no locking occurs
  if (InternalHelperRegistry = nil) then
  begin
    // Locking here only happens when there's a race to create the instance
    HelperRegistryLock.Enter; 
    try
      if (InternalHelperRegistry = nil) then
        // Locking inside MM only happens here - a single time
        InternalHelperRegistry := THelperRegistry.Create;
    finally
      HelperRegistryLock.Leave;
    end;
  end;
  Result := InternalHelperRegistry;
end;

initialization
  HelperRegistryLock := TCriticalSection.Create;
finalization
  InternalHelperRegistry := nil;
  HelperRegistryLock.Free;
end.

 

[Guest]

@Anders Melander, that is code even i can understand!

[Fr0sT.Brutal 900]

52 minutes ago, Anders Melander said:

A critical section would be much cheaper - and in plan view.

Using TMonitor over the instance itself could spare excess CS.

Btw, there are lots of such lazy inited singletones in RTL:

Quote

class function TEncoding.GetANSI: TEncoding;
var
  LEncoding: TEncoding;
begin
  if FANSIEncoding = nil then
  begin
    LEncoding := TMBCSEncoding.Create(GetACP, 0, 0);
    if InterlockedCompareExchangePointer(Pointer(FANSIEncoding), LEncoding, nil) <> nil then
      LEncoding.Free;
  end;
  Result := FANSIEncoding;
end;

 

 

[Anders Melander 1783]

Just now, Fr0sT.Brutal said:

Using TMonitor over the instance itself could spare excess CS.

Yes, but you can't use TMonitor without an instance which is exactly when we need it. A simply spinlock would probably be the cheapest in this particular case, but my example was just to illustrate what I meant.

 

1 minute ago, Fr0sT.Brutal said:

Btw, there are lots of such lazy inited singletones in RTL

Keyword here is Lazy

[Dalija Prasnikar 1396]

On 11/29/2021 at 2:55 AM, Anders Melander said:

Doesn't look thread safe to me. I haven't looked at the code apart from the snippet you posted, but as far as I can see there's a race condition.

It is thread-safe. This is commonly used pattern for thread-safe lazy instantiation.

[Anders Melander 1783]

4 minutes ago, Dalija Prasnikar said:

It is thread-safe.

Yes, I already acknowledged that. Having a Rudy moment?

[Dalija Prasnikar 1396]

2 hours ago, Anders Melander said:

My point was that since the code instantiates an object it isn't as lockless as it appears. The locking being performed is just out of view.

A critical section would be much cheaper - and in plan view.

The critical section or any other kind of lock requires another object that needs to be constructed and maintained separately for no reason. There is no need for introducing locks of any kind here. This is not only working code, but also good code for such situation.

[Anders Melander 1783]

4 minutes ago, Dalija Prasnikar said:

The critical section or any other kind of lock requires another object that needs to be constructed and maintained separately for no reason.

The critical section is only an object because Embarcadero chose to make it one. It doesn't need to be.

A spin lock is virtually costless and does not require any instantiation.

 

1 minute ago, Dalija Prasnikar said:

This is not only working code, but also good code for such situation.

Works, yes, but I beg to differ on the good part. It's not a pattern I would use. Too "clever".

[Dalija Prasnikar 1396]

34 minutes ago, Anders Melander said:

The critical section is only an object because Embarcadero chose to make it one. It doesn't need to be.

A spin lock is virtually costless and does not require any instantiation.

It is still separate entity.

34 minutes ago, Anders Melander said:

Works, yes, but I beg to differ on the good part. It's not a pattern I would use. Too "clever".

I don't mind you or anyone else writing code they are more comfortable with.

 

However, I will firmly defend this pattern as good code simply because it is. All lock-free code is "clever", there is no way around it and this is the simplest pattern as it gets for lock-free. And this pattern is also recognized and used across different languages. For anyone that wants to learn more and get out of their comfort zone, this is a good example to learn from.

[Anders Melander 1783]

16 minutes ago, Dalija Prasnikar said:

It is still separate entity.

It doesn't need to be, FTOH you can use the low bits of the pointer as a spin-lock flag.

 

4 minutes ago, Dalija Prasnikar said:

I don't mind you or anyone else writing code they are more comfortable with.

However, I will firmly defend this pattern as good code simply because it is.

That's rather condescending.  It's not that I'm not comfortable with it. It's just a solution I personally wouldn't use.

I would say that what constitutes "good" is subjective and not defined by "because it is".

[MarkShark 27]

Thanks Dalija and the other posters, this is all "good stuff" and I love to learn new things and techniques.  I'm not sure how the word condescending matches anything said here so far btw.  Also just as a note I see that Emba switched to using AtomicCmpExchange instead of InterlockedCompareExchangePointer in Delphi 11 (or perhaps earlier.)  Kind of interesting.

 

[Dalija Prasnikar 1396]

17 hours ago, Anders Melander said:

It doesn't need to be, FTOH you can use the low bits of the pointer as a spin-lock flag.

And how exactly would you do that in this scenario?

 

Not to mention that you are opposing simple full pointer exchange because it is too "clever", and your solution would be bit fiddling.

 

17 hours ago, Anders Melander said:

That's rather condescending.  It's not that I'm not comfortable with it. It's just a solution I personally wouldn't use.

Comfortable, prefer, personally use... those are all the same reasons, just different words. You are reading into words way too much. You don't want to use something because you have subjective reasons. I have no problem with that and I am doing the same in many places. 

The only reason why am I here objecting, is you saying this is not good pattern and this is not true and it sends wrong message to others that are not familiar with this kind of code. By you saying this is bad code, someone else might avoid such coding pattern because they will wrongly think it is a bad one. 

 

The only place where I wouldn't use this pattern is in places where constructed object is extremely heavy and where constructing object that would possibly be immediately discarded would consume plenty of resources or would take a lot of time.

 

17 hours ago, Anders Melander said:

I would say that what constitutes "good" is subjective and not defined by "because it is".

I already said why it is good, but I will repeat it.

 

It is lock-free, so the whole operation can be done with single reference (I am not talking about local variables, but broader scope where final reference is declared). There is no additional, separate entity involved. That is reason enough. 

[Dalija Prasnikar 1396]

17 hours ago, MarkShark said:

Also just as a note I see that Emba switched to using AtomicCmpExchange instead of InterlockedCompareExchangePointer in Delphi 11 (or perhaps earlier.)  Kind of interesting.

InterlockedCompareExchangePointer is part of Windows API. AtomicCmpExchange is added to provide cross-platform support. 

 

There is also TInterlocked class in System.SyncObjs that implements various static functions for performing interlocked operations, including CompareExchange that basically calls AtomicCmpExchange, but it is more convenient to use for some types.

[Anders Melander 1783]

40 minutes ago, Dalija Prasnikar said:

And how exactly would you do that in this scenario?

Okay. Here goes:

You can but don't need to do bit fiddling. We just need to store 3 different states in the pointer;

• Unassigned
• Assigned
• Locked - being assigned

It's easy to identify the first two states; If the pointer value is nil then the pointer is unassigned, if it's non-nil then it's assigned. But what about the locked state? Well, for a pointer to an object we can take advantage of the fact that memory allocations are aligned so the lower n bits will always be zero and can be (mis)used to store a lock flag. However since it's a pointer we can just as well just use a pointer value that are known never to be returned by the memory manager. For example ordinal 1.

var
  FSingleton: TSingleton = nil;

function Singleton: pointer;
const
  MagicValue = pointer(1);
begin
  if (TInterlocked.CompareExchange(FSingleton, MagicValue, nil) = nil) then
    FSingleton := TSingleton.Create;

  // Wait for value to become valid
  while (FSingleton = MagicValuel) do
    YieldProcessor;

  Result := FSingleton;
end;

 

1 hour ago, Dalija Prasnikar said:

Not to mention that you are opposing simple full pointer exchange because it is too "clever", and your solution would be bit fiddling.

Now you're mixing two different arguments. I'm not opposing full pointer exchange. I'm opposing the optimistic object instantiation (which presumably will cause a lock in the memory manager but regardless will be costlier than doing an explicit lock).