This is a larger number than the one cited in the post because the latter only includes "normal" numbers. This includes the "denormals" as well.
It's very easy to generalize this to 64 bits, there are 4,607,182,418,800,017,410 of them.
>>> import struct
>>> count = 0
>>> for i in range(0x1_0000_0000):
... f = struct.unpack('<f', struct.pack('<I', i))[0]
... if 0 <= f <= 1: count += 1
...
>>> count
1065353218
pypy never ceases to amaze me for low-effort performance gains on computational stuff.
A naive implementation in C compiled with Apple's clang (-O2) takes 0.62 seconds, of course.
import time, array
n = 0
start_time = time.time()
values = bytearray(b"".join(i.to_bytes(4, "big") for i in range(2**24)))
for prefix in range(256):
values[::4] = prefix.to_bytes(1, "big") * (2**24)
arr = array.array("f", values)
n += sum(1 for x in arr if 0.0 <= x <= 1.0)
print(f"Found: {n} Time: {time.time() - start_time:.1f} seconds")
Rather than build all 0x1_0000_0000 values in memory, I process 0x100_0000 at a time, and accumulate the partial sums.
On my laptop this reports "Found: 1065353218 Time: 228.5 seconds", so just under 4 minutes.
A slightly improved algorithm in NumPy takes 5.4 seconds.
import time, numpy as np
start_time = time.time()
arr = np.arange(2**24, dtype=np.uint32)
incr = np.full(2**24, 2**24, dtype=arr.dtype)
values = np.frombuffer(arr, np.float32)
n = ((0.0 < values) & (values <= 1.0)).sum()
for i in range(1, 256):
arr += incr
n += ((0.0 < values) & (values <= 1.0)).sum()
print(f"Found: {n} Time: {time.time() - start_time:.1f} seconds") #include <math.h> // nextafterf
#include <stdio.h> // printf
int main()
{
long n = 1;
float f = 0;
while (f <= 1)
{
f = nextafterf(f, 2);
n = n + 1;
}
printf("%ld\n", n);
return 0;
} long start = System.currentTimeMillis();
int count = 1;
for (int intBits = Float.floatToIntBits(0.0f); Float.intBitsToFloat(intBits) <= 1.0f; intBits ++) {
count++;
}
System.out.println(count);
System.out.println((System.currentTimeMillis() - start) + "ms"); long start = System.currentTimeMillis();
long count = IntStream.rangeClosed(Float.floatToIntBits(0.0f), Float.floatToIntBits(1.0f)).count();
System.out.println(count);
System.out.println((System.currentTimeMillis() - start) + "ms");
1065353217
0msReally cool trick!
I can't tell that'd be possible - I see the arguments could be evaluated at compile time, but knowing IntStream.rangeClosed will be evaluated at compile time is a leap, to me.
Did you know before you wrote the code that'd happen? Is it like C? You cross your fingers and hope the compiler unrolls?
So there's actually no reason to even invoke the streams API there.
While technically correct, in practice it is not the case.
First of all (and this relates to flerchin's comment), it's not actually done at "compile time" in the traditional sense (i.e. when you invoke `javac`). Rather, it is done at runtime when the method is compiled by the JIT.
As for this comment, the call to `IntStream.rangeClosed` will not simply be reduced to `(b - a) + 1` as you suggest (and one reason for this is that streams are far more complex internally than regular iterators). In reality, it will just be (potentially) inlined and then further optimized alongside the rest of the method's code.
Edit: the mentioned previous comment was from flerchin, not meese
Edit 2: I might have misunderstood what you were getting at there. You are sort of correct in that the `count` operation on this stream is optimized, but it is still technically going through the streams API.
How is this done?
The implementation of a `Spliterator` that is used internally by `IntStream.rangeClosed` overrides the `estimateSize` method to return `((long) upTo) - from + last`, and the `characteristics` method to return, among others, the `Spliterator.SIZED` characteristic. That characteristic indicates that `estimateSize` can be trusted to be exact, and when present, `estimateSize` will be used as a shortcut in the implementation of `Stream.count`, which can be seen in `ReduceOps.makeRefCounting`.
int count = 1;
int limit = Float.floatToIntBits(1.0f);
for (int intBits = Float.floatToIntBits(0.0f); intBits <= limit; intBits++) {
count++;
}
1065353218, 0.91
1065353218, 0.69
1065353218, 0.00
1065353218, 0.64
1065353218, 0.64
1065353218, 0.63
1065353218, 0.66
1065353218, 0.63
1065353218, 0.63
1065353218, 0.00
1065353218, 0.00
1065353218, 0.00
...
1065353218, 0.00
Process finished with exit code 0 ((long) upTo) - from + last;
https://github.com/openjdk/jdk/blob/caa841d9a52352a975394e55...
Also, in the case of your test, it's not even letting the JIT kick in, but rather using a shortcut to calculate the length of the range.
Curious to know the total compile + run time under different compiler optimizations. For code you only need to run once, I don't see how having the compiler unroll the loops actually saves you any time.
The compiler can unroll loops like that to `for (i=0; i < n; i+=8) { acc += 8; }` (ignoring the remainder of n/8), which does 8x fewer compare+conditional jump instructions. It has nothing to do with how many times you’ll be running the code; this kind of optimisation reduces the runtime of any single execution.
I had thought that in cases like this (where the output can already be determined at compile time) the compiler could just run the loop to get the answer, therefore avoiding running it every time the code runs, which was what I was picturing when I wrote my earlier comment.
Annotated https://gist.github.com/cormacrelf/4b2b37d1d870377d548b3a32a... and full Godbolt https://rust.godbolt.org/z/aKK4TEs3x. You may be interested to see the LLVM Opt Pipeline, any of the green passes (non-zero diffs) that are called LoopUnrollPass or LoopVectorizePass.
You can see that it does a couple of LoopUnrollPasses and LoopVectorizePasses. In the end it results in a transformation from something like this:
for (uint32_t i = 0; i <= 0xffff; i++) {
if (in range) acc += 1;
}
u32x4 v1 = [1,2,3,4];
u32x4 v0 = [0,0,0,0], v5 = [0,0,0,0];
u32x4 v6, v7;
uint32_t w8 = 0xfff8;
do {
v6 = v1 + [4,4,4,4];
v7 = v1 >= 0 && v1 <= 1;
v6 = v6 >= 0 && v6 <= 1;
v0 -= v7; // add 1 to each lane if lane was true in v7
v5 -= v6; // add 1 to each lane if lane was true in v6
v1 += [8,8,8,8];
w8 -= 8;
} while (w8);
return element_sum(v0 + v5);
Re "how does it know when it's finished?": it counts like normal, as you can see there, it uses a register to count iteration. Unrolling does not mean "completely eliminate the termination check" unless your heuristic/supplied unroll threshold is larger than the (known) number of iterations. It generally just does the termination check fewer times by taking bigger strides. It's like walking up stairs two at a time.
The answer re compile-time-full-evaluation: compilers use heuristics and pattern matching, they don't automatically try compile time evaluation for things they don't recognise. Nobody would have bothered to write a heuristic to detect "count floating point values in range" and eval it. There is no compiler pass to arbitrarily try to execute eveything in your program at compile time that's remotely possible.
const NaN=$7F80;
var x, total: Longint;
f: single absolute x;
r: record Lo,Hi:Word; end absolute x;
begin
total:=0;
x:=0;
repeat
inc(total, ord((r.Hi and NaN <> NaN) and (0<=f) and (f<=1)));
inc(x);
until x=0;
WriteLn('total: ', total);
end.
SELECT sum(reinterpretAsFloat32(number) BETWEEN 0.0 AND 1.0) FROM numbers_mt(0x100000000)
1 row in set. Elapsed: 0.170 sec. Processed 2.39 billion rows, 19.08 GB (14.02 billion rows/s., 112.13 GB/s.)