Hi alle,

also das Thema ist ein relativ schweres und ich wollte hier mal nach ein
paar praktischen Erfahrungen fragen. Zum Beispiel wie ihr zu
"piggybacking with synchronization" steht. Aber erst mal was anderes
vielleicht...

Für eine Datenstruktur hier habe mir folgendes Muster ausgedacht:

[..]
> private DataStructure init() {
> //....
> return new DataStructure();
> }
>
> public void clearDataStructure() {
> unsynchronizedPointer = null;
> synchronized(this) { synchronizedPointer=null; }
> }
> }



Die Anwendung wird nun in vielen Threads gleichzeitig getDataStructure()
aufrufen und hin und wieder wird die DatenStruktur gelöscht. Da
getDataStructure() extrem oft aufgerufen wird würde ein synchonisieren
hier dafür sorgen eine Menge Rechenleistung zu verlieren, und das auch
schon bei nur einem einzigen Thread.

Mein nächster Schritt wäre das explizite clearDataStructure() in ein
implizites um zu wandeln.. Dann wäre das vielleicht eher sowas:

[..]
> synchronizedPointer = new WeakReference<DataStructure>(sp);
> unsynchronizedPointer = synchronizedPointer;
> return sp;
> }
> }
>
> private DataStructure init() {
> //....
> }
> }

Nun meine ich dass es theoretisch möglich ist, dass
unsynchronizedPointer ein nicht vollständig initialisiertes Objekt
bekommt, oder nicht?

Meine erste Idee war dies zu tun:

[..]
> synchronizedPointer = new WeakReference<DataStructure>(sp);
> }
> unsynchronizedPointer = synchronizedPointer;
> return sp;
> }
>
> private DataStructure init() {
> //....
> }
> }

da die Zuweisung nach dem synchronized block erfolgt und dieser selbst
sicherstellt, dass synchronizedPointer ein vollständiges Objekt bekommt,
welches nach Ende des Blocks auch Verfügbar ist... solltes dies doch
eigentlich sicher sein... oder?

Gruss theo

Responding to Jochen Theodorou:

>> DataStructure sp = synchronizedPointer.get();
>> synchronized(this) {
>> if (sp==null) sp = init();
>> synchronizedPointer = new WeakReference<DataStructure>(sp);
>> }
>> unsynchronizedPointer = synchronizedPointer;
>> return sp;

So kannst Du doch wiederum keine Garantie dafuer ableiten, dass der
Zugriff auf synchronizedPointer in der ersten Zeile ein vollstaendig
initialisiertes Objekt sieht, oder?

Viele Gruesse,
Patrick

Am 12.03.2010, 00:53 Uhr, schrieb Jochen Theodorou <blackdrag>:

>
> Die Anwendung wird nun in vielen Threads gleichzeitig getDataStructure()
> aufrufen und hin und wieder wird die DatenStruktur gelöscht. Da
> getDataStructure() extrem oft aufgerufen wird würde ein synchonisieren
> hier dafür sorgen eine Menge Rechenleistung zu verlieren, und das auch
> schon bei nur einem einzigen Thread.

Ist das eine Vermutung oder hast du das gemessen?


>> public DataStructure getDataStructure() {
>> DataStructure usp = unsynchronizedPointer.get();
>> if (usp!=null) return usp;
>> synchronized(this) {
>> DataStructure sp = synchronizedPointer.get();
>> if (sp==null) sp = init();
>> synchronizedPointer = new WeakReference<DataStructure>(sp);
>> unsynchronizedPointer = synchronizedPointer;
>> return sp;
>> }
>> }

Erinnert mich irgendwie an double checked locking und ich bin mir fast
sicher, dass es sogar das gleiche Problem hat, solange
"unsynchronizedPointer" nicht volatile ist.

> Nun meine ich dass es theoretisch möglich ist, dass
> unsynchronizedPointer ein nicht vollständig initialisiertes Objekt
> bekommt, oder nicht?

Das meine ich auch.


