Partial evaluation of format_//2 and related constructs

[triska]

Dear all,

while trying to improve the speed of format_//2 for cases such as #2360, it occurred to me that the performance of format_//2, format/2 and related predicates can be improved with a technique known as partial evaluation: This means that we take into account everything we already know about these goals at compilation time, and only do what is still necessary at run time.

In almost all practical usage scenarios of format_//2, the format string (i.e., the first argument) is ground and can thus be compiled into dedicated instructions at compilation time. In this way, it is no longer necessary to parse the format string at run time.

I have now done this, and filed it as a draft in #2363.

Good news everyone!

With these changes applied, the example shown in #2360 runs more than twice as fast. In other programs, I measured a speedup of a factor 3 or greater. For example, the chacha20.pl implementation now produces its output much faster.

To illustrate the effect of these changes, let's consider word_hex/2 from that program:

word_hex(Bytes, Hex) :-
        binary_decimal(Bytes, D),
        phrase(("0x",format_("~`0t~16r~8+", [D])), Hex).

Note that the format string is fully known at compilation time, a very typical scenario.

With the partial evaluation changes to library(format) applied, the above clause automatically becomes:

?- listing(word_hex/2).
word_hex(A,B) :-
   binary_decimal(A,C),
   B=['0',x|D],
   format:format_cells([cell(0,E,[glue('0',F),goal(integer_to_radix(C,16,lowercase,G)),chars(G),goal(E is 0+8)])],D,[]).

Note how the format string has completely disappeared from the program! Instead, dedicated "instructions" appear that can be processed much faster, by relying on argument indexing and meta-calls.

I would greatly appreciate any feedback and tests, in particular if you have programs that describe a lot of output. For example, I think you @dcnorris described a larger CSV file at one point? If possible, please try these changes and see whether they work and yield performance improvements for your use cases.

Thank you a lot, and enjoy!
Markus

[dcnorris]

Upgrading from 0292cb7 to 2fdbb94, I see actually a little (~3%) slowdown, from 17.5 to 18.1 seconds, in the precautionary package code that writes the T[2-8].tab files. Perhaps this is due to more inferences in the latter case?

?- [scryer]. % using 0292cb7
% Warning: overwriting nth1/3 because the clauses are discontiguous
   true.
?- [esc].
   true.
?- time(maplist(write_T, [2,3,4,5,6,7,8])).
D = 2   J = 46
D = 3   J = 154
D = 4   J = 442
D = 5   J = 1162
D = 6   J = 2890
D = 7   J = 6922
D = 8   J = 16138
   % CPU time: 17.533s, 90_876_135 inferences
   true.
?- time(maplist(write_T, [2,3,4,5,6,7,8])).
D = 2   J = 46
D = 3   J = 154
D = 4   J = 442
D = 5   J = 1162
D = 6   J = 2890
D = 7   J = 6922
D = 8   J = 16138
   % CPU time: 17.420s, 90_876_158 inferences
   true.
?- halt.
% ... upgraded to 2fdbb94 
?- [scryer].
% Warning: overwriting nth1/3 because the clauses are discontiguous
   true.
?- [esc].
   true.
?- time(maplist(write_T, [2,3,4,5,6,7,8])).
D = 2   J = 46
D = 3   J = 154
D = 4   J = 442
D = 5   J = 1162
D = 6   J = 2890
D = 7   J = 6922
D = 8   J = 16138
   % CPU time: 18.126s, 95_669_949 inferences
   true.
?- time(maplist(write_T, [2,3,4,5,6,7,8])).
D = 2   J = 46
D = 3   J = 154
D = 4   J = 442
D = 5   J = 1162
D = 6   J = 2890
D = 7   J = 6922
D = 8   J = 16138
   % CPU time: 18.055s, 95_669_972 inferences
   true.
?- 

[triska]

Thank you a lot David for trying this!

I see that the format string is not statically known in this example, and therefore the partial evaluation cannot be applied: The format string is computed dynamically in a goal: https://github.com/dcnorris/precautionary/blob/a0019fc6baaa0a01ce1cef1b75982fdd7ae52d80/exec/esc.pl#L197 and then used in calls to format/3: https://github.com/dcnorris/precautionary/blob/a0019fc6baaa0a01ce1cef1b75982fdd7ae52d80/exec/esc.pl#L202

