And another frog task

[David Kastrup]

I just profiled the following code:

#include <stdlib.h>
#include <libguile.h>

void *test1(void *n)
{
  for (int i=0; i<(int)n; i++) {
    SCM list = SCM_EOL;
    SCM *tail = &list;
    for (int k=0; k<(int)n; k++) {
      *tail = scm_cons (SCM_BOOL_F, SCM_EOL);
      tail = SCM_CDRLOC(*tail);
    }
  }
  return 0;
}

void* test2(void *n)
{
  for (int i=0; i<(int)n; i++) {
    SCM list = SCM_EOL;
    for (int k=0; k<(int)n; k++) {
      list = scm_cons (SCM_BOOL_F, list);
    }
    list = scm_reverse_x (list, SCM_EOL);
  }
  return 0;
}

  
main(int ac, char**av)
{
  int n = atoi(av[1]);
  if (n<0)
    scm_with_guile (test1, (void*)-n);
  else
    scm_with_guile (test2, (void*)n);
  return 0;
}


I profiled both functions in separate runs to make sure the differences
were not because of hot/cold cache or heap.  The results were that
consing the list together from front to end (test1, corresponding with
the Lilypond manner of creating lists) were about 20% slower without,
40% slower with optimization in contrast to consing it together in
reverse order, then reversing.

Variant 1 "looks" more efficient and is what Lilypond does when it
creates linear lists in order.  It is, however, considerably less
efficient, _and_ it needs additional variables, _and_ it is quite more
complex to understand.  In addition, the tail pointer is opaque to the
conservative garbage collector, so you need to make sure that you do
things in the right order so that the tail does not fall victim to the
garbage collector.

So it would seem like another worthwhile frog task to get rid of
SCM_CDRLOC in the source tree when feasible (when the list is being
consulted front-to-back while it is in the process of being created,
this would not be possible.  However, since tail pointers in this manner
can't be kept around beyond the function call, chances are that we have
very few such cases if at all).

It will simplify the code, make it more readable and faster, and
decrease the amount of stack scanning that can go wrong.

-- 
David Kastrup