Benchmark of the search times with Visual Prolog 7 internal and external databases

 

 

 

The purpose of this Visual Prolog example project is to show effectiveness differences using internal and external database with different search strategies.

 

The program uses a public domain file of 260,000 English words (word.list).

 

When the programs menu item Search is started for the first time, the program creates internal and external databases. This will take some minutes depending from the speed of your computer. The total size of the formed databases is about 42 Mbytes. So you should check that there is enough space on the hard disk.

 

If someone wants to use this program only for its original goal (helping in finding the right word in a crossword) he should change in file searchDLG.pro

 

facts

benchmark: boolean := true().

to

facts

benchmark: boolean := false().

 

 

The search times depends from many things: Available memory, speed of the hard disk, traffic on the hard disk, disk fragmentation etc. Search times in the example programs benchmark include file opening and reading data in the memory.

 

Search strategies

 

Internal Database

 

  1. Backtracking

 

 

checkWords(IndexList,Length):-

word(w(WORD,Length)),

checkWord(IndexList,strings::stringToCharList(Word)),

fail.

checkWords(_IndexList,_).

 

  1. using findall predicate

 

..

 LIST = [X||findWord(CharList,Length,X)],

..

class predicates

findWord:(indexCharList,unsigned Length,string Word) determ(i,i,o).

clauses

findWord(IndexList,Length,Word):-

word(w(WORD,Length)),

N = checkIndex(IndexList,strings::stringToCharList(Word)),

N = 1,!.

 

External Database

 

  1. Searching scanning through a chain

 

Scanning through a chain in the external database is made with predicates

 

class predicates

scanChain:(chainDB,string ChainName,indexCharList,unsigned).

scanloop:(chainDB,chainDB::ref,indexCharList,unsigned) nondeterm.

clauses

scanChain(DB,CHAIN,CHARS,LEN):-

DB:chain_first(CHAIN,REF),

scanLoop(DB,REF,CHARS,LEN),!.

scanChain(_DBA,_CHAIN,_,_):-!.

 

scanLoop(DB,REF,IndexList,LEN):-

DB:ref_term(REF,W),

W = w(WORD,LEN),

N = checkIndex(IndexList,strings::stringToCharList(WORD)),

N = 1,

assert(found(WORD)),

fail.

scanLoop(DB,REF,I,L):-

DB:chain_next(REF,NREF),!,

scanLoop(DB,NREF,I,L).

scanLoop(_DBA,_REF,_,_):-!.

 

2. Searching using BTree indexes

 

LIST = [X||keys(DB2,INDEX,CharList,X)],

.

class predicates

keys:(chainDB,chainDB::bt_selector,indexCharList,string) nondeterm(i,i,i,o).

keyLoop:(chainDB,chainDB::bt_selector,indexCharList,string) nondeterm(i,i,i,o).

clauses

keys(A,INDEX,IndexList,KEY):-

A:key_first(INDEX,_),

keyloop(A,INDEX,IndexList,KEY).

 

keyloop(A,INDEX,IndexList,KEY):-

A:key_current(INDEX,KEY,_),

N = checkIndex(IndexList,strings::stringToCharList(KEY)),

N = 1.

keyloop(A,INDEX,I,KEY):-

A:key_next(INDEX,_),

keyloop(A,INDEX,I,KEY).

 

Using the program

 

Searching for the words

 

After starting the Search Words menu item there appears a dialog.

 

 

First choose the length of the word (between 2 15 letters).

 

Secondly fill the know letters in their right places (like in the picture above known letters are second letter a, 5th letter is d and the 8th letter is e). Unknown letters are empty.

 

After filling letters press button Search. It depends of the speed of your computer how long it takes before the results can be seen. With relative modern computers it will take 5 10 seconds.

 

Benchmark report

 

After staring this menu option a report with different search tests is created. Then the program loads Internet Explorer which shows the report.

 

 

Example of the report:

 

Letters Lenght of the word Internal database External database in file External database in memory
Backtracking Findall Chain scanning BTree Chain scanning BTree
1 2 1 2 1 2 1 2 1 2 1 2
AVERAGE VALUES 6.6 2.009 0.100 1.472 0.122 2.675 2.406 1.506 1.459 2.638 0.725 2.353 0.100
Standart deviation 2.2 0.144 0.083 0.063 0.094 0.376 0.059 0.855 0.837 0.178 0.120 2.128 0.100
C.D.E.... 9 1.938 0.156 1.563 0.250 3.078 2.438 1.734 1.688 2.609 0.781 0.875 0.250
C.D.E.... 9 2.219 0.219 1.500 0.188 2.359 2.359 1.672 1.609 2.906 0.875 0.938 0.156
AD... 5 1.828 0.031 1.422 0.031 2.531 2.438 0.078 0.063 2.453 0.594 0.594 0.031
AD... 5 2.016 0.047 1.469 0.047 3.078 2.469 1.656 1.609 2.516 0.609 4.641 0.031
AD... 5 2.047 0.047 1.406 0.094 2.328 2.328 2.391 2.328 2.703 0.766 4.719 0.031


1 Including database loading time
2 Excluding database loading time

 

 

 

The classic Prolog speed benchmark

 

The third option is a prolog speed benchmark, a naive reverse benchmark (list of 30 elements, repeated 10000 times). The figures are in "Lips" (Logical Inferences Per Second). The result can be seen in the Message window.

 

The original code for the benchmark (from www.sics.se/isl/sicstus/bench.pl) has only been changed to VP6 format. The file speedTest.pro includes also some comments of different steps in the benchmark.

 

With a 1.7 GHz processor and Windows XP Professional the result was 3.1 MLips.