Mercury Bugs - mercury
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0000263mercuryBugpublic2012-08-29 18:532013-05-17 16:16
Reporterlpimmes 
Assigned Tojuliensf 
PrioritynormalSeveritycrashReproducibilityalways
StatusresolvedResolutionno change required 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
Summary0000263: Segmentation fault: not enough memory when invoking solutions/2
DescriptionWorking 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 ReproduceCompile, 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 Informationgcc 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)?
TagsNo tags attached.
Relationships
Attached Files? tsp2.m (14,014) 2012-08-29 18:53
https://bugs.mercurylang.org/file_download.php?file_id=159&type=bug
? tsp2upd.m (15,136) 2012-09-12 01:12
https://bugs.mercurylang.org/file_download.php?file_id=160&type=bug

Notes
(0000478)
juliensf   
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.)
(0000479)
lpimmes   
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>
(0000513)
juliensf   
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.

Issue History
Date ModifiedUsernameFieldChange
2012-08-29 18:53lpimmesNew Issue
2012-08-29 18:53lpimmesFile Added: tsp2.m
2012-09-10 01:13juliensfNote Added: 0000478
2012-09-10 01:13juliensfAssigned To => juliensf
2012-09-10 01:13juliensfStatusnew => feedback
2012-09-12 00:40lpimmesNote Added: 0000479
2012-09-12 00:40lpimmesStatusfeedback => assigned
2012-09-12 00:59lpimmesNote Edited: 0000479bug_revision_view_page.php?bugnote_id=479#r4
2012-09-12 01:06lpimmesNote Edited: 0000479bug_revision_view_page.php?bugnote_id=479#r5
2012-09-12 01:12lpimmesFile Added: tsp2upd.m
2012-09-12 01:13lpimmesNote Edited: 0000479bug_revision_view_page.php?bugnote_id=479#r6
2012-09-12 01:51lpimmesNote Edited: 0000479bug_revision_view_page.php?bugnote_id=479#r7
2013-05-17 16:16juliensfNote Added: 0000513
2013-05-17 16:16juliensfStatusassigned => resolved
2013-05-17 16:16juliensfResolutionopen => no change required