>
> da die Zuweisung nach dem synchronized block erfolgt und dieser selbst
> sicherstellt, dass synchronizedPointer ein vollständiges Objekt bekommt,
> welches nach Ende des Blocks auch Verfügbar ist... solltes dies doch
> eigentlich sicher sein... oder?

Das ist eine Fehlannahme, siehe:
http://www.cs.umd.edu/~pugh/java/mem...edLocking.html
unter "A fix that doesn't work".

"Unfortunately, that intuition is absolutely wrong. The rules for
synchronization don't work that way. The rule for a monitorexit (i.e.,
releasing synchronization) is that actions before the monitorexit must be
performed before the monitor is released. However, there is no rule which
says that actions after the monitorexit may not be done before the monitor
is released. It is perfectly reasonable and legal for the compiler to move
the assignment helper = h; inside the synchronized block, in which case we
are back where we were previously. Many processors offer instructions that
perform this kind of one-way memory barrier. Changing the semantics to
require releasing a lock to be a full memory barrier would have
performance penalties."

In deinem Fall ist es also legal, dass der Compiler "unsynchronizedPointer
= synchronizedPointer;" in den synchronized-Block zieht.

Ich frage mich beim Blick auf den synchonized Block auch, warum du nicht
auf ein Lock-Objekt für dieses Feld synchronisierst. Gesetzt der Fall du
hast mehrere Felder auf die synchroniert zugegriffen werdeb muss, würdest
du mit synchronized(this) auf das ganze objekt locken, nicht nur auf das
Feld.

Also eher so:

private final syncPointerLock = new Object();
private DataStructure synchronizedPointer = ...

DataStructure getDataStructure(){
synchronized(syncPointerLock){
DataStructure sp = synchronizedPointer.get();
if(sp == null) sp = init();
synchronizedPointer = new WeakReference<DataStructure>(sp);
return sp;
}
}

Wenn du auf die WeakReference verzichtest und das Löschen wieder explizit
machst, kannst du dir vielleicht auch was mit einer
AtomicMarkableReference bauen, statt mit synchronization, aber ich würde
es mich an Josh Bloch halten:

"
If you need high-performance lazy initializing of an instance field, use
the double-check idiom with a volatile field. This idiom wasn't guaranteed
to work until release 5.0, when the platform got a new memory model. The
idiom is very fast but also complicated and delicate, so don't be tempted
to modify it in any way. Just copy and paste -- normally not a good idea,
but appropriate here:

// Double-check idiom for lazy initialization of instance fields.
private volatile FieldType field;
FieldType getField() {
FieldType result = field;
if (result == null) { // First check (no locking)
synchronized(this) {
result = field;
if (result == null) // Second check (with locking)
field = result = computeFieldValue();
}
}
return result;
}
"
http://java.sun.com/developer/techni...ive_08_qa.html

Was das synchronized in dem Snippet angeht: ich würde, wie gesagt, nicht
auf "this" locken, sondern auf ein Lock für genau dieses Feld.

Gruß,
-Wanja-

(schlaflos)

Am 12.03.2010 00:53, schrieb Jochen Theodorou:

> Für eine Datenstruktur hier habe mir folgendes Muster ausgedacht:
>

Zuweisung an Referenzen sind AFAIR atomar, daher kannst Du die
Synchronisation weglassen, wenn Du die Referenz volatile machst. Das ist
notwendig, weil es nicht reicht, der Variablen etwas zuzuweisen, der
neue Inhalt muss auch an die anderen Threads übertragen werden. Diese
dürfen nämlich Kopien von Objekten cachen.

Etwa so:

class MultithreadDataStrcutureHandler {
private volatile DataStructure pointer;

public getDataStructure()
{
return pointer;
}

public void init()
{
DataStructure newData = DataStructure();
// Weitere Initialisierung

// Hier ist newData vollständig erzeugt, es muss nur noch
// zugänglich gemacht werden
pointer = newData; // atomar
}

// Konstruktor ruft init()
}

Du kannst dann gelegentlich init() aufrufen, wenn Änderungen anstehen.
Das funktioniert, solange init() nicht konkurrierend aufgerufen wird.
Wenn das der Fall ist, müsstest Du entweder die Erzeugung von newData in
init() synchronisieren oder den Compare-and-Swap-Mechanismus aus der
concurrent-Bibliothek verwenden.

Das andere grundsäzliche Problem mit diesem Design ist, dass Benutzer
von MultithreadDataStrcutureHandler nicht notwendig die neuesten Daten
verarbeiten:

MultithreadDataStrcutureHandler myHandler = ...;
DataStructure ds = myHandler.getDataStructure();
// Verbringe viel Zeit mit was anderem

// Hier ist ds möglicherweise längst veraltet:
System.out.println( "Der Wert ist "
+ ds.x
+ " - ob das noch stimmt?" );

> Da
> getDataStructure() extrem oft aufgerufen wird würde ein synchonisieren
> hier dafür sorgen eine Menge Rechenleistung zu verlieren, und das auch
> schon bei nur einem einzigen Thread.

Generell gibt es keinen Ersatz für Synchronisation, der das gleiche
leistet. Die Alternativen volatile und concurrent-Package grefen nur da,
wo man am entscheidenden Punkt eine Variable von einfachem, kurzem
Datentyp umsetzen kann.

Unter http://www.angelikalanger.com/Articles/Topics.html findest Du ein
paar Artikel von Frau Langer zum Thema Concurrent Programming,
insbesondere die aus dem JavaMagazig von Juli - Dezember 2008. Ich
erinnere mich, im letzten Jahr in irgendwelchen Print-Ausgaben auch was
über das java.util.concurrent-Package gelesen zu haben, weiß aber die
Ausgaben nicht mehr. Wenn Du das rausfindest und nachliest, erfährst Du
auch, an welchen Stellen ich mich geirrt habe ;-)

Tschö, wa!
Thorsten

Jochen Theodorou wrote:

> also das Thema ist ein relativ schweres und ich wollte hier mal nach ein
> paar praktischen Erfahrungen fragen. [...]
>
> Die Anwendung wird nun in vielen Threads gleichzeitig getDataStructure()
> aufrufen und hin und wieder wird die DatenStruktur gelöscht. Da
> getDataStructure() extrem oft aufgerufen wird würde ein synchonisieren
> hier dafür sorgen eine Menge Rechenleistung zu verlieren, und das auch
> schon bei nur einem einzigen Thread.

So aus der Praxis:

- synchronized() verbrät nicht viel Rechenleistung im Sinne von
CPU-Zyklen sondern Du verbrätst höchstens Zeit verbraten wenn andere
warten müssen. Und das ist nicht viel in Deiner Konstruktion - ausser
neue Daten werden bereitgestellt.

- Wenn das Singleton .getDataStructure() so oft aufgerufen wird, dass
dir schon die synchronisation Bauchschmerzen bereitet, dann ist die
Konstruktion wohl nicht die Richtige. In diesem Fall würde ich die Daten
ganz weit vorne hochziehen ehe die Threads loslaufen und die Daten im
Thread selber halten statt jedesmal vom Singelton neu zu beziehen.

- Für den Austausch der Daten (der ja wohl eher seltener Auftritt als
der Aufruf von .getDataStructure()) würde ich mir ein Flag in
MultithreadDataStrcutureHandler anlegen was Du in den Threads genau dann
abfragen kannst, wenn Du auch bereit bist mit den neuen Daten zu arbeiten.

Also:

MultithreadDataStrcutureHandler.init();
for (...) new MeinOllerThread()

MeinOllerThread
run() {
MultithreadDataStrcutureHandler
local=MultithreadDataStrcutureHandler.getData()
while(true) {
.wait()
if (shutdown) break;
if (MultithreadDataStrcutureHandler.hasNew())
local=MultithreadDataStrcutureHandler.getData()
... machwas ...
}
}

Wenn Du noch etwas Unübersichtilichkeit (aka Eleganz) reinbringen
willst: Registriere "MeinOllerThread" in MultithreadDataStrcutureHandler
und setze dort ein Notify ab wenn sich die Daten geändert haben.

Bernd

