Re: Lua5 / poor performance

[RLake@...]

This may not be the fastest frexp in the world, but it seems to work. As it
stands, it is not 100% correct on IEEE-754 architecture, I don't think.
Given infinity as an argument, it returns infinity, which is not strictly
speaking in [0.5, 1) :) But it handles NaN's and subnormals right. Trying
to avoid testing explicitly for infinity is the rather pathetic explanation
for the renormalisation step after scaleup -- it would be less pathetic if
it did the right thing, although to be honest I don't know what frexp is
supposed to return if its argument is Infinity.

Since most of the time integer keys do not need to be hashed, and the
existing implementation does a poor job on them, and frexp actually is
normally available, I think this might be an adequate fallback. Personally
I would hash the result by a slightly different algorithm than I showed in
the previous sample code, using the same technique as Lua5beta uses for
addresses: add the exponent to the renormalised number and then mod by
(hashsize - 1) rather than hash size. Since the first bit in the normalised
number is almost guaranteed to be on, it might be a good idea to use
something like:

  ((lu_hash) ( (frexp(n, &exp)-.5) * (1 << 31)) + exp) % ((hashsize - 1) |
1)

although the above expression as written violates evaluation order
independence and should be written as two lines.

With IEEE-754 doubles, the worst case recursion is for subnormalised
numbers; I think that would be 11 recurses. All the multiplies and divides
are pure powers of two, so an fp emulator might be able to do this
reasonably quickly even though it involves divides. Since single-point
floats have smaller exponents, the worst case for them is somewhat smaller.

I was trying to make this do frexp right, but some simplifications are
possible if the final result doesn't have to be exact (for example, not
renormalising after scaleup). I believe this will work reasonably with
bignums, as well, in case anyone implements lua_Number as a bignum... but
it could be really slow :)

I release the following code into the public domain. Have fun with it.

Rici

/* n is > base; returns n in (base, base*base] */
double scaleup(double n, double base, int* exp) {
  double next = base * base;
  if (n > next) {
    n = scaleup(n, next, exp);
    *exp *= 2;
    if (n <= base) return n;
  }
  n /= base;
  ++*exp;
  return n;
}

/* n is < base; returns n in [base*base, base) */
double scaledown(double n, double base, int* exp) {
  double next = base * base;
  if (n < next) {
    n = scaledown(n, next, exp);
    *exp *= 2;
    if (n >= base) return n;
  }
  n /= base;
  --*exp;
  return n;
}

double myfrexp(double n, int *exp) {
  double sign = 1;
  *exp = 0;
  if (n == 0) {
    return 0;
  } else if (n < 0) {
    n = -n;
    sign = -1;
  }
  if (n >= 1) {
    if (n > 2) n = scaleup(n, 2, exp);
    n /= 2;
    ++*exp;
    if (n == 1.0) {
      n = 0.5;
      ++*exp;
    }
  } else {
    if (n < 0.5) n = scaledown(n, 0.5, exp);
  }
  return sign * n;
}