Please implement JIT indexing

[triska]

Commit 5893ff4 is not a good change:

The reason is that it now arbitrarily picks the first list of maplist/N in an attempt to benefit from argument indexing. This can go well, or it may also not. For example, what if the first list is a variable, and the second list is fully instantiated? To give this benefit also to other elements on the Prolog level, the code would have to check instantiation, pick an argument that is sufficiently instantiated (i.e., to a list), and pass that as the first argument to one of several auxiliary predicates so that maplist/N is deterministic. This would be messy, and moreover, all user programs in a similar situation will have to do the same.

Therefore, please consider fixing such issues once and for all at the engine level, for example by dynamically generating indices as necessary, if one of the arguments is sufficiently instantiated.

In this way, we can write Prolog code in a way that does not require such low-level considerations, and automatically benefit from indexing whenever possible. In particular, if this happens in the engine itself, the commit can largely be reverted again.

UPDATE: #732 has elegantly eliminated the need for the shown commit, solving the underlying issue much more generally. JIT indexing would still be nice of course, and would make maplist/N also deterministic if one of the other lists is instantiated. Contributors who would like to improve indexing may also be interested in #750.

[mthom]

Thanks. Does this mean I should switch back to the original implementation? Could you direct me to a good paper on JIT indexing?

[triska]

Personally, I think it is always good to keep Prolog code in the simplest and most natural form. If this does not yield efficient code, I recommend to first think about how efficiency can be improved at the engine level, i.e., at a place where application programmers need not worry about it at all.

So: Yes, personally, I think the previous version of maplist/N is better, since it is most natural.
If it currently leaves a choice-point: so be it. It is better to have simple Prolog code that will eventually improve automatically, than to now bother with countless ad hoc hacks that only deter from the actually beneficial core improvements that will improve all programs at once.

[triska]

One implementation idea mentioned by @UWN in our recent session:

Perform a linear scan of all potentially applicable clause heads to detect which one fits, and commit if exactly one applies.

The advantage of this is that no indices need to be built at all, and also that it gives strong guarantees regarding the minimization of choice-points. Of course, this is no true substitute for indexing if there are very many clauses, but it would make many cases work very nicely.

[UWN]

Some variations to an index-free indexing:

In case of two clauses, try the second and if it fails, execute the first determinately.

Alternatively, a very fast inline if-then-else might be an option too. Think of

maplist(_P_3, [], [], []).
maplist(P_3, [A|As], [B|Bs], [C|Cs]) :-
   call(P_3, A, B, C),
   maplist(P_3, As, Bs, Cs).

One way to make this determinate:

maplist(_P_3, As, Bs, Cs) :-
   (  Bs == [] -> !
   ;  Cs == [] -> !
   ;  As == [] -> !
   ;  As = []
   ),
   Bs = [],
   Cs = [].
maplist(P_3, [A|As], [B|Bs], [C|Cs]) :-
   ...

[UWN]

I am no longer happy with this version and I believe I somewhere posted a better one.