Optimizing symbolic processing code

Optimizing symbolic processing code

[Hugo Ferreira]

Hello,

I have implemented a simple Prolog like inference engine
to be used in machine learning algorithms (ILP). My first
basic test shows that inference is dismally slow (compared
to a Prolog compiler). Consequently I am looking for
information on optimizing the code. I have found:

http://ocaml.janestreet.com/?q=node/30
http://camltastic.blogspot.com/2008/05/optimizing-memory-allocation-and-loops.html

Does anyone have any other links or articles I may look at?

TIA,
Hugo F.

Re: [Caml-list] Optimizing symbolic processing code

[blue storm]

On 1/16/09, Hugo Ferreira <hmf@inescporto.pt> wrote:
> I have implemented a simple Prolog like inference engine
> to be used in machine learning algorithms (ILP). My first
> basic test shows that inference is dismally slow (compared
> to a Prolog compiler). Consequently I am looking for
> information on optimizing the code.

Before trying low-level optimizations, i suggest you check carefully
your implementation. It's a bit strange that your performance is so
bad, and i suspect there could be improvement of algorithmic nature.

There have been successful translations of Prolog to OCaml before :
http://groups.google.com/group/comp.lang.prolog/msg/28c4361bb5f865b8?pli=1
, wich is quite different as it uses the ocaml compiler itself to get
good performances.

Re: [Caml-list] Optimizing symbolic processing code

[Hugo Ferreira]

blue storm wrote:
> On 1/16/09, Hugo Ferreira <hmf@inescporto.pt> wrote:
>> I have implemented a simple Prolog like inference engine
>> to be used in machine learning algorithms (ILP). My first
>> basic test shows that inference is dismally slow (compared
>> to a Prolog compiler). Consequently I am looking for
>> information on optimizing the code.
> 
> Before trying low-level optimizations, i suggest you check carefully
> your implementation. It's a bit strange that your performance is so
> bad, and i suspect there could be improvement of algorithmic nature.
> 

Don't think it is algorithmic. The test specifically targets the
discriminant tree I developed according to the descriptions found
in various articles.

Note that the Prolog implementation tested also requires some time to
solve the problem. Now, I don't expect to have the same performance
as an optimized inference engine but... its so much slower.


> There have been successful translations of Prolog to OCaml before :
> http://groups.google.com/group/comp.lang.prolog/msg/28c4361bb5f865b8?pli=1
> , wich is quite different as it uses the ocaml compiler itself to get
> good performances.
> 

Yes I know of this. However the need to some additional stuff (forward
clause subsumption testing, coverage counting, clause ranking, etc.)
that are specific to the learning algorithm has prompted me to develop
this code.

Regards,
Hugo F.

Re: [Caml-list] Optimizing symbolic processing code

[Jon Harrop]

On Friday 16 January 2009 08:42:52 Hugo Ferreira wrote:
> Hello,
>
> I have implemented a simple Prolog like inference engine
> to be used in machine learning algorithms (ILP). My first
> basic test shows that inference is dismally slow (compared
> to a Prolog compiler).

Can you quantify that?

> Consequently I am looking for information on optimizing the code.

IIRC, the single most productive optimization I made to the Mathematica 
implementation I wrote in OCaml was to check when recursive rewrites were 
leaving an expression unaltered and return the original when possible to 
avoid copying. I don't know if that is relevant here.

Also IIRC, someone else wrote that they lashed together a quick Prolog 
implementation in OCaml and were surprised to find it outperforming real 
Prolog compilers.

> I have found: 
>
> http://ocaml.janestreet.com/?q=node/30
> http://camltastic.blogspot.com/2008/05/optimizing-memory-allocation-and-loo
>ps.html
>
> Does anyone have any other links or articles I may look at?

The articles on low-level optimization in the OCaml Journal are almost 
certainly relevant. OCaml for Scientists covers data structure performance in 
detail. No other sources are as comprehensive with regard to optimization 
AFAIK.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] Optimizing symbolic processing code

[Hugo Ferreira]

