I'm finding when the hash gets to be more than 27,000, I get the out-of-memory error.

hum, that's really not that big. Especially if it just hold URLs. You should see the following surpass that number in no time.

my $i;
my %urls;
for (;;)
   ++$url{"http://www.perlmonks.org/?node_id=".++$i};
   print("$i\n") if $i % 1000 == 0;
}
[download]

Tie a shoelace around a shoebox and wave a magic wand over it.

Actually, that's quite an apt description!

tie is a form of magic (yes, that's really what it's called) that ties methods to a variable (shoebox) such that those functions are called in response to the different actions taken on that variable. For example, $tied = $x; calls the tied variable's STORE method.

It's easier to understand if you look at it from the other end. tie allows a module to use a Perl variable as its interface. Instead of $obj->store($x), it allows $obj = $x;.

If instead of putting the urls in a hash, you use their md5 digests Digest::MD5 (in binary) as keys, then you will save a subtantial amount of space. 1 million binary MD5s stored as hash keys uses about 36 MB:

use Digest::MD5 qw[ md5 ];;

undef $h{ md5( $_ ) } for 1 .. 1e6;;

print total_size \%h;;
35665714
[download]

Note also the use of undef $hash{ ... }. This autovivifies the key without allocating any storage for a value--thereby saving space. Whilst some will view this as an unconscionable "trick", for this type of lookup application that is pushing your memory limits, the savings are worth having.

Using this method you should be able to index close to 60 million urls on a typical 2GB machine without problems. And far more quickly than any tie or DB mechanism that requires disk accesses.

My guess would be that you are leaking memory because you are not destroying your HTML::Treebuilder objects properly. From the docs:

4. and finally, when you're done with the tree, call $tree->delete() to erase the contents of the tree from memory. This kind of thing usually isn't necessary with most Perl objects, but it's necessary for TreeBuilder objects. See HTML::Element for a more verbose explanation of why this is the case.

A simple undef() is not enough.

Hi jau, yes! that was exactly the problem. Nice to see it was such a simple solution, and a real "duh" moment for me. Thanks so much. Scott

Some other strategies would be to use a Google search to get the number of pages narrowed down and then search further on those pages. Its not clear to me what you are doing and why you have to visit every single page on this large site. A more optimized strategy might be possible if you could present some more application info?

A hash with 27,000 keys of URL's doesn't sound large enough by itself to run out of memory, but sounds like there are multiple other large structures. A DB is one possible answer if you really do need to collect this massive amount of information for this site. The Perl DBI is very good and plays very well with MySQL or SQLlite.

Hi all, thank you for your interesting replies. To answer a couple of questions, this is actually for an internal site (actually several large collections of information, Eclipse instances) belonging to my employer. We're trying to catalog every page in every Eclipse instance, in part so that we can see which pages have zero hits. The left nav has a TOC tree that the script can traverse, but not all pages are in the TOC, so the script opens each page and scans for any hrefs not in the TOC, follows them down recursively, and adds them to the list. It's interesting to hear that 27,000 is not really that big, so I'm suspecting something else is going on.

In answer to the question why don't I use a database, I'm actually saving the URLs (and some other data from each page) to a CSV file, so other than the URL itself not much is getting written to memory. I'm not sure how a db would solve that -- I'd still need the hash to check for already-cataloged URLs, or else I'd have to query the db for each one.

Anyway I'll look through the interesting suggestions and see if I can figure out something that works for me. Thanks.

Scott