GNU bug report logs - #21883
unnecessary bit shifting range limits

Previous Next

To reply to this bug, email your comments to 21883 AT debbugs.gnu.org.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Zefram <zefram <at> fysh.org>
To: bug-guile <at> gnu.org
Subject: unnecessary bit shifting range limits
Date: Thu, 12 Nov 2015 07:07:25 +0000

Not really outright bugs, but these responses are less than awesome:

$ guile -c '(write (logbit? (ash 1 100) 123))'
ERROR: Value out of range 0 to 18446744073709551615: 1267650600228229401496703205376
$ guile -c '(write (ash 0 (ash 1 100)))'
ERROR: Value out of range -9223372036854775808 to 9223372036854775807: 1267650600228229401496703205376
$ guile -c '(write (ash 123 (ash -1 100)))'
ERROR: Value out of range -9223372036854775808 to 9223372036854775807: -1267650600228229401496703205376

In all three cases, the theoretically-correct result of the expression
is not only representable but easily computed.  The functions could be
improved to avoid failing in these cases, by adding logic amounting to:

(define (better-logbit? b v)
  (if (>= b (integer-length v)) (< v 0) (logbit? b v)))

(define (better-ash v s)
  (cond
    ((= v 0) 0)
    ((<= s (- (integer-length v))) (if (< v 0) -1 0))
    (else (ash v s))))

-zefram

Message #8 received at 21883 <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: Zefram <zefram <at> fysh.org>
Cc: 21883 <at> debbugs.gnu.org
Subject: Re: bug#21883: unnecessary bit shifting range limits
Date: Sun, 14 Oct 2018 04:18:13 -0400

Zefram <zefram <at> fysh.org> writes:

> Not really outright bugs, but these responses are less than awesome:
>
> $ guile -c '(write (logbit? (ash 1 100) 123))'
> ERROR: Value out of range 0 to 18446744073709551615: 1267650600228229401496703205376
> $ guile -c '(write (ash 0 (ash 1 100)))'
> ERROR: Value out of range -9223372036854775808 to 9223372036854775807: 1267650600228229401496703205376
> $ guile -c '(write (ash 123 (ash -1 100)))'
> ERROR: Value out of range -9223372036854775808 to 9223372036854775807: -1267650600228229401496703205376
>
> In all three cases, the theoretically-correct result of the expression
> is not only representable but easily computed.

Commit 011aec7e240ef987931548d90c53e6692c85d01c on the stable-2.2 branch
extends 'ash' and 'round-ash' to handle the easily computed cases of
huge shifts.

> The functions could be improved to avoid failing in these cases, by
> adding logic amounting to:
>
> (define (better-logbit? b v)
>   (if (>= b (integer-length v)) (< v 0) (logbit? b v)))
>
> (define (better-ash v s)
>   (cond
>     ((= v 0) 0)
>     ((<= s (- (integer-length v))) (if (< v 0) -1 0))
>     (else (ash v s))))

Unfortunately, simple implementations like the ones above slow down the
common case with expensive checks that are rarely needed.  The
aforementioned commit takes pains to avoid slowing down the common case,
but at the cost of extra code complexity.

In theory we could do something similar with many other procedures that
implement operations on bits and bit fields, but I wonder if it's worth
the extra complexity.

       Mark

Message #11 received at 21883 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Israelsson Tampe <stefan.itampe <at> gmail.com>
To: Mark H Weaver <mhw <at> netris.org>
Cc: 21883 <at> debbugs.gnu.org, Zefram <zefram <at> fysh.org>
Subject: Re: bug#21883: unnecessary bit shifting range limits
Date: Sun, 14 Oct 2018 11:46:12 +0200

[Message part 1 (text/plain, inline)]

how would this slow down the code. just add the correction where you throw
the exception which should be in a branch outside the hot path.

Den 14 okt 2018 10:19 AM skrev "Mark H Weaver" <mhw <at> netris.org>:

Zefram <zefram <at> fysh.org> writes:

> Not really outright bugs, but these responses are less than awesome:
>
> $ guile -c '(write (logbit? (ash 1 100) 123))'
> ERROR: Value out of range 0 to 18446744073709551615:
1267650600228229401496703205376
> $ guile -c '(write (ash 0 (ash 1 100)))'
> ERROR: Value out of range -9223372036854775808 to 9223372036854775807:
1267650600228229401496703205376
> $ guile -c '(write (ash 123 (ash -1 100)))'
> ERROR: Value out of range -9223372036854775808 to 9223372036854775807: -
1267650600228229401496703205376
>
> In all three cases, the theoretically-correct result of the expression
> is not only representable but easily computed.

Commit 011aec7e240ef987931548d90c53e6692c85d01c on the stable-2.2 branch
extends 'ash' and 'round-ash' to handle the easily computed cases of
huge shifts.

> The functions could be improved to avoid failing in these cases, by
> adding logic amounting to:
>
> (define (better-logbit? b v)
>   (if (>= b (integer-length v)) (< v 0) (logbit? b v)))
>
> (define (better-ash v s)
>   (cond
>     ((= v 0) 0)
>     ((<= s (- (integer-length v))) (if (< v 0) -1 0))
>     (else (ash v s))))

Unfortunately, simple implementations like the ones above slow down the
common case with expensive checks that are rarely needed.  The
aforementioned commit takes pains to avoid slowing down the common case,
but at the cost of extra code complexity.

In theory we could do something similar with many other procedures that
implement operations on bits and bit fields, but I wonder if it's worth
the extra complexity.

       Mark

[Message part 2 (text/html, inline)]

Message #14 received at 21883 <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: Stefan Israelsson Tampe <stefan.itampe <at> gmail.com>
Cc: 21883 <at> debbugs.gnu.org, Zefram <zefram <at> fysh.org>
Subject: Re: bug#21883: unnecessary bit shifting range limits
Date: Sun, 14 Oct 2018 18:19:36 -0400

Stefan Israelsson Tampe <stefan.itampe <at> gmail.com> writes:
> how would this slow down the code. just add the correction where you
> throw the exception which should be in a branch outside the hot path.

If you have a suggestion that's simpler than what I did in commits
011aec7e, 9448a078, and 1990aa91, and just as fast in the common cases,
feel free to propose a patch.  The words above are insufficient.

      Mark

Message #17 received at 21883 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Israelsson Tampe <stefan.itampe <at> gmail.com>
To: Mark H Weaver <mhw <at> netris.org>
Cc: 21883 <at> debbugs.gnu.org, Zefram <zefram <at> fysh.org>
Subject: Re: bug#21883: unnecessary bit shifting range limits
Date: Mon, 15 Oct 2018 09:08:51 +0200

[Message part 1 (text/plain, inline)]

i think you got it. sorry for the fuzz.


Den 15 okt 2018 12:19 AM skrev "Mark H Weaver" <mhw <at> netris.org>:

> Stefan Israelsson Tampe <stefan.itampe <at> gmail.com> writes:
> > how would this slow down the code. just add the correction where you
> > throw the exception which should be in a branch outside the hot path.
>
> If you have a suggestion that's simpler than what I did in commits
> 011aec7e, 9448a078, and 1990aa91, and just as fast in the common cases,
> feel free to propose a patch.  The words above are insufficient.
>
>       Mark
>

[Message part 2 (text/html, inline)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.