Patrick Roemer wrote:
> Responding to Jochen Theodorou:
>
>>> DataStructure sp = synchronizedPointer.get();
>>> synchronized(this) {
>>> if (sp==null) sp = init();
>>> synchronizedPointer = new WeakReference<DataStructure>(sp);
>>> }
>>> unsynchronizedPointer = synchronizedPointer;
>>> return sp;
>
> So kannst Du doch wiederum keine Garantie dafuer ableiten, dass der
> Zugriff auf synchronizedPointer in der ersten Zeile ein vollstaendig
> initialisiertes Objekt sieht, oder?

hmm.. stimmt... die Zuweisung muss nach dem Block erfolgen... hmm...
eventuell brauche ich synchronizedPointer dann gar nicht:

>>> DataStructure sp = synchronizedPointer.get();
>>> WeakReference<DataStructure> ref = null
>>> synchronized(this) {
>>> if (sp==null) sp = init();
>>> ref = new WeakReference<DataStructure>(sp);
>>> }
>>> synchronizedPointer = ref
>>> unsynchronizedPointer = synchronizedPointer;
>>> return sp;

wäre es dann...

Gruss theo

Wanja Gayk wrote:
> Am 12.03.2010, 00:53 Uhr, schrieb Jochen Theodorou <blackdrag>:
>
>> Die Anwendung wird nun in vielen Threads gleichzeitig
>> getDataStructure() aufrufen und hin und wieder wird die DatenStruktur
>> gelöscht. Da getDataStructure() extrem oft aufgerufen wird würde ein
>> synchonisieren hier dafür sorgen eine Menge Rechenleistung zu
>> verlieren, und das auch schon bei nur einem einzigen Thread.
>
> Ist das eine Vermutung oder hast du das gemessen?

gemessen... ein Vorschlag... mach mal ein fibonacci, welches auf einem
volatile-Feld rechnet. Es ist noch nicht einmal, dass volatile oder
synchronized alleine. Es ist das Problem, dass dann Hotspot hier jede
Menge Optimierungen einfach nicht mehr durchführen kann.

[...]
[..]
> monitor is released. It is perfectly reasonable and legal for the
> compiler to move the assignment helper = h; inside the synchronized
> block, in which case we are back where we were previously. Many
> processors offer instructions that perform this kind of one-way memory
> barrier. Changing the semantics to require releasing a lock to be a full
> memory barrier would have performance penalties."
>
> In deinem Fall ist es also legal, dass der Compiler
> "unsynchronizedPointer = synchronizedPointer;" in den synchronized-Block
> zieht.

ich dachte mir doch da stimmt etwas noch nicht... so ein mist.

> Ich frage mich beim Blick auf den synchonized Block auch, warum du nicht
> auf ein Lock-Objekt für dieses Feld synchronisierst. Gesetzt der Fall du
> hast mehrere Felder auf die synchroniert zugegriffen werdeb muss,
> würdest du mit synchronized(this) auf das ganze objekt locken, nicht nur
> auf das Feld.

Das habe ich gemacht um das Beispiel kleiner zu halten.

> Also eher so:
>
> private final syncPointerLock = new Object();
> private DataStructure synchronizedPointer = ...
>
> DataStructure getDataStructure(){
> synchronized(syncPointerLock){
> DataStructure sp = synchronizedPointer.get();
> if(sp == null) sp = init();
> synchronizedPointer = new WeakReference<DataStructure>(sp);
> return sp;
> }
> }
>
> Wenn du auf die WeakReference verzichtest und das Löschen wieder
> explizit machst, kannst du dir vielleicht auch was mit einer
> AtomicMarkableReference bauen, statt mit synchronization, aber ich würde
> es mich an Josh Bloch halten:[...]

Was ich haben will ist allerdings keine traditionelle Faktory, auch
keine die das Lazy macht. Es ist für absolut in Ordnung wenn zwei
Threads die Initialisierung parallel ausführen... sofern mir das am Ende
mehr Performance bringt. Normalerweise würde ich das komplett ohne
synchronization machen und dafür nur Objekte verwenden, die
ausschließlich final Felder haben. Allerdings muss ich sher viele
interne Datenstrukturen ändern und auf einige von denen habe ich
keinerlei Einfluss. Das heisst ich brauche unbedingt eine Lösung mit
Synchronisierung, nur soll die mir nicht ständig in die Quere kommen.

Gruss theo

Thorsten Nitz wrote:
> Am 12.03.2010 00:53, schrieb Jochen Theodorou:
[...]
>
> Zuweisung an Referenzen sind AFAIR atomar, daher kannst Du die
> Synchronisation weglassen, wenn Du die Referenz volatile machst. Das ist
> notwendig, weil es nicht reicht, der Variablen etwas zuzuweisen, der
> neue Inhalt muss auch an die anderen Threads übertragen werden. Diese
> dürfen nämlich Kopien von Objekten cachen.

stimmt, für ein =null ist das nicht notwendig. Gut das Beispiel ist
nicht so ganz ideal, denn die Löschung muss nicht, oder überhaupt in
anderen Threads sichtbar werden. Die Idee dahinter ist, dass man
Huckepack mit einer anderen Synchronisaton die Änderung zu einem
passenden Zeitpunkt propagieren wird. Daher ist es absolut ok, wenn die
Referenz nicht volatile ist... selbst wenn das später dazu führen wird,
dass mehrere initialisierungen durchgeführt wernden werden.

[...]
> Das andere grundsäzliche Problem mit diesem Design ist, dass Benutzer
> von MultithreadDataStrcutureHandler nicht notwendig die neuesten Daten
> verarbeiten:

Wie gesagt... das ist in meinem Fall ok. Oder besser gesagt, das ist ein
Nachteil, den ich bereit bin einzugehenund das Design der Applikation
entsprechend anzupassen, dass dies erlaubt ist. Dass es dann irgendwo
dann doch einmal Synchronisierungspunkte geben ist klar. Allerdings will
ich so zu sagen "externe Synchronisierung" machen.

Gruss theo

Bernd Hohmann wrote:
> Jochen Theodorou wrote:
[...]
> - synchronized() verbrät nicht viel Rechenleistung im Sinne von
> CPU-Zyklen sondern Du verbrätst höchstens Zeit verbraten wenn andere
> warten müssen. Und das ist nicht viel in Deiner Konstruktion - ausser
> neue Daten werden bereitgestellt.

Ok, ich schätze ich muss das einmal anders erklären. Es geht hier
eigentlich um die Groovy-Runtime. Für jeden Methodenaufruf aus Groovy
heraus werden in etwa 7 Stellen durchlaufen, an denen Synchronisierung
statt findet. Auf einem Mehrprozessorsystem bedeutet das 7
Speichersynchronisierungen pro Methodenaufruf. Und das ist einfach nicht
akzeptabel. Aber auch schon im Falle eines einzigen Threads verhindert
jedes volatile und jedes synchronized das Hotspot den Code optimiert.
Und auch das möchte ich so nicht akzeptieren.

> - Wenn das Singleton .getDataStructure() so oft aufgerufen wird, dass
> dir schon die synchronisation Bauchschmerzen bereitet, dann ist die
> Konstruktion wohl nicht die Richtige. In diesem Fall würde ich die Daten
> ganz weit vorne hochziehen ehe die Threads loslaufen und die Daten im
> Thread selber halten statt jedesmal vom Singelton neu zu beziehen.

Eigentlich ist das mehr eine Art Cache, denn ein Singleton. Es dürfen
also durchaus mehrere Instanzen existieren. Die Daten alle am Anfang zu
bestimmen geht dann natürlich nicht.

Gruss theo

Jochen Theodorou said...

> Was ich haben will ist allerdings keine traditionelle Faktory, auch
> keine die das Lazy macht. Es ist für absolut in Ordnung wenn zwei
> Threads die Initialisierung parallel ausführen... sofern mir das am Ende
> mehr Performance bringt.

Hmmm.. da die meisten Zugriffe wohl lesend sein werden, hast du es mal
mit einem ReentrantReadWriteLock versucht?

T value;
ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();

