WoodyWeaver has asked for the wisdom of the Perl Monks concerning the following question:

I have a program that plays solitaire.

There is a humungous data structure %positions. It looks something like this: 


do {
  require MIME::Base64;
  (
    MIME::Base64::decode("2qyANnIPJvTGkGfTQ8PTHtBUaKY4qm6eP8eTiC2MFzej
+iJLwnIwZayMREOmyRFgJ+3IHdV1fja3Y4lq3smfArLVhRVYYzbV1ZOVTw9aelSthia4Bq
+2pAw5Ws/StQvBNao1fpirK8Zq9Q4iDDuQY="),
    {
      desc   => "move 4C from col 4 to 0 turning a card (88)",
      metric => 5295,
      parent => MIME::Base64::decode("2qyANnIPJvTGkGfTQ8PTHtBUaKY4qm6e
+P8eTiC2MFzejiJLwnIwZayMREOmytBL25Q7qur4aW7HFtW5lz4BZa8OKrDCaa2vCyqeGR
+daelSthia4Bq2pAw5Ws/StQvBNao1fpirK8Zq9Q4iDDuQY="),
    },
    MIME::Base64::decode("2qyANnIPJvTGkGfTQ8PTHtBUaKY4qm6eP8eTiC2MFzej
+iJLwnIwZayMREOmytBL25Q7qur4aW7HFtW5lz4BZa4NnRVYYzbU1YeVTwyLr6MqVsKwBq
+2pAw5Ws/StQvBNao1fpirK8Zq9Q4iDDuQY="),
    {
      desc   => "move 9H from col 5 to 3 turning a card (92)",
      metric => 5291,
      parent => MIME::Base64::decode("2qyANnIPJvTGkGfTQ8PTHtBUaKY4qm6e
+P8eTiC2MFzejiJLwnIwZayMREOmytBL25Q7qur4aW7HFtW5lz4BZa8OKrDCaa2vCyqeGR
+daelSthia4Bq2pAw5Ws/StQvBNao1fpirK8Zq9Q4iDDuQY="),
    },
...
    MIME::Base64::decode("2qyANnIPJvTGkGfTQ8PTHtBUaKY4qm6eP8eTiC2MFzej
+iJLLknQl7Msd1HUdshpbscW1DrGyZ8CstQG5IiuM5tqa0F751LDI2hNbuRKW6BrAXFUDG
+q5k7ZetQPFOaI3OrdIVZXnNhq9Q4iDDuQY="),
    {
      desc   => "deal cards (-208)",
      metric => 5591,
      parent => MIME::Base64::decode("2qyANnIPJvTGkGfTQ8PTHtBUaKY4qm6e
+P8eTiC2MFzejiJLwnIwZayMREOmytBL25Q7qur4aW7HFtW5lz4BZa8OKrDCaa2vCyqeGR
+daelSthia4Bq2pAw5Ws/StQvBNao1fpirK8Zq9Q4iDDuQY="),
    },
    MIME::Base64::decode("2qyANnIPJvTGkGfTQ8PTHtBUaKY4qm6eP8eTiC2MFzej
+iJLwnIwZayMREOmytBL25Q7qur4aW7HFtW5lz4BZa8OKrDCaa2vCyqeGRdaelSthia4Bq
+2pAw5Ws/StQvBNao1fpirK8Zq9Q4iDDuQY="),
    { desc => "initial deal", metric => 5383 },
  );
}

[download]
After a couple of hours, the memory used by the perl app is several gigs in size, and I assume its due to this guy. Anyway, after running for several hours, my program gets tired of playing that hand and wants to play another. It goes to a re-initialization script that has a segment like this: 
  $|=1;
  open F, ">>state.txt";
  my $position = Spider::unmash($best);
  movestack($position, $best, ">lastpos".$$.".txt", 1);
  print F scalar localtime(time), "Moved stack\n";
  close F;
  open F, ">>state2.txt";

  %positions = ();
  print F scalar localtime(time), "Reset positions\n";
  close F;

[download]
The file state.txt gets updated appropriately, while state2.txt doesn't -- it just hangs. On the other hand, when %positions isn't that humungous -- say if I sigint after only ten minutes, or it finds a solution -- then the hash gets cleared and all is well.

I thought about breaking the hash into 32nds or something, and doing a pre-hash before looking up the hash key, to keep %positions fairly small, but that seems like such a crock. (And frankly, I don't care that much. If while playing solitaire my computer zones out, well, no harm done.)

Is there a better way than %positions = () to clear a hash?

--woody

Replies are listed 'Best First'.
Re: why won't the hash go away?
by davidrw (Prior) on Jan 12, 2008 at 22:39 UTC
[reply]
      Ok, fair enough. Its disappointing that I can't hand it back to the system, but I don't really need that (although it would be nice, of course.)

      What I want to do is to shuffle the cards and start over. I don't really mind keeping the memory around, really. I just want to make the hash list go away so I can start a new one.

      The program runs for a couple of hours, then gives up and decides to go run this re-init routine, then spends MORE THAN TEN HOURS just trying to execute %positions = ().

      I guess what you are telling me is that once it starts to thrash, I'm toast, and that page management or whatever just isn't going to help me. So even my approach to break the hash table into smaller pieces isn't going to help.

      Pity. Sounds like the solution will be to follow the re-exec approach; don't try to re-init, just die and restart yourself. Hm. Not sure I like that -- granted, I'm anthromophising shamelessly, but it then boils down to "play solitaire and win, or die"...

      --woody

[reply]
        You could set it up so that each shuffle is done after a fork, and just wait for that one to end/die before going to the next. Something like (untested; off top of head & docs, but i think is the general outline): 
        my @deck = create_deck();
while(1){  # or whatever; loop over specific deals, or do just N deals
+, etc.
  my $pid = fork;
  die unless defined $pid;
  if($pid){  # parent
    wait;
    # report on $? if desired
    next;
  }
  do_heavy_lifting(\@deck);
  exit;  # w/an error code based on result if desired
}

sub do_heavy_lifting {
  ...
  my %positions = ....;
  ...
}

        [download]
        So the %positions isn't created/populated (made huge) until in the fork'd process, so when that exits, the memory will get freed to the system, but your program is still going from the parent process.
[reply]
[d/l]
[select]
Re: why won't the hash go away?
by snoopy (Curate) on Jan 12, 2008 at 23:37 UTC
    You may want to consider mapping your game states to persistant storage using DBM::Deep(or similar).

    Not only do you free up memory; you get free game persistance. Saving and switching between games becomes near instantaneous.

[reply]
      ...but oh, the cost! This is a search algorithm, and the "trick" is to avoid having to search a node twice; the underlying game is "Spider", and there is a lot of repetitions between positions. So the hash lookup gets done *a lot*. By making it a tie, now not only do I have to do something fancy to invoke the tie, but I'm going to be bogged down my disk access.

      Of course, the thrashing means I'm bogged down by disk access as well, so...

[reply]
        >> but I'm going to be bogged down my disk access:

        Hmm, I'd be interested to see how DBM::Deep plays with open's mmap option (as of yet untested/unbenchmarked): 

        open(DATA, '<+:mmap', 'game.dbm')
my $db = DBM::Deep->new( { fh => \*DATA } );

        [download]
        Update: Have benchmarked. No appreciable benefits with the above :-|

        Now looking at the storage => ... option.

[reply]
[d/l]

Back to Seekers of Perl Wisdom