[Lemon-user] "bad alloc" while populating graph

[Alpár Jüttner]

Hi,

We (Balazs, Akos and me) investigated a bit this "bad alloc" issue, and
found that it is not a bug of either STL or LEMON, but rather a strange
consequence of the address space limitations.

To provide efficient push_back() operation, the std::vector (and
therefore ListGraph) may allocate more memory than is actual size. If
the allocated memory is not enough to accommodate a new element during a
push_back() operation, it allocates a two times larger block of memory
and copies the old elements there. The problem is that if you perform a
lot of push_back() on a single vector,  the old memory blocks can
(almost) never be reused, because the new block is larger then the size
of the previous allocations.

In a 32bit architecture, an algorithm can use at most 3GB (3072MB) for
the user code and data. lemon::ListGraph uses 24 bytes (6 integers) for
each edges. Now, in your case, when you try to add the 33554433th edge,
it would allocate a new memory block of size 33554432*24 byte = 768MB.
The old allocations together take the same amount of memory. That is why
we reach the address space limitation (2*768MG=3GB).

Tricks that may help:
      * If you don't need to remove edges, then use SmartGraph instead.
        It uses only 16 bytes per edges. Because the std::vector doubles
        its size when it is full, it means that you will be able to use
        two times more edges (up to 67108864).
      * If you know the number of the edges in advance (and if 24*#edges
        < 3GB) use the reserveEdge() member function of ListGraph. In
        this way, not only can you avoid the superfluous memory
        allocation, but the graph build-up will also be faster.

Best regards,
Alpar


On Thu, 2007-06-07 at 16:30 +0200, andrea marino wrote:
> Hi,
> I tried your source code and I verified what you say.
> So while I'm waiting for the workaround, I will search a 64 bit
> platform box.
> Thanks
> Andrea Marino