Jon Harrop wrote:
> On Friday 16 January 2009 08:42:52 Hugo Ferreira wrote:
>> Hello,
>>
>> I have implemented a simple Prolog like inference engine
>> to be used in machine learning algorithms (ILP). My first
>> basic test shows that inference is dismally slow (compared
>> to a Prolog compiler).
> 
> Can you quantify that?
> 

Yes. Give or take a second I get the following embarrassingly large
difference:

~/workspace/planner$ time swipl -f prolog.pl -g "win(A, B, C, D, E, F), 
halt."
/home/hugof/workspace/planner/docs/prolog.pl compiled 0.00 sec, 8,560 bytes

real    0m30.278s
user    0m30.222s
sys     0m0.012s

~/workspace/planner$ time ./itest_1.p.native
real	19m12.786s
user	19m6.728s
sys	0m0.196s


>> Consequently I am looking for information on optimizing the code.
> 
> IIRC, the single most productive optimization I made to the Mathematica 
> implementation I wrote in OCaml was to check when recursive rewrites were 
> leaving an expression unaltered and return the original when possible to 
> avoid copying. I don't know if that is relevant here.
> 

Unfortunately not. I am just scanning the Trie repeatedly. I do this
using functional like code using only folds and finds.

> Also IIRC, someone else wrote that they lashed together a quick Prolog 
> implementation in OCaml and were surprised to find it outperforming real 
> Prolog compilers.
> 

Yep. Blue Strom has already pointed out the link. Not quite what I am
looking for.

>> I have found: 
>>
>> http://ocaml.janestreet.com/?q=node/30
>> http://camltastic.blogspot.com/2008/05/optimizing-memory-allocation-and-loo
>> ps.html
>>
>> Does anyone have any other links or articles I may look at?
> 
> The articles on low-level optimization in the OCaml Journal are almost 
> certainly relevant. OCaml for Scientists covers data structure performance in 
> detail. No other sources are as comprehensive with regard to optimization 
> AFAIK.
> 

Was afraid of that.

Thanks.
HF.

Re: [Caml-list] Optimizing symbolic processing code

[Peter Ilberg]

On Friday 16 January 2009 08:42:52 Hugo Ferreira wrote:

> I have implemented a simple Prolog like inference engine
> to be used in machine learning algorithms (ILP). My first
> basic test shows that inference is dismally slow (compared
> to a Prolog compiler).

> Consequently I am looking for information on optimizing the code.

For implementing a Prolog-like language, you might want to look at
this book on the Warren Abstract Machine:

http://web.archive.org/web/20030213072337/http://www.vanx.org/archive/wam/wam.html

You might also want to look at 'KANREN' and specifically 'miniKANREN':

http://kanren.sourceforge.net/

miniKANREN is a simple declarative logic programming system embedded
into Scheme. I don't know how efficient the system is, but it might
give you further ideas on how to implement such a system.

--- Peter

Re: [Caml-list] Optimizing symbolic processing code

[Hugo Ferreira]

Peter Ilberg wrote:
> On Friday 16 January 2009 08:42:52 Hugo Ferreira wrote:
> 
>> I have implemented a simple Prolog like inference engine
>> to be used in machine learning algorithms (ILP). My first
>> basic test shows that inference is dismally slow (compared
>> to a Prolog compiler).
> 
>> Consequently I am looking for information on optimizing the code.
> 
> For implementing a Prolog-like language, you might want to look at
> this book on the Warren Abstract Machine:
> 
> http://web.archive.org/web/20030213072337/http://www.vanx.org/archive/wam/wam.html 
> 

Ok, new of this document. But I think this demands too-much effort.

> 
> You might also want to look at 'KANREN' and specifically 'miniKANREN':
> 
> http://kanren.sourceforge.net/
> 
> miniKANREN is a simple declarative logic programming system embedded
> into Scheme. I don't know how efficient the system is, but it might
> give you further ideas on how to implement such a system.
> 

Did not know about this. I'll take a look.

Thanks,
Hugo F.


> --- Peter
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 

Re: [Caml-list] Optimizing symbolic processing code

[Andrej Bauer]

