7 ms·

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 nano

by tom_ 8y ago

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-four-billion-floatsso-test-them-all/ 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.

Kenji 8y ago
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.
- deleted 8y ago
  [deleted]
kardos 8y ago
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?
- mehrdadn 8y ago
  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.
- namibj 8y ago
  Feed llvm bytecode through Z3 and hope you didn't implement something with cryptographic behaviour.
  - fao_ 8y ago
    Could you give some advice or pointers on this?
    - namibj 8y ago
      This should get you going. Come back if you get stuck. https://twitter.com/whitequark/status/915211914443153409 https://twitter.com/whitequark/status/915211914443153409 Edit: sorry, I just don't have the time to get you the details.
- pag 8y ago
  Check out DeepState! https://github.com/trailofbits/deepstate https://github.com/trailofbits/deepstate
- reitzensteinm 8y ago
  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.
  - kardos 8y ago
    Hmm that's surprisingly within reach. I bet you could crowd-source that kind of verification with BOINC.
chrisseaton 8y ago
> 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?
- dmoy 8y ago
  Frame of video at 60fps. For games I suppose that's a benchmark burned into your skull.
  - dvlsg 8y ago
    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.
    - dmoy 8y ago
      Yea but that would require spending more than $600 per 5 years on computer hardware :\
- earenndil 8y ago
  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).
mmphosis 8y ago
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.
- VMG 8y ago
  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.
- dagenix 8y ago
  > 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.
- ummonk 8y ago
  128 bits is actually good enough for basically anything. 64 bits comes close but not always good enough.
- 8y ago
mort96 8y ago
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.

by tom_ 8y ago

Kenji 8y ago

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.

deleted 8y ago
[deleted]

kardos 8y ago

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?

mehrdadn 8y ago
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.
namibj 8y ago
Feed llvm bytecode through Z3 and hope you didn't implement something with cryptographic behaviour.
- fao_ 8y ago
  Could you give some advice or pointers on this?
  - namibj 8y ago
    This should get you going. Come back if you get stuck. https://twitter.com/whitequark/status/915211914443153409 https://twitter.com/whitequark/status/915211914443153409 Edit: sorry, I just don't have the time to get you the details.
pag 8y ago
Check out DeepState! https://github.com/trailofbits/deepstate https://github.com/trailofbits/deepstate
reitzensteinm 8y ago
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.
- kardos 8y ago
  Hmm that's surprisingly within reach. I bet you could crowd-source that kind of verification with BOINC.

chrisseaton 8y ago

> 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?

dmoy 8y ago
Frame of video at 60fps. For games I suppose that's a benchmark burned into your skull.
- dvlsg 8y ago
  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.
  - dmoy 8y ago
    Yea but that would require spending more than $600 per 5 years on computer hardware :\
earenndil 8y ago
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).

mmphosis 8y ago

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.

VMG 8y ago
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.
dagenix 8y ago
> 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.
ummonk 8y ago
128 bits is actually good enough for basically anything. 64 bits comes close but not always good enough.
8y ago

mort96 8y ago

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.