I've tripped over an apparent bug in the Gabriel Benchmark "traverse".
Below I'm using the Scheme version, but the "bug" exists in the
original Lisp version too. Two questions:
1. Is this a known problem?
2. Does anyone care to refute that this is a bug?
The function "traverse-remove" apparently extracts an element from a
circularly linked list of objects. The first case handles a list that
contains only one object. The second case handles extraction of the
first object.
(define (traverse-remove n q)
(cond ((eq? (cdr (car q)) (car q))
(let ((x (caar q))) (set-car! q #f) x))
((zero? n)
(let ((x (caar q)))
(do ((p (car q) (cdr p)))
((eq? (cdr p) (car q))
(set-cdr! p (cdr (car q)))
(set-car! q p)))
x))
(else (do ((n n (- n 1))
(q (car q) (cdr q))
(p (cdr (car q)) (cdr p)))
((zero? n) (let ((x (car q))) (set-cdr! q p) x))))))
The else-clause contains the "bug". (set-cdr! q p) never does
anything useful, since p = (cdr q). Hence the list never gets smaller
when the else-clause is executed.
The benchmark apparently works because it pseudo-randomly removes
objects from a list, occasionally removing object 0. The second case
correctly deletes object 0 from the list, so the list does eventually
empty.
Andrew Wright
In article <··········@larry.rice.edu> ······@asia.cs.rice.edu (Andrew Wright) writes:
>I've tripped over an apparent bug in the Gabriel Benchmark "traverse".
>Below I'm using the Scheme version, but the "bug" exists in the
>original Lisp version too. Two questions:
> 1. Is this a known problem?
> 2. Does anyone care to refute that this is a bug?
I don't know about this particular 'bug', but I've found bugs in many of
the other Gabriel benchmarks, so this wouldn't surprise me. Bugs in
benchmarks are a real problem, because they can't be 'fixed' without
destroying the usefulness of the benchmark, yet the existence of such
a bug already makes the benchmark less useful. This is because 1) who
cares about optimizing code known to be buggy, and 2) a buggy benchmark
may be inappropriately stressing the sort of behavior you don't want
to encourage in either other programmers or in hardware architects (who
actually base designs on statistics from benchmarks).
Even bad programming style in benchmarks is not good, because it
either directly (through so many people studying the benchmark) or
indirectly (by affecting machine/compiler/os design & optimization)
encourages more bad programming style. (The bad programming styles
encouraged by C are reinforced by the coding styles of large corpuses
of C code -- e.g., Unix & Unix utilities -- which then affect machine
design; I think that this effect falls into the 'sins of the fathers'
category). Some of the 'optimizations' in the Gabriel benchmarks are
unfortunate for these reasons.
I think that benchmarks should be chosen with the best algorithms and
programming styles known, without any 'hackish' optimizations. If such
optimizations are to be done, they should be done by the implementation.