Re: Making 'eq' == 'eql' in bignum branch

[Pip Cet]

On Mon, Aug 20, 2018 at 12:05 AM Stefan Monnier
<address@hidden> wrote:
> I think its cost should not be too high in practice: the time to lookup
> up a GMP number in a hash table basically should never be longer than
> the time it took to construct this number in the first place, so that's
> a worst-case slowdown factor of 2 which I think is perfectly acceptable.

Can you explain why you think that's the case?

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.

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.
Perhaps we should make a wishlist of GMP features, which would
currently include three items:

 - make long-running integer operations interruptible (so C-g works)
 - don't abort() when overflowing the 16 GB limit (and/or remove that
limit entirely)
 - hash numbers as you create them, at least for the fast single-pass
operations (addition, left shift, negation).

Do we need to worry about algorithmic complexity attacks? Or about
integers created accidentally that collide in the hash?

I think 64-bit integers, at least, ought to be fast and small. Maybe
we could use our free tag value for that special case.