Discussion:
Dreiwertige Pseudo-L-Werte
(zu alt für eine Antwort)
Rainer Weikusat
2017-10-10 22:05:52 UTC
Permalink
Raw Message
Codezeile, die ich gerade geschrieben habe:

-------
*(n_pkg ? &n_pkg->p_me : &chain) = pkg->p_me;
-------

Das ist Teil einer Codesequenz, die ein Element aus einer doppelt
verketteten Liste loescht. Anstatt eines Vorgaenger- und eines
Nachfolgerzeigers hat jedes Element einen Nachfolgerzeiger und einen
Zeiger auf den Zeiger, der auf das Element selber zeigt. n_pkg ist der
Wert des Nachfolgerzeigers des zu entfernenden Objektes, chain ist der
top-level Zeiger, der auf den Zeiger zeigt, der beim Anfuegen eines
neuen Elementes modifiziert werden muss.

Hat jemand eine Ansicht zu obigem Trick oder zu der Konstruktion als
solcher und waere bereit, sie mitzuteilen?
Helmut Schellong
2017-10-12 14:36:05 UTC
Permalink
Raw Message
Post by Rainer Weikusat
-------
*(n_pkg ? &n_pkg->p_me : &chain) = pkg->p_me;
-------
Das ist Teil einer Codesequenz, die ein Element aus einer doppelt
verketteten Liste loescht. Anstatt eines Vorgaenger- und eines
Nachfolgerzeigers hat jedes Element einen Nachfolgerzeiger und einen
Zeiger auf den Zeiger, der auf das Element selber zeigt. n_pkg ist der
Wert des Nachfolgerzeigers des zu entfernenden Objektes, chain ist der
top-level Zeiger, der auf den Zeiger zeigt, der beim Anfuegen eines
neuen Elementes modifiziert werden muss.
Hat jemand eine Ansicht zu obigem Trick oder zu der Konstruktion als
solcher und waere bereit, sie mitzuteilen?
Früher habe ich (solche und) ähnliche Dinge öfter formuliert.
Dann haben Compiler immer öfter gemeckert: Kein L-Value!

Ich finde das da oben logisch und 'schön'.
Der Compiler wird das als if-else ansehen.
Man kann pkg->p_me als in (?:) 'hineinmultipliziert' ansehen.
--
Mit freundlichen Grüßen
Helmut Schellong ***@schellong.biz
www.schellong.de www.schellong.com www.schellong.biz
http://www.schellong.de/c.htm
Claus Reibenstein
2017-10-12 16:06:19 UTC
Permalink
Raw Message
Post by Helmut Schellong
Post by Rainer Weikusat
*(n_pkg ? &n_pkg->p_me : &chain) = pkg->p_me;
Ich finde das da oben logisch und 'schön'.
Logisch ja, aber schön? Solche "Obfuscated C"-Codezeilen erschweren das
Lesen und Interpretieren des Programmcodes.

Schön ist anders.

Gruß
Claus
Helmut Schellong
2017-10-12 17:06:11 UTC
Permalink
Raw Message
Post by Claus Reibenstein
Post by Helmut Schellong
Post by Rainer Weikusat
*(n_pkg ? &n_pkg->p_me : &chain) = pkg->p_me;
Ich finde das da oben logisch und 'schön'.
Logisch ja, aber schön? Solche "Obfuscated C"-Codezeilen erschweren das
Lesen und Interpretieren des Programmcodes.
Für mich ist das von Obfuscated noch sehr weit entfernt.
--
Mit freundlichen Grüßen
Helmut Schellong ***@schellong.biz
www.schellong.de www.schellong.com www.schellong.biz
http://www.schellong.de/c.htm
Thomas Koenig
2017-10-12 18:11:06 UTC
Permalink
Raw Message
Post by Rainer Weikusat
*(n_pkg ? &n_pkg->p_me : &chain) = pkg->p_me;
Hat jemand eine Ansicht zu obigem Trick oder zu der Konstruktion als
solcher und waere bereit, sie mitzuteilen?
Kannst du die notwendigen Typen- und Variablendeklarationen dazliefern,
damit man das mal kompilieren kann? Der Typ von n_pkg erschließt sich
mir nicht direkt.
Rainer Weikusat
2017-10-12 18:18:28 UTC
Permalink
Raw Message
Post by Thomas Koenig
Post by Rainer Weikusat
*(n_pkg ? &n_pkg->p_me : &chain) = pkg->p_me;
Hat jemand eine Ansicht zu obigem Trick oder zu der Konstruktion als
solcher und waere bereit, sie mitzuteilen?
Kannst du die notwendigen Typen- und Variablendeklarationen dazliefern,
damit man das mal kompilieren kann? Der Typ von n_pkg erschließt sich
mir nicht direkt.
-------
#include <stdlib.h>

struct node {
struct node *n, **me;
int x;
};

static struct node *head, **chain = &head;

void append_node(int x)
{
struct node *np;

np = malloc(sizeof(*np));

np->x = x;

np->n = NULL;
*chain = np;
np->me = chain;
chain = &np->n;
}

void remove_node(struct node *np)
{
struct node *n;

n = np->n;
*np->me = n;
*(n ? &n->me : &chain) = np->me;

free(np);
}
-------

Das habe ich jetzt allerdings nur aus dem Gedaechtnis runtergeschrieben
und uebersetzt, nicht getestet.
Thomas Koenig
2017-10-12 20:24:04 UTC
Permalink
Raw Message
Rainer Weikusat <***@talktalk.net> schrieb:

Danke für den Sourcecode.
Post by Rainer Weikusat
void remove_node(struct node *np)
{
struct node *n;
n = np->n;
*np->me = n;
*(n ? &n->me : &chain) = np->me;
free(np);
}
Ich habe das mal diese Funktion und dazu die funktional
äquivalente Variante

void remove_node_2(struct node *np)
{
struct node *n;

n = np->n;
*np->me = n;
if (n)
n->me = np->me;
else
chain = np->me;

free(np);
}

durch gcc und icc jeweils mit -O3 gejagt.

Ergebnis für gcc:

remove_node:
.LFB13:
.cfi_startproc
movq (%rdi), %rdx
movq 8(%rdi), %rcx
leaq 8(%rdx), %rax
movq %rdx, (%rcx)
testq %rdx, %rdx
movl $chain, %edx
cmove %rdx, %rax
movq %rcx, (%rax)
jmp free

remove_node_2:
.LFB14:
.cfi_startproc
movq (%rdi), %rax
movq 8(%rdi), %rdx
testq %rax, %rax
movq %rax, (%rdx)
je .L6
movq %rdx, 8(%rax)
jmp free
.p2align 4,,10
.p2align 3
.L6:
movq %rdx, chain(%rip)
jmp free


Ergebnis für icc:

remove_node:
# parameter 1: %rdi
..B1.1: # Preds ..B1.0
# Execution count [1.00e+00]
.cfi_startproc
..___tag_value_remove_node.1:
..L2:
#11.1
movl $chain, %r8d #16.21
movq (%rdi), %rdx #14.9
testq %rdx, %rdx #16.7
movq 8(%rdi), %rax #15.6
lea 8(%rdx), %rcx #16.12
cmovne %rcx, %r8 #16.7
movq %rdx, (%rax) #15.6
movq 8(%rdi), %rsi #16.30
movq %rsi, (%r8) #16.7
# free(void *)
jmp free #18.5

