Number of logical inferences of length/2 in Prolog (swi-pl)

Question

I expected the builtin length/2 predicate to be linear in the number of logical inferences. It appears, however, to be constant:

?- length(L,10),time(length(L,X)).
% 2 inferences, 0.000 CPU in 0.000 seconds (63% CPU, 142857 Lips)

?- length(L,20),time(length(L,X)).
% 2 inferences, 0.000 CPU in 0.000 seconds (62% CPU, 153846 Lips)

?- length(L,30),time(length(L,X)).
% 2 inferences, 0.000 CPU in 0.000 seconds (65% CPU, 111111 Lips)

Is this because the procedure is delegated to C? I could not find the pertinent code in the SWIPL codebase.

Answer 1

length/2 has a shallow but powerful interface near line 3230 in init.pl. From there it calls '$skip_list'(Length0, List, Tail), the 'swiss knife' of list C interface.

You can find it in src/pl-prims.c, line 2377 and following:

/** '$skip_list'(-Length, +Xs0, -Xs) is det.

Xs0, Xs is a pair of list differences. Xs0   is the input list and Xs is
the minimal remaining list. Examination of   Xs  permits to classify the
list Xs0:

        Xs        | list type of Xs0   | Length
        []    ... | well formed        | length
        Var   ... | partial            | elements skipped
        [_|_] ... | infinite           | upper bound for cycle
        Term  ... | malformed          | elements skipped
*/
PRED_IMPL("$skip_list", 3, skip_list, 0)
...