Hash im Skalaren Kontext 3/8 und so (gelöst) (Allgemeines zu Perl) - Perl-Community.de

Start · Board · Anwendungen/Programme/Skripte in Perl · Allgemeines zu Perl

2025-01-03 08:24:34
Europe/Berlin
Einloggen (Registrieren)
- Einstellungen
- Statistics
Jemand zu Hause?
0 Benutzer online

[thread]17677[/thread]

submit to reddit

Hash im Skalaren Kontext 3/8 und so [gelöst]

[gelöst]

Tags: perl5 Ähnliche Threads

Leser: 19

Articles: hide open all | hide show old branches

+16 replies
rosti

2012-08-16 18:32

User since
2011-03-19
3498 Artikel
BenutzerIn

Jow, soweit klar, die 3 steht für die Anzahl der Keys. So kriege ich 7/8, wenn der Hash 7 key/value Paare hat. Ab dem 8. Key heißts dann 8/16 und ab dem 12. Key 12/32.

Der Nenner, hat der irgendeine Bedeutung woraus sich Kapital gewinnen lässt?

--Rosti
- +3 replies
- Raubtier
  
  2012-08-16 18:51
  
  User since
  2012-05-04
  1076 Artikel
  BenutzerIn
  
  Das bedeutet, wie viele Buckets es gibt. Ich dachte, die Zahl davor heißt, wie viele Buckets benutzt sind, aber weiß gerade nicht, in welchem perldoc das steht...
  
  Auf jeden Fall kannst du, wenn du weißt, dass dein Hash groß werden wird, schon von Anfang an mehr Buckets erzeugen mit keys %h = $anzahlBuckets, wobei das immer auf eine Zweierpotenz aufrundet.
  
  Du findest das auf jeden Fall in den Dateien hv.c und hv.h im Source.
  - +2 replies
  - betterworld
    
    2012-08-16 18:56
    
    User since
    2003-08-21
    2614 Artikel
    ModeratorIn
    
    Das mit den Buckets ist was für Fans von Premature Optimization :)
    Lieblingsmodule: IPC::System::Simple, Path::Class
    - Raubtier
      
      2012-08-16 19:07
      
      User since
      2012-05-04
      1076 Artikel
      BenutzerIn
      
      Naja, da Hashes immer und überall in Perl verwendet werden, sollte der Hashing-Algorithmus schon gut sein, von daher ist das jetzt eher kein Fall von premature Optimisation - denn sonst könntest du ja auch vorschlagen, immer beim gcc sämtliche Optimierungen abzuschalten.
      
      Richtig ist allerdings, dass man sich normalerweise im Perl-Programm selbst nicht darum kümmern muss. Das ist aber nur so, weil das Hashing eben optimiert wurde! Und dazu sind diese Angaben, die da rauskommen, schon sinnvoll.
      
      Vor laaanger Zeit hatte ich mir mal in Pascal ein Perl-Hash zum Speichern von Strings gewünscht und hatte daher fast 1:1 den Code von Perl (5.6) übersetzt, hat mir dann auch in Pascal gute Dienste geleistet :-)
- +12 replies
- pq
  
  2012-08-16 19:02
  User since
  2003-08-04
  12208 Artikel
  Admin1
  die erste zahl steht *nicht* für die anzahl der keys.
  kannst du ja selbst ausprobieren.
  
  Code: (dl )
  
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
  
  perl -wE'for (1..20) { $hash{$_}++; say scalar %hash; }' 1/8 2/8 3/8 3/8 4/8 5/8 6/8 7/16 8/16 9/16 10/16 10/16 10/16 11/16 11/16 14/32 14/32 15/32 15/32 15/32
  
  perldoc perldata:
  
  Quote
  If you evaluate a hash in scalar context, it returns false if the hash is empty. If there are any
  key/value pairs, it returns true; more precisely, the value returned is a string consisting of the
  number of used buckets and the number of allocated buckets, separated by a slash.
  
  Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live. -- Damian Conway in "Perl Best Practices"
  lesen: Wie frage ich & perlintro brian's Leitfaden für jedes Perl-Problem
  - +11 replies
  - rosti
    
    2012-08-16 19:56
    
    User since
    2011-03-19
    3498 Artikel
    BenutzerIn
    
    Alles im Eimer ;)
    
    Danke Euch!!!!
    - +10 replies
    - Muffi
      
      2012-08-16 23:14
      
      User since
      2012-07-18
      1465 Artikel
      BenutzerIn
      
      Zusammenfassend kann man wohl sagen, dass man mit dem manuellen Setzen der Buckets ein bisschen Performance rausholen kann, wenn man weiss welche Zahlen man am besten setzt.
      Für was man die Zahlen allerdings auslesen können muss ist mir bis heute noch nicht so ganz klar.
      1 + 1 = 10
      - betterworld
        
        2012-08-16 23:59
        
        User since
        2003-08-21
        2614 Artikel
        ModeratorIn
        
        2012-08-16T21:14:43 Muffi
        wenn man weiss welche Zahlen man am besten setzt.
        
        Das kann man höchstens experimentell herausfinden. Dann performt es etwas besser, aber mit der nächsten Perlversion und bei einer anderen Mondphase stellt man dann fest, dass ganz andere Werte optimal sind.
        
        Ich würde gerne ein Beispiel sehen, wo man mit solchen Tricks tatsächlich für den Anwender spürbare Performanceverbesserungen rausholen kann :)
        Lieblingsmodule: IPC::System::Simple, Path::Class
      - +8 replies
      - Raubtier
        
        2012-08-17 01:58
        
        User since
        2012-05-04
        1076 Artikel
        BenutzerIn
        
        2012-08-16T21:14:43 Muffi
        Zusammenfassend kann man wohl sagen, dass man mit dem manuellen Setzen der Buckets ein bisschen Performance rausholen kann, wenn man weiss welche Zahlen man am besten setzt.
        
        Na, möglichst große natürlich!
        
        Aber das wird nur bei richtig großen Hashes was bringen. Denn jedes Mal, wenn die Größe geändert wird, wird ja die Speichergröße geändert und alle bisherigen Einträge müssen dann ggf. in den neuen Bereich verschoben werden. Das ist relativ teuer, deswegen wird auch immer gleich die Speichergröße verdoppelt, damit das selten passiert. Wenn ich aber sowieso weiß, dass mein Hash 1 Mio. Einträge haben wird, kann ich das Perl eben gleich mitteilen und somit das realloc und mehrmalige Umsortieren sparen. Wenn ich nun einen Algorithmus habe, der sehr oft solche großen Hashes aufbaut, dann könnte es spürbar sein. Mir fällt nur gerade kein konkretes Beispiel ein, wo man sowas braucht :-)
        
        Quote
        Für was man die Zahlen allerdings auslesen können muss ist mir bis heute noch nicht so ganz klar.
        
        Nur wenn man schauen will, wie gut das Hashing funktioniert. Wenn die Anzahl der Keys == die Zahl vor den Slash, dann war das Hashing optimal. Wenn du nie riesige Zahl von Keys hast aber vor dem Slash eine 1 steht, dann ist das der schlimmste Fall.
        
        Muffi
        
        2012-08-17 07:03
        
        User since
        2012-07-18
        1465 Artikel
        BenutzerIn
        
        Möglichst gross kann schon eine Lösung sein, muss aber nicht. Also z.b. bei den Mio. Einträgen, wie viele Buckets setz ich denn nun.
        
        Und beim Auslesen: Gut, ich hab dann die Infos, aber ich wüsst jetzt keinen Fall wo mir die Info ausser "Aha" wirklich was nützt.
        1 + 1 = 10
        
        FIFO
        
        2012-08-17 07:19
        
        User since
        2005-06-01
        469 Artikel
        BenutzerIn
        
        Unabhängig von den Bucket-Details kann man auch einfach eine skalare Zuweisung an die keys machen, keys(%hash) = 1000000;, dies kann tatsächlich einen ordentlichen Gewinn bringen, dieser ist aber nicht einfach vorhersagbar.
        
        edit mein gott, wie peinlich ist das denn? Das kommt davon, wenn man unten anfängt zu lesen. Merke: Nicht an Migränetagen posten ...
        Last edited: 2012-08-17 20:32:12 +0200 (CEST)
        Everyone knows that debugging is twice as hard as writing a program in the first place. So if you're as clever as you can be when you write it, how will you ever debug it? -- Brian Kernighan: "The Elements of Programming Style"
        
        Muffi
        
        2012-08-17 10:56
        
        User since
        2012-07-18
        1465 Artikel
        BenutzerIn
        
        2012-08-16T23:58:33 Raubtier
        Wenn die Anzahl der Keys == die Zahl vor den Slash, dann war das Hashing optimal.
        
        Gut, man kann Duseltreffer entdecken... aber was bringt das.
        Vielleicht, wenn man vorhat länger mit dem Hash zu arbeiten so oft neu aufbaun, bis der Fall eintritt ;)
        1 + 1 = 10
        
        +4 replies
        
        Raubtier
        
        2012-08-17 11:51
        
        User since
        2012-05-04
        1076 Artikel
        BenutzerIn
        
        Ich sollte nicht behaupten, etwas sei schneller ohne einen Benchmark gemacht zu haben! Erstaunlicherweise ist nämlich die Version ohne direkte Zuweisung an %keys schneller!
        
        Code: (dl )
        
        1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
        
        use Benchmark qw(:all); my ($resultPre, $resultNormal); timethese(-100, { preAssign => sub { my %h; keys %h = 1e8; $h{$_} = $_ for 1..1e8; $resultPre = scalar %h unless $resultPre; }, normal => sub { my %h; $h{$_} = $_ for 1..1e8; $resultNormal = scalar %h unless $resultNormal; }, }); print "Pre: $resultPre\n"; print "Normal: $resultNormal\n";
        
        Ergebnis für 100 mio Keys ist:
        
        Code: (dl )
        
        1 2 3 4 5 6 7
        
        Benchmark: running normal, preAssign for at least 100 CPU seconds... normal: 210 wallclock secs (209.64 usr + 0.01 sys = 209.65 CPU) @ 0.00/s (n=1) (warning: too few iterations for a reliable count) preAssign: 276 wallclock secs (275.12 usr + 0.32 sys = 275.44 CPU) @ 0.00/s (n=1) (warning: too few iterations for a reliable count) Pre: 70452330/134217728 Normal: 70452330/134217728
        
        Gut, nur ein Durchlauf. Aber trotzdem ein deutlicher Unterschied. Oder habe ich da irgendwas falsch gemacht?
        
        Oder muss man vielleicht noch bedenken, dass ein kleinerer Hash komplett im Prozessor-Cache gehalten werden kann und es daher schneller sein kann, diesen mehrmals in der Größe zu ändern?
        
        Wenn ich nur 40 statt 1e8 Keys nehme:
        
        Code: (dl )
        
        1 2 3 4 5
        
        Benchmark: running normal, preAssign for at least 100 CPU seconds... normal: 106 wallclock secs (104.92 usr + 0.01 sys = 104.93 CPU) @ 67924.06/s (n=7127272) preAssign: 104 wallclock secs (105.09 usr + 0.01 sys = 105.10 CPU) @ 50860.65/s (n=5345454) Pre: 33/64 Normal: 33/64
        
        Conclusion: es bringt nichts, daran rumzudoktoren. Das ist in Perl bereits wunderbar optimiert, sodass man selbst sich nicht mehr darum kümmern muss.
        
        (Tests mit 5.8.8 gemacht)
        
        modedit Editiert von pq: code-tags um benchmark-ausgabe, sonst unlesbar
        Last edited: 2012-08-17 12:32:20 +0200 (CEST)
        
        +3 replies
        
        Muffi
        
        2012-08-17 12:48
        
        User since
        2012-07-18
        1465 Artikel
        BenutzerIn
        
        1e8 Buckets bei 1e8 Keys ist zu wenig. Ich weiss nicht, wann Perl genau umhasht, aber so 20-30% Buckets sollten auf jeden Fall frei sein.
        
        Was hier evtl. passieren könnte ist, dass Perl relativ spät feststellt, dass die 1e8 Buckets nicht reichen und dann relativ viel neu hashen muss, während bei der Auto-variante schon viel früher das letzte mal neu gehasht wird.
        
        [EDIT]
        Hmm, ich glaub das ist doch ne schlechte Theorie...
        134217728 ist die nächste 2er-potenz zu 1e8, d.h. eigentlich sollt er nicht neu gehasht haben :-\
        
        [EDIT2]
        Bei mir ist ein kurzes perl -e mit 1e7 aber mit Bucketzuweisung schneller. Neue Theorie (bei mir kam bei 1e8 out of memory). Fängt der Rechner vielleicht bei der Zuweisung der Buckets zu swappen an?
        Last edited: 2012-08-17 13:13:04 +0200 (CEST)
        1 + 1 = 10
        
        +2 replies
        
        Raubtier
        
        2012-08-17 13:38
        
        User since
        2012-05-04
        1076 Artikel
        BenutzerIn
        
        Ich habe ja extra die Ausgabe von scalar %h mit eingebaut. In beiden Fällen sind es gleich viele Buckets.
        
        Perl vergrößert den Hash, sodass nie mehr Keys als Buckets da sind. In beiden Fällen ist der Hash am Ende ja gleichgroß, auch wenn die Reihenfolge in den Buckets, wo Kollisionen aufgetreten sind, natürlich unterschiedlich sein kann. Daher müsste eigentlich am Ende der Speicherverbrauch beider Varianten gleich groß sein. top (jaja, ist nicht das richtige Tool zum Messen des Speicherbedarfs...) hat mir 20g als Verbrauch angezeigt, da muss nichts swappen - und wenn, dann müsste er ja auch schon vorher geswappt haben, vermute ich.
        
        Muffi
        
        2012-08-17 13:43
        
        User since
        2012-07-18
        1465 Artikel
        BenutzerIn
        
        Ja, meine erste Theorie hab ich auch schon verworfen.
        
        Quote
        da muss nichts swappen - und wenn, dann müsste er ja auch schon vorher geswappt haben, vermute ich
        
        Naja, bei der Bucketzuweisung wird ja der Speicher sofort reserviert, d.h. wenn der Speicher nicht ausreicht würd er ja ab dem Zeitpunkt bei Hashzugriffen swappen.
        Im Auto-modus würd er so lange schnell mit dem Hash arbeiten können, bis er durch eine erweiterung irgendwann grösser als der Speicher wird.
        Oder denk ich grad falsch.
        1 + 1 = 10

View all threads created 2012-08-16 18:32.