Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.prolog > #15492

100% Prolog Hash map beats SWI C Trie (Was: VIP0111: Does a Map have a Constructor?)

Show all headers | View raw

Hi,

This is also fun:

% test
test :-
    distinct(dump(_)),
    fail.
test.

The Dogelog Player has a 100% Prolog implemented hash map,
using only some primitives term_hash/2 and (==)/2. While
SWI-Prolog uses a C code trie for distinct/2.

Problem with a trie, a lot of copying from the key term
into the trie sub keys. Right? Whereas my hash map doesn't
copy anything (decoupling), respectively I have program

sharing (PS) via the heap, since Dogelog Player is
a heap (sic!) Prolog system:

% SWI-Prolog 10.1.1
?- between(1,3,_), random_dump, time(test), fail; true.
% 400,009 inferences, 0.594 CPU in 0.635 seconds (94% CPU, 673699 Lips)
% 400,009 inferences, 0.578 CPU in 0.636 seconds (91% CPU, 691907 Lips)
% 400,009 inferences, 0.562 CPU in 0.640 seconds (88% CPU, 711127 Lips)
% true.

% Dogelog 2.1.6 for Java
?- between(1,3,_), random_dump, time(test), fail; true.
% Zeit 358.544 ms, GC 0.000 ms, Lips 20350 k
% Zeit 346.934 ms, GC 0.000 ms, Lips 21019 k
% Zeit 356.943 ms, GC 0.000 ms, Lips 20434 k
true.

The above is a preview, it uses a new feature of
Dogelog Player frozen compounds, namely pre-
computed hashes. The SWI C Trie overhead could be

also somewhere else, maybe acyclic_term/1 is slow?
I do a similar thing in my code as well, so I am
not comparing oranges with apples, its rather

a comparison apples with apples.

Have Fun!

Bye

Mild Shock schrieb:
> Hi,
> 
> How would we do a reverse sorted map?
> 
> I find in Java:
> 
> TreeMap(Comparator<? super K> comparator)
> Constructs a new, empty tree map, ordered
> according to the given comparator.
> https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html
> 
> Or in Dogelog Player:
> 
> tree_new(T):
> tree_new(T, F):
> The predicate succeeds in R with a new red-black tree.
> The binary predicate allows specifying a term compare F.
> https://www.dogelog.ch/typtab/doclet/book/12_lang/05_libraries/03_util/06_tree.html 
> 
> 
> Here is an example, using the destructive API. But
> the same constructor works also for the non-destructive API.
> 
> ?- tree_new(_T), tree_add(_T, 0rInf, foo),
>     tree_add(_T, 0rNaN, bar), tree_pairs(_T, L).
> L = [0rNaN-bar, 0rInf-foo].
> 
> And now using a comparator modifier, aggregate with a comparator,
> as a closure. Some Joy of Higher Order logic programming:
> 
> reverse(C, R, X, Y) :- call(C, R, Y, X).
> 
> ?- tree_new(_T,reverse(compare)), tree_add(_T, 0rInf, foo),
>     tree_add(_T, 0rNaN, bar), tree_pairs(_T, L).
> L = [0rInf-foo, 0rNaN-bar].
> 
> ?- tree_new(_T,reverse(reverse(compare))), tree_add(_T, 0rInf, foo),
>     tree_add(_T, 0rNaN, bar), tree_pairs(_T, L).
> L = [0rNaN-bar, 0rInf-foo].
> 
> Just toying around with my new NaNs.
> 
> Have Fun!
> 
> Bye
> 
> Mild Shock schrieb:
>> Hi,
>>
>> Functional requirement:
>>
>> ?- Y = g(_,_), X = f(Y,C,D,Y), term_singletons(X, L),
>>     L == [C,D].
>>
>> ?- Y = g(A,X,B), X = f(Y,C,D), term_singletons(X, L),
>>     L == [A,B,C,D].
>>
>> Non-Functional requirement:
>>
>> ?- member(N,[5,10,15]), time(singletons(N)), fail; true.
>> % Zeit 1 ms, GC 0 ms, Lips 4046000, Uhr 11.08.2025 01:36
>> % Zeit 3 ms, GC 0 ms, Lips 1352000, Uhr 11.08.2025 01:36
>> % Zeit 3 ms, GC 0 ms, Lips 1355333, Uhr 11.08.2025 01:36
>> true.
>>
>> Can your Prolog system do that?
>>
>> P.S.: Benchmark was:
>>
>> singletons(N) :-
>>     hydra2(N,Y),
>>     between(1,1000,_), term_singletons(Y,_), fail; true.
>>
>> hydra2(0, _) :- !.
>> hydra2(N, s(X,X)) :-
>>     M is N-1,
>>     hydra2(M, X).
>>
>> Bye
> 

Back to comp.lang.prolog | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

VIP0909: VibeCore Improvement Proposal Mild Shock <janburse@fastmail.fm> - 2025-08-11 11:35 +0200
  VIP0111: Does a Map have a Constructor? (Was: VIP0909: VibeCore Improvement Proposal) Mild Shock <janburse@fastmail.fm> - 2026-03-14 18:11 +0100
    100% Prolog Hash map beats SWI C Trie (Was: VIP0111: Does a Map have a Constructor?) Mild Shock <janburse@fastmail.fm> - 2026-03-17 04:07 +0100

csiph-web