remove_node_2:
# parameter 1: %rdi
..B2.1: # Preds ..B2.0
# Execution count [1.00e+00]
.cfi_startproc
..___tag_value_remove_node_2.4:
..L5:
#22.1
movq 8(%rdi), %rax #26.6
movq (%rdi), %rdx #25.9
movq %rdx, (%rax) #26.6
testq %rdx, %rdx #27.9
je ..B2.3 # Prob 12% #27.9
# LOE rdx rbx rbp rdi r12 r13 r14 r15
..B2.2: # Preds ..B2.1
# Execution count [8.80e-01]
movq 8(%rdi), %rax #28.15
movq %rax, 8(%rdx) #28.7
jmp ..B2.4 # Prob 100% #28.7
# LOE rbx rbp rdi r12 r13 r14 r15
..B2.3: # Preds ..B2.1
# Execution count [1.20e-01]
movq 8(%rdi), %rax #30.15
movq %rax, chain(%rip) #30.7
# LOE rbx rbp rdi r12 r13 r14 r15
..B2.4: # Preds ..B2.2 ..B2.3
# Execution count [1.00e+00]
# free(void *)
jmp free #32.5


Beide Compiler erzeugen für die zweite, einfacher lesbarere Variante
schnelleren Code. Vor allem wird die Adresse von chain nicht
angefasst, wenn es nicht (wegen n == NULL) nötig ist.

Daher würde ich deine Variante nicht empfehlen, abgesehen von
der schlechteren Lesbarkeit erzeugt sie auch schlechteren Code.
Rainer Weikusat
2017-10-12 21:00:38 UTC
Permalink
Raw Message
Post by Thomas Koenig
Danke für den Sourcecode.
Post by Rainer Weikusat
void remove_node(struct node *np)
{
struct node *n;
n = np->n;
*np->me = n;
*(n ? &n->me : &chain) = np->me;
free(np);
}
Ich habe das mal diese Funktion und dazu die funktional
äquivalente Variante
void remove_node_2(struct node *np)
{
struct node *n;
n = np->n;
*np->me = n;
if (n)
n->me = np->me;
else
chain = np->me;
free(np);
}
durch gcc und icc jeweils mit -O3 gejagt.
.cfi_startproc
movq (%rdi), %rdx
movq 8(%rdi), %rcx
leaq 8(%rdx), %rax
movq %rdx, (%rcx)
testq %rdx, %rdx
movl $chain, %edx
cmove %rdx, %rax
movq %rcx, (%rax)
jmp free
.cfi_startproc
movq (%rdi), %rax
movq 8(%rdi), %rdx
testq %rax, %rax
movq %rax, (%rdx)
je .L6
movq %rdx, 8(%rax)
jmp free
.p2align 4,,10
.p2align 3
movq %rdx, chain(%rip)
jmp free
[...]
Post by Thomas Koenig
Beide Compiler erzeugen für die zweite, einfacher lesbarere Variante
schnelleren Code. Vor allem wird die Adresse von chain nicht
angefasst, wenn es nicht (wegen n == NULL) nötig ist.
Bezueglich der 'einfacheren Lesbarkeit' wuerde ich hier das genaue
Gegenteil behaupten: Vier Zeilen Code sind nicht 'besser lesbar' nur
weil es sich um 4x soviel Code handelt, wie eine Zeile.

Ob das ein paar Milliardstelsekunden schneller oder langsamer ablaeuft,
spielt keine Rolle. Im uebrigen duerfte das davon abhaengen, wie haeufig
die Sprungvorhersage die bedingte Verzweigung korrekt vorhersagt.
Thomas Koenig
2017-10-12 21:16:41 UTC
Permalink
Raw Message
Post by Rainer Weikusat
Post by Thomas Koenig
Beide Compiler erzeugen für die zweite, einfacher lesbarere Variante
schnelleren Code. Vor allem wird die Adresse von chain nicht
angefasst, wenn es nicht (wegen n == NULL) nötig ist.
Bezueglich der 'einfacheren Lesbarkeit' wuerde ich hier das genaue
Gegenteil behaupten: Vier Zeilen Code sind nicht 'besser lesbar' nur
weil es sich um 4x soviel Code handelt, wie eine Zeile.
Der Code, den du geschrieben hast, ist ja durchaus komplex - es kommen
mehr Operationen drin vor, die Adressoperatoren und die Dereferenzierung.
Da muss man schon zweimmal hinschauen, bis man das verstanden hat.
Post by Rainer Weikusat
Ob das ein paar Milliardstelsekunden schneller oder langsamer ablaeuft,
spielt keine Rolle.
Wenn dir Performance egal ist, natürlich. Ich würde mir nur keinen Stil
angewöhnen, der mit Mikro-Pessimierungen Compiler erst mal ausbremst.
Post by Rainer Weikusat
Im uebrigen duerfte das davon abhaengen, wie haeufig
die Sprungvorhersage die bedingte Verzweigung korrekt vorhersagt.
Die Hot/cold - Partitionierung, die gcc da vorhergesehen hat,
düfrte da schon ein ziemlich guter Hinweis sein.
Rainer Weikusat
2017-10-12 21:43:44 UTC
Permalink
Raw Message
Post by Thomas Koenig
Post by Rainer Weikusat
Post by Thomas Koenig
Beide Compiler erzeugen für die zweite, einfacher lesbarere Variante
schnelleren Code. Vor allem wird die Adresse von chain nicht
angefasst, wenn es nicht (wegen n == NULL) nötig ist.
Bezueglich der 'einfacheren Lesbarkeit' wuerde ich hier das genaue
Gegenteil behaupten: Vier Zeilen Code sind nicht 'besser lesbar' nur
weil es sich um 4x soviel Code handelt, wie eine Zeile.
Der Code, den du geschrieben hast, ist ja durchaus komplex - es kommen
mehr Operationen drin vor, die Adressoperatoren und die Dereferenzierung.
Da muss man schon zweimmal hinschauen, bis man das verstanden hat.
Post by Rainer Weikusat
Ob das ein paar Milliardstelsekunden schneller oder langsamer ablaeuft,
spielt keine Rolle.
Wenn dir Performance egal ist, natürlich. Ich würde mir nur keinen Stil
angewöhnen, der mit Mikro-Pessimierungen Compiler erst mal ausbremst.
Warum in n Teufels Namen wird von jedem Sourcecode-Phaenomen angenommen,
dass es irgendwie die Machine kitzeln sollte? Es sollte dezidiert
nicht. Ich moechte einen Ausdruck haben, dessen Resultat etwas
zugewiesen werden kann, nicht irgendeine Annaeherung daran, die sich
durch schwach kaschiertes, explizites Herumgehuepfe erzielen laesst. Dh
ich moechte die linke Seite einer Zuweisung genauso berechnen koennen,
wie die rechte.

Das ist zugebenermassen ein Perl-Feature, das C nicht so ohne weiteres
unterstuetzen kann, aber der Umweg ueber * + & scheint mir ertraeglich
kompliziert (insofern er bekannt ist).
Post by Thomas Koenig
Post by Rainer Weikusat
Im uebrigen duerfte das davon abhaengen, wie haeufig
die Sprungvorhersage die bedingte Verzweigung korrekt vorhersagt.
Die Hot/cold - Partitionierung, die gcc da vorhergesehen hat,
düfrte da schon ein ziemlich guter Hinweis sein.
Der Sprung wird normalerweise ausgefuehrt werden.

