Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Ludovic Courtès]

Hello!

"Neil Jerram" <address@hidden> writes:

> I'm sorry but I'm still really struggling to see how this change helps us...

Yes, I see...  ;-)

I'm taking it the other way: I can't see how one can argue for unneeded
run-time overhead.

> 2008/9/1 Ludovic Courtès <address@hidden>:

>> You're right, but it's always better to traverse the list once rather
>> than twice.  :-)
>
> Not necessarily.  It depends what happens inside the loop, on each
> iteration, and whether the iteration time is significant in comparison
> with that.

I'd say it's better regardless of what's inside the loop.

Sure, one may argue that `memq' is rarely used with million-of-element
lists anyway, because other methods would be used in such situations
(hash tables, etc.).  But that's not necessarily the case with
`reverse', `partition', etc.

> What overhead?  (Quantifiably, I mean.)

In terms of profile dumps, a full run of the test suite under Callgrind
reveals that `scm_ilength ()' is *not* in the top 10.  But hey, one
could surely come up with a Real World(TM) application that does a lot
of list processing and is measurably impacted by that double traversal.

> I don't believe anyone's worked this all out yet, but, for example, if
> the arg to scm_reverse() was generated by some other function that is
> known only to produce proper lists, then the arg might be represented
> as (<proper-list> . the-actual-list), and obviously then the
> SCM_VALIDATE_LIST in scm_reverse() can be completely skipped.  If the
> validation code is interleaved with the actually-doing-something code,
> it becomes more difficult to skip (in some hypothetical future).

How would you remove those checks from compiled code like `list.o'?

Guile-VM, OTOH, may have clear opportunities to optimize away certain
cases at compilation time.

> Do we really need to continue this discussion?

Maybe not.

To be honest, I didn't expect I'd have to argue about this in the first
place.  I see it as a (maybe small, application-dependent) benefit,
while I have the impression that you regard it solely as a "possible
breakage" and as "code churning".  Probably we disagree because we don't
value the same things here.

Thanks,
Ludo'.