| View Issue Details [ Jump to Notes ] | [ Issue History ] [ Print ] | ||||||||
| ID | Project | Category | View Status | Date Submitted | Last Update | ||||
|---|---|---|---|---|---|---|---|---|---|
| 0000263 | mercury | Bug | public | 2012-08-29 18:53 | 2013-05-17 16:16 | ||||
| Reporter | lpimmes | ||||||||
| Assigned To | juliensf | ||||||||
| Priority | normal | Severity | crash | Reproducibility | always | ||||
| Status | resolved | Resolution | no change required | ||||||
| Product Version | |||||||||
| Target Version | Fixed in Version | ||||||||
| Summary | 0000263: Segmentation fault: not enough memory when invoking solutions/2 | ||||||||
| Description | Working with mercury language is quiet rewarding. But running into a memory problem of some kind, as expected with Traveling salesman problem. % Using generator length of 7 (see code): [2, 3, 4, 5, 6, 7, 8] % tsp2 501>MERCURY_OPTIONS=--solutions-heap-size-kwords=1024000 % tsp2 501>echo $MERCURY_OPTIONS % --solutions-heap-size-kwords=1024000 % tsp2 501>./tsp2 % Segmentation fault: 11 % tsp2 501> See attached tsp2.m file. (shows gcc and mmc, darwin versions) Any help would be appreciated, thanks. | ||||||||
| Steps To Reproduce | Compile, then run uploaded file(tsp2.m). tsp2 493>cat tsp2.bash #/bin/bash mmc --make --fully-strict -E -v -O 0 --use-subdirs tsp2 | ||||||||
| Additional Information | gcc 4.2 mmc 11.7 Aside: When analyzing mercury programs asymptotically, we can sometimes determine implicit for-loops, i.e., O(n), O(n^2), and so on, even n! if using solutions/2. But, I am not so sure if this is sufficient for 'Analysis of Algorithms graduate course'. Unification takes time, and so does resolution theorem proving. In other words, more computations are taking place 'behind the mercury code' so to speak. Any ideas, heuristics or suggestions (sites)? | ||||||||
| Tags | No tags attached. | ||||||||
| Attached Files | |||||||||
 Relationships |
|
 Relationships |
| Notes |
|
|
juliensf (administrator) 2012-09-10 01:13 |
The problem is a nondetstack overflow. This can be resolved by either expanding the size of the nondetstack using the --nondetstack-size-kwords option with the MERCURY_OPTIONS environment variable or by using a stack segments grade (grade component: stseg). (The latter provides a nondetstack that can grow dynamically at runtime.) |
|
lpimmes (reporter) 2012-09-12 00:40 Last edited: 2012-09-12 01:51 |
Follow Julian's advice about stseg; tsp2.m is working now. Yes, TSP is an np-complete problem; just examining mercury under heavy stress. %% cd mercury-compiler-11.07.2/ %% ./configure --with-cc="gcc -m64" --enable-libgrades=hlc.gc,none.gc,none.gc.stseg,java,erlang %% ... Unable to delete original file, so: Download tsp2upd.m ; mv tsp2upd.m tsp2.m % RUN %% ~ 515>cd $MERCURYPROGRAMS %% mercuryPrograms 513>cd algor91503/ %% algor91503 512>cd tsp2 %% tsp2 489>ulimit -H -s %% 65532 %% Cannot set to a higher value. %% Edit code and change generator length, then recompile. %% Generator lengths shown are: 10, 9, 8, 7. %% tsp2 489>which mmc %% /usr/local/mercury-11.07.2/bin/mmc %% tsp2 489>mmc --grade none.gc.stseg --fully-strict -E -v -O 0 --use-subdirs tsp2 % 10! = 3628800 % 430 m ~= 7 hours, most of the time spent swapping in and out of memory, as timer shows. %% tsp2 487>time ./tsp2 %% #Permutations: 3628800, Generator length: 10 using [2 3 4 5 6 7 8 9 10 11 ], %% minimum distance 23: 1_8(2) 8_6(2) 6_5(3) 5_4(1) 4_3(3) 3_9(2) 9_7(1) 7_11(1) 11_2(3) 2_10(3) 10_1(2) %% real 430m26.708s %% user 7m36.750s %% sys 12m29.934s % 9! = 362880 %% tsp2 489>./tsp2 %% #Permutations: 362880, Generator length: 9 using [2 3 4 5 6 7 8 9 10 ], %% minimum distance 23: 1_8(2) 8_6(2) 6_5(3) 5_4(1) 4_3(3) 3_9(2) 9_7(1) 7_2(4) 2_10(3) 10_1(2) % % real 0m32.049s % % user 0m30.823s % % sys 0m1.051s % 8! = 40320 %% tsp2 489>./tsp2 %% #Permutations: 40320, Generator length: 8 using [2 3 4 5 6 7 8 9 ], %% minimum distance 24: 1_5(4) 5_4(1) 4_3(3) 3_9(2) 9_7(1) 7_2(4) 2_6(5) 6_8(2) 8_1(2) % 7/! = 5040 %% tsp2 505>./tsp2 %% #Permutations: 5040, Generator length: 7 using [2 3 4 5 6 7 8 ], %% minimum distance 23: 1_3(5) 3_4(3) 4_5(1) 5_7(1) 7_2(4) 2_6(5) 6_8(2) 8_1(2) %% tsp2 505> |
|
juliensf (administrator) 2013-05-17 16:16 |
The problem can be avoided by increasing the nondet stack size (low-level C backend), C stack size (high-level C backend) or using a stack segments grade. |
| Notes |
| Issue History |
|||
| Date Modified | Username | Field | Change |
|---|---|---|---|
| 2012-08-29 18:53 | lpimmes | New Issue | |
| 2012-08-29 18:53 | lpimmes | File Added: tsp2.m | |
| 2012-09-10 01:13 | juliensf | Note Added: 0000478 | |
| 2012-09-10 01:13 | juliensf | Assigned To | => juliensf |
| 2012-09-10 01:13 | juliensf | Status | new => feedback |
| 2012-09-12 00:40 | lpimmes | Note Added: 0000479 | |
| 2012-09-12 00:40 | lpimmes | Status | feedback => assigned |
| 2012-09-12 00:59 | lpimmes | Note Edited: 0000479 | View Revisions |
| 2012-09-12 01:06 | lpimmes | Note Edited: 0000479 | View Revisions |
| 2012-09-12 01:12 | lpimmes | File Added: tsp2upd.m | |
| 2012-09-12 01:13 | lpimmes | Note Edited: 0000479 | View Revisions |
| 2012-09-12 01:51 | lpimmes | Note Edited: 0000479 | View Revisions |
| 2013-05-17 16:16 | juliensf | Note Added: 0000513 | |
| 2013-05-17 16:16 | juliensf | Status | assigned => resolved |
| 2013-05-17 16:16 | juliensf | Resolution | open => no change required |
| Issue History |