Generic LOGTEST conses even when given fixnum arguments.

[Lutz Euler]

See this transcript (SBCL 1.1.15.33-142dc0d on Linux/x86-64):

* (defun f (g)
    (let ((x 0))
      (dotimes (i 100000)
        (when (funcall g i)
          (incf x)))
      x))

F
* (let ((before (sb-ext:get-bytes-consed)))
    (f #'(lambda (i) (logtest i 1)))
    (- (sb-ext:get-bytes-consed) before))

12779520

This is bad because (LOGTEST X 1) is used in ODDP which is used in INTEXP, so the generic ODDP and EXPT (and EVENP and surely more) on fixnums all cons unnecessarily.

ROOM shows that the consing consists of bignums:

* (room)
[…]
  12,551,712 bytes for 647,394 bignum objects.
[…]

This is a regression. (Before the regression the second expression above returned 0 and ROOM shows no bignums). I have bisected it to sbcl-1.1.8-32-ga8419eb:

  a8419eb994f3b59b70cfa12e1004711a830a43fa is the first bad commit
  commit a8419eb994f3b59b70cfa12e1004711a830a43fa
  Author: Paul Khuong <email address hidden>
  Date: Fri Jun 7 18:46:25 2013 -0400

  Complete cut-to-width for modular arithmetic

  For each modular argument, go through the nodes that provide its
  value and try to narrow down their bitwidth. If we fail on any and
  the result might be too wide, splice in an explicit call to LOGAND
  or MASK-SIGNED-FIELD. Skip that last step if the value is an argument
  to an equivalent LOGAND or MASK-SIGNED-FIELD.

  Test case by Eric Marsden.

Disassembling ODDP shows a call to TWO-ARG-AND in the SBCL versions before
this commit and a call to SB-C::MASK-SIGNED-FIELD from this commit on.

Greetings,

Lutz

[Lutz Euler (lutz-euler)]

In case anyone wants to investigate this: There was some discussion on #sbcl about this on 2014-02-07 and 2014-02-08.

Regards,

Lutz

[Christophe Rhodes (csr21-cantab)]

Lutz Euler <email address hidden> writes:

> In case anyone wants to investigate this: There was some discussion on
> #sbcl about this on 2014-02-07 and 2014-02-08.

For this bug, we have to do generic arithmetic at some point (because
the argument is generic). Does the problem boil down to the fact that
the out-of-line implementation of mask-signed-field is itself very
generic? If it were redefined along the lines of two-arg-and, to handle
small-argument cases (and maybe word-sized cases) more effectively,
maybe some of these performance problems would go away...

Cheers,

Christophe

[Christophe Rhodes (csr21-cantab)]

Christophe Rhodes <email address hidden> writes:

> Lutz Euler <email address hidden> writes:
>
>> In case anyone wants to investigate this: There was some discussion on
>> #sbcl about this on 2014-02-07 and 2014-02-08.
>
> For this bug, we have to do generic arithmetic at some point (because
> the argument is generic). Does the problem boil down to the fact that
> the out-of-line implementation of mask-signed-field is itself very
> generic? If it were redefined along the lines of two-arg-and, to handle
> small-argument cases (and maybe word-sized cases) more effectively,
> maybe some of these performance problems would go away...

Proof-of-concept patch attached. It "fixes" the logtest issue, at least
with fixnum arguments, with a 90% speedup in the test case in this bug.

It's not a complete fix. If backends had a primitive to get the low
N-FIXNUM-BITS of a bignum, then we could use that to improve the
(MASK-SIGNED-FIELD [1,63] <BIGNUM>) case, which would make LOGTEST not
cons even on BIGNUM arguments -- as it is, it will do all the
out-of-line DPB consing.

Thoughts?

Christophe

[Alastair Bridgewater (alastair-bridgewater)]

On x86-64: (sb-bignum:%bignum-ref
#x1234567890123456789012345678901234567890 0) => #x5678901234567890. For
any other platform, you'd have to mask it down from there to
positive-fixnum or similar. All backends should support %BIGNUM-REF. Good
enough?

On Thu, Dec 3, 2015 at 9:40 AM, Christophe Rhodes <
<email address hidden>> wrote:

> Christophe Rhodes <email address hidden> writes:
>
> > Lutz Euler <email address hidden> writes:
> >
> >> In case anyone wants to investigate this: There was some discussion on
> >> #sbcl about this on 2014-02-07 and 2014-02-08.
> >
> > For this bug, we have to do generic arithmetic at some point (because
> > the argument is generic). Does the problem boil down to the fact that
> > the out-of-line implementation of mask-signed-field is itself very
> > generic? If it were redefined along the lines of two-arg-and, to handle
> > small-argument cases (and maybe word-sized cases) more effectively,
> > maybe some of these performance problems would go away...
>
> Proof-of-concept patch attached. It "fixes" the logtest issue, at least
> with fixnum arguments, with a 90% speedup in the test case in this bug.
>
> It's not a complete fix. If backends had a primitive to get the low
> N-FIXNUM-BITS of a bignum, then we could use that to improve the
> (MASK-SIGNED-FIELD [1,63] <BIGNUM>) case, which would make LOGTEST not
> cons even on BIGNUM arguments -- as it is, it will do all the
> out-of-line DPB consing.
>
> Thoughts?
>
>
>
> Christophe
>
>
> ** Patch added: "0001-better-out-of-line-MASK-SIGNED-FIELD.patch"
>
> https://bugs.launchpad.net/bugs/1277690/+attachment/4529063/+files/0001-better-out-of-line-MASK-SIGNED-FIELD.patch
>
> --
> You received this bug notification because you are subscribed to SBCL.
> https://bugs.launchpad.net/bugs/1277690
>
> Title:
> Generic LOGTEST conses even when given fixnum arguments.
>
> Status in SBCL:
> Triaged
>
> Bug description:
> See this transcript (SBCL 1.1.15.33-142dc0d on Linux/x86-64):
>
> * (defun f (g)
> (let ((x 0))
> (dotimes (i 100000)
> (when (funcall g i)
> (incf x)))
> x))
>
> F
> * (let ((before (sb-ext:get-bytes-consed)))
> (f #'(lambda (i) (logtest i 1)))
> (- (sb-ext:get-bytes-consed) before))
>
> 12779520
>
> This is bad because (LOGTEST X 1) is used in ODDP which is used in
> INTEXP, so the generic ODDP and EXPT (and EVENP and surely more) on
> fixnums all cons unnecessarily.
>
> ROOM shows that the consing consists of bignums:
>
> * (room)
> […]
> 12,551,712 bytes for 647,394 bignum objects.
> […]
>
> This is a regression. (Before the regression the second expression
> above returned 0 and ROOM shows no bignums). I have bisected it to
> sbcl-1.1.8-32-ga8419eb:
>
> a8419eb994f3b59b70cfa12e1004711a830a43fa is the first bad commit
> commit a8419eb994f3b59b70cfa12e1004711a830a43fa
> Author: Paul Khuong <email address hidden>
> Date: Fri Jun 7 18:46:25 2013 -0400
>
> Complete cut-to-width for modular arithmetic
>
> For each modular argument, go through the nodes that provide its
> value and try to narrow down their bitwidth. If we fail...

[Christophe Rhodes (csr21-cantab)]

Alastair Bridgewater <email address hidden> writes:

> On x86-64: (sb-bignum:%bignum-ref
> #x1234567890123456789012345678901234567890 0) => #x5678901234567890. For
> any other platform, you'd have to mask it down from there to
> positive-fixnum or similar. All backends should support %BIGNUM-REF. Good
> enough?

I think not quite -- we might still end up consing intermediate bignums,
because all our backend support for mask-signed-field requires constant
field width. Given support for mask-signed-field with non-constant (but
< n-word-bits) size, that could work; it should be about as hard as
getting ASH right (which has similar issues around word size).

However... the following works for me, but requires backend support
(implementation of MASK-SIGNED-FIELD-BIGNUM/C VOPs on non-x86[-64]
non-arm[64] platforms):

(defun sb!c::mask-signed-field (size integer)
  #!+sb-doc
  "Extract SIZE lower bits from INTEGER, considering them as a
2-complement SIZE-bits representation of a signed integer."
      (macrolet ((msf (size integer)
                   `(if (logbitp (1- ,size) ,integer)
                        (dpb ,integer (byte (1- ,size) 0) -1)
                        (ldb (byte (1- ,size) 0) ,integer))))
        (typecase size
          ((eql 0) 0)
          ((integer 0 #.sb!vm:n-fixnum-bits)
          (number-dispatch ((integer integer))
            ((fixnum) (msf size integer))
            ((bignum) (let ((fix (sb!c::mask-signed-field #.sb!vm:n-fixnum-bits integer)))
                        (msf size fix)))))
          ((integer (#.sb!vm:n-fixnum-bits) #.sb!vm:n-word-bits)
           (number-dispatch ((integer integer))
             ((fixnum) integer)
             ((bignum) (let ((word (sb!c::mask-signed-field #.sb!vm:n-word-bits integer)))
                         (msf size word)))))
          ((unsigned-byte) (msf size integer)))))

[Christophe Rhodes (csr21-cantab)]

Christophe Rhodes <email address hidden> writes:

> Alastair Bridgewater <email address hidden> writes:
>
>> On x86-64: (sb-bignum:%bignum-ref
>> #x1234567890123456789012345678901234567890 0) => #x5678901234567890. For
>> any other platform, you'd have to mask it down from there to
>> positive-fixnum or similar. All backends should support %BIGNUM-REF. Good
>> enough?
>
> I think not quite -- we might still end up consing intermediate bignums,
> because all our backend support for mask-signed-field requires constant
> field width. Given support for mask-signed-field with non-constant (but
> < n-word-bits) size, that could work; it should be about as hard as
> getting ASH right (which has similar issues around word size).

I take this back. The IR2-CONVERT optimizer for MASK-SIGNED-FIELD
supports exactly the cases that we need, probably not entirely
coincidentally. Rewrite in progress...

(finding that IR2-CONVERT optimizer makes me wonder whether we actually
need the MASK-SIGNED-FIELD-{WORD,BIGNUM}/C VOPs on any platform...)

Cheers,

Christophe

[Lutz Euler (lutz-euler)]

As the reporter of this bug I feel I should say something, too.

Christophe, in #2 you wrote
> For this bug, we have to do generic arithmetic at some point (because
> the argument is generic). Does the problem boil down to the fact that
> the out-of-line implementation of mask-signed-field is itself very
> generic?

Yes, as surely is clear by now, if mask-signed-field could be made non-consing and faster for small arguments that's a good solution.

But, I would still like to know if it was not possible in the case at hand to convince the compiler to emit a call to two-arg-and even after the regression-introducing commit. Since the commit message says "splice in an explicit call to LOGAND or MASK-SIGNED-FIELD", maybe the process of choosing one or the other could be improved?

I don't have much time at the moment to look into these things myself, so many thanks to all that contribute here!

Greetings,

Lutz

[Christophe Rhodes (csr21-cantab)]

Lutz Euler <email address hidden> writes:

> As the reporter of this bug I feel I should say something, too.
>
> Christophe, in #2 you wrote
>> For this bug, we have to do generic arithmetic at some point (because
>> the argument is generic). Does the problem boil down to the fact that
>> the out-of-line implementation of mask-signed-field is itself very
>> generic?
>
> Yes, as surely is clear by now, if mask-signed-field could be made non-
> consing and faster for small arguments that's a good solution.

I believe I have an architecture-neutral fix that should sort this out.
I don't have a benchmarking infrastructure to really test it, but the
microbenchmarks on LOGTEST/ODDP are good :-)

> But, I would still like to know if it was not possible in the case at
> hand to convince the compiler to emit a call to two-arg-and even after
> the regression-introducing commit. Since the commit message says "splice
> in an explicit call to LOGAND or MASK-SIGNED-FIELD", maybe the process
> of choosing one or the other could be improved?

Well. The commit in question, as far as I recall, was for correctness:
the modular optimizations assume that everything inside them is treated
in the same way, and incorrect results can ensue if something is not cut
to the appropriate width in the appropriate way.

There is a preference order (see BEST-MODULAR-VERSION); at the moment,
it prefers signed, tagged reductions where that is possible -- hence
introducing mask-signed-field rather than logand. The rationale for
that is that we would rather not pay the cost of shifts for untagging
fixnums when we don't have to. If we had a tagged unsigned version of
modular arithmetic, we would probably prefer that over the signed
version, but I think that involves a certain amount of backend work.

Cheers,

Christophe