On Fri, Jan 16, 2009 at 5:19 PM, Hugo Ferreira <hmf@inescporto.pt> wrote:
>> http://web.archive.org/web/20030213072337/http://www.vanx.org/archive/wam/wam.html
>
> Ok, new of this document. But I think this demands too-much effort.

Judging from what your responses, the most probable explanation for
inefficiency is that you implemented your prolog interpreter badly. It
would help a lot if you just showed us your code.

Best regards,

andrej

Re: [Caml-list] Optimizing symbolic processing code

[Andrej Bauer]

After being so bad spirited in my last message, I decided to make it
up by doing something positive. I have added to the PL Zoo a mini
prolog interpreter, see http://andrej.com/plzoo/ . It is very slow and
I am sure a decent implementation would speed it up by an order of
magnitude (at least a 100 fold). I wonder how your implementation
compares to mine.

Best regards,

Andrej

Re: [Caml-list] Optimizing symbolic processing code

[Kuba Ober]

On Jan 16, 2009, at 11:19 AM, Hugo Ferreira wrote:

> Peter Ilberg wrote:
>> On Friday 16 January 2009 08:42:52 Hugo Ferreira wrote:
>>> I have implemented a simple Prolog like inference engine
>>> to be used in machine learning algorithms (ILP). My first
>>> basic test shows that inference is dismally slow (compared
>>> to a Prolog compiler).
>>> Consequently I am looking for information on optimizing the code.
>> For implementing a Prolog-like language, you might want to look at
>> this book on the Warren Abstract Machine:
>> http://web.archive.org/web/20030213072337/http://www.vanx.org/archive/wam/wam.html
>
> Ok, new of this document. But I think this demands too-much effort.

What you expect, basically, is for OCaml to magically translate your
likely cobbled-together, slowly performing interpreter into a bytecode
compiler and a VM.

That ain't happening, and it's not OCaml's fault. Try compiling your  
code
in F# and see how fast it runs - I doubt you'll see an improvement of
more than an order of magnitude, unless you're really unlucky to hit
some OCaml's deficiencies. I doubt that SWI Prolog would be
substantially (as in more than an order of magnitude linear constant)  
slower
if it were ported to OCaml.

Writing a well-performing Prolog system is not an overnight task, at  
least
not without using some decent compiler/system building libraries, which
may not even exist.

Cheers, Kuba

Re: [Caml-list] Optimizing symbolic processing code

[Hugo Ferreira]

Andrej,

First and foremost thanks for taking the time to answer.

Andrej Bauer wrote:
> After being so bad spirited in my last message, I decided to make it
> up by doing something positive. I have added to the PL Zoo a mini
> prolog interpreter, see http://andrej.com/plzoo/ . 

Interesting. I had visited this page for a quick look and never
realized (or don't remember) seeing any Prolog interpreter.

> It is very slow and

Maybe be slow, but it is very clear and concise.

> I am sure a decent implementation would speed it up by an order of
> magnitude (at least a 100 fold). 

Indeed this may be possible.

> I wonder how your implementation
> compares to mine.
> 

I will go through your code in the order it is available:

1) First thing I noticed is that you have very few type of terms.
    In my case I add parsing and unification of integers, strings,
    lists, negation (not), etc. I also added some extras because
    I use the same parser to manipulate first order logic
    sentences used  by a AI planner.

2) Your parsing doesn't construct a symbol table. So this means
    that all comparisons are string based. In my case all
    comparisons are integer based i.e: everything from a predicate
    symbol to a constant is an integer.

3) Your variable bank is based on a list. This means that any
    look-up requires linear time. I use arrays for this. This
    has effects on unification.

4) Related to the above I use a Union-Find implementation
    (See http://www.lri.fr/~filliatr/ for the implementation
     I use) to bind variables. I have also experimented with
    another data structure for this, but this implementation
    is simple and fast although mutable.

5) Your unification algorithm looks like a standard (at-worst)
    quadric order unifier, which is not too bad. However you
    use your linear list of substitutions (3+4). What is more
    your occurs check is done on every variable - term binding.
    I on the other hand, use a near-linear algorithm using fast
    union-find and do a occurs check only at the end for only
    those terms bound to variable and again using the U-F data
    structure.

6) Ok, this one is the one that seems to be killing my application.
    You use a very simple database, its basically a list of
    assertions. Any look-up is linear in respect to the number of
    assertions, which means that resolution of a goal is exponential
    in respect to the number of assertions and number of goals. I
    use a discriminant trie whose search is linear in respect to
    the number of goal (as opposed to the assertions).

7) Before unification you take care of performing variable
    renaming. This has to be repeated every time you use a
    predicate. I use clauses represented in a canonical form.
    Renaming for me is simply a matter of bumping a counter of
    variables in the variable bank and attaching this offset to
    the terms in question. I also "reuse" variables because of
    the way the variable bank is implemented.

8) Your algorithm is a very clean implementation of SLDNF.
    You keep a stack of sorts and allow one to continue search
    for the next goal. One of my implementations did this however
    keeping track of the position in a trie resulted in complicated
    code. I now use simple folds over the data structure. A
    function is invoked whenever a solution is found. If only one
    solution is required then a quick exit is performed via an
    exception. In your case your implementation is simpler because
    it uses only lists.

Ok, in respect to your first response:

 > Judging from what your responses, the most probable explanation for
 > inefficiency is that you implemented your prolog interpreter badly.

Possibly yes, but from what I have explained above you can see I have
taken pains to have a decent intepreter.

 > It would help a lot if you just showed us your code.

True. But the problem is I did not know what was killing performance,
hence the request for more information on how to diagnose the problem.
Only then would I analyse further and ask for help with more details.

I have compiled and executed the code with profiling. "grpof" shows
that about 8-10 % of the time is spent on folding over the trie (I
use map folds and finds, why are map folds taking so long?). In other
words it is not an issue on unification or the resolution function but
the search in the trie. I also find calls to caml currying functions.
This seems to point me to [1] for solutions.

I am going to make some additional experiments in order to diagnose
the problem further.

One simple question: is Ocaml matching fast enough that I need
not worry with:

a) the number of variants in a type
b) comparisons of the sort:

and bind_all_var_to_any f h ps t delay acc =
   (* k a b -> b *)
   let scan k e acc =
     match e with
     | Leaf _ -> acc
     | Node(Pred.Rel _,ps',vs',jps',jvs') ->
             (* jump over ptedicate *)
             fold_all f jps' jvs' t delay acc

     | Node(_,ps',vs',jps',jvs') ->
             fold_all f ps' vs' t delay acc
    in
    Node_map.fold (scan) ps acc


Once again, appreciate any comments on the above.

Regards,
Hugo F.

[1] http://ocaml.janestreet.com/?q=node/30









> Best regards,
> 
> Andrej
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 

Re: [Caml-list] Optimizing symbolic processing code

[Hugo Ferreira]

Hello,

Kuba Ober wrote:
 >
 > On Jan 16, 2009, at 11:19 AM, Hugo Ferreira wrote:
 >
 >> Peter Ilberg wrote:
 >>> On Friday 16 January 2009 08:42:52 Hugo Ferreira wrote:
 >>>> I have implemented a simple Prolog like inference engine
 >>>> to be used in machine learning algorithms (ILP). My first
 >>>> basic test shows that inference is dismally slow (compared
 >>>> to a Prolog compiler).
 >>>> Consequently I am looking for information on optimizing the code.
 >>> For implementing a Prolog-like language, you might want to look at
 >>> this book on the Warren Abstract Machine:
 >>> 
http://web.archive.org/web/20030213072337/http://www.vanx.org/archive/wam/wam.html 

 >>>
 >>
 >> Ok, new of this document. But I think this demands too-much effort.
 >
 > What you expect, basically, is for OCaml to magically translate your
 > likely cobbled-together, slowly performing interpreter into a bytecode
 > compiler and a VM.
 >

See response to Andrej Bauer's e-mail please.

 > That ain't happening, and it's not OCaml's fault. Try compiling your
 > code in F# and see how fast it runs - I doubt you'll see an
 > improvement of more than an order of magnitude, unless you're really
 > unlucky to hit some OCaml's deficiencies.

