3

I am making extensive use of the swi assoc library. When loading the prolog KB with 160K elements, i notice that significant time goes into looking up and writing new keys into the assoc.

And the assoc that is passed around and includes current state information grows to around 150K bytes/words.

I wonder if there are some higher performance libraries like assoc that could help significantly improve performance at least by one order of magnitude.

thank you,

Daniel

false
  • 10,264
  • 13
  • 101
  • 209
user2193970
  • 345
  • 2
  • 10
  • how does one backtrack with loaded data in the database – user2193970 Jan 02 '18 at 21:53
  • time ago I explored hashtables, but after some trouble porting to YAP - I settled on a simpler interface, an example is [here](https://github.com/CapelliC/prolog-snippets/blob/master/genealogy/allocator.pl) – CapelliC Jan 03 '18 at 07:58
  • thank you. Any idea how this compares performance wise to the assoc data structure – user2193970 Jan 03 '18 at 13:35
  • I think there are two reasons why i couldn't use this implementation as-is: I need several dictionaries working concurrently and, its seems to me that this implementation doesn't handle backtracking -- i.e. to remove entries to the last backtracking point -- if a predicate fails. – user2193970 Jan 03 '18 at 13:59
  • Oops, you're true. Transactional memory required ! The interface could return an attributed variable ? – CapelliC Jan 03 '18 at 14:23

2 Answers2

2

How about using self-balancing red-black trees? SWI-Prolog includes library(rbtrees).

Use it together with iwhen/2 to safeguard against insufficient instantiation like so:

:- use_module(library(rbtrees)).

assoc_to_rb(Ps, T) :-
   iwhen(ground(Ps), groundassoc_to_rb(Ps,T)).

groundassoc_to_rb(Ps0, T) :-
   keysort(Ps0, Ps),
   (  append(_, [K-_,K-_|_], Ps)
   -> throw(error(domain_error(unique_keyed_assoc,Ps0),_))
   ;  list_to_rbtree(Ps, T)
   ).

Sample queries using SWI-Prolog 8.0.0:

?- assoc_to_rb([three-3,two-2,one-1,four-4], T), rb_in(four,Value,T).
   T = t(black('', _7860, _7862, ''), black(black(black('', _7860, _7862, ''), four, 4, black('', _7860, _7862, '')), one, 1, black(black('', _7860, _7862, ''), three, 3, red(black('', _7860, _7862, ''), two, 2, black('', _7860, _7862, ''))))), Value = 4
;  false.

?- assoc_to_rb([3-three,2-two,1-one,4-four,4-vier], T).
ERROR: Domain error: `unique_keyed_assoc' expected, found `[3-three,2-two,1-one,4-four,4-vier]'
repeat
  • 18,496
  • 4
  • 54
  • 166
0

In the SWI-Prolog you can store values in global vars:

backtrackable b: b_setval, b_getval
not backtrackable nb:  nb_setval, nb_getval
besides using dynamic predicates: assert/retract.
Anton Danilov
  • 1,246
  • 11
  • 26