Spielt aber wirklich keine Rolle, denn die Aktion wird als Reaktion auf
eine Kernel-Nachricht ausgefuehrt, die als Antwort auf eine Nachricht an
den Kernel gesendet wird. Dh zwischen queue und dequeue liegen ein sent,
ein recv und eine Runde durch die generelle Ereignisverarbeitungschleife
(die natuerlich ebenfalls einen Systemaufruf macht). Verglichen mit der
Zeit, die fuer das alles gebraucht wird, ist der zusaetlizch Aufwand von
zwei oder drei Instruktionen in der pipeline Null.
Thomas Koenig
2017-10-13 06:14:05 UTC
Permalink
Raw Message
Post by Rainer Weikusat
Post by Thomas Koenig
Wenn dir Performance egal ist, natürlich. Ich würde mir nur keinen Stil
angewöhnen, der mit Mikro-Pessimierungen Compiler erst mal ausbremst.
Warum in n Teufels Namen wird von jedem Sourcecode-Phaenomen angenommen,
dass es irgendwie die Machine kitzeln sollte? Es sollte dezidiert
nicht.
Du hattest gefragt, was wir von dem Ausdruck halten. Dann musst du auch
mit den Anworten leben, die kommen :-)

Eine Bemerkung "Ich weiss, dass das Performance kostet, aber das
ist mir in diesem Fall egal" in deinem Original-Post hätte die
Diskussion dazu gar nicht erst entsehen lassen. Wusstest du vorher,
dass das so ist?
Post by Rainer Weikusat
Ich moechte einen Ausdruck haben, dessen Resultat etwas
zugewiesen werden kann, nicht irgendeine Annaeherung daran, die sich
durch schwach kaschiertes, explizites Herumgehuepfe erzielen laesst.
Das "Herumgehüpfe" ist im ? : - Operator auch drin, nur syntaktisch
kaschiert.

Und was die Geschwindigkeit angeht - das Problem sehe ich eher
darin, dass da für den Fall, dass du nicht gerade vom Anfang der
Liste löschst, eine unnötige Variable aus dem Speicher holst.
Das kostet dich, wenn es dumm läuft, eine Cache Line, und das
sind dann mal so eben 250 Zyklen.
Post by Rainer Weikusat
Post by Thomas Koenig
Post by Rainer Weikusat
Im uebrigen duerfte das davon abhaengen, wie haeufig
die Sprungvorhersage die bedingte Verzweigung korrekt vorhersagt.
Die Hot/cold - Partitionierung, die gcc da vorhergesehen hat,
düfrte da schon ein ziemlich guter Hinweis sein.
Der Sprung wird normalerweise ausgefuehrt werden.
Du meinst, deine Liste ist normalerweise leer?

Und das es in deinem speziellen Fall Performance keine Rolle
spielt (worauf du ja nicht von Anfang an hingewiesen hattest):
Als genereller Stil ist das nicht gut. Es war mir von vorneherein
klar, dass ich dich nicht überzeugen würde, aber wenigstens
sollen die anderen Leser des Threads die prinzipiellen Nachteile
deiner Konstruktion kennen.
Rainer Weikusat
2017-10-13 17:38:52 UTC
Permalink
Raw Message
Post by Thomas Koenig
Post by Rainer Weikusat
Post by Thomas Koenig
Wenn dir Performance egal ist, natürlich. Ich würde mir nur keinen Stil
angewöhnen, der mit Mikro-Pessimierungen Compiler erst mal ausbremst.
Warum in n Teufels Namen wird von jedem Sourcecode-Phaenomen angenommen,
dass es irgendwie die Machine kitzeln sollte? Es sollte dezidiert
nicht.
Du hattest gefragt, was wir von dem Ausdruck halten. Dann musst du auch
mit den Anworten leben, die kommen :-)
Meiner Ansicht nach gewinnt man Erkenntnisse/ Einsichten dadurch, dass
man sich mit anderer Leute Ansichten zu einem Thema
auseinandersetzt. Was nicht heisst, dass man mit ihnen uebereinstimmen
sollte oder muesste.

Allerdings mag ich die "Mikro-Pessimierungen", was ich als "misslungener
Versuch, durch seltsame C-Konstruktionen Takte zu schinden" nicht auf
mir sitzen zu lassen. Darum geht es mir naemlich grundsaetzlich
nicht. Ich moechte eine in C sinnvolle Formulierung eines Algorithmus
haben und um Uebersetzung in sinnvollen Machinencode soll sich bitte der
Compiler kuemmern.
Post by Thomas Koenig
Eine Bemerkung "Ich weiss, dass das Performance kostet, aber das
ist mir in diesem Fall egal" in deinem Original-Post hätte die
Diskussion dazu gar nicht erst entsehen lassen. Wusstest du vorher,
dass das so ist?
Ich wusste vorher, zu was das uebersetzt wird, weil ich sichergehen
wollte, dass die Addressoperationen nicht zum auslagener lokaler
Variablen auf den Stack fuehren wuerden. Allerdings unnoetigerweise,
denn der Code braucht keine Addresses einer lokalen Variablen sondern
die Adresses eines Strukturelements auf dessen Struktur eine lokale
Variable zeigt.

Mit dem "kostet Performance" bin ich mir uebrigens nicht so sicher. Wenn
man den Code zwecks Vereinfachung auf den fraglichen Ausdruck reduziert,

------
void remove_node(struct node *np)
{
struct node *n;

n = np->n;
*(n ? &n->me : &chain) = np->me;
}

void remove_node_if(struct node *np)
{
struct node *n;

n = np->n;
if (n) n->me = np->me;
else chain = np->me;
}
------

bekommt man unoptimiert

remove_node:
.LFB0:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
movq %rdi, -24(%rbp)
movq -24(%rbp), %rax
movq (%rax), %rax
movq %rax, -8(%rbp)
cmpq $0, -8(%rbp)
je .L2
movq -8(%rbp), %rax
addq $8, %rax
jmp .L3
.L2:
movl $chain, %eax
.L3:
movq -24(%rbp), %rdx
movq 8(%rdx), %rdx
movq %rdx, (%rax)
popq %rbp
.cfi_def_cfa 7, 8
ret
.cfi_endproc

und

remove_node_if:
.LFB1:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
movq %rdi, -24(%rbp)
movq -24(%rbp), %rax
movq (%rax), %rax
movq %rax, -8(%rbp)
cmpq $0, -8(%rbp)
je .L5
movq -24(%rbp), %rax
movq 8(%rax), %rdx
movq -8(%rbp), %rax
movq %rdx, 8(%rax)
jmp .L4
.L5:
movq -24(%rbp), %rax
movq 8(%rax), %rax
movq %rax, chain(%rip)
.L4:
popq %rbp
.cfi_def_cfa 7, 8
ret
.cfi_endproc

Die erste Variante ist etwas kuerzer, weil der Code zum Speichern des
Wertes nur einmal vorhanden ist. Optimiert wird das zu

remove_node:
.LFB7:
.cfi_startproc
movq (%rdi), %rdx
movl $chain, %eax
leaq 8(%rdx), %rcx
testq %rdx, %rdx
movq 8(%rdi), %rdx
cmovne %rcx, %rax
movq %rdx, (%rax)
ret
.cfi_endproc

und

