From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Stefan Israelsson Tampe Newsgroups: gmane.lisp.guile.bugs Subject: bug#21883: unnecessary bit shifting range limits Date: Sun, 14 Oct 2018 11:46:12 +0200 Message-ID: References: <20151112070725.GA875@fysh.org> <87tvlpszzu.fsf@netris.org> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000e39c6605782d302f" X-Trace: blaine.gmane.org 1539510306 8779 195.159.176.226 (14 Oct 2018 09:45:06 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 14 Oct 2018 09:45:06 +0000 (UTC) Cc: 21883@debbugs.gnu.org, Zefram To: Mark H Weaver Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Sun Oct 14 11:45:02 2018 Return-path: Envelope-to: guile-bugs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1gBcxJ-00029a-4R for guile-bugs@m.gmane.org; Sun, 14 Oct 2018 11:45:01 +0200 Original-Received: from localhost ([::1]:47770 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gBczP-00046y-PJ for guile-bugs@m.gmane.org; Sun, 14 Oct 2018 05:47:11 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:36272) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gBczK-00046t-0D for bug-guile@gnu.org; Sun, 14 Oct 2018 05:47:07 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1gBczG-0005AR-QN for bug-guile@gnu.org; Sun, 14 Oct 2018 05:47:05 -0400 Original-Received: from debbugs.gnu.org ([208.118.235.43]:44564) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1gBczG-0005AH-Kb for bug-guile@gnu.org; Sun, 14 Oct 2018 05:47:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1gBczG-0007OX-Gs for bug-guile@gnu.org; Sun, 14 Oct 2018 05:47:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Stefan Israelsson Tampe Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Sun, 14 Oct 2018 09:47:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 21883 X-GNU-PR-Package: guile X-GNU-PR-Keywords: Original-Received: via spool by 21883-submit@debbugs.gnu.org id=B21883.153951038228376 (code B ref 21883); Sun, 14 Oct 2018 09:47:02 +0000 Original-Received: (at 21883) by debbugs.gnu.org; 14 Oct 2018 09:46:22 +0000 Original-Received: from localhost ([127.0.0.1]:48822 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1gBcya-0007Na-88 for submit@debbugs.gnu.org; Sun, 14 Oct 2018 05:46:21 -0400 Original-Received: from mail-vs1-f45.google.com ([209.85.217.45]:41125) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1gBcyY-0007NN-El for 21883@debbugs.gnu.org; Sun, 14 Oct 2018 05:46:18 -0400 Original-Received: by mail-vs1-f45.google.com with SMTP id w1so14621935vsj.8 for <21883@debbugs.gnu.org>; Sun, 14 Oct 2018 02:46:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=mc/yHcYs1J7DueOSR5hws2qw/RAbYhrfI32wxdIvbtw=; b=veMc07NA1EeZvBxHZJK6GnWNrGbrbTXODbss+sHx1XIKOWFeLVdJb76bvKPUlrw32Q EUIw+v9iLV4H77x+VQwXrPaKTvLKk4Y5cWjN9sDG0b84tl28iwu9uICEyJEE4SUidd8N F8pZs/KIUHRE+bJ4hIyaouRkTjbujCNNiffO00mFUtSgVGRugbbRqj582NKlck6DSfvH QULR18K3/PzDH5z4o8GRhSKUGl12lZbcV76gQejBnRNegng++UOuJAmp1ngRSxhGap+c fHmG2jKvGwqjRW/9JuGn8sQ8MVlPpiD45vmWuBZaB24a7sMvuMMKtMc2NkYHA0NFv08R SvGQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=mc/yHcYs1J7DueOSR5hws2qw/RAbYhrfI32wxdIvbtw=; b=tcqMmCehjJfT4cKZKYXM8q1DNBziZLbjjM6jPmMsLMS429s0TlIbL9XciwwzB+d3OG GFKwjz36iVomj1eoMaR4RTP0I2Spf8F77soaa6rvh1AUimL6dDIkY4rTTVygalTWLcCO /gZKJ5Ap1hsAC2ZFSObQjHYnq4Remuw6Vgs1q4/SgbGptCDBlpYJCh5S14oxK09riQ77 59yZayvAKz5gFTkaaEyYZHYexvMrUfikmvki0hAwcrS6FGuz1FgFPeXsQRZEewQFblnd Oi9VZ0Zr0LAcZ+O3C94UFrv4/lyz/LLuULc74lz0h7r2H0s3EAOHyzSTIRcPPh/+IxXc asVQ== X-Gm-Message-State: ABuFfoj8ZmTNxKVGxozFhbuzZO42WStG9d0jObFV17jXt+YK5BP0x7Bn oO2H7f80WdXNBoY6f/rNkFqsakhk9A/vtOnpDi9NFg== X-Google-Smtp-Source: ACcGV63QJK3bIexJFaVxEt2yXSeJMCYHDY/X6edaZvISQ6+DnkSBx+eb04M9fapuY+AGZqJsh3Ft3dahkV24TZrWhwY= X-Received: by 2002:a67:8801:: with SMTP id k1-v6mr153615vsd.103.1539510372636; Sun, 14 Oct 2018 02:46:12 -0700 (PDT) Original-Received: by 2002:a1f:2801:0:0:0:0:0 with HTTP; Sun, 14 Oct 2018 02:46:12 -0700 (PDT) Original-Received: by 2002:a1f:2801:0:0:0:0:0 with HTTP; Sun, 14 Oct 2018 02:46:12 -0700 (PDT) In-Reply-To: X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 208.118.235.43 X-BeenThere: bug-guile@gnu.org List-Id: "Bug reports for GUILE, GNU's Ubiquitous Extension Language" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Original-Sender: "bug-guile" Xref: news.gmane.org gmane.lisp.guile.bugs:9189 Archived-At: --000000000000e39c6605782d302f Content-Type: text/plain; charset="UTF-8" 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" : Zefram 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 --000000000000e39c6605782d302f Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
how would this slow down the code. just add the correctio= n where you throw the exception which should be in a branch outside the hot= path.

Den 1= 4 okt 2018 10:19 AM skrev "Mark H Weaver" <mhw@netris.org>:
Zefram <zefram@fysh.org<= /a>> 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: 12676506002282294= 01496703205376
> $ 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 bran= ch
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)
>=C2=A0 =C2=A0(if (>=3D b (integer-length v)) (< v 0) (logbit? b v= )))
>
> (define (better-ash v s)
>=C2=A0 =C2=A0(cond
>=C2=A0 =C2=A0 =C2=A0((=3D v 0) 0)
>=C2=A0 =C2=A0 =C2=A0((<=3D s (- (integer-length v))) (if (< v 0) = -1 0))
>=C2=A0 =C2=A0 =C2=A0(else (ash v s))))

Unfortunately, simple implementations like the ones above slow down the
common case with expensive checks that are rarely needed.=C2=A0 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.

=C2=A0 =C2=A0 =C2=A0 =C2=A0Mark




--000000000000e39c6605782d302f--