This is exactly the type of information I am looking for.
What deficiencies does Ocaml have that may cause efficiency problems?
How should one go about looking for these problems?
What can one do to avoid or correct these problems?

 > I doubt that SWI Prolog would be
 > substantially (as in more than an order of magnitude linear constant)
 > slower
 > if it were ported to OCaml.
 >

Let me make this clear: I am not attempting to port anything.
I want a resolution based system to be used in a learning algorithm.
Naturally I want performance on par with possibly less efficient
Prolog implementations like SWI (BTW, SWI is my preferred Prolog 
interpreter, so don't misread what I just said). In fact I don't
need much of Prolog's programming capabilities (otherwise I would
have used Prolog).

 > Writing a well-performing Prolog system is not an overnight task, at
 > least not without using some decent compiler/system building
 > libraries, which may not even exist.
 >

Admittedly I am no expert in this or any other area for that matter.
Nevertheless this has not been "an overnight task". Again see
response to Andrej Bauer's e-mail please.

Hugo F.


 > Cheers, Kuba
 >
 > _______________________________________________
 > Caml-list mailing list. Subscription management:
 > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
 > Archives: http://caml.inria.fr
 > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
 > Bug reports: http://caml.inria.fr/bin/caml-bugs
 >

Re: [Caml-list] Optimizing symbolic processing code

[Andrej Bauer]

Dear Hugo,

you have not noticed miniprolog before because it was not there until yesterday.

Almost any optimization will cause my interpreter to go much faster. I
think the most reasonable one to do would be to avoid explicit
subtitutions during unification (since I already keep track of the
environment), but then I get into the union-find business.

I would not be too sure that lists are much slower than arrays when
the lists and arrays are both short. You might be yet another victim
of premature optimization.

How does the performance of your prolog compare to my miniprolog?
Judging from the care you took with your interpreter, yours should be
much faster. It should be easy to run the same program on both and see
what happens.

Best regards,

Andrej

Re: [Caml-list] Optimizing symbolic processing code

[Hugo Ferreira]

[-- Attachment #1: Type: text/plain, Size: 5100 bytes --]

Hello Andrej,

Andrej Bauer wrote:
> Dear Hugo,
> 
> you have not noticed miniprolog before because it was not there until yesterday.
> 

I see.

> Almost any optimization will cause my interpreter to go much faster. 

Not quite. It depends a lot on the problem to solve and the order
in which the knowledge base is declared. More on this later.

> I think the most reasonable one to do would be to avoid explicit
> subtitutions during unification 

Not quite. You still need to deal with creating and using new
variables somewhere, somehow.

> (since I already keep track of the
> environment), but then I get into the union-find business.
> 
> I would not be too sure that lists are much slower than arrays when
> the lists and arrays are both short. 

The reason why I used arrays is because the union-find data
structure uses arrays, specifically persistent arrays implemented
using standard arrays.

> You might be yet another victim
> of premature optimization.
>

Maybe. But I haven't really done any optimization save for using
"standard" data structures and techniques in resolution.

> How does the performance of your prolog compare to my miniprolog?

~/Desktop/prolog_test/miniprolog$ time ./miniprolog.native -n prolog.pl
A = p
B = r
C = o
D = l
E = o
F = g
real    12m14.648s
user    12m8.606s
sys     0m0.168s

versus my

~/workspace/planner$ time ./itest_1.p.native
real    19m12.786s
user    19m6.728s
sys    0m0.196s

Note that I changed your code slightly to terminate after the
first solution. See changes below.

> Judging from the care you took with your interpreter, yours should be
> much faster. 

This depends on the problem. I have attached the Prolog code for
you to see and experiment with. You will notice that the order
of the assertions are done so as to make resolution very difficult.

Notice however that:

1) Care was taken so that (nearly) all assertions you compare with are
    the same one (letter/1) so indexing won't help.

2) These predicates also use a single variable so copying during
    renaming is cheap.

3) Lastly unification only binds with one variable so the unification
    algorithm will also not determine the efficiency of the application.

