[Top][All Lists]

[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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]