feature request time/1 in WASM

[Jean-Luc-Picard-2021]

Was just playing around with the new playground. Very cool, can even bignums. But somehow time/1 is not implemented, I get for a factorial example:

?- time(fac(1000,_)).
no
?- fac(1000,_).
yes

Which is also a little misleading to return no for a time/1 call. Would it be possible to add a time/1 predicate to WASM? Its pretty standard in other Prolog systems,

since the evaluable predicate cputime/0 or the predicate statistics/2 was not available in WASM, I couldn't bootstrap it by myself. Or is there a way to import time/1

by some use_module/1?

[jfmc]

Dear Captain,

Thank you for your kind words regarding the playground :)

The predicate time/1 is already defined in Ciao with a different meaning (mapped to POSIX time() to get time in seconds). This has been there for ages for compatibility with SICStus Prolog. It seems that SICStus renamed it later to now/1, and we'll probably do the same change. SWI calls this predicate get_time/1 but the output may be a float, while we'd like to keep it closer to SICStus (unless there is a good reason for changing it).

I did a quick check and I didn't found many systems beside SWI Prolog that implements time/1 to benchmark predicates (with that name). Do you know about more systems that implement that (with that name)? (besides all new Prolog systems that mimic SWI libraries).

You can implement time/1 easily in Ciao with code like this:

:- use_package(hiord). % (enables call/N).
:- use_module(engine(runtime_control), [statistics/2]).
:- use_module(engine(io_basic), [display/1]).

:- export(time/2).
:- meta_predicate time(goal,?).
time(G, T) :-
    statistics(walltime, [T0|_]),
    call(G),
    statistics(walltime, [T1|_]),
    T is T1-T0.

:- export(ctime/1). % rename to time/1 when old time/1 is renamed to now/1
:- meta_predicate ctime(goal).
ctime(G) :-
    time(G, T),
    Ts is T/1000.0,
    display('% '), display(Ts), display(' seconds\n').

The use_package and use_module are usually needed in Ciao-style modules (declared with module/3) since we try be very conservative about dependencies by default (allow the user not include anything that is not really used, which is very useful for static analysis).

Basically statistics(walltime, [T0|_]) seems to be working perfectly in WASM, while runtime, usertime, or systemtime are not (we always get 0). WASM has been very picky about what users can measure due to side-channel attacks like Spectre (it is well known that shared memory + precise time measures can enable this kind of attacks) so I'm not sure if it is a bug on our side, Emscripten, or if this is done on purpose.

Performance-wise, our engine compiled to WASM is around 2 times slower than a native one (we hope this improves in the future, although Ciao can be very fast on some benchmarks). The main limitation is that WASM on browsers is limited to 32-bit address space. This may affect some applications.

[Jean-Luc-Picard-2021]

Prolog systems that have meanwhile time/1 are not only SWI-Prolog, but also Scryer, Trealla, Jekejeke, Dogelog and maybe some more. The challenge is to make it show some

time measurement during backtracking as well, and to detect a deterministic success and then show no time measurement during backtracking.

Ok the playground tells me:

?- use_module(engine(runtime_control), [statistics/2]).
Note: module runtime_control already in executable, just made visible
yes
?- statistics(walltime, [T1|_]).
T1=23044.0 ? 

So I will be able to bootstrap something. Now I get the following measure for Ciao WASM:

/* Ciao WASM */
?- time2(fac(10000,_)).
% walltime 67.0 ms

Thats nice, since for example the SWI-Prolog WASM so far has no bignums. I can run the same in Dogelog though, which doesn't use WASM but directly JavaScript, and I get:

/* Dogelog JavaScript */
?- time(fac(10000,_)).
% Wall 63 ms, gc 1 ms, 476920 lips
true.

So practically the same concerning this kind of test....

[Jean-Luc-Picard-2021]

In another small test Ciao WASM is refreshingly fast:

/* Ciao WASM */
?- time2(fib(31,X)).
% walltime 895.0 ms
X=1346269 ?

