Comment by tom_ | Hacker News Reader

Comment by tom_ | Hacker News Reader

4 billion was a lot when I first got into programming, but it just isn't that much any more. Always start out by making your sequence numbers 64 bits: 2^64 nanoseconds = ~585 years. (I have in the past stolen a few bits for other uses, but I'm less certain of the wisdom of that these days.)

32 bits is suitable for things that can only happen once a frame - (2^32/60) seconds = 2.26 years - but not much more than that.

But there's a flip side to computers being able to wrap a uint32_t so quickly: if you've got 32 bits'-worth of combinations, then you can might actually be able to do an exhaustive test. 2^32 microseconds = 71 minutes. Work in C++, run on all threads, and you probably won't even need to wait that long.

Good example: https://randomascii.wordpress.com/2014/01/27/theres-only-fou... - runs in 90 seconds.

I did something similar a few years ago, prototyping a 16x16 multiply routine for an 8-bit CPU. It took about 5 minutes running on both threads on my 2.5GHz dual core laptop, and found some interesting cases I'd got completely wrong.

65536 was a lot when I first got into programming, there was also floating point, and then the realization that we don't need to be constrained to 4 bits, 8 bits, 16 bits, 24 bits, 32 bits, 64 bits, 128 bits, two digit years, 640K of RAM, small stack frames, broken memory models and all the other ridiculous limits. Give it a decade and I bet the ~585 year time frame is reduced to a small enough interval where bugs appear. Bet on lots of 64-bit bugs appearing, and a programmer in the future commenting that 128-bits should have been used, and 128-bits will break in the future of that future, and so on.

For me, the biggest bug in the modern x86 chip is ME: a full system that can be turned on, take over everything and eats up valuable core space.

Bear in mind that the 128 bit space is not double the size of the 64 bit space - it's 2^64 times the size.

Cryptography actually relies on there being a space that is too large to count though, even in parallel.

> Give it a decade and I bet the ~585 year time frame is reduced to a small enough interval where bugs appear.

I'm skeptical that much changes in the next decade regarding where 64-bit integers are useful. It's been a long time since there are been meaningful clock frequency increases in commodity CPUs. Even if we had a 100Ghz CPU and we had it increment a register once per clock cycle, we're still talking ~6 years for it to overflow. And, thats assuming a 20+ times increase in clock frequency when clock frequencies have been mostly flat for the last 10 years.

> a programmer in the future commenting that 128-bits should have been used, and 128-bits will break in the future of that future, and so on.

I disagree with this statement. With 128-bits, it becomes difficult (though not impossible) to even come up with things that are numerous enough to be unable to count with that number of bits. That was never the case for 64-bit or smaller integers.

128 bits is actually good enough for basically anything. 64 bits comes close but not always good enough.

ME is implemented with a tiny Quark processor on the PCH. It doesn't consume any valuable space in the CPU. Every modern non-trivial support ASIC has an embedded processor for housekeeping duty. The problem is how much ME can extend its tendrils into every aspect of a modern PC.

Exhaustive search is untenable for the 64-bit case. Any strategy here? Testing 2^40 bits might be tenable; any way to select which ones would have the best ROI?

It's hard to give a general strategy without knowing the problem structure, but I guess you could say one general strategy is to exploit the problem structure in a way that lets you test multiple values in one shot.

Feed llvm bytecode through Z3 and hope you didn't implement something with cryptographic behaviour.

Could you give some advice or pointers on this?

This should get you going. Come back if you get stuck. https://twitter.com/whitequark/status/915211914443153409

Edit: sorry, I just don't have the time to get you the details.

Check out DeepState! https://github.com/trailofbits/deepstate

I'm not so sure that's true. You can rent a Skylake chip on Google Cloud that'll perform 1.6 trillion 64 bit operations per second for $0.96/hr preemptively. That's enough to run one instruction over a 64 bit address space exhaustively over 120 days, or for ~$2800.

Obviously that needs to be multiplied by the number of instructions a test needs to execute (and it has to be well written with AVX 512), but we're not talking nation state levels of resources here for simple cases, and that figure is only going to drop further with time.

Not to mention the potential for FPGA or ASIC implementations if the tests are important enough.

Hmm that's surprisingly within reach. I bet you could crowd-source that kind of verification with BOINC.

> 32 bits is suitable for things that can only happen once a frame - (2^32/60) seconds = 2.26 years

What do you mean by a 'frame' and how does 2.26 years relate to a frame?

Frame of video at 60fps. For games I suppose that's a benchmark burned into your skull.

144 please. :)

For real though, the difference between 60 and 144 is night and day. I can't go back to 60 after playing with 144. I wonder if going beyond 144 would have the same effect.

Yea but that would require spending more than $600 per 5 years on computer hardware :\

A frame is 1/60 of a second (generally), so if you are indexing your frames with a 32-bit integer, you have enough for 2.26 years of video (or video game, or whatever).

High refresh rate monitors are getting more and more popular; at 240 FPS, a signed 32-bit counter will just last a bit over 3 months. Competitive players may want to play at even higher frame rates to decrease input lag even further. It's _probably_ still fine, because people _generally_ don't leave the game running for months, but those 31 usable bits get used up rsurprisingly quickly.

Yes, that's a good point. I unit test all small functions that take no more than 32 bit in input on literally all inputs.

Reply on news.ycombinator.com