Oh, and just to add info from another language
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
using namespace std;
using namespace boost;
typedef adjacency_list<vecS, vecS, directedS> Graph;
int main()
{
const int VERTEXES = 250000;
const int EDGES = 1000;
Graph g(VERTEXES);
cout << " Boost Graph Library - Inserting edges" << endl;
for (int i = 0; i < VERTEXES; ++i)
for (int j = 1; j < EDGES; ++j)
add_edge(i, j, g);
}
$ g++ boost-example.cpp -o boost-example
$ time ./boost-example
Boost Graph Library - Inserting edges
Killed
real 2m10.779s
user 0m47.279s
sys 0m2.548s
-------------------------------------------------------
I don't know if "Killed" is the same as a segfault.
Best wishes,
Arthur
2013/2/3 Arthur Maciel <[email protected]>
> Jim, that's great! Thank you so much!
>
> I've read that facebook reached out billions of users. As I'm testing
> graph implementations to create a graph database, do you believe this code
> could handle billions nodes or I would need a lot more RAM to run it?
>
> I'm not experienced in programming so I don't know if there is a way to
> handle this problem, like share this graph data structures along many
> machines, serializing it to disk and handle in memory only a part of it,
> etc. Do you know any applicable strategy to make it work properly?
>
> Thanks again!
> Arthur
> Em 03/02/2013 02:54, "Jim Ursetto" <[email protected]> escreveu:
>
> OK, I patched the core and the program runs to completion. Patch
>> forthcoming.
>>
>> $ ./list-partials -:d -:hm16G
>> [debug] application startup...
>> [debug] heap resized to 1048576 bytes
>> [debug] stack bottom is 0x7fff6f80f4b0.
>> [debug] entering toplevel toplevel...
>> [debug] entering toplevel library_toplevel...
>> [debug] entering toplevel build_2dversion_toplevel...
>> [debug] entering toplevel eval_toplevel...
>> [debug] resizing mutation-stack from 8k to 16k ...
>> [debug] entering toplevel expand_toplevel...
>> [debug] entering toplevel modules_toplevel...
>> [debug] resizing mutation-stack from 16k to 32k ...
>> [debug] entering toplevel chicken_2dsyntax_toplevel...
>> [debug] entering toplevel srfi_2d69_toplevel...
>>
>> Hash-tables - Inserting edges
>> [debug] resizing heap dynamically from 1024k to 2048k ...
>> [debug] resizing heap dynamically from 2048k to 4096k ...
>> [debug] resizing heap dynamically from 4096k to 8192k ...
>> [debug] resizing heap dynamically from 8192k to 16384k ...
>> [debug] resizing heap dynamically from 16384k to 32768k ...
>> [debug] resizing heap dynamically from 32768k to 65536k ...
>> [debug] resizing heap dynamically from 65536k to 131072k ...
>> [debug] resizing heap dynamically from 131072k to 262144k ...
>> 5000 nodes inserted
>> [debug] resizing heap dynamically from 262144k to 524288k ...
>> 10000 nodes inserted
>> [debug] resizing heap dynamically from 524288k to 1048576k ...
>> 15000 nodes inserted
>> 20000 nodes inserted
>> [debug] resizing heap dynamically from 1048576k to 2097152k ...
>> 25000 nodes inserted
>> 30000 nodes inserted
>> 35000 nodes inserted
>> 40000 nodes inserted
>> [debug] resizing heap dynamically from 2097152k to 4194304k ...
>> 45000 nodes inserted
>> 50000 nodes inserted
>> 55000 nodes inserted
>> 60000 nodes inserted
>> 65000 nodes inserted
>> 70000 nodes inserted
>> 75000 nodes inserted
>> 80000 nodes inserted
>> 85000 nodes inserted
>> [debug] resizing heap dynamically from 4194304k to 8388608k ...
>> 90000 nodes inserted
>> 95000 nodes inserted
>> 100000 nodes inserted
>> 105000 nodes inserted
>> 110000 nodes inserted
>> 115000 nodes inserted
>> 120000 nodes inserted
>> 125000 nodes inserted
>> 130000 nodes inserted
>> 135000 nodes inserted
>> 140000 nodes inserted
>> 145000 nodes inserted
>> 150000 nodes inserted
>> 155000 nodes inserted
>> 160000 nodes inserted
>> 165000 nodes inserted
>> 170000 nodes inserted
>> 175000 nodes inserted
>> [debug] resizing heap dynamically from 8388608k to 16777216k ...
>> 180000 nodes inserted
>> 185000 nodes inserted
>> 190000 nodes inserted
>> 195000 nodes inserted
>> 200000 nodes inserted
>> 205000 nodes inserted
>> 210000 nodes inserted
>> 215000 nodes inserted
>> 220000 nodes inserted
>> 225000 nodes inserted
>> 230000 nodes inserted
>> 235000 nodes inserted
>> 240000 nodes inserted
>> 245000 nodes inserted
>> 1042.938s CPU time, 50.714s GC time (major), 250066522 mutations,
>> 44/851838 GCs (major/minor)
>> [debug] forcing finalizers...
>> [debug] application terminated normally
>>
>>
>> On Feb 2, 2013, at 8:06 PM, Jim Ursetto wrote:
>>
>> > (bug found -- tl;dr see end of message)
>> >
>> > Figured it out: you're exceeding the default maximal heap size, which
>> is 2GB. For whatever reason, Chicken doesn't terminate reliably and with
>> an error in this situation, it just tries to continue.
>> >
>> > Simply run your program with -:d to see:
>> >
>> > $ ./list-partials -:d
>> > Hash-tables - Inserting edges
>> > [debug] resizing heap dynamically from 1024k to 2048k ...
>> > [debug] resizing heap dynamically from 2048k to 4096k ...
>> > [debug] resizing heap dynamically from 4096k to 8192k ...
>> > [debug] resizing heap dynamically from 8192k to 16384k ...
>> > [debug] resizing heap dynamically from 16384k to 32768k ...
>> > [debug] resizing heap dynamically from 32768k to 65536k ...
>> > [debug] resizing heap dynamically from 65536k to 131072k ...
>> > [debug] resizing heap dynamically from 131072k to 262144k ...
>> > 5000 nodes inserted
>> > [debug] resizing heap dynamically from 262144k to 524288k ...
>> > 10000 nodes inserted
>> > [debug] resizing heap dynamically from 524288k to 1048576k ...
>> > 15000 nodes inserted
>> > 20000 nodes inserted
>> > [debug] resizing heap dynamically from 1048576k to 2097151k ...
>> > 25000 nodes inserted
>> > 30000 nodes inserted
>> > 35000 nodes inserted
>> > 40000 nodes inserted
>> >
>> > Error: segmentation violation
>> >
>> >
>> >
>> > The easy fix to is increase the max heap size, say to 8GB:
>> >
>> > $ ./list-partials -:d -:hm8192000k
>> > [debug] application startup...
>> > [debug] heap resized to 1048576 bytes
>> > [debug] stack bottom is 0x7fff693fa4b0.
>> > [debug] entering toplevel toplevel...
>> > [debug] entering toplevel library_toplevel...
>> > [debug] entering toplevel build_2dversion_toplevel...
>> > [debug] entering toplevel eval_toplevel...
>> > [debug] resizing mutation-stack from 8k to 16k ...
>> > [debug] entering toplevel expand_toplevel...
>> > [debug] entering toplevel modules_toplevel...
>> > [debug] resizing mutation-stack from 16k to 32k ...
>> > [debug] entering toplevel chicken_2dsyntax_toplevel...
>> > [debug] entering toplevel srfi_2d69_toplevel...
>> >
>> > Hash-tables - Inserting edges
>> > [debug] resizing heap dynamically from 1024k to 2048k ...
>> > [debug] resizing heap dynamically from 2048k to 4096k ...
>> > [debug] resizing heap dynamically from 4096k to 8192k ...
>> > [debug] resizing heap dynamically from 8192k to 16384k ...
>> > [debug] resizing heap dynamically from 16384k to 32768k ...
>> > [debug] resizing heap dynamically from 32768k to 65536k ...
>> > [debug] resizing heap dynamically from 65536k to 131072k ...
>> > [debug] resizing heap dynamically from 131072k to 262144k ...
>> > 5000 nodes inserted
>> > [debug] resizing heap dynamically from 262144k to 524288k ...
>> > 10000 nodes inserted
>> > [debug] resizing heap dynamically from 524288k to 1048576k ...
>> > 15000 nodes inserted
>> > 20000 nodes inserted
>> > [debug] resizing heap dynamically from 1048576k to 2097152k ...
>> > 25000 nodes inserted
>> > 30000 nodes inserted
>> > 35000 nodes inserted
>> > 40000 nodes inserted
>> > [debug] resizing heap dynamically from 2097152k to 4194304k ...
>> > 45000 nodes inserted
>> > 50000 nodes inserted
>> > 55000 nodes inserted
>> > 60000 nodes inserted
>> > 65000 nodes inserted
>> > 70000 nodes inserted
>> > 75000 nodes inserted
>> > 80000 nodes inserted
>> > 85000 nodes inserted
>> > [debug] resizing heap dynamically from 0k to 1024k ...
>> > [panic] out of memory - heap full while resizing - execution terminated
>> >
>> > Uh oh, we've hit an actual bug now. Although we can get nodes up to
>> > 85000 by increasing max heap size from 2GB to 8GB, it appears to bomb
>> > after the heap exceeds 4GB, maybe indicating some 32-bit sizes
>> > left laying around in the code.
>> >
>> > Jim
>> >
>> > On Feb 2, 2013, at 7:18 PM, Jim Ursetto wrote:
>> >
>> >> On Feb 2, 2013, at 3:46 PM, Kristian Lein-Mathisen wrote:
>> >>
>> >>> I'm getting the same result here, when I run it through csc. When I
>> run it through csi, though, it never seems to finish - is the task that
>> big? I had to kill it after 2-3 hours.
>> >>
>> >> It's a hash table with 250,000 entries and 1,000 items per entry.
>> That's going to be tens of gigabytes for heap (memory usage at 40,000
>> nodes just before it dies is about 2GB on my machine). It's 250,000 node
>> inserts (O(V)), 250 million edge inserts (O(V*E)), and 125 billion
>> operations (O(V*E^2)) to traverse the edge lists (since you are using
>> member). To me that is pretty big.
>> >>
>> >> csi doesn't crash but appears to be stuck after 40,000 nodes inserted,
>> the same place that csc crashes maybe. It's not swap related, I had plenty
>> of memory, so something is maybe up with the hash table or GC. I can't
>> explain why csi does not crash.
>> >>
>> >> This machine is 64-bit OS X with 16GB main memory and no obvious limit
>> to the process data segment.
>> >>
>> >> Probably stupid shot in the dark: what happens when the Chicken heap
>> size exceeds 4GB on a 64-bit machine?
>> >>
>> >> Jim
>> >
>>
>>
_______________________________________________
Chicken-users mailing list
[email protected]
https://lists.nongnu.org/mailman/listinfo/chicken-users
