[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Making 'eq' == 'eql' in bignum branch
From: |
Stefan Monnier |
Subject: |
Re: Making 'eq' == 'eql' in bignum branch |
Date: |
Mon, 20 Aug 2018 10:02:34 -0400 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux) |
> I think it's currently true, but only because make_number always
> creates a copy of its argument (at which point we might as well hash
> it), and it sounded like Paul was going to fix that soon.
Two options:
1- the operation does not create a new number. Since Elisp's
side only sees immutable bignum numbers if the number is not new we
indeed shouldn't create a new number and can reuse the existing
bignum without any need for hash-consing either: so hash-consing
doesn't make this case any slower.
2- the operation does create a new number. In that case the
creation of the number almost inevitably will have to touch every
"limb" of the number (it has a complexity of O(N) in the best case),
so computing the hash shouldn't take noticeably more time.
> It sounds to me like a good implementation of this would require GMP
> support, keeping a hash of each mpz_t in the memory allocated for it.
We can keep the hash in the hash-table.
> Do we need to worry about algorithmic complexity attacks? Or about
> integers created accidentally that collide in the hash?
Emacs already offers so many other attack vectors that I don't think
it's worth worrying about this one at this point.
> I think 64-bit integers, at least, ought to be fast and small.
Indeed, it's for those small bignums that hash-consing will be most
expensive, but I'm not sure it'll be a significant problem.
Stefan
- Re: Making 'eq' == 'eql' in bignum branch, (continued)
- Re: Making 'eq' == 'eql' in bignum branch, Stefan Monnier, 2018/08/30
- Re: Making 'eq' == 'eql' in bignum branch, Richard Stallman, 2018/08/28
- Re: Making 'eq' == 'eql' in bignum branch, Johan Bockgård, 2018/08/30
- Re: Making 'eq' == 'eql' in bignum branch, Clément Pit-Claudel, 2018/08/30
- Re: Making 'eq' == 'eql' in bignum branch, Tom Tromey, 2018/08/30
- Re: Making 'eq' == 'eql' in bignum branch, Clément Pit-Claudel, 2018/08/30
- Re: Making 'eq' == 'eql' in bignum branch, Stefan Monnier, 2018/08/20
- Re: Making 'eq' == 'eql' in bignum branch, Eli Zaretskii, 2018/08/20
- Re: Making 'eq' == 'eql' in bignum branch, Paul Eggert, 2018/08/20
- Re: Making 'eq' == 'eql' in bignum branch, Helmut Eller, 2018/08/20
- Re: Making 'eq' == 'eql' in bignum branch,
Stefan Monnier <=