remove_node_if:
.LFB8:
.cfi_startproc
movq (%rdi), %rax
testq %rax, %rax
je .L5
movq 8(%rdi), %rdx
movq %rdx, 8(%rax)
ret
.p2align 4,,10
.p2align 3
.L5:
movq 8(%rdi), %rax
movq %rax, chain(%rip)
ret
.cfi_endproc

Ich bin mir recht sicher, dass die Compiler-Autoren die Elimination des
Sprungs fuer eine Optimierung halten, denn sonst waere er wohl
dringeblieben.
Post by Thomas Koenig
Post by Rainer Weikusat
Ich moechte einen Ausdruck haben, dessen Resultat etwas
zugewiesen werden kann, nicht irgendeine Annaeherung daran, die sich
durch schwach kaschiertes, explizites Herumgehuepfe erzielen laesst.
Das "Herumgehüpfe" ist im ? : - Operator auch drin, nur syntaktisch
kaschiert.
Oder auch nicht, siehe oben.
Post by Thomas Koenig
Und was die Geschwindigkeit angeht - das Problem sehe ich eher
darin, dass da für den Fall, dass du nicht gerade vom Anfang der
Liste löschst, eine unnötige Variable aus dem Speicher holst.
Das kostet dich, wenn es dumm läuft, eine Cache Line, und das
sind dann mal so eben 250 Zyklen.
movl $chain, %eax

laedt die Address von chain in eax. Und das ist eine Konstante deren
Wert zum Linkzeitpunkt feststeht (komme mir hier bitte keiner damit, das
keineswegs feststeht, ob das eine Konstante sein wird, oder ein
zufaelliger Wert, der vor jeder Programmausfuehrung vom 'OpenBSD
Sicherheitsteam' per Post bestellt und per Nachname bezahlt werden muss
...).
Stefan Reuther
2017-10-14 12:10:30 UTC
Permalink
Raw Message
Post by Rainer Weikusat
Allerdings mag ich die "Mikro-Pessimierungen", was ich als "misslungener
Versuch, durch seltsame C-Konstruktionen Takte zu schinden" nicht auf
mir sitzen zu lassen. Darum geht es mir naemlich grundsaetzlich
nicht. Ich moechte eine in C sinnvolle Formulierung eines Algorithmus
haben und um Uebersetzung in sinnvollen Machinencode soll sich bitte der
Compiler kuemmern.
Das wichtigste Optimierungsziel sollte eigentlich Lesbarkeit sein, nicht
Anzahl Maschinenbefehle. Schon die Korrelation zwischen Anzahl
Maschinenbefehle und Ausführungszeit ist heute deutlich schwächer als
vor 20 Jahren, aber spätestens bei der Lesbarkeit wird's vollends
unvorhersehbar^Wsubjektiv.

Da würde ich der Formulierung, so wie sie dasteht, schon ein paar Punkte
Abzug geben. Sicherlich auch aufgrund von Unvertrautheit mit der Codebasis.

Wenn der ternäre Ausdruck aus einem Makro kommt und somit einen Namen hat
#define ANCHOR_NODE(p, c) *(p ? &p->p_me : &c)
ANCHOR_NODE(n_pkg, chain) = pkg->p_me;
oder wenn das ganze C++ wäre, wo man WIMRE das *& weglassen kann
(n_pkg ? n_pkg->p_me : chain) = pkg->p_me;
wird's zumindest subjektiv ein wenig lesbarer.


Stefan
Rainer Weikusat
2017-10-23 15:14:30 UTC
Permalink
Raw Message
Post by Stefan Reuther
Post by Rainer Weikusat
Allerdings mag ich die "Mikro-Pessimierungen", was ich als "misslungener
Versuch, durch seltsame C-Konstruktionen Takte zu schinden" nicht auf
mir sitzen zu lassen. Darum geht es mir naemlich grundsaetzlich
nicht. Ich moechte eine in C sinnvolle Formulierung eines Algorithmus
haben und um Uebersetzung in sinnvollen Machinencode soll sich bitte der
Compiler kuemmern.
Das wichtigste Optimierungsziel sollte eigentlich Lesbarkeit sein, nicht
Anzahl Maschinenbefehle. Schon die Korrelation zwischen Anzahl
Maschinenbefehle und Ausführungszeit ist heute deutlich schwächer als
vor 20 Jahren, aber spätestens bei der Lesbarkeit wird's vollends
unvorhersehbar^Wsubjektiv.
Da würde ich der Formulierung, so wie sie dasteht, schon ein paar Punkte
Abzug geben. Sicherlich auch aufgrund von Unvertrautheit mit der Codebasis.
Wenn der ternäre Ausdruck aus einem Makro kommt und somit einen Namen hat
#define ANCHOR_NODE(p, c) *(p ? &p->p_me : &c)
ANCHOR_NODE(n_pkg, chain) = pkg->p_me;
Wenn schon, dann etwas in der Art von

-----
#include <stdio.h>

#define DST_IF(cond, d0, d1) *((cond) ? &(d0) : &(d1))

static int a = 3, b = 4;

int main(int argc, char **argv)
{
DST_IF(argv[1], a, b) += 5;
printf("a %d, b %d\n", a, b);
return 0;
}
------

Da sind wenigstens nicht auch noch die Parameternamen unsichtbar drin
versteckt. Allerdings ist man meiner Ansicht nach gut beraten wenn man
von Makros groesstenteils die Finger laesst: Ich empfinde solche
zusaetzlichen Syntaxkonstrukte als extrem leseflussstoerend.

Ein Unterprogram ist ein strukturiertes Konstrukt. Es hat einen
Eintrittspunkt und einen Austrittspunkt und seine Bedeutung ist
unabhaengig vom syntaktischen Kontext des Aufrufs. Ein Makro nimmt
irgendeine Textersetzung vor und man muss die Definition kennen, um die
effektive Bedeutung in einer bestimmten Umgebung vorhersagen zu
koennen.

Abschreckendes Beispiel:

[***@duesterwald]~/work/linux-2-6 $grep '^#define' include/linux/list.h | grep each
#define list_for_each(pos, head) \
#define list_for_each_prev(pos, head) \
#define list_for_each_safe(pos, n, head) \
#define list_for_each_prev_safe(pos, n, head) \
#define list_for_each_entry(pos, head, member) \
#define list_for_each_entry_reverse(pos, head, member) \
#define list_for_each_entry_continue(pos, head, member) \
#define list_for_each_entry_continue_reverse(pos, head, member) \
#define list_for_each_entry_from(pos, head, member) \
#define list_for_each_entry_safe(pos, n, head, member) \
#define list_for_each_entry_safe_continue(pos, n, head, member) \
#define list_for_each_entry_safe_from(pos, n, head, member) \
#define list_for_each_entry_safe_reverse(pos, n, head, member) \
#define hlist_for_each(pos, head) \
#define hlist_for_each_safe(pos, n, head) \
#define hlist_for_each_entry(pos, head, member) \
#define hlist_for_each_entry_continue(pos, member) \
#define hlist_for_each_entry_from(pos, member) \
#define hlist_for_each_entry_safe(pos, n, head, member) \

