[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Paul Eggert
Subject: Re: Making 'eq' == 'eql' in bignum branch
Date: Mon, 20 Aug 2018 00:05:56 -0700
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1

Pip Cet wrote:

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's on my list of things to look at, though I can't guarantee I'll fix it (much less "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)

We can approximate this by checking for C-g in the GMP-specific memory allocator hooks. Perhaps all we need is some sort of guarantee that unbounded computation won't occur without some memory allocation action.

  - don't abort() when overflowing the 16 GB limit (and/or remove that
limit entirely)

Yes, that reeally needs to be fixed. I think I have a handle on avoiding that glitch in the meantime (still polishing it).

  - hash numbers as you create them, at least for the fast single-pass
operations (addition, left shift, negation).

Could well be a win, yes. Not sure how much of a win it would be for typical use, though. Usually bignums are pretty small.

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

Both, I'd think.
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.

Hold on, let's not spend that valuable tag so casually! Perhaps bignums or floats are a better use for a tag than 64-bit ints.

One other thing: we can pry another tag free. Now that we have bignums we no longer need to give fixnums two tags.

reply via email to

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