Ann: SWI-Prolog 9.3.14

Releases
1

Dear SWI-Prolog user,

SWI-Prolog 9.3.14 is ready for download. This release fixes some
regression issues resulting from the rather large changes in 9.3.13,
and some portability issues. It has some usability improvements.
Following Jan Burse’s comments, library(nb_set) has been reimplemented
using close hash tables. This does not make much difference for
performance, but the memory usage is about 30% lower.

Enjoy --- Jan

SWI-Prolog Changelog since version 9.3.13

  • DOC: Update library(shlib) documentation.

  • ENHANCED: Re-implement library(nb_set) using closed hash tables.
    This provides better performance at lower memory usage. It comes
    with a few modifications:

    • The term representation is different. This only affects
      applications that access the internals.
    • gen_nb_set/2 enumerates the elements in hash order rather than
      in standard order of terms.
    • Invalid usage now traps nu matching rule errors due to the usage
      of => rules. Used to fail or succeed incorrectly.

  • BUILD: Make sure to clear DISPLAY when running xpce steps
    (one more)

  • BUILD: Make sure to clear DISPLAY when running xpce steps While
    the build works without a DISPLAY variable, an invalid variable causes
    the build to fail.

  • TEST: Disable collation_key/2 test for MacOS Macos Sequoia (15)
    wcsxfrm() returns garbage.

  • FIXED: Avoid corruption in setjmp()/longjmp() Clang demands using
    a volatile variable for protecting the throw environment’s parent.
    This is probably correct, although it seems weird to place this
    variable in a register.

  • ENHANCED: Add Prolog navigator to theme/dark.pl

  • FIXED: build order for dependencies in packs. Based on #1326, but
    fixing build_order/2 rather than reversing afterwards.

  • FIXED: expand_term/2 to succeed twice when expanding a toplevel
    list. Results in duplicate clauses when compiling [f(1), f(2)]..
    Reported by Uwe Neumerkel.

  • FIXED: pack management: find available versions from wildcard URL.
    Patch by Nicos Angelopoulos

  • PORT: Added FreeBSD signal names to the name/number map. Contributed
    by Dewayne Geraghty

  • ENHANCED: file_autoload_directives/3: deal with library(main) hooks.

  • FIXED: Flush pending output on halt/1.

  • FIXED: select_dict/3: deal with attributed variables.

  • CLEANUP: Split select_dict/3 and :</2 code. Although there is some
    shared functionality, the merge complicates things more than it solves.

Package mqi

  • TEST: Specify encoding in test_prologserver.py

  • TEST: Specify encoding in test_prologserver.py Fixes a problem for
    MSYS2. I hope my ad hoc fix is harmless.

(test_prologserver.TestPrologMQI.test_variable_attributes)

Traceback (most recent call last): File
“c:/msys64/home/c7201178/swipl-devel/packages/mqi/python/test_prologserver.py”,
line 95, in setUp
self.initialProcessCount = self.process_count(“swipl”)
^^^^^^^^^^^^^^^^^^^^^^^^^^^
File
“c:/msys64/home/c7201178/swipl-devel/packages/mqi/python/test_prologserver.py”,
line 123, in process_count output =
subprocess.check_output(call).decode()
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ UnicodeDecodeError:
‘utf-8’ codec can’t decode byte 0xff in position 237: invalid start
byte ````

Package plunit

  • FIXED: Report generator state on failing forall(Generator) test.
    This was completely broken. Format has been changed to print the
    generator goal rather than just the variables.

Package xpce

  • ENHANCED: #38 Support themes in navigator.

  • FIXED: #38 Avoid loading the GUI tracer when trace/util.pl is loaded.
    The navigator loads this, but should not load the GUI debugger itself.

  • FIXED: Class tabbed_window: avoid sending ->resize_window when freed.

4 Likes
2

While my original post started with a ChatGPT lead, where I
proposed a rehash threshold of 0.75. I have a new ChatGPT
lead for what was done in release 9.3.14:

  • No Linked Lists for Overflow: Unlike separate chaining, where multiple elements can hash to the same index by storing them in a linked list, open addressing has to resolve collisions within the array itself. This creates a scenario where even a single collision forces a probe sequence, leading to more potential conflicts along the way.

  • Cluster Formation: As more elements are added, clusters (groups of filled slots) can form, especially in linear probing. These clusters grow, making future insertions or lookups within these clusters more prone to further collisions. This effect is called primary clustering and significantly impacts performance as the load factor approaches 1.

We see this, the new implementation is slower. My code snippet
with keeping separate chaining would have improved the 2.204 seconds.
Now the open adressing slows down, needs more inferences:

/* SWI-Prolog 9.3.13 */
?- time(test3).
% 34,383,478 inferences, 2.141 CPU in 2.204 seconds (97% CPU, 16062355 Lips)
true.

/* SWI-Prolog 9.3.14 */
?- time(test3).
% 39,694,226 inferences, 2.609 CPU in 2.657 seconds (98% CPU, 15212158 Lips)
true.

Whether the present open addressing is more memory savy I don’t
know. One surely spares the separate chaining. On the other hand
the new implementation uses a rehash threshold of 0.5,

making the primary table bigger. Test case:

distgen.p.log (842 Bytes)

3

The new implementation depends a bit more on arithmetic. Using -O, the performance difference on this test is about 3%. I think that is a reasonable price for a 30% space reduction. There is probably room for some more optimization. For example, we need a good “empty” entry. As a plain variable is also valid, this is hard. Ideally you’d have a module-local atom or something like that. As is, I use a term and same_term/2.

But … I tried implementing distinct/1,2 and reduced/1,3 using tries. That takes the time for your test down from 1.5 sec to 0.3 seconds. Most of the time is now in generating the data :slight_smile:

The price is that tries cannot handle attributed variables nor cyclic terms. This is often fine, but I wonder whether it is acceptable?

edit Added cycle and attvar test and if found create a new term for variant testing with these extracted. That slows down from 0.3 to 0.45 sec, but it is fully compatible and still provides a good speed improvement. Sooner or later tries will handle attributed variables for implementing constraint support in tabling.

5

term_size/2 gets you the size in cells

6

Ok, one can save quite some memory:

/* SWI-Prolog 9.3.13 */
?- memory(test4).
% Memory 536870912 bytes
true .

/* SWI-Prolog 9.3.14 */
?- memory(test4).
% Memory 268435456 bytes
true

Test Harness was with garbage collection and trim stacks:

memory(G) :-
   garbage_collect, trim_stacks,
   statistics(stack, A),
   G,
   garbage_collect, trim_stacks,
   statistics(stack, B),
   C is B-A,
   write('% Memory '), write(C), write(' bytes'), nl.

Its measuring the distinct cache, and I went to N=10000000:

test4 :-
   offset(6000000, distinct(gen2(_))).

gen2(Z) :-
   between(1,10000000,_),
   random(Y),
   Z is floor(Y*10000000).
7

This is the allocated size for all Prolog stacks in all threads. Better use globalused (after garbage_collect/0). In this case though, calling term_size/2 on the nb_set term is the easiest way to figure out how big it is.