Das sind 19 unterschiedliche Konfiguration von for (;;;)-Schleifen, die
unterschiedliche, undokumentierte Annahmen ueber ihre Umgebung
enthalten. Kuerzlich musste ich hier ein Basiskernelupdate von 3.2.54
auf 3.16.48 machen. Auf dem Weg dorthin hat jemand aus einem von diesen
Unkraeutern ein Feature ausgebaut, von dem er sich gerade gar nicht
vorstellen konnte, wofuer es gut sein koennte. Leider war das aber eins,
dass ich fuer etwas benutzt hatte. Es hat dann auch nur zwei Tage
Debugging von Oopses gebraucht, bis es mir gelungen war, experimentell
zu ermitteln, wie man das, was der fragliche Code tun muss, unter den
veraenderten Rahmenbedingen so implementiert, dass alles huebsch nett
aussieht (und wieder genauso funktioniert, wie es das seit Jahren
bereits tat).
Post by Stefan Reuther
oder wenn das ganze C++ wäre, wo man WIMRE das *& weglassen kann
(n_pkg ? n_pkg->p_me : chain) = pkg->p_me;
wird's zumindest subjektiv ein wenig lesbarer.
C unterstuetzt nunmal keine transparenten Referenzen, bloss Zeigerwerte.
Hans-Peter Diettrich
2017-11-08 13:20:34 UTC
Permalink
Raw Message
Post by Rainer Weikusat
Allerdings mag ich die "Mikro-Pessimierungen", was ich als "misslungener
Versuch, durch seltsame C-Konstruktionen Takte zu schinden" nicht auf
mir sitzen zu lassen. Darum geht es mir naemlich grundsaetzlich
nicht. Ich moechte eine in C sinnvolle Formulierung eines Algorithmus
haben und um Uebersetzung in sinnvollen Machinencode soll sich bitte der
Compiler kuemmern.
Für Lesbarkeit ist hier ?: grundsätzlich nicht geeignet, weil das per
Definition keinen LValue liefert.

Mich wundert zudem, warum die Bedingung vor ? nicht in Klammern stehen muß.

DoDi
Rainer Weikusat
2017-11-08 17:04:41 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Post by Rainer Weikusat
Allerdings mag ich die "Mikro-Pessimierungen", was ich als "misslungener
Versuch, durch seltsame C-Konstruktionen Takte zu schinden" nicht auf
mir sitzen zu lassen. Darum geht es mir naemlich grundsaetzlich
nicht. Ich moechte eine in C sinnvolle Formulierung eines Algorithmus
haben und um Uebersetzung in sinnvollen Machinencode soll sich bitte der
Compiler kuemmern.
Für Lesbarkeit ist hier ?: grundsätzlich nicht geeignet, weil das per
Definition keinen LValue liefert.
Heute ist es kaelter als draussen?

Um zu wissen, was fuer einen Wert ein ?:-Ausdruck zurueckliefert, muss
man ihn lesen. Rechts wie links.
Post by Hans-Peter Diettrich
Mich wundert zudem, warum die Bedingung vor ? nicht in Klammern stehen muß.
Weil ?: sinnvollerwiese einen geringeren Operator-Vorrang hat als alles,
woraus man ueblicherweise Bedingungen konstruiert. Lediglich die
Prioritaet der Zuweisungsoperatoren und die von , ist noch niedriger.
Helmut Schellong
2017-10-13 11:57:23 UTC
Permalink
Raw Message
Post by Thomas Koenig
Wenn dir Performance egal ist, natürlich. Ich würde mir nur keinen Stil
angewöhnen, der mit Mikro-Pessimierungen Compiler erst mal ausbremst.
Ich würde mal -O1 verwenden.
Manchmal ergibt das schnelleren Code als -O2, -O3.
--
Mit freundlichen Grüßen
Helmut Schellong ***@schellong.biz
www.schellong.de www.schellong.com www.schellong.biz
http://www.schellong.de/c.htm
Peter J. Holzer
2017-10-13 09:03:09 UTC
Permalink
Raw Message
Post by Thomas Koenig
Post by Rainer Weikusat
void remove_node(struct node *np)
{
struct node *n;
n = np->n;
*np->me = n;
*(n ? &n->me : &chain) = np->me;
free(np);
}
Ich habe das mal diese Funktion und dazu die funktional
äquivalente Variante
void remove_node_2(struct node *np)
{
struct node *n;
n = np->n;
*np->me = n;
if (n)
n->me = np->me;
else
chain = np->me;
free(np);
}
durch gcc und icc jeweils mit -O3 gejagt.
.cfi_startproc
movq (%rdi), %rdx
movq 8(%rdi), %rcx
leaq 8(%rdx), %rax
movq %rdx, (%rcx)
testq %rdx, %rdx
movl $chain, %edx
cmove %rdx, %rax
movq %rcx, (%rax)
jmp free
.cfi_startproc
movq (%rdi), %rax
movq 8(%rdi), %rdx
testq %rax, %rax
movq %rax, (%rdx)
je .L6
movq %rdx, 8(%rax)
jmp free
.p2align 4,,10
.p2align 3
movq %rdx, chain(%rip)
jmp free
[Ähnliches Ergebnis für icc gelöscht]
Post by Thomas Koenig
Beide Compiler erzeugen für die zweite, einfacher lesbarere Variante
schnelleren Code.
Hast Du das gemessen? Abgesehen davon, dass die Routine wahrscheinlich
ohnehin den Löwenanteil ihrer Zeit in free() verbringen wird und das
bisschen Pointerschaufeln davor vernachlässigbar ist, ist es bei
modernen Prozessoren notorisch schwierig, aus dem Assemblerlisting die
Laufzeit abzulesen. Einfaches Zyklenzählen funktioniert nicht, wenn der
Prozessor Instruktionen umordnen und parallel ausführen kann, und ein
einzelner Memory-Zugriff bringt sowieso alles durcheinander, wenn man
nicht weiß, aus welchem Cache der bedient wird.
Post by Thomas Koenig
Vor allem wird die Adresse von chain nicht angefasst, wenn es nicht
(wegen n == NULL) nötig ist.
Das ist ein immediate load, die Adresse ist Teil der Instruktion. Wird
also wohl maximal einen Zyklus brauchen.

Den Jump in der zweiten Variante halte ich da von der Performance her
für kritischer: In den meisten Szenarien wird der wohl fast immer
genommen (Liste fast leer) oder nicht genommen (Liste gut gefüllt)
werden, aber es gibt auch Szenarien (Neue Nodes weren paarweise erzeugt
und wieder gelöscht), wo der Sprung immer abwechselnd genommen und nicht
genommen wird. Kann sein, dass moderne Prozessoren sowas auch schon
können, aber im zweifelsfall hast Du dann jedesmal einen Miss.

Aber wie gesagt: Code lesen und spekulieren ist eine Sache, messen eine
andere.
Post by Thomas Koenig
Daher würde ich deine Variante nicht empfehlen, abgesehen von
der schlechteren Lesbarkeit erzeugt sie auch schlechteren Code.
Die Lesbarkeit ist very much in the eye of the beholder. In diesem
einfachen Fall sehe ich wenig Unterschied. Wenn der Ausdruck auf der
rechten Seite komplizierter wird, würde ich eher Rainers Variante den
Vorzug geben. Sie macht klarer, dass es der gleiche Wert ist, der an
unterschiedliche Ziele zugewiesen wird.

hp
--
_ | Peter J. Holzer | Fluch der elektronischen Textverarbeitung:
|_|_) | | Man feilt solange an seinen Text um, bis
| | | ***@hjp.at | die Satzbestandteile des Satzes nicht mehr
__/ | http://www.hjp.at/ | zusammenpaßt. -- Ralph Babel
G.B.
2017-10-27 04:28:43 UTC
Permalink
Raw Message
Post by Rainer Weikusat
Post by Rainer Weikusat
*(n_pkg ? &n_pkg->p_me : &chain) = pkg->p_me;
Hat jemand eine Ansicht zu obigem Trick oder zu der Konstruktion als
solcher und waere bereit, sie mitzuteilen?
void remove_node(struct node *np)
Hier oder an einer geeigneteren Stelle würde ich den Vermerk nützlich
finden, dass der übergebene Zeiger auf einen Knoten zeigen sollte.
Post by Rainer Weikusat
{
struct node *n;
n = np->n;
*np->me = n;
*(n ? &n->me : &chain) = np->me;
free(np);
}
Wenn feststeht, dass alle verwendeten Compiler verschachtelt
definierte Funktionen sinnvoll unterstützen (Ha!), würde ich überlegen,
den Einzeiler in eine zweckvermittelnd benannte lokale Funktion
zu wickeln.
Post by Rainer Weikusat
-------
Das habe ich jetzt allerdings nur aus dem Gedaechtnis runtergeschrieben
und uebersetzt, nicht getestet.
Peter J. Holzer
2017-10-27 08:56:39 UTC
Permalink
Raw Message
Post by G.B.
Post by Rainer Weikusat
void remove_node(struct node *np)
Hier oder an einer geeigneteren Stelle würde ich den Vermerk nützlich
finden, dass der übergebene Zeiger auf einen Knoten zeigen sollte.
Dieser Vermerk steht doch da: »struct node *«.

hp
--
_ | Peter J. Holzer | Fluch der elektronischen Textverarbeitung:
|_|_) | | Man feilt solange an seinen Text um, bis
| | | ***@hjp.at | die Satzbestandteile des Satzes nicht mehr
__/ | http://www.hjp.at/ | zusammenpaßt. -- Ralph Babel
G. B.
2017-10-27 18:18:51 UTC
Permalink
Raw Message
Post by Peter J. Holzer
Post by G.B.
Post by Rainer Weikusat
void remove_node(struct node *np)
Hier oder an einer geeigneteren Stelle würde ich den Vermerk nützlich
finden, dass der übergebene Zeiger auf einen Knoten zeigen sollte.
Dieser Vermerk steht doch da: »struct node *«.
Leider entstehen aus dieser Auffassung Löcher
in Systemen.
Rainer Weikusat
2017-10-27 18:29:14 UTC
Permalink
Raw Message
Post by G. B.
Post by Peter J. Holzer
Post by G.B.
Post by Rainer Weikusat
void remove_node(struct node *np)
Hier oder an einer geeigneteren Stelle würde ich den Vermerk nützlich
finden, dass der übergebene Zeiger auf einen Knoten zeigen sollte.
Dieser Vermerk steht doch da: »struct node *«.
Leider entstehen aus dieser Auffassung Löcher
in Systemen.
Das klingt nicht gut. Gibt es spezielle Rostschutskommentare? Oder tut
es auch beliebiges Gerade?
G.B.
2017-10-28 06:50:22 UTC
Permalink
Raw Message
Post by Rainer Weikusat
Post by G. B.
Post by Peter J. Holzer
Post by G.B.
Post by Rainer Weikusat
void remove_node(struct node *np)
Hier oder an einer geeigneteren Stelle würde ich den Vermerk nützlich
finden, dass der übergebene Zeiger auf einen Knoten zeigen sollte.
Dieser Vermerk steht doch da: »struct node *«.
Leider entstehen aus dieser Auffassung Löcher
in Systemen.
Das klingt nicht gut. Gibt es spezielle Rostschutskommentare? Oder tut
es auch beliebiges Gerade?
Als spezieller Rostschutz haben sich Hinweise auf zulässige
Werte bewährt. Auch dann, wenn sie im Kontext der aktuellen
Entwicklung redundant erscheinen können.

Der Typ struct node* umfasst einen Wert, den zu benutzen
an der einen Stelle der Implementierung der Datenstruktur
wesentlich ist (n == NULL), an einer anderen Stelle fatal
(np == NULL). Plausiblerweise, wie ich finde, nimmt remove_node
die entsprechende Prüfung nicht vor. Wenn das ein Konstruktions-
Prinzip ist - es ist keine Folge nur des Typs - dann kann
ein Hinweis auf diese Wahl aufmerksam machen.

Nicht gleich aber ähnlich wie wenn Programmierer darauf hingewiesen
werden, dass eine Prüfung nur auf "negative Rückgabe" zu
Fehlschlüssen führen kann. Denn die Annahmen über den Vorrat
an Werten, die der Funktions-Aufrufer macht, können von den
entsprechenden Annahmen des Funktions-Entwicklers abweichen.

x += 1;
return x;

Unausgesprochene Annahmen sorgen oft für konfligierende
Entwicklung und das kann dann ungewollt Löcher erzeugen.
Rainer Weikusat
2017-10-29 13:54:26 UTC
Permalink
Raw Message
Post by G.B.
Post by Rainer Weikusat
Post by G. B.
Post by Peter J. Holzer
Post by G.B.
Post by Rainer Weikusat
void remove_node(struct node *np)
Hier oder an einer geeigneteren Stelle würde ich den Vermerk nützlich
finden, dass der übergebene Zeiger auf einen Knoten zeigen sollte.
Dieser Vermerk steht doch da: »struct node *«.
Leider entstehen aus dieser Auffassung Löcher
in Systemen.
Das klingt nicht gut. Gibt es spezielle Rostschutskommentare? Oder tut
es auch beliebiges Gerade?
Als spezieller Rostschutz haben sich Hinweise auf zulässige
Werte bewährt. Auch dann, wenn sie im Kontext der aktuellen
Entwicklung redundant erscheinen können.
Hmm, naja, zulaessige Werte fuer eine Funktion, die einen Knoten aus
einer verketteten Liste entfernt, sind gueltige Zeiger auf Knoten. Alles
andere hat keinen Sinn. Insofern der aufrufende Code auch mit
ungueltigen Zeigern hantieren kann, ist es dessen Aufgabe,
sicherzustellen, dass die Vorbedingung erfuellt ist, bevor die Funktion
aufgerufen wird.

[...]
Post by G.B.
Nicht gleich aber ähnlich wie wenn Programmierer darauf hingewiesen
werden, dass eine Prüfung nur auf "negative Rückgabe" zu
Fehlschlüssen führen kann. Denn die Annahmen über den Vorrat
an Werten, die der Funktions-Aufrufer macht, können von den
entsprechenden Annahmen des Funktions-Entwicklers abweichen.
x += 1;
return x;
Unausgesprochene Annahmen sorgen oft für konfligierende
Entwicklung und das kann dann ungewollt Löcher erzeugen.
Absichtliche, mutwillige oder fahrlaessige Fehlnutzung technischer
Geraete, auch solcher, die via Software emuliert werden, kann
unerwuenschte Effekte hervorrufen. Das laesst sich durch
inline-Dokumentation von Selbsverstaendlichkeiten nicht verhindern,
bestenfalls macht man dadurch eine fadenscheinige Ausrede etwas
fadenscheiniger. Man musss ausserdem gewaertig sein, das jemand den Code
spaeter aendert, aber nicht den Kommentar, denn der wird ja nicht
ausgefuehrt.

Hier wuerde ich auch gerne mal ein Beispiel sehen. Sogenannte
"Sicherheitsluecken" in Software gibt es ueblicherweise weil

- das Design fehlerhaft war (=> WPA2)

- mal wieder jemand der Ansicht war, man koenne 'erst mal'
Eingabedaten aus einer nicht vertrauenswuerdigen Quelle
ungeprueft verarbeiten, denn um eine solche Ueberpruefung
ginge es im Moment nicht (Seggelmannoever).
G.B.
2017-10-31 09:56:46 UTC
Permalink
Raw Message
Post by Rainer Weikusat
Hmm, naja, zulaessige Werte fuer eine Funktion, die einen Knoten aus
einer verketteten Liste entfernt, sind gueltige Zeiger auf Knoten. Alles
andere hat keinen Sinn.
"Hat keinen Sinn" ist eine Annahme, die ich dann vertretbar finde,
wenn alle Aufrufer sie teilen. Ich kann mir nicht vorstellen,
dass dies unter allen Umständen gegeben ist oder auch sein muss:
Es erscheint mir nicht abwegig, wenn jemandes Algorithmus aus einer
Knotenmenge die leere Knotenmenge entfernen möchte und dabei
de facto nicht zutreffende Annahmen über remove_node macht,
seien sie auch der beruflichen Belastung, der verfügbaren
Nachdenkzeit, bzw. der für Quellenstudium und die logische
Erschließung der Annahmen der Datenstruktur fehlenden Zeit
geschuldet.

Deswegen klappt auch der Verweis auf Selbstverständlichkeiten
nicht zuverlässig. Es gibt sozusagen Fremdverständlichkeiten,
die sich später als plausibel herausstellen.
Post by Rainer Weikusat
Absichtliche, mutwillige oder fahrlaessige Fehlnutzung technischer
Geraete, auch solcher, die via Software emuliert werden, kann
unerwuenschte Effekte hervorrufen.
Viele Nutzungen haben Effekte. Die Absichten des Aufrufers mit
Adjektiven einzugrenzen erinnert mich an Gesetze, deren Effekt
den guten Willen voraus setzt. Manchmal macht die Erwähnung
von offensichtlich erscheinenden Annahmen offensichtlich,
dass den Lesern die Annahme nicht offensichtlich war.
Rainer Weikusat
2017-10-31 18:51:06 UTC
Permalink
Raw Message
Post by G.B.
Post by Rainer Weikusat
Hmm, naja, zulaessige Werte fuer eine Funktion, die einen Knoten aus
einer verketteten Liste entfernt, sind gueltige Zeiger auf Knoten. Alles
andere hat keinen Sinn.
,----
| Insofern der aufrufende Code auch mit ungueltigen Zeigern hantieren
| kann, ist es dessen Aufgabe, sicherzustellen, dass die Vorbedingung
| erfuellt ist, bevor die Funktion aufgerufen wird.
`----
Post by G.B.
"Hat keinen Sinn" ist eine Annahme, die ich dann vertretbar finde,
wenn alle Aufrufer sie teilen. Ich kann mir nicht vorstellen,
Es erscheint mir nicht abwegig, wenn jemandes Algorithmus aus einer
Knotenmenge die leere Knotenmenge entfernen möchte und dabei
de facto nicht zutreffende Annahmen über remove_node macht,
Man kann niemanden daran hindern, 'anzunehmen' was auch immer ihm
passt. Allerdings ist anzunehmen, dass Leute um so weniger bereit sind,
Dokumentation zu lesen, wie sie mehr dazu neigen anzunehmen,
unbegruendete Annahmen haetten richtig zu sein, weil sie angenommen
wurden.
G.B.
2017-11-04 09:59:16 UTC
Permalink
Raw Message
Post by Rainer Weikusat
Post by Rainer Weikusat
Hmm, naja, zulaessige Werte fuer eine Funktion, die einen Knoten aus
einer verketteten Liste entfernt, sind gueltige Zeiger auf Knoten. Alles
andere hat keinen Sinn.
,----
| Insofern der aufrufende Code auch mit ungueltigen Zeigern hantieren
| kann, ist es dessen Aufgabe, sicherzustellen, dass die Vorbedingung
| erfuellt ist, bevor die Funktion aufgerufen wird.
`----
Der aufrufende code (sein Autor) bekommt ja keine Chance,
zu wissen, welche Zeiger ungueltig sind: Nur die Quellen
lassen Schlussfolgerungen zu. Und dort, in den Quellen,
ist bspw. ein NULL-Zeiger am Ende ein gültiges Instrument.
Post by Rainer Weikusat
Man kann niemanden daran hindern, ...
unbegruendete Annahmen haetten ... sein....
Diese zwischenmenschliche Kommentierung wäre nicht nötig, wenn,
im bevorzugten Stil, z.B. geschrieben stünde

void remove_node(
struct node *np /* np nicht NULL */
);

Damit wären die m.E. wahrscheinlichsten Annahmen zweckmäßig
dokumentiert, mit gewissermaßen bindender Wirkung. Die Verwendung eines
Zeigers auf realiter irgendetwas anderes beim Aufruf kann dann im Fehler-
oder gar Streitfall als eine selbst zu verantwortende Verwendung von
Typ-Wandlung o.ä. charakterisiert werden.
Thomas Koenig
2017-11-04 14:00:36 UTC
Permalink
Raw Message
Post by G.B.
Diese zwischenmenschliche Kommentierung wäre nicht nötig, wenn,
im bevorzugten Stil, z.B. geschrieben stünde
void remove_node(
struct node *np /* np nicht NULL */
);
... oder

void remove_node {
struct node *np;

assert (np);
}
Rainer Weikusat
2017-11-10 16:03:30 UTC
Permalink
Raw Message
Post by Thomas Koenig
Post by G.B.
Diese zwischenmenschliche Kommentierung wäre nicht nötig, wenn,
im bevorzugten Stil, z.B. geschrieben stünde
void remove_node(
struct node *np /* np nicht NULL */
);
... oder
void remove_node {
struct node *np;
assert (np);
}
Das erscheint mir grundsaetzlich sinnvoller, weil es die Vorbedinung ueberprueft
anstatt sie bloss zu dokumentieren. Andererseits ist das aber auch bloss
eine halbe Massnahme, weil ein Zeiger, der einem struct node *
zugewiesen werden kann und kein Nullzeiger ist, nicht notwendigerweise
auf ein Objekt des entsprechenden Typs zeigt.

ZB ist das hier:

--------
#include <assert.h>

struct node {
struct node *p, **me;
};

static struct node nodes[20], *head, **chain = &head;

static void remove_node(struct node *np)
{
struct node *next;

assert(np);

next = np->p;
*np->me = next;
*(next ? &next->me : &chain) = np->me;
}

int main(void)
{
remove_node(nodes + 20);
return 0;
}
--------

grammatisch einwandfreier C-Code mit undefiniertem Verhalten, weil der
"eins hinter das Feld"-Zeiger nicht dereferenziert werden darf. Hatte
man stattdessend nodes + 19 benutzt, waere das Verhalten undefiniert,
weil ein Nullzeiger dereferenziert wurde (np->me).

Man koennte die unterschiedlichen Positionen hier wie folgt umreissen:

1. Wir wollen so viel Ueberpruefung, wie moeglich, weil auch eine
unvollstaendige Ueberpruefung wenigstens manche Fehler automatisch
erkennt.

