3 ms·

I was recently wondering how much CPU time would be regained if we got an instruction to do x * 10 ^ y where x is an int64/y an int (or something like that) and

I was recently wondering how much CPU time would be regained if we got an instruction to do x * 10 ^ y where x is an int64/y an int (or something like that) and do so without error. This is a really really common operation and needs a bigint library to do properly now for many cases. It’s also slow, I think aggregate it’s around 500MB/s to 1GB/s, but the slow path is < 100MB/s. But pretty much every JSON/XML/Number.from_string is using an operation like this, to the scale is quite large.

stephencanon 5y ago
Converting a number from string can be done without any bignum operations at all, this has been well-understood for a while now. This is mostly just widely-used libraries having not caught up with the state of the art. There is some opportunity for ISA support to speed it up, but multiplication by powers of ten is not the bottleneck, that’s just a table lookup and full-width product in high-performance implementations (i.e. a load and a mul instruction).
- beached_whale 5y ago
  Got links? Even Daniel Lemire's Fast Double parser will dump to strtod when the numbers are not handleable because of this. You cannot represent 10^x, or even all 5^x beyond a certain point in IEEE754 double's but need to do the full y * 10^x operation without loss. Doing it lossy is easy(0 to 1 or 2 ulp off optimal)
  - stephencanon 5y ago
    You don’t need to do it without loss, you need to do it with loss smaller than the closest that the digit sequence could be to an exact halfway point between two representable double-precision values. This means you may need arbitrary-precision for arbitrary-precision decimal strings, but in practice these libraries are “always” converting strings that came from formatting exact doubles (eg round-tripping through JSON), and so have bounded precision. Thus you can tightly bound the precision required. This precisely mirrors how formatting fp numbers used to require bignum arithmetic, but all the recent algorithms (Ryu, Dragonbox, SwiftDtoa) do it with fixed int128 arithmetic and deliver always correct results. We’ll see analogous algorithms for the other direction adopted in the next few years—the only reason this direction came later is that the other was a bigger performance problem originally.
    - beached_whale 5y ago
      I use dragonbox and it makes the serialization task quite easy and fast. It would be great for a mirror library that did so for deserialization of arbitrary decimal numbers. The current libraries are not fast, and it isn't the parsing, it's the math they do with those characters.
  - gpderetta 5y ago
    Some compilers these days offer 128bit floats (which is different from 754 quad) which is basically twice the mantissa of a standard double. IIRC multiplications and additions are relatively cheap.
  - jeffbee 5y ago
    Adding hardware to speed up decimal number handling strikes me as an old-school approach, the type of thing you might expect from 1960s mainframes. Isn't the more significant opportunity at the application architecture level instead? Why exchange numbers between computers in decimal? Even for people who are just devoted to the idea of human readability, which is an idea in need of scrutiny in my opinion, you can still exchange real numbers in base 16 format, 0xh.hPd.
    - beached_whale 5y ago
      hex floats are great, but text formats using decimal floats are ubiquitous and never going away.
    - Someone 5y ago
      I wouldn’t expect that from 1960’s mainframes. In cases where ingestion and outputting of decimal numbers could be a bottleneck, they would be programmed in COBOL, with a compiler using BCD (https://en.wikipedia.org/wiki/Binary-coded_decimal https://en.wikipedia.org/wiki/Binary-coded_decimal) to store numbers. Also, x87 has/had the FBLD and FBSTP instructions that can be used to convert between floating point and packed decimal (https://en.wikipedia.org/wiki/Intel_BCD_opcode https://en.wikipedia.org/wiki/Intel_BCD_opcode) If these still are supported, I doubt Intel or AMD spend lots of effort making/keeping them fast, though.

stephencanon 5y ago

Converting a number from string can be done without any bignum operations at all, this has been well-understood for a while now. This is mostly just widely-used libraries having not caught up with the state of the art. There is some opportunity for ISA support to speed it up, but multiplication by powers of ten is not the bottleneck, that’s just a table lookup and full-width product in high-performance implementations (i.e. a load and a mul instruction).

beached_whale 5y ago
Got links? Even Daniel Lemire's Fast Double parser will dump to strtod when the numbers are not handleable because of this. You cannot represent 10^x, or even all 5^x beyond a certain point in IEEE754 double's but need to do the full y * 10^x operation without loss. Doing it lossy is easy(0 to 1 or 2 ulp off optimal)
- stephencanon 5y ago
  You don’t need to do it without loss, you need to do it with loss smaller than the closest that the digit sequence could be to an exact halfway point between two representable double-precision values. This means you may need arbitrary-precision for arbitrary-precision decimal strings, but in practice these libraries are “always” converting strings that came from formatting exact doubles (eg round-tripping through JSON), and so have bounded precision. Thus you can tightly bound the precision required. This precisely mirrors how formatting fp numbers used to require bignum arithmetic, but all the recent algorithms (Ryu, Dragonbox, SwiftDtoa) do it with fixed int128 arithmetic and deliver always correct results. We’ll see analogous algorithms for the other direction adopted in the next few years—the only reason this direction came later is that the other was a bigger performance problem originally.
  - beached_whale 5y ago
    I use dragonbox and it makes the serialization task quite easy and fast. It would be great for a mirror library that did so for deserialization of arbitrary decimal numbers. The current libraries are not fast, and it isn't the parsing, it's the math they do with those characters.
- gpderetta 5y ago
  Some compilers these days offer 128bit floats (which is different from 754 quad) which is basically twice the mantissa of a standard double. IIRC multiplications and additions are relatively cheap.
- jeffbee 5y ago
  Adding hardware to speed up decimal number handling strikes me as an old-school approach, the type of thing you might expect from 1960s mainframes. Isn't the more significant opportunity at the application architecture level instead? Why exchange numbers between computers in decimal? Even for people who are just devoted to the idea of human readability, which is an idea in need of scrutiny in my opinion, you can still exchange real numbers in base 16 format, 0xh.hPd.
  - beached_whale 5y ago
    hex floats are great, but text formats using decimal floats are ubiquitous and never going away.
  - Someone 5y ago
    I wouldn’t expect that from 1960’s mainframes. In cases where ingestion and outputting of decimal numbers could be a bottleneck, they would be programmed in COBOL, with a compiler using BCD (https://en.wikipedia.org/wiki/Binary-coded_decimal https://en.wikipedia.org/wiki/Binary-coded_decimal) to store numbers. Also, x87 has/had the FBLD and FBSTP instructions that can be used to convert between floating point and packed decimal (https://en.wikipedia.org/wiki/Intel_BCD_opcode https://en.wikipedia.org/wiki/Intel_BCD_opcode) If these still are supported, I doubt Intel or AMD spend lots of effort making/keeping them fast, though.