Don't fold ash in cp0 when the shift is too big

[gus-massa]

Don't fold ash in cp0 when the shift is too big . Fix also bitwise-arithmetic-shift/-right/-left.

Some code like

(expand/optimize '(ash 1 10000000))

takes too long to compile or fail with an memory error. (If it works, just add a few additional zeroes.)

The problem is that ash is marked as mifoldable, so cp0 tries to fold it. Note that expt has a similar behavior with fixnums, but the before folding the exponent is checked to ensure it is small.

Probably bitwise-rotate-bit-field and bitwise-reverse-bit-field need a special case too, but I haven't add it.

Based in a bug report by @samth in https://github.com/racket/racket/issues/2865.

[gus-massa]

I added a fix by @samth and more tests. For the new tests, it's necessary to update the mats/patch-* files.

Anyway,the test don't trigger the error in the automated test. With o=0 the optimizations are skipped and with o=3 the tests are skipped.

To find the errors in the automated test, it is necessary to add

$(MAKE) allxhelp o=2 cp0=t

to partialx/allx/bullyx.

[akeep]

This isn't actually an issue with the expander being slow, in fact the optimize can fold it almost instantaneously, as we can see from using time:

> (time (expand/optimize '(ash 1 10000000)))
(time (expand/optimize (quote (...))))
    no collections
    0.001654019s elapsed cpu time
    0.001650000s elapsed real time
    3754912 bytes allocated

However, the computed number is very large, and it takes a long time to print to the repl, which is what expand/optimize is attempting to do after the time result. Incidentally, we can also see this by binding the value on the repl:

> (time (ash 1 10000000))
(time (ash 1 ...))
    no collections
    0.000000000s elapsed cpu time
    0.000000000s elapsed real time
    0 bytes allocated

Which then also sits for a long time, but if we bind it we can immediately see the result:

> (define n (time (ash 1 10000000)))
(time (ash 1 ...))
    no collections
    0.000000000s elapsed cpu time
    0.000000000s elapsed real time
    0 bytes allocated
> (time (bitwise-first-bit-set n))
(time (bitwise-first-bit-set n))
    no collections
    0.000143273s elapsed cpu time
    0.000143000s elapsed real time
    0 bytes allocated
10000000

These operations return almost immediately.

[gus-massa]

You are right that in my example it's a printer problem, I prefer

(time (number? (expand/optimize '(ash 1 10000000))))

that runs instantly.

But the problem of the optimizer can be found again if you add more zeros.
(Run in a virtual box in a old I3 noteboot, with only 4GB of memory. So you may need to add more zeros to get a problem.)

> (time (number? (expand/optimize '(ash 1 1000000000))))
(time (number? (expand/optimize (...))))
    1 collection
    0.571710115s elapsed cpu time, including 0.232732946s collecting
    1.472691818s elapsed real time, including 0.600797040s collecting
    375007920 bytes allocated, including 254319344 bytes reclaimed
#t

And if I add an additional zero

> (time (number? (expand/optimize '(ash 1 10000000000))))

I expected the runtime to be like 5 second, but it's actually slower and I didn't have enough patient to wait it to finish. (So it's at least like 10 minutes, probably more.)

[akeep]

Ah, okay, I'll have to give this another look.

Thanks for the quick response on this!

[samth]

Just FYI, the linked Racket bug has a number of other relevant commits linked from it.

[mflatt]

Included in v9.9.9 merge 47daa9b34016de84fd111801d9d589d15a523abe.