How can I tell what the computational complexity of a clpfd program is?

Question

For instance, say I have this program (only tested in swi-prolog):

:- use_module(library(clpfd)).
:- use_module(library(lists)).

% Sorted has the same elements as List and is also sorted
clpfd_sort(List, Sorted) :-
  same_length(List, Sorted),
  chain(Sorted, #=<),
  permutation(List, Sorted).

Where could I find enough information on how clpfd works to know whether this is an efficient solution? It might be greedy to ask such a simple solution to be n lg(n) but for all I know it's 10^n.

I've looked at sources such as this and they all do a great job of explaining the magic of clpfd but none of them explain enough of how it's implemented for me to get an idea of which programs will run quickly and which will run slowly. clpfd apparently uses attributes to hook into unification? I don't know enough about attributes to know what that means for the complexity of the programs I write. Is there somewhere I could find out?

Answer 1

Example experiment:

:- use_module(library(clpfd)).
:- use_module(library(lists)).

call_time(G,T) :-
   statistics(runtime,[T0|_]),
   G,
   statistics(runtime,[T1|_]),
   T is T1 - T0.

% Sorted has the same elements as List and is also sorted
clpfd_sort(List):-
  same_length(List, Sorted),
  chain(Sorted, #=<),
  permutation(List, Sorted).

item_goal(I,clpfd_sort(I)).

n_randoms_times(NumberOfExperiments,Random_Lists,Times) :- 
  numlist(1,NumberOfExperiments,Experiment_Sizes),
  maplist(numlist(1),Experiment_Sizes,ExperimentLists),
  maplist(random_permutation,ExperimentLists,Random_Lists),
  maplist(item_goal,Random_Lists,Goals),
  maplist(call_time,Goals,Times).

Test:

?- n_randoms_times(15,R,T),write(T).
[0,0,0,1,1,1,2,5,4,3,16,34,43,115,246]

So it looks like the time doubles as we add one to the size of the list ...

Answer 2

The best way to tackle with complexities of a Prolog or clpfd program is to avoid the actual mechanisms within and concentrate on concrete answers or sets of answers first. After all, if such an analysis already indicates a very large O, any further details are just futile, as is the case in your program.

Consider a list of n equal numbers. In this case, we will get n valid permutations. Thus worst-case complexity is at least O(n!). That seems to be bad enough to reconsider your approach.

The best in this case would be to develop a constraint that relates that list of integers to the actual list directly. If my memory does serve me well such has been implemented in the context of Prolog IV.