On Monday, 20 May 2013 at 16:40:27 UTC, Dmitry Olshansky wrote:
> Long story short - re-read the discussion in the Low-lock thread again:
> http://forum.dlang.org/thread/pelhvaxwjzhehdjtpsav@forum.dlang.org

To sum up the discussion, there are three problems with unsynchronized access to the __gshared instance reference:

1) Unbaked object - the writer might write the __gshared reference before it finished the construction of the actual object.

2) Non-atomic read/write - this could result in a bad reference where the reader get some bytes from the old reference and some bytes from the new reference.

3) Unsynchronized cache - reader reads the reference, but the part of it's cache that is mapped to the memory containing the object instance itself is out of date and has not received the object yet.

All these problems do not affect `hasInstance()` - which is the only part of my implementation that touches the __gshared reference without synchronization - simply because it does not touch the object and does not return the reference - it only checks if it's initialized:

1) It doesn't matter if the object is not ready, because when you want to actually access the object, you need to use `instance()` which has synchronization.

2) It does not matter if we get half a reference due to non-atomic read/write, because we only care if it's null or not. If the half reference we got is not null, that means the whole reference is not null and we have the correct answer. If the half reference we got is null - well, maybe the other half is not null, but the reference is only now being made not-null, so no harm is done it treating it as null for now(if we actually try to initialize it we will enter synchronization).

3) Since we don't try to access the object itself, we don't care that our local cache doesn't have it yet. Again - once we reach for the object itself, we will enter synchronization.

20-May-2013 22:14, Idan Arye пишет:
> On Monday, 20 May 2013 at 16:40:27 UTC, Dmitry Olshansky wrote:
>> Long story short - re-read the discussion in the Low-lock thread again:
>> http://forum.dlang.org/thread/pelhvaxwjzhehdjtpsav@forum.dlang.org
>
> To sum up the discussion, there are three problems with unsynchronized
> access to the __gshared instance reference:
>
> 1) Unbaked object - the writer might write the __gshared reference
> before it finished the construction of the actual object.
>
> 2) Non-atomic read/write - this could result in a bad reference where
> the reader get some bytes from the old reference and some bytes from the
> new reference.
>
> 3) Unsynchronized cache - reader reads the reference, but the part of
> it's cache that is mapped to the memory containing the object instance
> itself is out of date and has not received the object yet.
>
> All these problems do not affect `hasInstance()` - which is the only

2 & 3 do.

> part of my implementation that touches the __gshared reference without
> synchronization - simply because it does not touch the object and does
> not return the reference - it only checks if it's initialized:

It _reads_ the _shared_ reference without proper indication of this intent to the writers.

>
> 1) It doesn't matter if the object is not ready, because when you want
> to actually access the object, you need to use `instance()` which has
> synchronization.

Then where you see hasInstance to fit the bill?

>
> 2) It does not matter if we get half a reference due to non-atomic
> read/write, because we only care if it's null or not. If the half
> reference we got is not null, that means the whole reference is not null
> and we have the correct answer.

Or you may never get the reference updated until the cache got flushed. It's generally not defined when you will see the update until then (or some such hardware event). The word is *eventually*.

> If the half reference we got is null -
> well, maybe the other half is not null, but the reference is only now
> being made not-null, so no harm is done it treating it as null for
> now(if we actually try to initialize it we will enter synchronization).

So it doesn't matter if hasInstance is fulfilling it's questionable contract properly only sometimes.

> 3) Since we don't try to access the object itself, we don't care that
> our local cache doesn't have it yet. Again - once we reach for the
> object itself, we will enter synchronization.

The big question is how you imagine somebody would want to use this

The false case may stay this way for unknown amount of time for instance even after the initialization happened (on some architectures). At the very least make that read atomicLoad that will make the operation properly tied to the current view of memory.

Even if we assume it's atomic then the other big question is what is the use case.
I argue that hasInstance only welcomes poor designs like:

while(!hasInstance()){
	//busy wait  for somebody else to init it?
}
inst = instance();

or:
if(hasInstance()){
	//should be initialized then the call won't construct it
	... //dunno what advantage it gets
}
else{
	//might or might not initialize/block on call to instance()
	...//again dunno
}


I'd say:

If you need to poke under it to avoid initialization then you shouldn't be using lazy-init singleton in the first place.

If you need synchronization and coordination based on what the reference happens to be right now then there are tools far better fit for the job - mutexes, semaphore, condition vars etc.

The last but not least is the fact that LowLock returns TLS reference to a (__g)shared instance make me worry about how the users code now is full of hidden race conditions anyway. This applies to the pattern as presented not only your implementation of it.
So the singleton itself would need some synchronization... and for that it really should be marked shared. The alternative is to have a per-thread singleton without any locking.

-- 
Dmitry Olshansky

On Saturday, 18 May 2013 at 16:58:19 UTC, Idan Arye wrote:
> OK, I implemented everything and made a pull request: https://github.com/D-Programming-Language/phobos/pull/1294

I've added this to the review queue.

The module is in need of documentation (publishing not required) before it can be formally reviewed.

On Monday, 20 May 2013 at 21:01:36 UTC, Jesse Phillips wrote:
> On Saturday, 18 May 2013 at 16:58:19 UTC, Idan Arye wrote:
>> OK, I implemented everything and made a pull request: https://github.com/D-Programming-Language/phobos/pull/1294
>
> I've added this to the review queue.
>
> The module is in need of documentation (publishing not required) before it can be formally reviewed.

http://wiki.dlang.org/Review_Queue

Should have been more specific with this. The documentation looks to be sparse with few examples and little introduction. I'll have to do more examining of the specific functions/classes. Due to the nature of the module I may need to reconsider how much can actually go into an introduction.

On Monday, 20 May 2013 at 19:15:34 UTC, Dmitry Olshansky wrote:
> 20-May-2013 22:14, Idan Arye пишет:
>> 1) It doesn't matter if the object is not ready, because when you want
>> to actually access the object, you need to use `instance()` which has
>> synchronization.
>
> Then where you see hasInstance to fit the bill?

`hasInstance()` tells you if an instance is already initialized, without returning it and without risking in initializing it if it isn't already initialized.

>> 2) It does not matter if we get half a reference due to non-atomic
>> read/write, because we only care if it's null or not. If the half
>> reference we got is not null, that means the whole reference is not null
>> and we have the correct answer.
>
> Or you may never get the reference updated until the cache got flushed. It's generally not defined when you will see the update until then (or some such hardware event). The word is *eventually*.

When you call `instance()` to fetch the reference(opposed to `hasInstance()`, which only tells you if it's null), the thread will enter the synchronization block inside `instance()` which will make sure the cache is refreshed before it begins.

>> If the half reference we got is null -
>> well, maybe the other half is not null, but the reference is only now
>> being made not-null, so no harm is done it treating it as null for
>> now(if we actually try to initialize it we will enter synchronization).
>
> So it doesn't matter if hasInstance is fulfilling it's questionable contract properly only sometimes.

If `hasInstance()` returns `true`, you can assume that there is an instance for you to access, because even if the instance is not ready yet, some other thread has entered the synchronization block and the user can't get the instance until that thread finishes the instantiation - so from the thread's point of view, whenever it'll call `instance()` it'll get a ready instance that was not created beacause of it.

If `hasInstance()` returns `false` then it's not a guarantee that the singleton has not been instantiated, but even if `hasInstance()` was synchronized you wouldn't get that guarantee, because it is always possible that the singleton is instantiated after the synchronization in `hasInstance()` but before you get to act upon it's result.

The only way to get a `false` with that guarantee is to make the synchronization from outside `hasInstance()`. So, not using synchronization inside it does not break any contract an internally synchronized `hasInstance()` could promise.

>> 3) Since we don't try to access the object itself, we don't care that
>> our local cache doesn't have it yet. Again - once we reach for the
>> object itself, we will enter synchronization.
>
> The big question is how you imagine somebody would want to use this
>
> The false case may stay this way for unknown amount of time for instance even after the initialization happened (on some architectures). At the very least make that read atomicLoad that will make the operation properly tied to the current view of memory.

`atomicLoad` requires a `shared` reference. Using it will force me to turn the singleton into a shared singleton. Maybe I should add a shared version(I'll return to that at the end of this response), but I still want to keep the __gshared version.

> Even if we assume it's atomic then the other big question is what is the use case.
> I argue that hasInstance only welcomes poor designs like:
>
> while(!hasInstance()){
> 	//busy wait  for somebody else to init it?
> }
> inst = instance();
>
> or:
> if(hasInstance()){
> 	//should be initialized then the call won't construct it
> 	... //dunno what advantage it gets
> }
> else{
> 	//might or might not initialize/block on call to instance()
> 	...//again dunno
> }
>
>
> I'd say:
>
> If you need to poke under it to avoid initialization then you shouldn't be using lazy-init singleton in the first place.
>
> If you need synchronization and coordination based on what the reference happens to be right now then there are tools far better fit for the job - mutexes, semaphore, condition vars etc.

First and foremost - this is library library code, so it should expose as much interface as possible without exposing or breaking the implementation.

Personally, I think `hasInstance()` would be mainly used in the second use case you suggested. It would be useful if you have a long running loop(for example - a game loop) that needs to interact with the singleton instance if it exists, but can't or shouldn't instantiate it.

As for the first use case, you are right - it is a bad design to busy-wait for a singleton to be instantiated somewhere else. I should probably add another method that waits for the instance using a condition.

> The last but not least is the fact that LowLock returns TLS reference to a (__g)shared instance make me worry about how the users code now is full of hidden race conditions anyway. This applies to the pattern as presented not only your implementation of it.
> So the singleton itself would need some synchronization... and for that it really should be marked shared. The alternative is to have a per-thread singleton without any locking.

There is also a thread local version called `ThreadLocalSingleton`. If I made a shared version, would that solve those possible hidden race conditions? Is there a point in using the TLS Low Lock method for shared singletons?

On Monday, 20 May 2013 at 21:08:36 UTC, Jesse Phillips wrote:
> On Monday, 20 May 2013 at 21:01:36 UTC, Jesse Phillips wrote:
>> On Saturday, 18 May 2013 at 16:58:19 UTC, Idan Arye wrote:
>>> OK, I implemented everything and made a pull request: https://github.com/D-Programming-Language/phobos/pull/1294
>>
>> I've added this to the review queue.
>>
>> The module is in need of documentation (publishing not required) before it can be formally reviewed.
>
> http://wiki.dlang.org/Review_Queue
>
> Should have been more specific with this. The documentation looks to be sparse with few examples and little introduction. I'll have to do more examining of the specific functions/classes. Due to the nature of the module I may need to reconsider how much can actually go into an introduction.

Well, obviously an example introduction like in `std.concurrency` or `std.variant` will not fit - since `std.idioms` is not centered around a single feature - but a table organized by idioms will be in order, and ofcourse - a short general description.

I'll get to that as soon as I can.

On Monday, 20 May 2013 at 22:02:57 UTC, Idan Arye wrote:
> On Monday, 20 May 2013 at 19:15:34 UTC, Dmitry Olshansky wrote:
>> 20-May-2013 22:14, Idan Arye пишет:
>>> 1) It doesn't matter if the object is not ready, because when you want
>>> to actually access the object, you need to use `instance()` which has
>>> synchronization.
>>
>> Then where you see hasInstance to fit the bill?
>
> `hasInstance()` tells you if an instance is already initialized, without returning it and without risking in initializing it if it isn't already initialized.

Saying what it does is not a use-case.


> If `hasInstance()` returns `true`, you can assume that there is an instance for you to access, because even if the instance is not ready yet, some other thread has entered the synchronization block and the user can't get the instance until that thread finishes the instantiation - so from the thread's point of view, whenever it'll call `instance()` it'll get a ready instance that was not created beacause of it.

It can return true even if the instance has not been initialised yet or false if it has because there's no synchronisation on the read. Given that in either situation it can return either true or false, there's no use for it.

> First and foremost - this is library library code, so it should expose as much interface as possible without exposing or breaking the implementation.

Only if the interface is useful and not likely to promote bad code... It's better to give someone multiple tools, each well suited for its purpose, than one tool that tries to do everything but is not well suited to anything.

>
> Personally, I think `hasInstance()` would be mainly used in the second use case you suggested. It would be useful if you have a long running loop(for example - a game loop) that needs to interact with the singleton instance if it exists, but can't or shouldn't instantiate it.

In the second example you may as well do:
if (getRandomBool()) {
    ...
} else {
    ...
}

It has the exact same guarantees as your code.

So what's the point of 'hasInstance'?

On Monday, 20 May 2013 at 23:18:59 UTC, Diggory wrote:
> On Monday, 20 May 2013 at 22:02:57 UTC, Idan Arye wrote:
>> If `hasInstance()` returns `true`, you can assume that there is an instance for you to access, because even if the instance is not ready yet, some other thread has entered the synchronization block and the user can't get the instance until that thread finishes the instantiation - so from the thread's point of view, whenever it'll call `instance()` it'll get a ready instance that was not created beacause of it.
>
> It can return true even if the instance has not been initialised yet or false if it has because there's no synchronisation on the read. Given that in either situation it can return either true or false, there's no use for it.

If it returns `true` that means that either the instance is already initialized, or that it is currently being initialized in another thread. For all threads but the one that initializes the singleton, there is no difference between these two states:

1) a call to `instance()` will *not* create a new instance, and will return the *ready* instance.
2) a call to `singleton_tryInitInstance()` will *not* invoke the lazy initializer argument and will return `false`.
3) a call to `singleton_initInstance()` will *not* invoke the lazy initializer argument and will throw a `SingletonException`.

and ofcourse:

4) a call to `hasInstance()` will return `true`.

The only thing that will behave differently is a direct access to `__singleton_instance` - but this is something users of this library shouldn't be doing anyways!

>> First and foremost - this is library library code, so it should expose as much interface as possible without exposing or breaking the implementation.
>
> Only if the interface is useful and not likely to promote bad code... It's better to give someone multiple tools, each well suited for its purpose, than one tool that tries to do everything but is not well suited to anything.

Programmers are lazy - they won't check if a singleton has been instantiated just for fun, not when the singleton handles instantiation automatically, or the method for manual instantiation does that check for you.

Bad usage of `hasInstance()`(beside busy waiting that Dmitry Olshansky mentioned - I'm going to provide a condition waiting function for that) involves more effort and gives nothing in return - therefore, people won't use it.

>> Personally, I think `hasInstance()` would be mainly used in the second use case you suggested. It would be useful if you have a long running loop(for example - a game loop) that needs to interact with the singleton instance if it exists, but can't or shouldn't instantiate it.
>
> In the second example you may as well do:
> if (getRandomBool()) {
>     ...
> } else {
>     ...
> }
>
> It has the exact same guarantees as your code.
>
> So what's the point of 'hasInstance'?

    class Foo{
        mixin LowLockSingleton;

        public this(int x){
            ...
        }

        public void bar(){
            ...
        }
    }

    ......

    if(getRandomBool()){
        /*1*/ Foo.instance.bar();
    }

    if(Foo.hasInstance){
        /*2*/ Foo.instance.bar();
    }

/*1*/ has a chance to throw an `SingletonException` if `Foo` has not been instantiated yet.
/*2*/ will not throw(unless `bar()` throws), because if `Foo.hasInstance` returns true, that means that either:
1) Foo is already instantiated.
2) Foo is in the instantiation process, which means that `Foo.instance` will reach a synchronization block, wait until `Foo` is instantiated.
In both of those cases, the fact that `Foo.hasInstance` returned `true` guarantee that `Foo.instance` will return a reference to a ready-to-use instance.

21-May-2013 02:02, Idan Arye пишет:
> On Monday, 20 May 2013 at 19:15:34 UTC, Dmitry Olshansky wrote:

>> If you need synchronization and coordination based on what the
>> reference happens to be right now then there are tools far better fit
>> for the job - mutexes, semaphore, condition vars etc.
>
> First and foremost - this is library library code, so it should expose
> as much interface as possible without exposing or breaking the
> implementation.
>

A-ha. That's it and it's totally wrong. Exposing as much interface as possible is a disaster. Libraries (esp standard) take great deal of deliberation in picking what to expose. Exposing less is a common theme in interfaces. "Doing more" is a common theme in wrappers, helpers and has a proverbial "kitchen sink" effect.

> Personally, I think `hasInstance()` would be mainly used in the second
> use case you suggested. It would be useful if you have a long running
> loop(for example - a game loop) that needs to interact with the
> singleton instance if it exists, but can't or shouldn't instantiate it.

Message passing, queues, condition variables. Singleton pattern assumes you have an object with unknown initialization order and who ever touches it first gets to create it.

> As for the first use case, you are right - it is a bad design to
> busy-wait for a singleton to be instantiated somewhere else. I should
> probably add another method that waits for the instance using a condition.

And your are falling into a trap I decidedly put in my example - this is a no use case for singletons. Want to wait on smth to happen? - use *separate* condition var, event pump etc. Want to check on some external state? - same answer.

Though you might provide separate class for waitable singleton that incorporates
condition variable. Could be useful sometimes(?) in case there is no other logic
to define order of initialization.

BTW Why not just make a template Singleton!T instead of mixin?

>> The last but not least is the fact that LowLock returns TLS reference
>> to a (__g)shared instance make me worry about how the users code now
>> is full of hidden race conditions anyway. This applies to the pattern
>> as presented not only your implementation of it.
>> So the singleton itself would need some synchronization... and for
>> that it really should be marked shared. The alternative is to have a
>> per-thread singleton without any locking.
>
> There is also a thread local version called `ThreadLocalSingleton`. If I
> made a shared version, would that solve those possible hidden race
> conditions?

It would make people do something about it - shared allows only calling shared methods of a class and prohibits all basic operations on the fields. Points of race become fairly obvious - they need casts and lack of locks in the vicinity.

Every time I see __gshared I think "lazy, old and broken" and usually at least one of these is true.

> Is there a point in using the TLS Low Lock method for shared
> singletons?

Good question. Yes, it is as it will allow you to have lazy initialization from any thread on any multicores w/o always taking a lock. If you can't figure out how to make order of initialization deterministic (or who creates what and when) then these lazy-init singletons are good idea.

I personally despise singletons and the code patterns they introduce. IMHO lazy initialization (not to mistake with lazy loading/caching) is so rarely *required* that you may as well avoid it, and in D we have static this/shared static this.

-- 
Dmitry Olshansky

On Tuesday, 21 May 2013 at 06:44:02 UTC, Dmitry Olshansky wrote:
> A-ha. That's it and it's totally wrong. Exposing as much interface as possible is a disaster. Libraries (esp standard) take great deal of deliberation in picking what to expose. Exposing less is a common theme in interfaces. "Doing more" is a common theme in wrappers, helpers and has a proverbial "kitchen sink" effect.
>
>> ...
>
> Message passing, queues, condition variables. Singleton pattern assumes you have an object with unknown initialization order and who ever touches it first gets to create it.
>
>> ...
>
> And your are falling into a trap I decidedly put in my example - this is a no use case for singletons. Want to wait on smth to happen? - use *separate* condition var, event pump etc. Want to check on some external state? - same answer.

The user of a library usually knows what they want to do with the library much more than the designer of the library. I see no reason to force the user to hack around trying to get information that the library could easily provide them without breaking anything or exposing the implementation.

> Though you might provide separate class for waitable singleton that incorporates
> condition variable. Could be useful sometimes(?) in case there is no other logic
> to define order of initialization.
>
> BTW Why not just make a template Singleton!T instead of mixin?

Something like that is possible, but I believe it's place is in `std.idioms` but in `std.parallelism`, since it is very similar to `Task` - a structure that represents a calculation(in this case - the initialization) that will be performed sooner or later, and provides synchronization on the invocation, synchronized access to the result and information whether it happened already or not.

> It would make people do something about it - shared allows only calling shared methods of a class and prohibits all basic operations on the fields. Points of race become fairly obvious - they need casts and lack of locks in the vicinity.
>
> Every time I see __gshared I think "lazy, old and broken" and usually at least one of these is true.

D provides 3 types of global - `shared`, `__gshared` and `static`(which is only global in the same thread). Since a singleton is a lazy global, I'm gonna provide a implementation an implementation for each type of global D has and let the users choose, like they do with regular globals.

Though, it might be a good idea to rename it to `__GSharedSingleton`. On one hand, the double underline prefix represents an implementation detail. On the other hand, using just `GSharedSingleton` will be too similar to `SharedSingleton` and might confuse even more.

>> Is there a point in using the TLS Low Lock method for shared
>> singletons?
>
> Good question. Yes, it is as it will allow you to have lazy initialization from any thread on any multicores w/o always taking a lock. If you can't figure out how to make order of initialization deterministic (or who creates what and when) then these lazy-init singletons are good idea.

Is it possible to save a thread local copy of the lock though? I can't use `static`, because it'll have to be `static shared` to keep the `shared`ness of the instance, which will not be thread local.

Ofcourse, using a boolean is always possible, it'll just be slower.

> I personally despise singletons and the code patterns they introduce. IMHO lazy initialization (not to mistake with lazy loading/caching) is so rarely *required* that you may as well avoid it, and in D we have static this/shared static this.

Even if you think singletons are bad, you have to agree that some ways to implement them are far worse than others. My library implementation would be better than most project local implementations because I have put in it much more time and effort than the what's dedicated to such a common pattern in a large project, and because it is being peer reviewed here.