/* Dogelog JavaScript */
?- time(fib(31,X)).
% Wall 6148 ms, gc 159 ms, 2125948 lips
X = 1346269.

Very cool! Thats a weak spot of my system...

P.S.: Ciao WASM being faster than Scryer Prolog:

/* Scryer Prolog */
?- time(fib(31,X)).
   % CPU time: 1.012s
   X = 1346269.

[jfmc]

Thanks. Ciao has a very good engine (&-Prolog derivate) that implements some state-of-the-art techniques for sequential Prolog execution. Except if your program depends on some specific builtin or feature (e.g., indexing beyond 1st functor, 1st arg; ground optimization assert, etc.) it should be fast for typical benchmarks. Of course performance in benchmarks may be irrelevant for some applications. Other engines with really good emulators are Yap Prolog, hProlog (AFAIK was never open source) or B-Prolog (now Picat).

Scryer Prolog is a promising system... but being written in Rust does not give optimized bytecode emulators for free.

Regarding bignum performance, it seems that when bignum operations dominate the execution time, some engine optimizations become almost irrelevant (we saw that when compiling Prolog to C).

Ciao WASM startup time may be considerably slower than a pure JS implementation like Dogelog (if the program is small, more code needs to be downloaded). And JS<->WASM communication time is fast but not negligible. In the past, some people argued that Prolog needed just 1 system. IMHO, having different systems and techniques for different scenarios seems more reasonable.

We did some experiments (around 2013, you can find the paper) on compiling Prolog to JS, directly. Our issue there was that for a real system it was painfully difficult to port all the libraries C code to JS, so we kept it as an experiment. Surprisingly performance of Ciao WASM is competitive (even faster) than this JS port with very little effort and maintenance costs.

[Jean-Luc-Picard-2021]

I am not yet through with testing. Although I share your excitement, already from what I have seen. Here is a little puzzle, intended to test some backtracking. How does Ciao Prolog compare? Can I run it, has it between/3?

step(E-R, G-S, (E+G)-T) :- T is R+S.
step(E-R, G-S, (E-G)-T) :- T is R-S.
step(E-R, G-S, (E*G)-T) :- T is R*S.
step(E-R, G-S, (E div G)-T) :- S =\= 0, R mod S =:= 0, T is R div S.

puzzle(1, 8-8).
puzzle(N, C) :- N > 0,
   M is N-1,
   between(1, M, K),
   puzzle(K, A),
   J is N-K,
   puzzle(J, B),
   step(A, B, C).

?- puzzle(8, G-1000), !.

So far I can even not consult it, looks like Ciao Prolog ignores the ISO core standard?

?- use_module('/draft.pl').
{Reading /draft.pl
ERROR: (lns 11-11) syntax error: ) or operator expected
step( E - R , G - S ,( E
** here **
div G ) - T ) :- S =\= 0 , R mod S =:= 0 , T is R div S .
WARNING: Predicate puzzle/2 undefined in module c_itf
{ERROR: No handle found for thrown exception 
error(existence_error(procedure,'c_itf:puzzle'/2),'c_itf:puzzle'/2)}

aborted

But I guess I can fix it, using (//)/2 instead of (div)/2.

[Jean-Luc-Picard-2021]

Ok, its also quite good in this example, I get:

/* Ciao  WASM */
?- puzzle(8, G-1000), !.
G=8+(8+8)*(8*8-(8+8)//8) ?
?- time2((puzzle(8, G-1000), fail; true)).
% walltime 1481.0 ms

/* Dogelog 1.0.1 JavaScript */
?- puzzle(8, G-1000), !.
G = 8+(8+8)*(8*8-(8+8)//8).
?- time((puzzle(8, G-1000), fail; true)).
% Wall 7610 ms, gc 8 ms, 2484552 lips
true.

Brilliant!!!

[jfmc]

Update: time/1 will be supported in the next push to github (the branch is still in a private clone)

[jfmc]

For reference, fixed in https://github.com/ciao-lang/ciao/commit/12d0f5417fb0e323a37674887d3dcd2217cc67d7