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.
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.
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,
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
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.
I just was wondering how space is measured? Was looking
into statistics/2 recently. Would you call statistics(stack, X) ?
And maybe call a garbage collection before hand?
I would like to run the test case and measure not only time
but also memory usage. Are all Prolog data structures for library(nb_set) allocated on the stacks?
BTW: Concerning the random test case, which picks
1000 random numbers in the range 1-1000, you get a kind
of Birthday Paradox in action!
?- aggregate_all(count, distinct(gen(Z)), A), B is 1000-A.
A = 629,
B = 371.
The count is usually lower than 1000, so randomly in the average
you get like ca. 36.7% of the elements have a distinct cache hit
anyway. This is from the test file distgen.p:
gen(Z) :-
between(1,1000,_),
random(Y),
Z is floor(Y*1000).
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.
