Sorting large lists in Prolog: Not enough memory

Question

I'm trying to sort a 10k element list in prolog with bubblesort and I get the out of local stack error. Mergesort seems to be the best option since I don't get any errors for the same input. However I'd really like to get some running times for bubblesort with large input data but I can't. Any ideas?

Here's the code:

 %% NOTE: SWI-PROLOG USED

 %% generate_list(Limit, N, L): - insert upper limit and length of list N
 %% to get a random list with N numbers from 0 to limit
 generate_list(_, 0, []).
 generate_list(Limit, N, [Y|L]):-
    N =\= 0,
    random(0, Limit, Y),
    N1 is N-1,
    generate_list(Limit, N1, L).


 %% bubble(L, Ls, max):- insert list L and get max member of list by
 %% swapping members from the start of L.
 bubble([Z], [], Z).
 bubble([X,Y|L], [X|Ls], Z):- X =< Y, bubble([Y|L], Ls, Z).
 bubble([X,Y|L], [Y|Ls], Z):- X  > Y, bubble([X|L], Ls, Z).

 %% bubble_sort(List, Accumulator, Sorted_List)
 bubblesort([X], Ls, [X|Ls]).
 bubblesort(L, Accumulate, Result):- bubble(L, Ls, Max),
       bubblesort(Ls, [Max|Accumulate], Result).

 bubble_sort(L, Sorted):- bubblesort(L, [], Sorted).

As you can I see I'm using tail recursion. I've also tried enlarging the stacks by using:

  set_prolog_stack(global, limit(100 000 000 000)).
  set_prolog_stack(trail,  limit(20 000 000 000)).
  set_prolog_stack(local,  limit(2 000 000 000)).

but it just runs for a bit longer. Eventually I get out of local stack again. Should I use another language like C and malloc the list or not use recursion?

Answer 1

Since there are two answers, and no one pointed out explicitly enough the reason why you get into "out of local stack" trouble (Mat says in the comment to your question that your predicates are not deterministic, but does not explain exactly why).

Two of the predicates you have defined, namely, bubblesort/3 and bubble/3, have mutually exclusive clauses. But Prolog (at least SWI-Prolog) does not recognize that these are mutually exclusive. So, choice points are created, you don't get tail recursion optimization, and probably no garbage collection (you need to measure using your implementation of choice if you want to know how much goes where and when).

You have two different problems.

Problem 1: lists with exactly one element

This problem pops up in both predicates. In the most simple predicate possible:

foo([_]).
foo([_|T]) :-
    foo(T).

And then:

?- foo([a]).
true ;
false.

This is not surprising; consider:

?- [a] = [a|[]].
true.

You can solve this by using a technique called lagging:

bar([H|T]) :-
    bar_1(T, H).
bar_1([], _).
bar_1([H|T], _) :-
    bar_1(T, H).

Then:

?- bar([a]).
true.

In the definition of bar_1/2, the first argument to the first clause is the empty list; the first argument to the second clause is a non-empty list (a list with at least one element, and a tail). Prolog does not create choice points when all clauses are obviously exclusive. What obvious means will depend on the implementation, but usually, when the first arguments to all clauses are all terms with different functors, then no choice points are created.

Try the following (you might get different results, but the message is the same):

?- functor([], Name, Arity).
Name = [],
Arity = 0.

?- functor([_|_], Name, Arity).
Name = '[|]',
Arity = 2.

See this question and the answer by Mat to see how you can use this to make your program deterministic.

Mat, in his answer, uses this approach, if I see correctly.

Problem 2: constraints (conditions) in the body of the clauses

This is the problem with the second and third clause of bubble/3. In the textbook "correct" example of choosing the minimum of two elements:

min(A, B, B) :- B @< A.
min(A, B, A) :- A @=< B.

Then:

?- min(1,2,1).
true.

but:

?- min(2,1,1).
true ;
false.

You can solve this in two ways: either by doing what Mat is doing, which is, using compare/3, which succeeds deterministically; or, by doing what CapelliC is doing, which is, using an if-then-else.

Mat:

min_m(A, B, Min) :-
    compare(Order, A, B),
    min_order(Order, A, B, Min).
