Viele Fragen zu padding

rapso

Senfgurke schrieb:

Warum wird damit überhaupt konkret eine bessere Cachetrefferquote erreicht?
Ich verstehe nicht was es bringen soll einen 64/128 Byte (je nach Cachelinegröße) großen Speicherbereich – minus der kleinen Mengen der benötigten Daten einer Struktur, zu verschwenden.

aus sicht der cpu ist der speicher aus cachelines aufgebaut. wenn du eine struct von 63byte nutzt, verbrauchst du für 64 von denen 63 cachelines. außer bei der ersten und letzten struct sind alle über 2 cachelines verteilt, greifst du auf irgendeine zu, ist die chance 30:1 dass die cpu 128byte lesen muss um dir die 63byte zur verfügung zu stellen (falls nicht schon im cache). dadurch muss fast doppelt soviel übertragen werden und es passen effektiv nur halb soviele structs in den cache, das bedeutet 50% der möglichen cachehits.
je mehr speicher man nutzt desto wichtiger ist das. wenn die daten eh in den cache passen und man viel darauf zugreift, sollte man sie tightfitting ohne padding machen.

Senfgurke schrieb:

Können nicht die Daten etwas hinter der Cache-Tag-Adresse gelesen und genutzt werden?

klar, besser als padding ist natürlich wenn man die cacheline mit nützlichen daten füllt. wenn eine struct 63 byte verbrauchtn könnte man sich noch überlegen ob man das byte nutzt.
anders ist es natürlich wenn du 65byte nutzt, da könnte man sich überlegen ob man nicht mit ein wenig rechenaufwand ein paar bytes zusammenlegen kann.

wenn man große structs hat, ist es oft nützlich selten genutzte daten auszulagern und sich nur nen pointer darauf zu merken (zb char arrays für namen von nodes).

TGGC schrieb:

Das Padding hat doch nichts mit den Cache-Grössen zu tun,

hat ja auch niemand behauptet.

Zunächst erstmal Danke für Eure Erklärungsversuche.

rapso schrieb:

aus sicht der cpu ist der speicher aus cachelines aufgebaut. wenn du eine struct von 63byte nutzt, verbrauchst du für 64 von denen 63 cachelines.

Leuchtet mir nicht ein.

Wenn eine cacheline 64 Byte groß ist und Strukturen durch padding 64 Bytes groß werden, besetzen 64 Strukturen mit 63 Byte genutztem Speicherumfang auch 64 cachelines – es wird halt einfach ein Byte an dem Speicherbereich einer 63 Byte Struktur angehängt, damit sie die gleiche Größe einer cacheline hat.

außer bei der ersten und letzten struct sind alle über 2 cachelines verteilt, greifst du auf irgendeine zu, ist die chance 30:1 dass die cpu 128byte lesen muss um dir die 63byte zur verfügung zu stellen (falls nicht schon im cache). dadurch muss fast doppelt soviel übertragen werden und es passen effektiv nur halb soviele structs in den cache, das bedeutet 50% der möglichen cachehits.

Das was du hier meinst sind aber kapazitive Cache-Verfehlungen - padding wird doch aber betrieben um Konflikt-Verfehlungen zu vermeiden, verstärken kapazitive Cache-Verfehlungen jedoch etwas.

rapso

Senfgurke schrieb:

]Das was du hier meinst sind aber kapazitive Cache-Verfehlungen - padding wird doch aber betrieben um Konflikt-Verfehlungen zu vermeiden, verstärken kapazitive Cache-Verfehlungen jedoch etwas.

würde man meinen, aber je größer der tradeoff zwischen cachegröße und dem wirklich verwendetem speicher ist, desto besser ist das caching mit padding, weil, wie gesagt, jeder eintrag so wenig cachelines wie möglich verbraucht und somit mehr einträge vorhanden sind und somit mehr cachehits.

Sgt. Nukem

Senfgurke schrieb:

Zunächst erstmal Danke für Eure Erklärungsversuche.

rapso schrieb:

aus sicht der cpu ist der speicher aus cachelines aufgebaut. wenn du eine struct von 63byte nutzt, verbrauchst du für 64 von denen 63 cachelines.

Leuchtet mir nicht ein.

Wenn eine cacheline 64 Byte groß ist und Strukturen durch padding 64 Bytes groß werden, besetzen 64 Strukturen mit 63 Byte genutztem Speicherumfang auch 64 cachelines – es wird halt einfach ein Byte an dem Speicherbereich einer 63 Byte Struktur angehängt, damit sie die gleiche Größe einer cacheline hat.

Yo. rapso hat halt den Fall für OHNE PADDING beschrieben (nehme ich mal an).

rapso

Sgt. Nukem schrieb:

Yo. rapso hat halt den Fall für OHNE PADDING beschrieben (nehme ich mal an).

oui
falls das nucht klargeworden ist,
wollte zeigen dass für 64 structs 63 cachelines benutzt werden, aber für fast jede einzelne struct die man lädt 2cachelines behandelt werden.

Auch so kann ich dies nicht nachvollziehen.

Wie soll die Größe der Struktur durch padding Einfluss darauf haben ob sie auf einer oder mehreren cachelines abgebildet wird?
Es währe ja dann davon abhängig von welcher Adresse an die Struktur(en) im Speicher stehen.

rapso

zum padding dazu gehört allignment und das beeinflusst natürlich wie die daten im speicher liegen. wenn du ne struct hast

struct
{
byte
dword
}

dann wird dein kompiler nicht das machen

struct
{
byte
dword
byte
byte
byte
}

sondern

struct
{
byte
byte
byte
byte
dword
}

deswegen muss auch structs von 1byte auf 64byte nicht padden, das würde das allignment nicht verbessern.

weil das allignment im cache nur eines der alliignments der cpus sind.
manche cpus sind strikt an allignments gebunden nd können garnicht anders als z.b. 32bit addresen ansprechen, dadurch muss der compiler bei einer "falsch" gepadeten variable per hand daten umschiften um die variable schlussendlich so im register liegen zu haben, wie sie im source steht.
die meisten cpus machen das intern von selbst (bei x86 war das ab dem pentiuum pro so, deswegen war er in vielen 16bit anwendungen oft viel langsammer als ein gleichgetakteter pentium). wr merken das kaum außer durch nen performancedrop. manche cpus bieten dafür zwei instruktionen, zB bei sse kann man alligned oder unalligned daten lesen.

padding ist also ein mittel um allignment zu erreichen. das kann sich dann je nach cpu und system performancemässig auswirken, oder überhaupt erst erlauben dass programme richtig laufen. bei einigen konsolen ist es zb so, dass manche speicherbereiche nur mit zb 16bit beschrieben oder gelesen werden können und programmcode kann manchmal nur an 32bit grenzen von der cpu geladen werden.

wieso überhaupt allignment? genau so wie 8bit zu einem byte zusammengefasst wird, so fasst man in vielen bussen (auch cpu intern) mehrere bytes zu einem datenelement zusammen, darauf ist dann die ganze architektur ausgelegt.

die busbreite hat dann wiederrum mit der vorherigen analyse der anwendung zu tun.

Hmm, könnt ihr aktuelle Literatur empfehlen die das genauer erläutert?

Senfgurke schrieb:

Hmm, könnt ihr aktuelle Literatur empfehlen die das genauer erläutert?

Ich fand das schon nicht schlecht, aber ich versuche es nochmal ohne auf eine konkrete CPU einzugehen:

Eine angenommene CPU mit einem 32-Bit-Datenbus hat oft nur Adressleitungen von A2-An, sie liest im Idealfall mit einem Zugriff also ein Langwort oder vier Bytes ein, aber immer an einer durch vier Teilbaren Adresse (da es ja kein A0/A1 gibt).

Sei eine Struktur:

struct {
char a;
char b;
long c;
} s;

Dann würde ohne Padding bei einem Beginn von s an einer durch vier Teilbaren Adresse das long c an einem Offset von 2 liegen. Leider liegt es dann aber zur Hälfte in diesem 32-Bit-Block, zur Hälfte im nächsten. Also kann die CPU trotz ihrer tollen 32-Bit-Datenbus nur mit zwei Lesezugriffen jeweils eine Hälfte des long lesen und muß diese dann zusammenbasteln. Das dauert natürlich länger, als wenn das padding dafür gesorgt hätte, das c an einer durch vier teilbaren Adresse liegt und mit einem Lesezugriff gelesen werden kann.

Warum die CPU nicht einfach A0 und A1 bekommt? Nun, die RAM-Module haben auch eine Breite und sind nicht an "Byte-Adressen" sondern an vielfachen der Modulbreite adressierbar, also helfen A0 und A1 nicht. (Auch die Module sind so gebaut, weil sonst einige der Chips auf dem Modul eine andere Adresse bekommen müssten als andere und man so mehr Zeit für den Zugriff (oder evtl. mehr pins oder aufwändigere, langsamere Logik) bräuchte.)

