I was originally thinking of making a lookup table, but thought of this along the way.
Thanks for that - I still haven't worked my way through it properly.
It seems to work fine now that I've changed:
long long smallest_invalid = last_set << 52;
to
long long smallest_invalid = last_set << 53;
Without that change, the following values (for example) wrongly reported "NOPE":
1844674407366955264,
1844674407366955776,
1844674407366956288,
1844674407366956800,
1844674407366957312,
1844674407366957824,
1844674407366958336,
1844674407366958848,
1844674407366959360,
1844674407366959872,
1844674407366960384,
1844674407366960896,
1844674407366961408,
1844674407366961920,
1844674407366962432,
1844674407366962944,
1844674407366963456,
1844674407366963968,
1844674407366964480,
1844674407366964992
In the following XS adaptation it's taking over twice as long as uv_fits_double3.
use warnings;
use Benchmark;
use Inline C => Config =>
BUILD_NOISY => 1;
use Inline C => <<'EOC';
int uv_fits_double3(SV * x, ...) {
dXSARGS;
int i, count = 0;
UV arg;
for(i = 0; i < items; i++) {
arg = SvUV(ST(i));
if(arg) {
while(!(arg & 1)) arg >>= 1;
if(arg < 9007199254740993) count++;
}
}
return count;
}
int uv_fits_double_bitfiddle(SV * t, ...) {
dXSARGS;
int i, count = 0;
for(i = 0; i < items; i++) {
/* First we need to identify the lowest bit set */
IV neg_t = -(SvIV(ST(i)));
IV last_set = SvUV(ST(i)) & neg_t;
/* Shift it left 53 bits to get location of lowest invalid bit
+ *
* NOTE: If smallest invalid bit is far enough left, then this wil
+l *
* turn into 0 making the invalid bits also 0, which happens to be
+ OK! */
IV smallest_invalid = last_set << 53;
UV valid_bits = smallest_invalid - 1;
UV invalid_bits = ~valid_bits;
/* It's a 'valid' number unless one of the upper-order invalid bit
+s are set */
if(!(SvUV(ST(i)) & invalid_bits)) count++;
}
return count;
}
EOC
@in = (1844674407366955161 .. 1844674407378955161);
# @in = (9007199248740992 .. 9007199260740992);
# @in = (184467436737095 .. 184467448737095);
# @in = (184463440737 .. 184475440737);
die "wrong size" unless @in == 12000001;
timethese (1, {
'uv_fits_double3' => '$count1 = uv_fits_double3(@in);',
'uv_fits_double_bitfiddle' => '$count2 = uv_fits_double_bitfiddle(@in)
+;',
});
print "$count1 $count2\n";
die "Error in at least one of the XSubs" unless $count1 == $count2;
__END__
Benchmarking results on my Windows 7 machine with perl-5.30.0 are:
Benchmark: timing 1 iterations of uv_fits_double3, uv_fits_double_bitf
+iddle...
uv_fits_double3: 0 wallclock secs ( 0.44 usr + 0.00 sys = 0.44 CPU)
+ @ 2.29/s (n=1)
(warning: too few iterations for a reliable count)
uv_fits_double_bitfiddle: 1 wallclock secs ( 0.94 usr + 0.00 sys =
+0.94 CPU) @ 1.07/s (n=1)
(warning: too few iterations for a reliable count)
12000001 12000001
Can you see room for significant improvement in performance of uv_fits_double_bitfiddle ?
Thanks for another interesting approach !!
Cheers,
Rob
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.