Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Slow bitwise operations on bignums #798

Open
jkoser opened this issue Jun 9, 2017 · 1 comment
Open

Slow bitwise operations on bignums #798

jkoser opened this issue Jun 9, 2017 · 1 comment

Comments

@jkoser
Copy link
Contributor

jkoser commented Jun 9, 2017

(This is related to #414, but only incidentally.)

As noted in the code, bitwise-{and|ior|xor} and functions that use them are really slow. Specifically, the pattern of splitting into high and low parts and recombining makes these operations take time quadratic in the length of their input.

I've written a benchmark that stresses bitwise ops. Currently Racket 6.8 outperforms Larceny on it by a factor of 10 (though, of course, that varies when the problem size changes).

Ideally, these functions would take linear time. I notice that Larceny provides integer-logand and friends (in bignums.sch). Is there any reason we can't just use those?

@WillClinger
Copy link
Member

You can use anything listed in src/Lib/Common/toplevel.sch. integer-logand is listed.

jkoser added a commit to jkoser/larceny that referenced this issue Jun 14, 2017
jkoser added a commit to jkoser/larceny that referenced this issue Jun 14, 2017
jkoser added a commit to jkoser/larceny that referenced this issue Jun 14, 2017
WillClinger added a commit that referenced this issue Jun 15, 2017
Faster bitwise operations on bignums (ticket #798)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants