why won't the hash go away?

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

Comment on why won't the hash go away? Select or Download Code

Replies are listed 'Best First'.
Re: why won't the hash go away? by davidrw (Prior) on Jan 12, 2008 at 22:39 UTC
See "How can I free an array or hash so my program shrinks?" in perlfaq3 ... Just clearing/undef'ing a variable won't release the memory back to the system (though it is then available to the program again).	[reply]
Re^2: why won't the hash go away? by WoodyWeaver (Monk) on Jan 12, 2008 at 23:36 UTC
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]
Re^3: why won't the hash go away? by davidrw (Prior) on Jan 12, 2008 at 23:49 UTC
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^4: why won't the hash go away? by kyle (Abbot) on Jan 13, 2008 at 02:35 UTC
Re^5: why won't the hash go away? by WoodyWeaver (Monk) on Jan 14, 2008 at 22:21 UTC
Some notes below your chosen depth have not been shown here
Managing re-exec (was: Re^4: why won't the hash go away? by WoodyWeaver (Monk) on Jan 13, 2008 at 00:29 UTC
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]
Re^2: why won't the hash go away? by WoodyWeaver (Monk) on Jan 13, 2008 at 00:17 UTC
...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]
Re^3: why won't the hash go away? by snoopy (Curate) on Jan 13, 2008 at 01:48 UTC
>> 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]


"be consistent"
	PerlMonks