So, to benefit from the newly available partial evaluation of format strings in this example, the sample program would have to generate suitable calls of format_//2, format/2 or format/3 at compilation time (say, for a certain number of suitable arguments D that are expected to arise in practice), where the format string and argument list appears explicitly in the generated clauses. Without this, the partial evaluation indeed unfortunately even leads to a slowdown, because the goals that a static optimization would have inserted at compilation time are now created at run-time. Fortunately, the slowdown is very small in this example.

You can try to generate suitable clauses for example with term_expansion/2, by defining an expansion for, say, the fact format_n_columns. that would appear in your code, and expand for example to DCG clauses of the form:

format_n_columns(1, [A]) --> format_("...", [A]).
format_n_columns(2, [A,B]) --> format_("...", [A,B]).
...

The important point would be to have the format strings ("...") appear statically in the clauses above, because only then can the partial evaluation take them into account at compilation time. To obtain such clauses at compilation time, you would define:

term_expansion(format_n_columns, Clauses) :- ...

where the list Clauses of DCG clauses like above would by dynamically described for suitable values of  N. With such an expansion defined, you can add a single fact to your program to make Scryer add the list of clauses at compilation time:

format_n_columns.

You can use phrase_to_file/2 from library(pio) to write the described output to a file.

[triska]

Alternatively, you can also simply copy and paste these clauses and use them in your program, I think only these arguments are needed in your example:

format_n_columns(2,[A,B]) :-
   format("~w\t~w~n",[A,B]).
format_n_columns(3,[A,B,C]) :-
   format("~w\t~w\t~w~n",[A,B,C]).
format_n_columns(4,[A,B,C,D]) :-
   format("~w\t~w\t~w\t~w~n",[A,B,C,D]).
format_n_columns(5,[A,B,C,D,E]) :-
   format("~w\t~w\t~w\t~w\t~w~n",[A,B,C,D,E]).
format_n_columns(6,[A,B,C,D,E,F]) :-
   format("~w\t~w\t~w\t~w\t~w\t~w~n",[A,B,C,D,E,F]).
format_n_columns(7,[A,B,C,D,E,F,G]) :-
   format("~w\t~w\t~w\t~w\t~w\t~w\t~w~n",[A,B,C,D,E,F,G]).
format_n_columns(8,[A,B,C,D,E,F,G,H]) :-
   format("~w\t~w\t~w\t~w\t~w\t~w\t~w\t~w~n",[A,B,C,D,E,F,G,H]).

I generated them with:

run :-
        member(N, [2,3,4,5,6,7,8]),
        phrase(columns_format(N), Format),
        length(Args, N),
        portray_clause((format_n_columns(N, Args) :- format(Format, Args))),
        false.

[triska]

I have now done this, defining write_esc_array/2 as follows (using phrase_to_file/2 from library(pio)):

write_esc_array(D, Ms) :-
    phrase(format_("T~d.tab", [D]), Filename),
    phrase_to_file(esc_array_(Ms, D), Filename).

esc_array_([], _) --> [].
esc_array_([C1-C2|Ps], D) -->
    format_n_columns(D, C1),
    format_n_columns(D, C2),
    esc_array_(Ps, D).

format_clause(N, (format_n_columns(N, Args) --> format_(Format, Args))) :-
        phrase(columns_format(N), Format).

term_expansion(compile_format, Clauses) :-
        maplist(format_clause, [2,3,4,5,6,7,8], Clauses).

compile_format.

With this change, I get:

   % CPU time: 24.984s, 86_831_115 inferences

whereas previously, I got:

   % CPU time: 28.776s, 91_604_600 inferences

So, at least not a slowdown but a slight improvement due to partial evaluation. In this example, it seems not worth to do this because the improvement is so small. But the general technique may be interesting to know: That we can generate format strings and other data at compilation time, so that they can be partially evaluated by libraries.