2024-12-11 05:16 AEDT

View Issue Details Jump to Notes ]
IDProjectCategoryView StatusLast Update
0000263mercuryBugpublic2013-05-17 16:16
Reporterlpimmes 
Assigned Tojuliensf 
PrioritynormalSeveritycrashReproducibilityalways
StatusresolvedResolutionno change required 
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.
Attached Files
  • ? file icon tsp2.m (14,014 bytes) 2012-08-29 18:53
  • ? file icon tsp2upd.m (15,136 bytes) 2012-09-12 01:12

-Relationships
+Relationships

-Notes

~0000478

juliensf (administrator)

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 (reporter)

Last edited: 2012-09-12 01:51

View 5 revisions

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 (administrator)

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