What does determine the speed of execution is basically how quickly one
can scan the available (candidate) predicates to form the resolvent,
update the stack and quickly backtrack to the next candidate. Your code
in this respect is "optimal" because it uses a simple lists for both
scanning and keeping track of the variables.

> It should be easy to run the same program on both and see
> what happens.
> 

The results are, I think, consistent. Consider:

a) We have more or less the same order of magnitude in execution times.

b) Note that _my_ code should be a little _slower_ given that none of
    its "optimizations" are useful and only make running times larger.
    However the difference of 7 minutes is I believe too large.

c) Given the very simple mechanisms required to solve this problem, I
    figure only low-level stuff will make your "optimal" application
    faster for the test problem (I haven't tried but you can also
    consider using single letter predicate names to measure the weight
    that string comparisons have, should speed up things).


Which brings me to the initial question. Why such a big gap between SWI 
Prolog for example and our Ocaml code?

~/workspace/planner$ time swipl -f prolog.pl -g "win(A, B, C, D, E, F),
halt."
/home/hugof/workspace/planner/docs/prolog.pl compiled 0.00 sec, 8,560 bytes

real    0m30.278s
user    0m30.222s
sys     0m0.012s

Stack use, function calls, tail recursion, currying, garbage collection
and many other issues could be to blame. My question is what can it be,
how may I diagnose it, what can I do to speed things up.

Finally, for those that may think I may be simply giving to much
importance to this, consider that I need to execute resolution
hundreds of thousands of times for the ML algorithm.

Once again, any suggestions are welcome.

Regards,
Hugo F.


> Best regards,
> 
> Andrej
> 


(** [display_solution ch env] displays the solution of a goal encoded
     by [env]. It then gives the user the option to search for other
     solutions, as described by the list of choice points [ch], or to abort
     the current proof search. *)
let rec display_solution ch env =
   match string_of_env env, ch with
     | "Yes", _ -> print_endline "Yes"
     | answer, [] -> print_endline answer
     | answer, ch -> begin
         print_string answer ; Pervasives.exit 1  <-------- Changes !!
         (*
	print_string (answer ^ "\nmore? (y/n) [y] ") ;
	flush stdout ;
	match String.lowercase (read_line ()) with
	  | "y" | "yes" | "" -> continue_search ch
	  | _ -> raise NoSolution
          *)
       end


> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 


