[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Making 'eq' == 'eql' in bignum branch
From: |
Pip Cet |
Subject: |
Re: Making 'eq' == 'eql' in bignum branch |
Date: |
Mon, 20 Aug 2018 06:35:44 +0000 |
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.
Re: Making 'eq' == 'eql' in bignum branch, Elias MÃ¥rtenson, 2018/08/10
Re: Making 'eq' == 'eql' in bignum branch, Stefan Monnier, 2018/08/19
- Re: Making 'eq' == 'eql' in bignum branch, Paul Eggert, 2018/08/19
- Re: Making 'eq' == 'eql' in bignum branch,
Pip Cet <=
- Re: Making 'eq' == 'eql' in bignum branch, Paul Eggert, 2018/08/20
- Re: Making 'eq' == 'eql' in bignum branch, Pip Cet, 2018/08/20
- Re: Making 'eq' == 'eql' in bignum branch, Paul Eggert, 2018/08/20
- Re: Making 'eq' == 'eql' in bignum branch, Andy Moreton, 2018/08/20
- Re: Making 'eq' == 'eql' in bignum branch, Paul Eggert, 2018/08/20
- Re: Making 'eq' == 'eql' in bignum branch, Andy Moreton, 2018/08/20
- Re: Making 'eq' == 'eql' in bignum branch, Paul Eggert, 2018/08/20
- Re: Making 'eq' == 'eql' in bignum branch, Andy Moreton, 2018/08/20
- Re: Making 'eq' == 'eql' in bignum branch, Pip Cet, 2018/08/20
- Re: Making 'eq' == 'eql' in bignum branch, Andy Moreton, 2018/08/20