Re: New: SCM_DEBUG_CELL_ACCESSES

[Dirk Herrmann <dirk at ida dot ing dot tu-bs dot de>]

On 22 May 2000, Mikael Djurfeldt wrote:

> > The major difference between the use as a standalone function and the use
> > in scm_mark_location, IMO, is the expected case:  in scm_mark_locations
> > there is a (I guess) large probability that the SCM value is not pointing
> > into the heap, thus it makes sense to first see if the value is in the
> > total range of all heap cells at all.  In contrast, scm_cellp as used in
> > combination with SCM_DEBUG_CELL_ACCESSES expects that the SCM value is
> > actually a cell because the other case indicates a failure.  I will do
> > some analysis between the two.
> 
> Good.
> 
> We *only* need to optimize the mark case.

I have investigated a little bit:

- it seems that the checks for scm_heap_table[seg_id].valid != NULL are
  unnecessary, since that feature is not used.  There's even a comment
  about it not being used at the head of gc.c.  If we want to speed
  things up, unused features should be removed.
- The comments about span are wrong, IMO.  It says, span is the "number of
  SCM words per object in this segment", but it rather seems to be the
  number of scm_cells per object:  span is 1 most of the times.  However,
  for the sake of generalization it may be better to make span be the
  number of SCM/scm_bits_t words:  This would even allow for cells with 3
  entries etc.
- The initial number of stack frames when guile has started seems to be
  very large.  As soon as the repl is reached, there are about 70 stack
  frames (with the debugging evaluator, I haven't checked the other
  one).  Since the size of the stack defines the time for conservative
  stack scanning, continuation creation and calling, this is something
  that we also should try to reduce, if possible.

1) I suggest to remove the "valid" stuff.
2) the use of span (or the comment about it) should be fixed.
3) Some evaluator guru might take a look at the enormously large
   initial number of stack frames.

I have instrumented the code of scm_mark_locations with counters to see
the relative frequencies of the different execution paths.  A typical run
looks like this:

> guile
(2 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 574 400 96 96 94 2 0 0 0 0 0 0 0 0 0 96 96)
(2 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)

Reading ~/.guile.
(2 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 1810 1245 569 569 556 13 0 0 0 0 0 0 0 0 0 569 569)
(2 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 3264 2268 1039 1039 1023 16 0 0 0 0 0 0 0 0 0 1039 1039)
(2 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 2984 2083 991 991 972 19 0 0 0 0 0 0 0 0 0 991 991)
(2 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 3180 2210 1041 1041 1024 17 0 0 0 0 0 0 0 0 0 1041 1041)
(2 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 2664 1857 891 891 876 15 0 0 0 0 0 0 0 0 0 891 891)
(2 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 2364 1641 733 733 717 16 0 0 0 0 0 0 0 0 0 733 733)
(2 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 1896 1314 603 603 590 13 0 0 0 0 0 0 0 0 0 603 603)
(2 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 1930 1340 637 637 623 14 0 0 0 0 0 0 0 0 0 637 637)
(2 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 1458 993 476 476 461 15 0 0 0 0 0 0 0 0 0 476 476)
(2 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(3 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(3 1226 858 463 468 265 183 20 0 5 5 0 15 0 15 0 448 448)
(3 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
guile> (gc)
(3 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(3 2250 1554 869 888 724 138 26 0 19 19 0 7 0 7 0 862 862)
(3 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
guile> (gc)
(3 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(3 2996 2107 1145 1161 998 128 35 0 16 16 0 19 0 19 0 1126 1126)
(3 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(3 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(3 2250 1558 886 902 806 67 29 0 16 16 0 13 0 13 0 873 873)
(3 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
guile> (gc)
(3 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(3 2250 1555 881 897 801 67 29 0 16 16 0 13 0 13 0 868 868)
(3 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
guile> 


The first number is the number of heap segments, the second is the number
of objects to be checked, the third number is the number of objects that
fulfill the SCM_CELLP predicate, the fourth number is the number of
objects that lie in the total range of all heap segments.  The last number
is the number of objects that finally get marked.  The numbers in between
denote the different paths and are not of much interest.

The lines with 12 and 17 objects correspond to jumpbuffer scanning and
such.  Only the other lines correspond to scanning of the stack itself.

* After guile starts up, I entered (gc).  The first time, (gc) is
  performed once.  When I enter (gc) for the second time, it seems to
  be performed twice.  Why?
* The number of objects on the stack seems to be surprisingly
  large:  about 850 objects get marked each time, about one third of all
  data on the stack.

I also performed the same checks with the guile test-suite.  Again,
about one third of all objects on the stack get actually marked.  However,
in this case the number of marked objects on the stack varies a lot
during one run through the test-suite, but seems to have a minimum of
about 300.

Something interesting about the most probable position of objects in the
heap segments:  Objects are most probably within the first segment
(actually, in the heap segment with the lowest memory address, but I
assume that this is also the first one allocated).  This is not
surprising, since as I said above, the initial number of stack frames is
quite large, and consequently, if there are objects being pointed to from
the stack, these are most probably objects that were created during
startup.

Something interesting about the variation of object numbers on the stack:
> guile -s empty.scm     // just an empty file
(2 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 544 379 84 84 82 2 0 0 0 0 0 0 0 0 0 84 84)
(2 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
This (84) was the lowest number of actually marked objects that I
encountered.  The maximum was 90.  The most probable is 87.  The stack
size, however, was alwas 544.  This leads to the assumption that any
object number larger than 84 indicates objects that are conservatively
scanned.
> guile -s gc.scm        // a file with only '(gc)' in it
(2 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 544 382 88 88 86 2 0 0 0 0 0 0 0 0 0 88 88)
(2 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 12 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(2 754 492 177 177 172 5 0 0 0 0 0 0 0 0 0 177 177)
(2 17 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
Again, 177 was the lowest number encountered, while 202 was the largest,
and 199 was the typical.

Best regards
Dirk