[-- Attachment #2: prolog.pl --]
[-- Type: application/x-perl, Size: 711 bytes --]

Re: [Caml-list] Optimizing symbolic processing code

[Hugo Ferreira]

[-- Attachment #1: Type: text/plain, Size: 6305 bytes --]

Hello,

Just to rule out the issue with string comparison, I did a test
by changing the predicate names names. I include the Prolog
code for you. The results are:

~/Desktop/prolog_test/miniprolog$ time ./miniprolog.native -n prolog_opt.pl
A = p
B = r
C = o
D = l
E = o
F = g
real    11m27.547s
user    11m19.870s
sys     0m0.204s

So we may add to the conclusions that the use of symbol tables in this
problem also doesn't have much weight because we only shaved off a
"measly" minute.


Regards,
Hugo F.


Hugo Ferreira wrote:
> Hello Andrej,
> 
> Andrej Bauer wrote:
>> Dear Hugo,
>>
>> you have not noticed miniprolog before because it was not there until 
>> yesterday.
>>
> 
> I see.
> 
>> Almost any optimization will cause my interpreter to go much faster. 
> 
> Not quite. It depends a lot on the problem to solve and the order
> in which the knowledge base is declared. More on this later.
> 
>> I think the most reasonable one to do would be to avoid explicit
>> subtitutions during unification 
> 
> Not quite. You still need to deal with creating and using new
> variables somewhere, somehow.
> 
>> (since I already keep track of the
>> environment), but then I get into the union-find business.
>>
>> I would not be too sure that lists are much slower than arrays when
>> the lists and arrays are both short. 
> 
> The reason why I used arrays is because the union-find data
> structure uses arrays, specifically persistent arrays implemented
> using standard arrays.
> 
>> You might be yet another victim
>> of premature optimization.
>>
> 
> Maybe. But I haven't really done any optimization save for using
> "standard" data structures and techniques in resolution.
> 
>> How does the performance of your prolog compare to my miniprolog?
> 
> ~/Desktop/prolog_test/miniprolog$ time ./miniprolog.native -n prolog.pl
> A = p
> B = r
> C = o
> D = l
> E = o
> F = g
> real    12m14.648s
> user    12m8.606s
> sys     0m0.168s
> 
> versus my
> 
> ~/workspace/planner$ time ./itest_1.p.native
> real    19m12.786s
> user    19m6.728s
> sys    0m0.196s
> 
> Note that I changed your code slightly to terminate after the
> first solution. See changes below.
> 
>> Judging from the care you took with your interpreter, yours should be
>> much faster. 
> 
> This depends on the problem. I have attached the Prolog code for
> you to see and experiment with. You will notice that the order
> of the assertions are done so as to make resolution very difficult.
> 
> Notice however that:
> 
> 1) Care was taken so that (nearly) all assertions you compare with are
>    the same one (letter/1) so indexing won't help.
> 
> 2) These predicates also use a single variable so copying during
>    renaming is cheap.
> 
> 3) Lastly unification only binds with one variable so the unification
>    algorithm will also not determine the efficiency of the application.
> 
> What does determine the speed of execution is basically how quickly one
> can scan the available (candidate) predicates to form the resolvent,
> update the stack and quickly backtrack to the next candidate. Your code
> in this respect is "optimal" because it uses a simple lists for both
> scanning and keeping track of the variables.
> 
>> It should be easy to run the same program on both and see
>> what happens.
>>
> 
> The results are, I think, consistent. Consider:
> 
> a) We have more or less the same order of magnitude in execution times.
> 
> b) Note that _my_ code should be a little _slower_ given that none of
>    its "optimizations" are useful and only make running times larger.
>    However the difference of 7 minutes is I believe too large.
> 
> c) Given the very simple mechanisms required to solve this problem, I
>    figure only low-level stuff will make your "optimal" application
>    faster for the test problem (I haven't tried but you can also
>    consider using single letter predicate names to measure the weight
>    that string comparisons have, should speed up things).
> 
> 
> Which brings me to the initial question. Why such a big gap between SWI 
> Prolog for example and our Ocaml code?
> 
> ~/workspace/planner$ time swipl -f prolog.pl -g "win(A, B, C, D, E, F),
> halt."
> /home/hugof/workspace/planner/docs/prolog.pl compiled 0.00 sec, 8,560 bytes
> 
> real    0m30.278s
> user    0m30.222s
> sys     0m0.012s
> 
> Stack use, function calls, tail recursion, currying, garbage collection
> and many other issues could be to blame. My question is what can it be,
> how may I diagnose it, what can I do to speed things up.
> 
> Finally, for those that may think I may be simply giving to much
> importance to this, consider that I need to execute resolution
> hundreds of thousands of times for the ML algorithm.
> 
> Once again, any suggestions are welcome.
> 
> Regards,
> Hugo F.
> 
> 
>> Best regards,
>>
>> Andrej
>>
> 
> 
> (** [display_solution ch env] displays the solution of a goal encoded
>     by [env]. It then gives the user the option to search for other
>     solutions, as described by the list of choice points [ch], or to abort
>     the current proof search. *)
> let rec display_solution ch env =
>   match string_of_env env, ch with
>     | "Yes", _ -> print_endline "Yes"
>     | answer, [] -> print_endline answer
>     | answer, ch -> begin
>         print_string answer ; Pervasives.exit 1  <-------- Changes !!
>         (*
>     print_string (answer ^ "\nmore? (y/n) [y] ") ;
>     flush stdout ;
>     match String.lowercase (read_line ()) with
>       | "y" | "yes" | "" -> continue_search ch
>       | _ -> raise NoSolution
>          *)
>       end
> 
> 
>> _______________________________________________
>> Caml-list mailing list. Subscription management:
>> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
>> Archives: http://caml.inria.fr
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>>
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs


[-- Attachment #2: prolog_opt.pl --]
[-- Type: application/x-perl, Size: 506 bytes --]