2. Wasserdichte Ueberpruefung gibt es nicht, wenigstens nicht in
C. Ausserdem erfordern diese Pruefungen eigens dafuer geschriebenen
Code. Mehr Code bedeutet nicht nur, dass das Programm als ganzer
schwerer zu verstehen wird, sondern ausserdem moeglicherweise auch
noch 'mehr Fehler' denn der Ueberpruefungscode ist magisch gegen
diese gefeit. Im Zweifelsfalls ist deswegen 'weniger Code', dh keine
unvollstaendige Ueberpruefung, vorzuziehen.

(Diese Beschreibung soll neutral sein. Eventuell ist mir das nicht
gelungen).

Ich halte 2 fuer sinnvoller.
G.B.
2017-11-11 09:41:37 UTC
Permalink
Raw Message
Post by Rainer Weikusat
Wasserdichte Ueberpruefung gibt es nicht,
Deswegen finde ich nützlich, per kurzem, nur schwer zu
übersehenden Hinweis zu dokumentieren, dass Aufrufer
genau die fachliche Vorsicht walten lassen sollten,
die sich ihrer Art nach aus einer Wahlentscheidung des
Datenstruktur-Anbieters nach Zweck und Mitteln ergibt.

Ein assert() kann nicht das Halteproblem lösen, aber
der aufrufende Algorithmus mag ergeben können, dass
Aufrufe nur mit per Konstruktion gültigen Listenknoten
erfolgen werden.

void remove_node(
struct node* p /* ein gültiger Knoten */
);

ist dann, wie sie sein soll, Implementierung wie gehabt.

Falls Korinthen verhandelt werden müssen, lässt sich
der Spielraum von "gültig" außerhalb der Quellen
spezifizieren. Ein Verweis in Klammern reicht dann.

Rainer Weikusat
2017-11-04 19:47:27 UTC
Permalink
Raw Message
Post by G.B.
Post by Rainer Weikusat
Post by Rainer Weikusat
Hmm, naja, zulaessige Werte fuer eine Funktion, die einen Knoten aus
einer verketteten Liste entfernt, sind gueltige Zeiger auf Knoten. Alles
andere hat keinen Sinn.
,----
| Insofern der aufrufende Code auch mit ungueltigen Zeigern hantieren
| kann, ist es dessen Aufgabe, sicherzustellen, dass die Vorbedingung
| erfuellt ist, bevor die Funktion aufgerufen wird.
`----
Der aufrufende code (sein Autor) bekommt ja keine Chance,
zu wissen, welche Zeiger ungueltig sind: Nur die Quellen
lassen Schlussfolgerungen zu. Und dort, in den Quellen,
ist bspw. ein NULL-Zeiger am Ende ein gültiges Instrument.
Ein Nullzeiger ist ein Zeiger, dessen Wert garantiert unterschiedlich
von jedem Zeiger auf etwas existierendes ist. Insofern darf man ihn wohl
einen 'ungueltigen' Zeiger nennen. Mit einem Nullzeiger kann man auch
gar nichts machen, ausser ihn festzustellen, dass er ein Nullzeiger ist.

Insofern fuer diesen Fall nicht ausdruecklich eine Semantik definiert,
sollte man billigerweise von undefiniertem Verhalten ausgehen.
Post by G.B.
Post by Rainer Weikusat
Man kann niemanden daran hindern, ...
unbegruendete Annahmen haetten ... sein....
Diese zwischenmenschliche Kommentierung wäre nicht nötig, wenn,
im bevorzugten Stil, z.B. geschrieben stünde
void remove_node(
struct node *np /* np nicht NULL */
);
Damit wären die m.E. wahrscheinlichsten Annahmen zweckmäßig
dokumentiert, mit gewissermaßen bindender Wirkung. Die Verwendung eines
Zeigers auf realiter irgendetwas anderes beim Aufruf kann dann im Fehler-
oder gar Streitfall als eine selbst zu verantwortende Verwendung von
Typ-Wandlung o.ä. charakterisiert werden.
Es gaebe sehr viel weniger (manchmal gefaehrlich) kaputte Software auf
diesem Planet, wenn der Aufwand, der zur Verteidigung gegen finstere
Absichten und/ oder Bloedheit von Kollegen getrieben wird, zur
Abwechslung mal auf Eingabeueberpruefung angewendet wuerde ...
Helmut Schellong
2017-10-12 18:19:14 UTC
Permalink
Raw Message
Post by Thomas Koenig
Post by Rainer Weikusat
*(n_pkg ? &n_pkg->p_me : &chain) = pkg->p_me;
Hat jemand eine Ansicht zu obigem Trick oder zu der Konstruktion als
solcher und waere bereit, sie mitzuteilen?
Kannst du die notwendigen Typen- und Variablendeklarationen dazliefern,
damit man das mal kompilieren kann? Der Typ von n_pkg erschließt sich
mir nicht direkt.
n_pkg wird ein Pointer auf eine Struktur sein.
--
Mit freundlichen Grüßen
Helmut Schellong ***@schellong.biz
www.schellong.de www.schellong.com www.schellong.biz
http://www.schellong.de/c.htm
Patrick.Schluter
2017-10-16 18:49:49 UTC
Permalink
Raw Message
Post by Rainer Weikusat
-------
*(n_pkg ? &n_pkg->p_me : &chain) = pkg->p_me;
-------
Das ist Teil einer Codesequenz, die ein Element aus einer doppelt
verketteten Liste loescht. Anstatt eines Vorgaenger- und eines
Nachfolgerzeigers hat jedes Element einen Nachfolgerzeiger und einen
Zeiger auf den Zeiger, der auf das Element selber zeigt. n_pkg ist der
Wert des Nachfolgerzeigers des zu entfernenden Objektes, chain ist der
top-level Zeiger, der auf den Zeiger zeigt, der beim Anfuegen eines
neuen Elementes modifiziert werden muss.
Hat jemand eine Ansicht zu obigem Trick oder zu der Konstruktion als
solcher und waere bereit, sie mitzuteilen?
Ja, ich finde sowas auch lesbarer als das if/else Geschwurbel in diesem
Fall. Der Grund dafür liegt darin das es sich hauptsächlich um die
Operation: pkg->p_me einfändeln. Die Auswahl wo es hinkommt is logisch
dieser Operation untergeordnet. Besonders wenn der Test so
unausgeglichen ist (heisst das die Wahl n_pkg->p_me überagt da chain ja
in wirklichkeit nur ein einziges Mal vorkommt).

if/else hat so eine 50/50 Beigeschmack der hier irritierend ist.
Es ist aber sehr Subjektiv und niemand soll sich jetzt darüber aufregen.
Es ist nichts mehr als eine persönliche Marotte.
Thomas Koenig
2017-10-17 18:54:54 UTC
Permalink
Raw Message
Post by Patrick.Schluter
if/else hat so eine 50/50 Beigeschmack der hier irritierend ist.
Für einen NULL-Check sehe ich das anders, und gcc auch. Für einen
Pointer a betrachtet gcc bei

if (a)
something();
else
something_else();

den something_else() - Zweig als "cold" und schiebt den Code dazu
ans Ende der Funktion.

Das folgt halt der bei C üblichen Konvention, bei der NULL häufig
als Fehlerwert (oder auch nur als seltener Wert) verwendet wird.
Loading...