T get(){
try{
rwl.readLock().lock();
if(value == null){
try{
//lock-upgrade
rwl.readLock().unlock(); //readlock aufgeben
rwl.writeLock().lock(); //writelock holen
if(value == null){ //nochmal checken, diesmal unter writelock
value = init();
}
}finally{
// lock von write auf readlock downgraden
rwl.readLock().lock();
rwl.writeLock().unlock();
}
}
return value;
}finally{ //readLock aufgeben
rwl.readLock().unlock();
}
}

T müsste man jetzt durch ne WeakReference ersetzen.
Ich befürchte aber fast, dass du auch dort nicht um eine volatile
Referenz herum kommst.

Gruß,
-Wanja-

Jochen Theodorou said...

> Eigentlich ist das mehr eine Art Cache, denn ein Singleton. Es dürfen
> also durchaus mehrere Instanzen existieren. Die Daten alle am Anfang zu
> bestimmen geht dann natürlich nicht.

Irgendwie geistert die ganze Zeit "ThreadLocal" in meinem Kopf herum..

Gruß,
-Wanja-

Jochen Theodorou wrote:
> Ok, ich schätze ich muss das einmal anders erklären. Es geht hier
> eigentlich um die Groovy-Runtime. Für jeden Methodenaufruf aus Groovy
> heraus werden in etwa 7 Stellen durchlaufen, an denen Synchronisierung
> statt findet. Auf einem Mehrprozessorsystem bedeutet das 7
> Speichersynchronisierungen pro Methodenaufruf. Und das ist einfach nicht
> akzeptabel. Aber auch schon im Falle eines einzigen Threads verhindert
> jedes volatile und jedes synchronized das Hotspot den Code optimiert.
> Und auch das möchte ich so nicht akzeptieren.
>
> Eigentlich ist das mehr eine Art Cache, denn ein Singleton. Es dürfen
> also durchaus mehrere Instanzen existieren. Die Daten alle am Anfang zu
> bestimmen geht dann natürlich nicht.

Ich würde bei allen Referenzen, bei denen es möglich ist,
den Modifier

final

benutzen.

Entsprechend dem Java Memory Model wird eine final-Referenz
nur einmal in den lokalen Memory eines Threads gelesen.
Der lokale Memory eines Threads wird technisch wahrscheinlich
auf den Cache eines CPU-Kerns abgebildet.

Dagegen müssen volatile-Referenzen bei jedem Zugriff zwischen
Heap und Thread Memory abgeglichen werden, was weitgehend
einem synchronisierten Zugriff entspricht.

Natürlich können nicht alle Referenzen final sein, dann wäre
Deine Datenstruktur unveränderlich.

Also als Regel entweder final oder volatile benutzen.

Aber wenn nur eine (oder wenige) Stelle(n) in Deinem
Objekt-Graphen volatile sind, dann hast Du einen guten
Kompromiss zwischen Performance und Sicherheit.

Dazu sollte aber Dein Code eine Art Executions-Klammer
einhalten (das Wort Transaktions-Klammer passt hier nicht,
es geht nicht um Transaktionen).

Am Beginn dieser Klammer wird die Wurzel des
Objekt-Graphen besorgt (volatile) und innerhalb der
Executions-Klammer mit den Kind-Elementen des
Objekt-Graphen gearbeitet (final).

Damit realisiert die Datenstruktur so etwas ähnliches
wie die CopyOnWriteArrayList aus dem JDK-API.

Innerhalb der Executions-Klammer wird immer
nur ein einziges Exemplar des Objekt-Graphen
verwendet.

Eine neue Executions-Klammer kann einen
neuen Objekt-Graphen bekommen.

Wichtig ist dabei, dass keine Unter-Struktur des
Objekt-Graphen ausserhalb der Executions-Klammer
dauerhaft referenziert wird.

Diese Idee ist übrigens nicht neu.
Ich habe vor etlichen Jahren mal mit einem Kollegen
über CMS diskutiert und er hatte vorgeschlagen,
die zu statifizierenden Änderungen in eine(mehrere)
temporäre Datei(en) zu schreiben und den ganzen
Kram durch Umbenennen mit einem Schlag
wirksam zu machen.

> Gruss theo

Gruss
Heiner
www.heinerkuecker.de