Unterschied Array Structure

J

jmc

0
Warum ist eigenltich der Zugriff auf eine Struktur so viel langsamer als auf einen Array?
z.B. der Zugriff auf

Code: 
typedef __HASH {
unsigned char a : 8;
unsigned char b : 8;
unsigned char c : 8;
unsigned char d : 8;
unsigned char e : 8;
unsigned char f : 8;
unsigned char g : 8;
unsigned char h : 8;
} hash;

ist bei mir viel langsamer als auf

Code: 
typedef unisgned char hash[8]

woran liegt das?

Noch etwas: Kennt ihr zufälligerweise eine schnelle Hashmethode um aus 2* 64bit 32 bit zu machen? Bei jeder 64 bit Zahl gilt: Bit k*8+6 und k*8+7 sind immer 0 und es werden nur die ersten 56 bits benötigt, der Rest ist immer 0. Die Hashfunktion sollte eine sehr hohe Performance aufweisen

Die auf 1 gesetzten Bits der folgenden Zahl sind also wichtig. Der Rest ist immer 0:
0000000000111111001111110011111100111111001111110011111100111111
 
Warum ist eigenltich der Zugriff auf eine Struktur so viel langsamer als auf einen Array?
Zum Vergrößern anklicken....
weil der Compiler schlechte Laune hat ;). Lass Dir mal die generierte Assembly zeigen - wenn ich Deine Beispiele mit gcc compiliere, bekomme ich identischen Code:
Code: 
typedef struct __HASH {
unsigned char a : 8;
unsigned char b : 8;
unsigned char c : 8;
unsigned char d : 8;
unsigned char e : 8;
unsigned char f : 8;
unsigned char g : 8;
unsigned char h : 8;
} hash;

typedef unsigned char hash_arr[8];
hash_arr myArray={1,2,3,4,5,6,7,8};
hash myHash={1,2,3,4,5,6,7,8};

int  main()
{

  char a=myHash.a;
  unsigned char b=myArray[1];
  printf("hello %d %d",a,b);
 return 0;
}

Wird zu:
globl _myArray
	.section .data
_myArray:
	.byte	1
	.byte	2
	.byte	3
	.byte	4
	.byte	5
	.byte	6
	.byte	7
	.byte	8
.globl _myHash
_myHash:
	.byte	1
	.byte	2
	.byte	3
	.byte	4
	.byte	5
	.byte	6
	.byte	7
	.byte	8
	.section .text
Zugriff:
movb	_myHash, %al
	movb	%al, -1(%ebp)
	movb	_myArray+1, %al
	movb	%al, -2(%ebp)
	subl	$4, %esp
	movl	$0, %eax
	movb	-2(%ebp), %al
	pushl	%eax
	movsbl	-1(%ebp),%eax
	pushl	%eax
	pushl	$LC0
	call	_printf
der g++ spuckt mir auch so ähnliche Version aus:
Code: 
call	___main
	movzbl	_myHash, %eax
	movb	%al, -6(%ebp)
	movzbl	_myArray+1, %eax
Das ganze ohne irgendwelche Optimierungen.
 
Hallo,
eine ganz schnelle Hashfunktion wäre, wenn man die 32 Bit Hälften einfach XORed, evt. mit einer kleinen Verschiebung/Rotation, also part1 XOR (part2 ROTATE 3) XOR (part3 ROATE 5) ...

Natürlich nicht sicher, aber schnell.
 
Wenn ich einen solchen Code benutze, dann ergibt es bei mir auch dasselbe, aber ich habe zwei Arrays, mit einer Grösse von 0x1FFFFFFF dieser beiden Typen und wenn ich diese danach besetze und wieder abrufe ist der Array ca. 4x schneller, was mich ziemlich überrascht hat, da der doch eigentlich gleich aufgebaut werden könnte.
Compiliert wird mit dem Compiler von VC++ 2008 mit den Optionen
Code: 
/O2 /Oi /Ot /GL /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /Gm /EHsc /MDd /FA /Fa"Debug\\" /Fo"Debug\\" /Fd"Debug\vc80.pdb" /W3 /nologo /c /Wp64 /TP /errorReport:prompt

@ Elderan Ich hötte noch erwähnen müssen, dass es möglichst wenige Kollisionen geben sollte, denn ansonsten wird das ganze trotzdem wieder zu langsam.
Bis jetzt habe ich für alle 128 bit zu Begin einmal eine Zufallszahl(64 bit) erstellen lassen.
Danach habe ich meinen Hash (zu Begin 0) mit jeder der Zufallszahlen geXORed, die gesetzt sind. Danach habe ich die ersten 32 bit um 6 nach links rotiert und die zweiten um 6 nach rechts. Danach habe ich die beiden geXORed. Es ergeben sich relativ wenige Kollosionen, aber es ist relativ langsam. Insgesamt ist es aber leider beim Erhalten einer Situation mittels des Hashs immer noch schneller als dein Vorschlag, da es dort wohl zu viele Kollosionen gibt. Es findet also viel zu wenige Situationen in der Hashtabelle und die Situationen (bei einer AI) müssen neu berechnet werden.
 
0x1FFFFFFF wird von meiner gcc/g++ Version gar nicht akzeptiert ;). Bis zur akzeptierten Größe wird aber der gleiche Code generiert (wobei beide Arrays in eine Section kommen). D.h es wäre schon relevant zu wissen, was der VC genau ausspuckt - und ob das Problem nur im Debug Modus auftritt.
Wenn ich Dich richtig verstehe, verwendest Du beide Arrays nebeneinander? Eventuell wird durch die Initialisierung/Zugriff des einen Arrays das andere aus dem Ram in den virtuellen Speicher verdrängt und beim Zugriff auf dieses Array bekommt man die Lade-Verzögerung zu spüren (0x1FFFFFFF*8 ist schon eine ganze Menge Speicher).
 
