Skip to content

Instantly share code, notes, and snippets.

@jburse
Last active May 1, 2021
Embed
What would you like to do?
/**
* <p>Debugging example.</p>
* <p/>
* Warranty & Liability
* To the extent permitted by applicable law and unless explicitly
* otherwise agreed upon, XLOG Technologies GmbH makes no warranties
* regarding the provided information. XLOG Technologies GmbH assumes
* no liability that any problems might be solved with the information
* provided by XLOG Technologies GmbH.
* <p/>
* Rights & License
* All industrial property rights regarding the information - copyright
* and patent rights in particular - are the sole property of XLOG
* Technologies GmbH. If the company was not the originator of some
* excerpts, XLOG Technologies GmbH has at least obtained the right to
* reproduce, change and translate the information.
* <p/>
* Reproduction is restricted to the whole unaltered document. Reproduction
* of the information is only allowed for non-commercial uses. Selling,
* giving away or letting of the execution of the library is prohibited.
* The library can be distributed as part of your applications and libraries
* for execution provided this comment remains unchanged.
* <p/>
* Restrictions
* Only to be distributed with programs that add significant and primary
* functionality to the library. Not to be distributed with additional
* software intended to replace any components of the library.
* <p/>
* Trademarks
* Jekejeke is a registered trademark of XLOG Technologies GmbH.
*/
package buggy;
public class Buggy {
public static void test() {
System.out.println("Hello World!");
}
}
<!DOCTYPE html>
<!-- Warranty & Liability -->
<!-- To the extent permitted by applicable law and unless explicitly -->
<!-- otherwise agreed upon, XLOG Technologies GmbH makes no warranties -->
<!-- regarding the provided information. XLOG Technologies GmbH assumes -->
<!-- no liability that any problems might be solved with the information -->
<!-- provided by XLOG Technologies GmbH. -->
<!-- -->
<!-- Rights & License -->
<!-- All industrial property rights regarding the information - copyright -->
<!-- and patent rights in particular - are the sole property of XLOG -->
<!-- Technologies GmbH. If the company was not the originator of some -->
<!-- excerpts, XLOG Technologies GmbH has at least obtained the right to -->
<!-- reproduce, change and translate the information. -->
<!-- -->
<!-- Reproduction is restricted to the whole unaltered document. -->
<!-- Reproduction of the information is only allowed for non-commercial -->
<!-- uses. Selling, giving away or letting of the execution of the -->
<!-- library is prohibited. The library can be distributed as part of -->
<!-- your applications and libraries for execution provided this comment -->
<!-- remains unchanged. -->
<!-- -->
<!-- Restrictions -->
<!-- Only to be distributed with programs that add significant and primary -->
<!-- functionality to the library. Not to be distributed with additional -->
<!-- software intended to replace any components of the library. -->
<!-- -->
<!-- Trademarks -->
<!-- Jekejeke is a registered trademark of XLOG Technologies GmbH. -->
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Recursion</title>
</head>
<body>
<h1>Micro Benchmark Elevator Recursion</h1>
<button onclick="main()">Try it</button>
<p id="demo"></p>
<script>
function elevator(n) {
return elevator_(n, 0);
}
function elevator_(n, m) {
if (n == 0) {
return m;
} else {
return elevator_(n - 1, m + 1);
}
}
function main() {
document.getElementById("demo").innerHTML = "elevator(100)="+elevator(100)+"<br>";
t1 = new Date().getMilliseconds();
for (i = 0; i < 10000; i++)
elevator(10000);
t2 = new Date().getMilliseconds();
document.getElementById("demo").innerHTML += "time=" + (t2 - t1) + " (ms)"+"<br>";
t1 = new Date().getMilliseconds();
for (i = 0; i < 10000; i++)
elevator(10000);
t2 = new Date().getMilliseconds();
document.getElementById("demo").innerHTML += "time=" + (t2 - t1) + " (ms)"+"<br>";
}
</script>
</body>
</html>
package misc3.deter;
/**
* Micro Benchmark Elevator Recursion
*
* Warranty & Liability
* To the extent permitted by applicable law and unless explicitly
* otherwise agreed upon, XLOG Technologies GmbH makes no warranties
* regarding the provided information. XLOG Technologies GmbH assumes
* no liability that any problems might be solved with the information
* provided by XLOG Technologies GmbH.
* <p>
* Rights & License
* All industrial property rights regarding the information - copyright
* and patent rights in particular - are the sole property of XLOG
* Technologies GmbH. If the company was not the originator of some
* excerpts, XLOG Technologies GmbH has at least obtained the right to
* reproduce, change and translate the information.
* <p>
* Reproduction is restricted to the whole unaltered document. Reproduction
* of the information is only allowed for non-commercial uses. Selling,
* giving away or letting of the execution of the library is prohibited.
* The library can be distributed as part of your applications and libraries
* for execution provided this comment remains unchanged.
* <p>
* Restrictions
* Only to be distributed with programs that add significant and primary
* functionality to the library. Not to be distributed with additional
* software intended to replace any components of the library.
* <p>
* Trademarks
* Jekejeke is a registered trademark of XLOG Technologies GmbH.
*/
public class Elevator {
private static int elevator(int n) {
return elevator(n, 0);
}
private static int elevator(int n, int m) {
if (n == 0) {
return m;
} else {
return elevator(n - 1, m + 1);
}
}
public static void main(String[] args) {
System.out.println("elevator(100)=" + elevator(100));
long t1 = System.currentTimeMillis();
for (int i = 0; i < 10000; i++)
elevator(10000);
long t2 = System.currentTimeMillis();
System.out.println("time=" + (t2 - t1) + " (ms)");
t1 = System.currentTimeMillis();
for (int i = 0; i < 10000; i++)
elevator(10000);
t2 = System.currentTimeMillis();
System.out.println("time=" + (t2 - t1) + " (ms)");
}
}
<!DOCTYPE html>
<!-- Warranty & Liability -->
<!-- To the extent permitted by applicable law and unless explicitly -->
<!-- otherwise agreed upon, XLOG Technologies GmbH makes no warranties -->
<!-- regarding the provided information. XLOG Technologies GmbH assumes -->
<!-- no liability that any problems might be solved with the information -->
<!-- provided by XLOG Technologies GmbH. -->
<!-- -->
<!-- Rights & License -->
<!-- All industrial property rights regarding the information - copyright -->
<!-- and patent rights in particular - are the sole property of XLOG -->
<!-- Technologies GmbH. If the company was not the originator of some -->
<!-- excerpts, XLOG Technologies GmbH has at least obtained the right to -->
<!-- reproduce, change and translate the information. -->
<!-- -->
<!-- Reproduction is restricted to the whole unaltered document. -->
<!-- Reproduction of the information is only allowed for non-commercial -->
<!-- uses. Selling, giving away or letting of the execution of the -->
<!-- library is prohibited. The library can be distributed as part of -->
<!-- your applications and libraries for execution provided this comment -->
<!-- remains unchanged. -->
<!-- -->
<!-- Restrictions -->
<!-- Only to be distributed with programs that add significant and primary -->
<!-- functionality to the library. Not to be distributed with additional -->
<!-- software intended to replace any components of the library. -->
<!-- -->
<!-- Trademarks -->
<!-- Jekejeke is a registered trademark of XLOG Technologies GmbH. -->
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Loop</title>
</head>
<body>
<h1>Micro Benchmark Elevator Loop</h1>
<button onclick="main()">Try it</button>
<p id="demo"></p>
<script>
function elevator(n) {
return elevator_(n, 0);
}
function elevator_(n, m) {
while (n != 0) {
n--;
m++;
}
return m;
}
function main() {
document.getElementById("demo").innerHTML = "elevator2(100)="+elevator(100)+"<br>";
document.getElementById("demo").innerHTML += "elevator2(BigInt(100))="+elevator(BigInt(100))+"<br>";
t1 = new Date().getMilliseconds();
for (i = 0; i < 10000; i++)
elevator(10000);
t2 = new Date().getMilliseconds();
document.getElementById("demo").innerHTML += "time=" + (t2 - t1) + " (ms)"+"<br>";
t1 = new Date().getMilliseconds();
for (i = 0; i < 10000; i++)
elevator(10000);
t2 = new Date().getMilliseconds();
document.getElementById("demo").innerHTML += "time=" + (t2 - t1) + " (ms)"+"<br>";
}
</script>
</body>
</html>
package misc3.deter;
/**
* Micro Benchmark Elevator Loop
*
* Warranty & Liability
* To the extent permitted by applicable law and unless explicitly
* otherwise agreed upon, XLOG Technologies GmbH makes no warranties
* regarding the provided information. XLOG Technologies GmbH assumes
* no liability that any problems might be solved with the information
* provided by XLOG Technologies GmbH.
* <p>
* Rights & License
* All industrial property rights regarding the information - copyright
* and patent rights in particular - are the sole property of XLOG
* Technologies GmbH. If the company was not the originator of some
* excerpts, XLOG Technologies GmbH has at least obtained the right to
* reproduce, change and translate the information.
* <p>
* Reproduction is restricted to the whole unaltered document. Reproduction
* of the information is only allowed for non-commercial uses. Selling,
* giving away or letting of the execution of the library is prohibited.
* The library can be distributed as part of your applications and libraries
* for execution provided this comment remains unchanged.
* <p>
* Restrictions
* Only to be distributed with programs that add significant and primary
* functionality to the library. Not to be distributed with additional
* software intended to replace any components of the library.
* <p>
* Trademarks
* Jekejeke is a registered trademark of XLOG Technologies GmbH.
*/
public class Elevator2 {
private static int elevator(int n) {
return elevator(n, 0);
}
private static int elevator(int n, int m) {
while (n != 0) {
n--;
m++;
}
return m;
}
public static void main(String[] args) {
System.out.println("elevator2(100)=" + elevator(100));
long t1 = System.currentTimeMillis();
for (int i = 0; i < 10000; i++)
elevator(10000);
long t2 = System.currentTimeMillis();
System.out.println("time=" + (t2 - t1) + " (ms)");
t1 = System.currentTimeMillis();
for (int i = 0; i < 10000; i++)
elevator(10000);
t2 = System.currentTimeMillis();
System.out.println("time=" + (t2 - t1) + " (ms)");
}
}
/**
* Modern Albufeira Prolog Interpreter
*
* Warranty & Liability
* To the extent permitted by applicable law and unless explicitly
* otherwise agreed upon, XLOG Technologies GmbH makes no warranties
* regarding the provided information. XLOG Technologies GmbH assumes
* no liability that any problems might be solved with the information
* provided by XLOG Technologies GmbH.
*
* Rights & License
* All industrial property rights regarding the information - copyright
* and patent rights in particular - are the sole property of XLOG
* Technologies GmbH. If the company was not the originator of some
* excerpts, XLOG Technologies GmbH has at least obtained the right to
* reproduce, change and translate the information.
*
* Reproduction is restricted to the whole unaltered document. Reproduction
* of the information is only allowed for non-commercial uses. Selling,
* giving away or letting of the execution of the library is prohibited.
* The library can be distributed as part of your applications and libraries
* for execution provided this comment remains unchanged.
*
* Restrictions
* Only to be distributed with programs that add significant and primary
* functionality to the library. Not to be distributed with additional
* software intended to replace any components of the library.
*
* Trademarks
* Jekejeke is a registered trademark of XLOG Technologies GmbH.
*/
/**
* Basic Idea:
* Single stack consisting of a pair I-Z by index and compound.
* Variable display consisting of compound V.
* Instructions: atom(C), var(N), functor(F,A), pop
*/
tep(atom(C), _, [I-Z|S], [J-Z|S]) :-
arg(I, Z, C),
J is I+1.
step(var(N), V, [I-Z|S], [J-Z|S]) :-
arg(N, V, W),
arg(I, Z, W),
J is I+1.
step(functor(F,A), _, [I-Z|S], [1-K,J-Z|S]) :-
arg(I, Z, K),
functor(K, F, A),
J is I+1.
step(pop, _, [_|S], S).
exec([X|L], V, S, T) :-
step(X, V, S, H),
exec(L, V, H, T).
exec([], _, S, S).
/* build a term */
?- exec([functor(f, 3), atom(a), functor(g, 2),
atom(b), var(1), pop, var(1), pop], display(W),
[1-result(_)], L).
L = [2-result(f(a, g(b, W), W))]
/* unify a term */
?- exec([functor(f, 3), atom(a), functor(g, 2),
atom(b), var(1), pop, var(1), pop], display(W),
[1-result(f(a,X,Y))], L).
W = Y,
X = g(b, Y),
L = [2-result(f(a, g(b, Y), Y))]
?- exec([functor(f, 3), atom(a), functor(g, 2),
atom(b), var(1), pop, var(1), pop], display(W),
[1-result(f(X,Y))], L).
No
/**
* Sequence Match Problem
* https://stackoverflow.com/q/67301959/502187
* <p/>
* Warranty & Liability
* To the extent permitted by applicable law and unless explicitly
* otherwise agreed upon, XLOG Technologies GmbH makes no warranties
* regarding the provided information. XLOG Technologies GmbH assumes
* no liability that any problems might be solved with the information
* provided by XLOG Technologies GmbH.
* <p/>
* Rights & License
* All industrial property rights regarding the information - copyright
* and patent rights in particular - are the sole property of XLOG
* Technologies GmbH. If the company was not the originator of some
* excerpts, XLOG Technologies GmbH has at least obtained the right to
* reproduce, change and translate the information.
* <p/>
* Reproduction is restricted to the whole unaltered document. Reproduction
* of the information is only allowed for non-commercial uses. Selling,
* giving away or letting of the execution of the library is prohibited.
* The library can be distributed as part of your applications and libraries
* for execution provided this comment remains unchanged.
* <p/>
* Restrictions
* Only to be distributed with programs that add significant and primary
* functionality to the library. Not to be distributed with additional
* software intended to replace any components of the library.
* <p/>
* Trademarks
* Jekejeke is a registered trademark of XLOG Technologies GmbH.
*/
% :- use_module(library(apply_macros)).
% :- use_module(library(apply)).
% :- use_module(library(yall)).
match2(Seq1, Seq2, Count) :-
( maplist([X,Y,X-Y]>>true, Seq1, Seq2, Seq3)
-> aggregate_all(count, (member(X-X, Seq3), X\='_'), Count)
; Count = 0 ).
pair_member(X, Y, [X|_], [Y|_]).
pair_member(X, Y, [_|L], [_|R]) :-
pair_member(X, Y, L, R).
match3(Seq1, Seq2, Count) :-
aggregate_all(count,
(pair_member(X, X, Seq1, Seq2), X \= '_'), Count).
gimme_random_sequence(Length, Seq) :-
length(Seq, Length),
maplist([E]>>(random_between(0,3,Ix), nth0(Ix, [a,t,c,g], E)), Seq).
test(N) :-
gimme_random_sequence(N, S1),
gimme_random_sequence(N, S2),
time(match2(S1, S2, Count)),
time(match3(S1, S2, Count)).
% without library(apply_macros), etc..
% ?- test(100000).
% 1,575,520 inferences, 0.186 CPU in 0.190 seconds (98% CPU, 8465031 Lips)
% 175,519 inferences, 0.018 CPU in 0.019 seconds (98% CPU, 9577595 Lips)
% true.
% with library(apply_macros), etc..
% ?- test(100000).
% % 374,146 inferences, 0.019 CPU in 0.019 seconds (99% CPU, 19379778 Lips)
% % 174,145 inferences, 0.014 CPU in 0.014 seconds (99% CPU, 12400840 Lips)
% true.
/**
* Ackerman Graph
* <p/>
* Warranty & Liability
* To the extent permitted by applicable law and unless explicitly
* otherwise agreed upon, XLOG Technologies GmbH makes no warranties
* regarding the provided information. XLOG Technologies GmbH assumes
* no liability that any problems might be solved with the information
* provided by XLOG Technologies GmbH.
* <p/>
* Rights & License
* All industrial property rights regarding the information - copyright
* and patent rights in particular - are the sole property of XLOG
* Technologies GmbH. If the company was not the originator of some
* excerpts, XLOG Technologies GmbH has at least obtained the right to
* reproduce, change and translate the information.
* <p/>
* Reproduction is restricted to the whole unaltered document. Reproduction
* of the information is only allowed for non-commercial uses. Selling,
* giving away or letting of the execution of the library is prohibited.
* The library can be distributed as part of your applications and libraries
* for execution provided this comment remains unchanged.
* <p/>
* Restrictions
* Only to be distributed with programs that add significant and primary
* functionality to the library. Not to be distributed with additional
* software intended to replace any components of the library.
* <p/>
* Trademarks
* Jekejeke is a registered trademark of XLOG Technologies GmbH.
*/
edge(ack(X, ack(Y, Z)), ack(X, H)) :- !, edge(ack(Y, Z), H).
edge(ack(0, N), X) :- !, X is N+1.
edge(ack(M, 0), ack(H, 1)) :- !, H is M-1.
edge(ack(M, N), ack(H, ack(M, J))) :- H is M-1, J is N-1.
depth(ack(X, Y), N, M) :- !,
edge(ack(X, Y), H),
J is N+1,
depth(H, J, M).
depth(_, N, N).
% ?- depth(ack(3,4), 0, N).
% N = 10307.
@jburse

This comment has been minimized.

Copy link
Owner Author

@jburse jburse commented Apr 17, 2021

Prolog JIT choosing between if-then-else and hash table. (Jekejeke) I

Jekejeke Prolog clause indexing is presented as always building a cascade
of hash tables that point to clause sets. But under the hood there is more
going on. There are situations where hash table are too costly:

  • Expensive Hashvalue:
    Not all datatypes provide a fast hash value computation. In Java
    the immutable String datatype does cache its hash value. But other
    immutable datatypes, like for example BigInteger do not do so.
    Which makes the hash value computation expensive.

  • Expensive Scrambling:
    Not all datatypes provide hash values that are suitable for hash tables.
    For example it is known in Java that the float bit patterns don't work
    well for hash tables. Therefore the hash value has to be scrambled. We
    do so by Murmur which induces further time consuming computation.

  • Expensive Lookup:
    A hash table is a fairly complex data structure. Even after a suitable hash
    key has been computed, the hash table has still to be scanned. This involves
    indirections and equality computation, adding to the time consumption.

Based on this, we have deviced a method to reduce the hash table time
overhead by adaptively switching to if-then-else, which only needs equality
computation. We will explain in more detail whats going on.

Prolog just-in-time indexing assumes a fair amount of runtime memory, but
doesn't need any extra space in the object files. The trade-off choice between
if-then-else and hash table also saves a little runtime memory.

@jburse

This comment has been minimized.

Copy link
Owner Author

@jburse jburse commented Apr 17, 2021

Prolog JIT choosing between if-then-else and hash table. (Jekejeke) II

Jekejeke Prolog builds clause indexes at runtime. Clause indexes are
also maintained for dynamic predicates. So generally the clause indexes
are a dynamic datastructure that can expand or shrink.

By a simple heuristic for this datastructure we decide upon either
a hash table or overwise a scan list, which corresponds to a tranditional
if-then-else. There is a low watermark and a high watermark:

  • High Watermark (MAX_ASSOC_SMALL= 6):
    The clause index starts with a scan list, and converts into
    a hash table when the scan list becomes larger than
    the high watermark.

  • Low Watermark (MIN_ASSOC_LARGE = 3):
    When a clause index is shrunk, the low watermark is
    checked, and a hash table might be converted back to
    a scan list.

Previous to release 1.5.0 we had a Java interface that covers
both kinds of clause indexes. From release 1.5.0 we have simplified
the clause indexes and directly use a base class from our list

utility library. The base class is AbstractAssoc, and the two specialization
AssocArray for scan list and MapHash for hash table. The list
utility library is custom and simpler than the Java library that

classes_small

comes with the Java runtime. For example we do not check for
concurrent modification like the Java runtime does. And therefore
the implementation does not have the burden of a modCount field.

@jburse

This comment has been minimized.

Copy link
Owner Author

@jburse jburse commented Apr 17, 2021

Prolog JIT choosing between if-then-else and hash table. (Jekejeke) III

Was it worth to remove the interface class for release 1.5.0? Only time will
tell. Surely the code got smaller since the result has fewer classes than
before up to release 1.4.7, and we could eliminate the overhead of Java

interface method call. But the price is the use of (pairs instanceof AssocArray)
check here and then, to switch between scan list and hash table. What do
other Prolog systems do? One can compare with SWI-Prolog, we find that

SWI-Prolog does also switch between scan list and hash table. From the
documentation of SWI-Prolog we see:

  • Linear scan on first argument
    The principal clause list maintains a key for the first argument. [...]

  • Hash lookup
    If none of the above applies, the system considers the available hash tables [...]

https://www.swi-prolog.org/pldoc/man?section=jitindex

But unlike SWI-Prolog our use of scan list is not limited to first argument.
Depending on the clause index size it can happen for the first argument or
any other argument or even for a multi-argument index.

The source code of our just-in-time indexing is open source. A link is found at
the end of this post. What we do have on our wish list is deep indexing.
Currently our indexing moves only sideways but doesn't try to enter a compound.

Deep indexing has various applications but the dilemma is to find a quick
just-in-time method, that quicky adjusts depending on call patterns. SWI-Prolog
hints how this could be done, by identifying candidate clause indexes that

do have many compound terms with a common functor. If this criteria is met
it is likely the functor has not enough sensitivity and an attempt to use a deep
index could be rewarding. We might come up with deep indexing some time.

Open Source: Package "rope"
https://github.com/jburse/jekejeke-devel/tree/master/jekrun/headless/jekpro/model/rope

@jburse

This comment has been minimized.

Copy link
Owner Author

@jburse jburse commented Apr 22, 2021

Debugger halts in Java, and then debugger halts in Prolog:

Halt in Java:
image

After pressing Resume Program in Java, halt in Prolog:

Halt in Prolog
image

@jburse

This comment has been minimized.

Copy link
Owner Author

@jburse jburse commented Apr 25, 2021

The WAM is based on registers:

Bildschirmfoto 2021-04-25 um 19 29 09

@jburse

This comment has been minimized.

Copy link
Owner Author

@jburse jburse commented Apr 25, 2021

What are tagged pointers:

Bildschirmfoto 2021-04-25 um 19 36 26

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment