in reply to Re^3: Detecting whether UV fits into an NV
in thread Detecting whether UV fits into an NV

My first guess is that the overhead in SvUV(ST(i)) is causing twiddle to be slower

Yes, I thought of replacing them with a variable, but decided there wouldn't be that much difference between looking at the value of an SV's IV slot and looking at the value of an IV.
I guess for a few calls there's not much difference, but when you're making 36 million of them it's not hard to believe that things might add up - and I should have thought that through a little better. (Actually, a "lot better".)

Fixing that alone makes uv_fits_double_bitfiddle almost twice as fast as uv_fits_double3 for me:
Benchmark: timing 1 iterations of uv_fits_double3, uv_fits_double_bitf +iddle... uv_fits_double3: 1 wallclock secs ( 0.45 usr + 0.00 sys = 0.45 CPU) + @ 2.21/s (n=1) (warning: too few iterations for a reliable count) uv_fits_double_bitfiddle: 0 wallclock secs ( 0.25 usr + 0.00 sys = +0.25 CPU)@ 4.02/s (n=1) (warning: too few iterations for a reliable count)
This is pretty much the type of approach whose existence I had wondered about.
It had never been pointed out to me that iv & -iv would identify the least significant set bit, and I'm certainly not sharp enough to have ever realized it myself.
This method is just brilliant ... and it's great that it turns out to be faster, too !!
I'll certainly be using it (with due accreditation to you) unless further testing, contrary to my expectations, reveals some problem with it.


Replies are listed 'Best First'.
Re^5: Detecting whether UV fits into an NV
by roboticus (Chancellor) on Mar 05, 2020 at 03:38 UTC


    Nice! I'm glad you got a usful result.

    Regarding thinking of that trick: I didn't think of it either, but years ago, I read a document that had a lot of bit-fiddling tricks in it, and remembered that there was a trick for that, and my Google-fu let me dredge it up.


    When your only tool is a hammer, all problems look like your thumb.

      I didn't think of it either

      It's also worth pointing out that once you've isolated that critical bit, it's still not exactly braindead straightforward as to how best to make use of that info.
      Think of an integer, find its least significant set bit, left-shift its value 53 places, subtract 1, flip all of the bits, and then & that result with the number you first thought of.

      I made a small modification to the sub so that it handled negative and positive IV/UV values.
      I also compounded the guts of the code into 2 lines. (It could be put into 1 line, but I didn't go that far.)
      Here's what I ended up with ... minus explanatory comments.
      int iv_fits_double(SV * t, ...) { dXSARGS; int i, count = 0; for(i = 0; i < items; i++) { IV arg = SvIV(ST(i)); int sign = ( arg > 0 || SvUOK(ST(i)) ) ? 1 : -1; UV valid_bits = ((arg & -arg) << 53) - 1; if(!((arg * sign) & (~valid_bits))) count++; } return count; }