Du hast recht, ich hab war falsches geschrieben, es ist ein F zuviel also 0x1FFFFFF wäre es eigentlich. Und nein, ich mache es nicht parallel. Ich habe es hintereinander getestet. Das Problem ist, dass der Code ziemlich lange ist und es geht nur sehr schlecht die wichtigen Zeilen daraus zu posten, da das immer noch viel zu viel wäre.
Ich habs im release-mode compiliert ohne Debug Infos in der exe Datei
 
Hab hier leider keinen VC zum rumexperementieren. Falls Du magst, kannst Du gerne ein minimalistisches Beispiel erstellen (eine Main, nur Array/Struct Erstellung, Dummydaten rein und Zugriff darauf) und den Assemlyoutput (Option sollte /FA sein) oder Exe hier anhängen.
Ansonsten - falls wirklich für beide Verfahren derselbe Code generiert wird, wäre es interessant zu Wissen wie die Arrays und die Einträge dazu erstellt werden.
Vorstellbar wäre, dass bei einem Struct-Zu Array das große Array einfach nur Pointer auf die einzelnen Structs enthält (und dadurch der Zugriff natürlich deutlich langsammer ist), während bei Array-Zu-Array (eventuell durch Optimierung) der Compiler die Einträge mit hineinnimmt - das ist dann deutlich schneller. Ansonsten gilt natürlich: je einfacher die(Code) Struktur, desto besser kann der Compiler optimieren.
 
Hallo,
Original von jmc
Bis jetzt habe ich für alle 128 bit zu Begin einmal eine Zufallszahl(64 bit) erstellen lassen.
Zum Vergrößern anklicken....
Bitte?
Eine Hashfunktion sollte für die selbe Eingabe auch die selbe Ausgabe besitzen, mit Zufallszahlen wird soetwas schwierig.

Wenn es nicht gefordert ist, selbe Eingabe selbe Ausgabe, ist das kinderleicht, einfach nur eine Zufallszahl erzeugen und zurückgeben.


Ansonsten evt. folgendes Testen:
part1, part2... usw. sind die 32 Bit Wörter die du hast.

val1 = ((part1 * 1103515245) + 12345) & 0x7fffffff;
val2 = ((part2 * 1103515245) + 12345) & 0x7fffffff;
...
hash = val1 ^ val2 ^ ...;


Dies ist ein linearer Kongruenzgenerator, der auch in z.B. GNU C Library genutzt wird um Zufallszahlen zu erzeugen.

Dieser sollte eigentlich relativ wenige Kollisionen verursachen und hoffentlich recht schnell sein.

Ansonsten wenn das zulange dauert, evt. mal:
part1 XOR (part2 <<< 3) XOR (part3 <<< 13) XOR (part4 <<< 17)

Wobei <<< für Linksrotate steht.

Dies ergibt dann:
Code: 
00000000001111110011111100111111 64 Bit Wort1
11111001111110011111100111111001  (<<< 3)
11100111111001111110000000000111 (<<< 13)  64 Bit Wort2
01111110011111100111111001111110 (<<< 17)

Hier hängt dann jedes Ausgabebit (bis auf eins) von mindestens zwei variablen Eingaben ab. Sofern die Eingaben relativ gut verteilt sind, sollte das einen ganz guten Hashcode ergeben.
 
Danke, ich werde es einmal ausprobieren @Elderan. Die Ausgabe ist übrigens immer dieselbe, denn, was ich vieleicht nicht klar beschrieben habe, die Zufallszahlen werden zu Beginn einmal erzeugt und nachher für alle zu erstellenden Hashs beibehalten.
Hat es irgendeinen Grund, dass du auf 1103515245 kommst oder hast du das einfach frei gewählt? Auch bei 12345?


Auch das, was du geschrieben hast, CDW, werde ich heute Nachmittag noch einmal ausprobieren.
 
Hallo,
naja Konstanten bringen relativ wenig bei Hashfunktionen.

Die Zahlen 1103515245 und 12345 entstammen der GNU C Library. Für lineare Kongruenzgeneratoren muss die Zahlen nach bestimmten Kriterien wählen, um eine optimale Periodenlänge zu erhalten. Bei der einmaligen Generiung von Zahlen sollte es aber relativ egal sein.

Ansonsten gibts hier mehr zum Thema: Linearer Kongruenzgenerator

Diese linearen Kongruenzgeneratoren sind relativ verbreitet, in Java findet man es z.B. oder hier sind ein paar weitere mögliche Parameter: Linear congruential generator
 
Danke für den Link und noch eine Frage dazu. Warum nimmst du nur die ersten 31 bits und nicht 32 (mit 0x7fffffff)?
 
Hallo,
naja das ist, wie gesagt, nur der Code aus der GNU C Lib., das man 0x7fffffff nutzt hängt mit dem signed/unsigned zusammen.
Würde man alle 32 Bit nutzen, also ohne "&0x7fffffff", dann würden auch negative Zufallszahlen zurückgegeben werden, da ja das höchste Bit, also 0x800000, gesetzt sein könnte.

Da aber rand() eine positive Zahl zurückgeben soll, nutzt man eben dieses &0x7fffffff. Dies ist die schnellste und schönste Variante, um immer positive Ergebnisse zu erhalten.

Es kommt nun darauf an, was du brauchst.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben