std::list.sort() blocks on very large lists (>12GB) GCC 4.0.1 Mac OS X 64-bit

std::list.sort() blocks on very large lists (>12GB) GCC 4.0.1 Mac OS X 64-bit

[jpitt]

Hi-

I'm experiencing a weird problem that makes me wonder if there is a  
problem with the std::list.sort member function when used on very  
large lists. I have a very large list (~20GB) that is made up of a  
class (382bytes each) of DNA sequence data. When the list is on the  
order of 12GB it sorts fine, but if it gets up into the 17GB range  
when I call sort() it seems to block. The list has already been built  
so I don't think it's a malloc issue. I also don't think it's a  
complexity problem because the 12GB list sorts fine (it takes a minute  
or so), so I'm wondering if the std sort method doesn't properly  
handle the excess memory available in 64bit mode? Has anyone  
experienced this?

-thanks
jason

=====================================================================
Jason Pitt PhD                                        jpitt@fhcrc.org
Ferre-D'Amare Lab                                        206.667.3603
Howard Hughes Medical Institute
University of Washington
Fred Hutchinson Cancer Research Center
1100 Fairview Ave N A3-015 Seattle WA 98109
=====================================================================

Re: std::list.sort() blocks on very large lists (>12GB) GCC 4.0.1 Mac OS X 64-bit

[Ian Lance Taylor]

jpitt@fhcrc.org writes:

> I'm experiencing a weird problem that makes me wonder if there is a
> problem with the std::list.sort member function when used on very
> large lists. I have a very large list (~20GB) that is made up of a
> class (382bytes each) of DNA sequence data. When the list is on the
> order of 12GB it sorts fine, but if it gets up into the 17GB range
> when I call sort() it seems to block. The list has already been built
> so I don't think it's a malloc issue. I also don't think it's a
> complexity problem because the 12GB list sorts fine (it takes a minute
> or so), so I'm wondering if the std sort method doesn't properly
> handle the excess memory available in 64bit mode? Has anyone
> experienced this?

Without more information, my first guess would be that you are exceeding
the available working set on your machine, and thrashing.
std::list.sort is written to assume that the entire list can be stored
in the working set.  Sorting an amount of data that is significantly
larger than available RAM generally requires different techniques for
efficiency.  For example, manually splice() the list into lists which
are small enough to sort efficiently, and then merge() the results
together.

Ian

Re: std::list.sort() blocks on very large lists (>12GB) GCC 4.0.1 Mac OS X 64-bit

[Nicholas Sherlock]

jpitt@fhcrc.org wrote:
> I'm experiencing a weird problem that makes me wonder if there is a 
> problem with the std::list.sort member function when used on very large 
> lists. I have a very large list (~20GB) that is made up of a class 
> (382bytes each) of DNA sequence data. When the list is on the order of 
> 12GB it sorts fine, but if it gets up into the 17GB range when I call 
> sort() it seems to block. The list has already been built so I don't 
> think it's a malloc issue. I also don't think it's a complexity problem 
> because the 12GB list sorts fine (it takes a minute or so), so I'm 
> wondering if the std sort method doesn't properly handle the excess 
> memory available in 64bit mode? Has anyone experienced this?

Double check the comparison function you're using. If it doesn't 
properly conform to the specification, sort() can get into an infinite 
loop. Here's some info on the matter:

http://blogs.msdn.com/oldnewthing/archive/2009/05/08/9595334.aspx
http://blogs.msdn.com/oldnewthing/archive/2003/10/23/55408.aspx

Cheers,
Nicholas Sherlock