# VM code refactor - thoughts?

**URL:** <https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845>\
**Category:** Request For Comments\
**Tags:** on-topic-only\
**Created:** [April 19, 2021, 11:31pm UTC](https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845 "2021-04-19T23:31:34Z")\
**Posts on this page:** 14\
**Page:** 6

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [May 21, 2021, 4:58am UTC](https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845/174 "2021-05-21T04:58:53Z")

</div>

A few more Python-optimization links from [Python Software Foundation News: The 2021 Python Language Summit: Making CPython Faster](https://pyfound.blogspot.com/2021/05/the-2021-python-language-summit-making.html) – I have no idea how applicable any of these ideas might be.  
[PEP 659 -- Specializing Adaptive Interpreter | Python.org](https://www.python.org/dev/peps/pep-0659/)  
[GitHub - faster-cpython/ideas](https://github.com/faster-cpython/ideas)  
[GitHub - faster-cpython/tools](https://github.com/faster-cpython/tools)  
[http://github.com/markshannon/faster-cpython](http://github.com/markshannon/faster-cpython)

---

<div class="post-metadata">

**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\
**Post date:** [May 21, 2021, 5:02am UTC](https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845/175 "2021-05-21T05:02:02Z")

</div>

I still don’t understand why those FASM libraries are (apparently) so much faster than functionality equivalent c implementations …

The libraries themselves aren’t complex code, and complexity analysis applies equally to both implementations – so why does assembly make such a difference … where is performance lost with C compilation.

---

<div class="post-metadata">

**Author:** ![CapelliC](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/capellic/32/17_2.png) [@CapelliC](https://swi-prolog.discourse.group/u/CapelliC)\
**Post date:** [May 21, 2021, 5:49am UTC](https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845/176 "2021-05-21T05:49:29Z")

</div>

> [@grossdan](#):
>
> where is performance lost

Good question. I will take a different approach attempting to answer it, since I observed

| implementation | time (msec) |
| --- | --- |
| latest SWI-Prolog | 192 |
| GNU Prolog | 172 |
| gplc (compiled GNU Prolog) | 48 |

for the pure Prolog benchmark of 10 queens (724 solutions, no arithmetic, just list processing)

```prolog
place_queen(I,[I|_],[I|_],[I|_]).
place_queen(I,[_|Cs],[_|Us],[_|Ds]):-place_queen(I,Cs,Us,Ds).

place_queens([],_,_,_).
place_queens([I|Is],Cs,Us,[_|Ds]):-
  place_queens(Is,Cs,[_|Us],Ds),
  place_queen(I,Cs,Us,Ds).

gen_places([],[]).
gen_places([_|Qs],[_|Ps]):-gen_places(Qs,Ps).

qs(Qs,Ps):-gen_places(Qs,Ps),place_queens(Qs,Ps,_,_).

% goal(Ps):-qs([0,1,2,3],Ps).
goal(Ps):-qs([0,1,2,3,4,5,6,7,8,9],Ps).

```

---

<div class="post-metadata">

**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\
**Post date:** [May 21, 2021, 6:11am UTC](https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845/177 "2021-05-21T06:11:05Z")

</div>

@CapelliC do you think the ratio will hold for much larger inputs as well –

So, how do you interpret these results …

Where in list processing does performance get lost.

One though of mine was time to access memory (pointer chasing) but this likely happen equally often – so, it then pure processing speed of term / list referencing, manipulation and stack handling (aka unification).

---

<div class="post-metadata">

**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\
**Post date:** [May 21, 2021, 6:28am UTC](https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845/179 "2021-05-21T06:28:27Z")

</div>

That’s a great observation …

I would imagine that in the overall structure of Prolog programs, built-ins can appear in two places: a) the base case and b) in much used data structures.

Regarding base cases, the these would be called less often, so shouldn’t contribute much to speedup.

But, regarding data structures those are often accesssed and hence making them built in could be significant: e.g. instead of prolog assoc library to have a assembly implementation of assoc.

Another consequence of your observation might be that the execution of VM instructions will likely have less impact – or, its impact will be significantly felt once data structures often used are optimized.

Edit:

Btw, in @CapelliC example, there aren’t really any built-ins – as far as i can tell …

---

<div class="post-metadata">

**Author:** ![CapelliC](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/capellic/32/17_2.png) [@CapelliC](https://swi-prolog.discourse.group/u/CapelliC)\
**Post date:** [May 21, 2021, 6:41am UTC](https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845/180 "2021-05-21T06:41:09Z")

</div>

Comparing GNU Prolog and SWI-Prolog it’s not too much instructive, even ruling out arithmetic, because gprolog doesn’t have multithreading, that - I think - will slow down SWI-Prolog engine in single thread computations. What is interesting, is the improvement in the compiled gprolog implementation. More than 300%, it’s a lot… now I’m reading the document [On the implementation of GNU Prolog](https://arxiv.org/abs/1012.2496), before delving into details…

---

<div class="post-metadata">

**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\
**Post date:** [May 21, 2021, 6:45am UTC](https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845/181 "2021-05-21T06:45:12Z")

</div>

> [@CapelliC](#):
>
> I think - will slow down SWI-Prolog engine in single thread computations.

Perhaps, on the contrary, having both work on a problem single threadedly is good for machinery comparison … and deriving conclusions.

Its an artificial setup but can perhaps shed light on where to make optimizations that are then felt by each processing thread as well.

Dan

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [May 21, 2021, 8:33am UTC](https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845/182 "2021-05-21T08:33:20Z")

</div>

> [@CapelliC](#):
>
> Comparing GNU Prolog and [SWI-Prolog](https://www.swi-prolog.org/pldoc/doc_for?object=manual) it’s not too much instructive, even ruling out arithmetic, because gprolog doesn’t have multithreading, that - I think - will slow down SWI-Prolog engine in single thread computations.

Threading doesn’t slow down much. Normal (pure) Prolog execution is not affected at all and neither are most built-ins. A couple are, but given that most low-level operations are lock-free and the impact is low unless threads really hammer some shared resource. There is some impact for dynamic code from which some clauses have been retracted because the logic for deciding whether a clause is visible or not on is more complicated and we need an additional indirection in the clause representation to safely add and remove clauses concurrently.

There are a couple of reasons that make SWI-Prolog slower though. To name a few (I don’t know the impact of each)

- Unbounded arithmetic. E.g. `A is 1<<1000` says `1099511627776` in GNU-Prolog. SWI-Prolog has to do overflow checking and move to GMP on overflow.

- Lack of GC and stack expansion in GNU-Prolog. Try the program below. GC and stack expansion are not free as we need to be aware of all reachable Prolog data at any time and we must be aware that data can move at any time. This implies we need indirect pointers to data or, when we use direct pointers we must be careful to recover if we call a function that may shift the stacks or run GC.

- SWI-Prolog has rather aggressive GC. That is intended to keep stack usage low and accommodate many threads. That surely implies a performance loss compared to just allocating a fixed stack size and give up if that overflows. SWI-Prolog’s initial stacks are small and at any overflow it must decide on GC and/or enlarging the stacks. Under some workloads the result can be pretty bad.

- Lack atom garbage collection in GNU-Prolog. This too requires visibility of data structures and reference counting for atoms that are (only) accessible from foreign code.

- Lack of support for cyclic terms. Try `?- X = f(X), Y = f(Y), X = Y.` Cyclic unification and comparison is slower, except when there is significant structure _sharing_ in the terms being unified or compared.

- Almost all Prolog systems distinguish list cells from normal compounds. SWI-Prolog does not. It does have some special instructions. This surely makes SWI-Prolog loose on space requirements for lists. I’m not too sure about time as it also means we avoid code duplication.

> [@CapelliC](#):
>
> More than 300%, it’s a lot

It is. Native code generation together with GC/shift is a lot harder though. Also, these evaluations are nearly invariably on small programs. On big programs that have no clear (small) hotspots things might well be different. It always reminds me on SWI-Prolog’s optimized arithmetic: programs that are mostly doing arithmetic tend to get 2 or 3 times faster. Larger programs that do some arithmetic occasionally tend to get _slower_ by a couple of percent, _even_ if profiling shows they spent a clearly measurable fraction of their time on arithmetic.

---

<div class="post-metadata">

**Author:** ![ridgeworks](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/ridgeworks/32/886_2.png) [@ridgeworks](https://swi-prolog.discourse.group/u/ridgeworks)\
**Post date:** [May 24, 2021, 4:47pm UTC](https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845/183 "2021-05-24T16:47:28Z")

</div>

> [@jan](#):
>
> It always reminds me on SWI-Prolog’s optimized arithmetic: programs that are mostly doing arithmetic tend to get 2 or 3 times faster. Larger programs that do some arithmetic occasionally tend to get _slower_ by a couple of percent, _even_ if profiling shows they spent a clearly measurable fraction of their time on arithmetic.

I’ve observed the big gains with optimized arithmetic but was surprised that some programs get slower by a few percent. Any ideas as to why (and when) that’s the case, e.g., complex expressions? Or is it caused by second order effects like cacheing efficiency or small errors in the performance measurement techniques.

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [May 24, 2021, 7:47pm UTC](https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845/184 "2021-05-24T19:47:22Z")

</div>

I think caching is the only sensible explanation.

---

<div class="post-metadata">

**Author:** ![logicmoo](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/logicmoo/32/193_2.png) [@logicmoo](https://swi-prolog.discourse.group/u/logicmoo)\
**Post date:** [May 30, 2021, 7:43am UTC](https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845/185 "2021-05-30T07:43:55Z")

</div>

A little late to jump in…

> [@CapelliC](#):
>
> |GNU Prolog|172|  
> |gplc (compiled GNU Prolog)|48|

I assume this time difference between translating a Prolog program to C then compiling it with the conventional C compiler vs not.

For Sicstus I assumed that the speed up is that they experimented with a PL2AM “emulator” (a PL2VMI) … and experimented, and experimented , and experimented until the VMI instead of having only XX instructions it now has XXX instructions (lots of specializations that get rid of unneeded work but adds lots of extra cruft)

One pathway I went towards finding the “right size” of VMI (not that I am interested in doing it anymore) was to start out with a PL2AM (example [https://github.com/TeamSPoon/SxxMachine/blob/cb7ee3dab4035bdc0d2e383a4cb962129b9d5922/prolog/sxx\_pl2cpp.pl](https://github.com/TeamSPoon/SxxMachine/blob/cb7ee3dab4035bdc0d2e383a4cb962129b9d5922/prolog/sxx_pl2cpp.pl) ) translate several benchmarks/ typical programs and finding the least dumb outputs. No mater how dumb (or smart) they were relative to each other and gave me tons of optimizations I would not otherwise considered had it hidden the intermediate output from me.

Whenever, I, as a human, could written a faster impl than my translator could write, I pretended it was a bug. Examples would be program translations involving `between/3` or `repeat/0` Not that I needed better more or better builtins, but i need to catch many idioms that prolog programs are going to try to silently sneak by the translator like:

```prolog
foo:-foo.
foo.

bar :- foo, baz, fail.

``
```

---

<div class="post-metadata">

**Author:** ![CapelliC](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/capellic/32/17_2.png) [@CapelliC](https://swi-prolog.discourse.group/u/CapelliC)\
**Post date:** [May 30, 2021, 9:46am UTC](https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845/186 "2021-05-30T09:46:47Z")

</div>

> [@logicmoo](#):
>
> translating a Prolog program to C then compiling it with the conventional C compiler

From pag.4 of the document referred above, seems that GNU Prolog was born when they ditched such route and introduced instead the MiniAssembly intermediate language…

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [May 30, 2021, 6:43pm UTC](https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845/188 "2021-05-30T18:43:04Z")

</div>

> [@anon95304481](#):
>
> In Dogelog I have written the tokenizer in Prolog, using the [two-level DCG](https://stackoverflow.com/a/66800186/502187) approach.

There’s also Richard O’Keefes tokeniser (section 10.7 of _The Craft of Prolog_). It’s probably online somewhere, but I didn’t see it at [http://www.cs.otago.ac.nz/staffpriv/ok/software.htm](http://www.cs.otago.ac.nz/staffpriv/ok/software.htm)

---

<div class="post-metadata">

**Author:** ![logicmoo](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/logicmoo/32/193_2.png) [@logicmoo](https://swi-prolog.discourse.group/u/logicmoo)\
**Post date:** [May 30, 2021, 11:36pm UTC](https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845/190 "2021-05-30T23:36:19Z")

</div>

> [@anon95304481](#):
>
> Looks like your directory contains a mash up of two Prolog systems, PrologCafe (pl2cpp) and jProlog (Prolog.cpp).

Yeah.. I mashed together `PrologCafe`, `jProlog` and `KernelProlog` (Predecessor to `JinniProlog`). Although `KernelProlog` and `jProlog` had a much more advanced System.Objects (like Attributed Variables, Multivars, Memoization Fluents, Closures etc) that with some care, the `PrologCafe` compiler had no problem targeting all three systems. Even though most of the code you will see is emitting java, it was retranslated as a next step into C++ using the [Source Code Converters](https://www.tangiblesoftwaresolutions.com/index.html) . Though i tried hard to make sure the java was still testable.

> [@anon95304481](#):
>
> What I didn’t get yet, where is the jProlog compiler?

The repo link I gave was wrong above I meant to have given [https://github.com/DouglasRMiles/SxxMachine](https://github.com/DouglasRMiles/SxxMachine)

**Edit**

Still, you might be mistaking Eärendil’s “JProlog” with Bart’s “jProlog”

jProlog does have a compiler but it was rudimentary .. ORINIGALLY [Wayback Machine](https://web.archive.org/web/20150325165056/http://people.cs.kuleuven.be/~bart.demoen/PrologInJava/comp) (the rest is found here `https://web.archive.org/web/*/http://people.cs.kuleuven.be/~bart.demoen/PrologInJava/*` )

Examples of different compilers (boven.pl / comp\*.pl) and their output in the .j files in.. [SxxMachine/jsrc-kuleuven/prolog at master · DouglasRMiles/SxxMachine · GitHub](https://github.com/DouglasRMiles/SxxMachine/blob/master/jsrc-kuleuven/prolog/)

like:

> <https://github.com/DouglasRMiles/SxxMachine/blob/master/jsrc-kuleuven/prolog/pred_writevars_1.j#L1-L12>

> [@anon95304481](#):
>
> if it were a compiler and not an interpreter, it could compile itself.

It does,  
see:

> **[SxxMachine/jsrc-kuleuven/comp/SxxMachine at master · DouglasRMiles/SxxMachine](https://github.com/DouglasRMiles/SxxMachine/tree/master/jsrc-kuleuven/comp/SxxMachine)**
>
> C++ Prolog/Datalog Inference Engine. Contribute to DouglasRMiles/SxxMachine development by creating an account on GitHub.

* * *

* * *

> [@anon95304481](#):
>
> But [SWI-Prolog](https://www.swi-prolog.org/pldoc/doc_for?object=manual) is ZIP based. Disclaimer: Things might be nevertheless useful, kind of a trash heap where you can pick up things.

The 3 systems I used each had their own methodology all three very good at things the other 2 are 10x slower at) the resulting combined set becomes a `PredikatenPrologMachine` that ended up having typical WAM and non-WAM Machine operations and Tarau’s kernel machine _unfolders_ .. Who knows, maybe I overlapped with some ZIP instructions. In many cases (often as I had time for) I ensured they did not simply convert into inline javafications of WAM instructions (the PrologCafe method) but instead to a set of static method calls and around the ever evolving 3±system prolog machine.

My point was answering why some systems are faster than others .(.My two cents costs only that).. I believe it has less to do with whether they are compiled and more to do with different styles of abstract “PrologMachine” instructions available. If ZIP instructions have unneeded slowdowns they will be _NOT_ fixed by starting to compile/emit the them into llvm. And not some setting change that could have been made all along to existing workflow.. ZIP will be sped up by adding/changing instructions and detecting when new instructions will be more optimal and updating how existing prolog code will benefit from them.

[Previous page](https://swi-prolog.discourse.group/t/vm-code-refactor-thoughts/3845.md?page=5)