min_order(<, A, _, A).
min_order(=, A, _, A).
min_order(>, _, B, B).

And Carlo:

min_c(A, B, Min) :-
    (   B @< A
    ->  Min = B
    ;   Min = A
    ).

I know there will always be at least as many opinions as heads, but both are fine, depending on what you are doing.

PS

You could use the built in length/2 to generate a list, and re-write your generate_list/3 like this:

generate_list(Limit, Len, List) :-
    length(List, Len),
    random_pos_ints(List, Limit).

random_pos_ints([], _).
random_pos_ints([H|T], Limit) :-
    random(0, Limit, H),
    random_pos_ints(T, Limit).

The helper random_pos_ints/2 is a trivial predicate that can be expressed in terms of maplist:

generate_list(Limit, Len, List) :-
    length(List, Len),
    maplist(random(0, Limit), List).    

Answer 2

Here is a version of bubble/3 that is deterministic if the first argument is instantiated, so that tail call optimisation (and, more specifically, tail recursion optimisation) applies:

bubble([L|Ls0], Ls, Max) :- phrase(bubble_(Ls0, L, Max), Ls).

bubble_([], Max, Max) --> [].
bubble_([L0|Ls0], Max0, Max) -->
        elements_max(L0, Max0, Max1),
        bubble_(Ls0, Max1, Max).

elements_max(X, Y, Max) -->
        { compare(C, X, Y) },
        c_max(C, X, Y, Max).

c_max(<, X, Y, Y) --> [X].
c_max(=, X, Y, Y) --> [X].
c_max(>, X, Y, X) --> [Y].

Example usage, with the rest of the program unchanged (running times depend on the random list, which is bad if you want to reproduce these results - hint: introduce the random seed as argument to fix this):

?- generate_list(100, 10_000, Ls), time(bubble_sort(Ls, Ls1)).
% 200,099,991 inferences, 29.769 CPU in 34.471 seconds
...

For testing different versions, please use a version of the query that you can use to reliably reproduce the same initial list, such as:

?- numlist(1, 10_000, Ls0), time(bubble_sort(Ls0, Ls)).

The nice thing is: If you just use zcompare/3 from library(clpfd) instead of compare/3, you obtain a version that can be used in all directions:

?- bubble(Ls0, Ls, Max).
Ls0 = [Max],
Ls = [] ;
Ls0 = [Max, _G677],
Ls = [_G677],
_G677#=<Max+ -1,
zcompare(<, _G677, Max) ;
Ls0 = [Max, _G949, _G952],
Ls = [_G949, _G952],
_G952#=<Max+ -1,
_G949#=<Max+ -1,
zcompare(<, _G952, Max),
zcompare(<, _G949, Max) ;
etc.

This describes the relation in general terms between integers.

Answer 3

Disclaimer: following the hint by @mat could be more rewarding...

I've played a bit with your code, in my experiment the local stack overflow was thrown with a list length near 2500. Then I've placed some cut:

%% bubble(L, Ls, max):- insert list L and get max member of list by
%% swapping members from the start of L.
bubble([Z], [], Z).
bubble([X,Y|L], [R|Ls], Z):-
 ( X =< Y -> (R,T)=(X,Y) ; (R,T)=(Y,X) ),
 bubble([T|L], Ls, Z).

%% bubble_sort(List, Accumulator, Sorted_List)
bubblesort([X], Ls, [X|Ls]) :- !.
bubblesort(L, Accumulate, Result):-
 bubble(L, Ls, Max),
 !, bubblesort(Ls, [Max|Accumulate], Result).

and I get

?- time(generate_list(100,10000,L)),time(bubble_sort(L,S)).
% 60,000 inferences, 0.037 CPU in 0.037 seconds (99% CPU, 1618231 Lips)
% 174,710,407 inferences, 85.707 CPU in 86.016 seconds (100% CPU, 2038460 Lips)
L = [98, 19, 80, 24, 16, 59, 70, 39, 22|...],
S = [0, 0, 0, 0, 0, 0, 0, 0, 0|...] 
.

so, it's working, but very slowly, showing the quadratic complexity...