Einige CPUs können einfach nicht selber solche verteilten longs lesen, also läuft ein Programm nur mit padding und alignten Daten oder noch langsamerem Code der dafür sorgt das die Zugriffe von Hand simuliert werden, andere machen das zwar, aber brauchen natürlich auch dann mehr Zyklen für den Zugriff, weil es in Wirklichkeit zwei sind.

Ich hoffe das war zu irgendwas gut.

Gut, soweit klar.

Allerdings beziehe ich mich um das padding auf 8 Byte / 64 Bit, die der Größe einer cacheline entsprechen.
Liegt dies ähnlich gelagert am Adressraster der cache-MMU?
8 Byte für jede Struktur sind ja ganz schön der Hammer.

rapso

Senfgurke schrieb:

Gut, soweit klar.

Allerdings beziehe ich mich um das padding auf 8 Byte / 64 Bit, die der Größe einer cacheline entsprechen.
Liegt dies ähnlich gelagert am Adressraster der cache-MMU?
8 Byte für jede Struktur sind ja ganz schön der Hammer.

wie ich schon in einem meiner ersten postings schrieb sind es 64byte(nicht bit) bei den mesiten neuen x86 cpus.

Ach ja, klar.

Aber jedenfalls ist doch das standard padding im VC++ compiler 64 Bit.
Und dies war doch bereits vor 64 Bit x86 CPUs so?

Senfgurke schrieb:

Ach ja, klar.

Aber jedenfalls ist doch das standard padding im VC++ compiler 64 Bit.
Und dies war doch bereits vor 64 Bit x86 CPUs so?

Sagt wer?

struct S {
    char a;
    char b;
    char c;
    short d;
    long e;
};

Hier gibt sizeof(S) 12, nicht 16, wie es nach Deiner Meinung sein müsste.
Und auch sizeof(s[3]) gibt natürlich 36. und bei einem

struct S2 { S a; S b; S c; };

gibt sizeof(S2) auch artig 36. Ich weiss also gerade nicht, wo auf 64-Bit "gepadded" wird (alle Angaben mit VC++ 2003). Gib mal ein Beispiel was Du meinst, wenn Du was anderes meinst.

Was anderes ist, wie klein die Speicherbereiche granuliert sind, die man mit malloc/new dann tatsächlich bekommt. Die sind bei den meisten Systemen in vielfachen von 8 Byte, was oft (nicht immer) daran liegt, das bei Freigabe ein Next-Pointer und eine Grössenangabe für die Freispeicherverwaltung reinpassen müssen, und die brauchen halt zusammen 8 Bytes.

rapso

class S
{ 
	char a; 
	short d; 
};

int main(int argc,char* argv[])
{
	int cc=sizeof(S);

	printf("%d\n",cc);
	return 0;
}

class S
{ 
	char a; 
	char b; 
	char c; 
	int d; 
};

.
.
.

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vccore/html/_core_.2f.zp.asp

Dort wird eben ein standard alignment auf 8 Byte angegeben (ist auch so im VC++ 2003).

Senfgurke schrieb:

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vccore/html/_core_.2f.zp.asp

Dort wird eben ein standard alignment auf 8 Byte angegeben (ist auch so im VC++ 2003).

Okay, eine Kleinigkeit spielt da noch mit rein, nämlich die Grösse des grössten Elementes.

Packe ich in das S aus meinem Beispiel noch ein double f; hinten rein, bekomme ich in der Tat ein 8-Byte-Alignment, weil f 8 Byte groß ist. Das Alignment die POD-Typen werden halt auf ein vielfaches ihrer eigenen grösse aligned, bzw. die Struktur auf die Alignment-Anforderungen ihres grössten PODs (max. 8 Bytes default).

Mit dem double wird S 24 Bytes gross:

Offset(hex):
  00  a
  01  b
  02  c
  03  .
  04  dd
  06  ..
  08  eeee
  0c  ....
  10  ffffffff

Erzwingt man hingegen ein 4-Byte-Alignment, sind es nur 20 Bytes und f beginnt ab 0x0c.

Daraus folgt aber wie schon vorher, das eine Struct durchaus kleiner als 8 sein kann, egal ob 8-Byte-Alignment Default ist. Ein double erzwingt halt mit den Defaults das 8-Byte-Alignment, sowohl für die Position des double, als auch für die Grösse des Struct, damit in einem Array davon auch im nächsten Struct der double korrekt liegt.