Understanding Scryer's stack frame management

[dnmfarrell]

Hi,
I have two rules for calculating the height of a binary tree dictionary:

height(Dict,Height) :-
  (   Dict = nil ->
      Height = -1
  ;   height_([0-Dict|Hole],Hole,Height)
  ).

height_([Depth-Dict|TasksLeft],Hole,Height) :-
  Dict = dict(_, Left, Right),
  Depth1 is Depth + 1,
  (   Left = nil ->
      Hole = Hole1
  ;   Hole = [Depth1-Left|Hole1]
  ),
  (   Right = nil ->
      Hole1 = Hole2
  ;   Hole1 = [Depth1-Right|Hole2]
  ),
  (   TasksLeft = [] ->
      Height is Depth
  ;   height_(TasksLeft,Hole2,Height)
  ).

height_rec(Dict,Depth,Height) :-
  (  Dict = nil ->
     Height = Depth
  ;  Dict = dict(_,Left,Right),
     height_rec(Left,Depth,LeftDepth),
     height_rec(Right,Depth,RightDepth),
     (   LeftDepth > RightDepth ->
         Height is LeftDepth + 1
     ;   Height is RightDepth + 1
     )
   ).

height/2 uses a queue and breadth first search. It's about 50% slower than height_rec/3 which uses double recursion. I've benched both rules with trees containing up to a million nodes.

As I understand it, Scryer-Prolog manages its call stack on the heap, so a (non-tail call optimized) recursive algorithm may pile up stack frames on the heap but never risks breaching the underlying scryer-prolog process' fixed-size stack.

Is that right?

[triska]

From this description, it seems that one of these programs is faster than the other, for a specific test case and for a specific version of Scryer Prolog.

As to why, there are many potential reasons for this. For instance, height_/3 constructs and inspects terms that height_rec/3 does not. This alone can easily account for a measurable performance difference. I think this specific example does not justify any conclusions about the speed, strategy or trade-offs of stack frame allocation, and none of those should be a major concern when writing Prolog code.

As I see it, the direction of Prolog code and engine developments should be:

1. We write the most elegant Prolog code we can.
2. The Prolog engine gets designed and tuned to make such programs fast.

An example of what we don't want is:

a. We choose a specific version of Scryer Prolog.
b. We contort ourselves to make a fast program for that version.

Personally, I think that understanding Scryer Prolog's stack frame management is not required for writing elegant Prolog code. It may even be an obstacle because it costs too much attention and detracts us from finding more elegant solutions.

If the available memory is exceeded, we expect Scryer to throw an appropriate exception that can be caught within Prolog.

In your specific case, the more elegant, shorter and more natural version is also faster, and that's in my experience also the typical situation.

[dnmfarrell]

Thank you for responding!

My concern was coming from adding one of these rules to a shared library where I wouldn't know how large the dictionary would be ahead of time. I'd hate for someone to use the library and hit a stack overflow error for example.

But your reply made me realize I potentially won't even know which interpreter is running the code.

@triska as an author of shared code, how do you satisfy yourself that it is fit for purpose? In this example I could imagine doing (informal) boundary analysis on different sizes of inputs.

[triska]

Personally, I aim for correctness and elegance. We can use Prolog itself to query the defined relations in various ways, and test them very exhaustively.

In this concrete example, let's ask Prolog what the predicate means. Let's start with the most general query: Which solutions are there in general?

?- height(D, H).
   D = nil, H = -1.

From this, it appears that the entire relation can be defined with a single fact. On the other hand, this is probably not the intended relation, so there is likely a mistake in the code.

Regarding efficiency: For large data structures, the used algorithms must generally stay sub-quadratic, and otherwise quickly become infeasible.