12 ms·

Formatting floating point numbers

170 points by matt_d 7y ago

cbsmith 7y ago
This highlights, for me, one of the reasons why our obsession with "human readable" serialization formats is so misplaced. You're burning up a lot of CPU power here, potentially creating a synchronization point, just to do something that could be addressed with a simple 4 or 8 byte memcpy.
- taneq 7y ago
  The thing is, "human readable" files aren't, once they get to a nontrivial size. Picking apart a megabyte XML file in a text editor is arguably harder than the same data as a blob in a hex editor. In fact, thinking about it now, I bet Wireshark would be awesome for that.
  - otabdeveloper3 7y ago
    "Human readable" means "forward-compatible and debugabble without specialized tools". Humans aren't actually reading these things.
  - renox 7y ago
    ??? Even integers are difficult to read in an hex editors thanks to little endianness..
    - taneq 7y ago
      Eh, once you're used to reading integers in hexadecimal, byte order isn't that important. If I told you that 1234 was going to be written right to left, you'd know how big 4321 was, right?
- fluffything 7y ago
  > that could be addressed with a simple 4 or 8 byte memcpy. This won't account for endianness.
  - jgtrosh 7y ago
    Floating point formatting deals only with the default endianness of the hardware though. Afaik if you need to deal with that you have to do it yourself regardless (with bswap functions or similar).
  - pedrocr 7y ago
    In a serialization format you should explicitly define the endianness to be used and then convert to and from it explicitly in the serialize/deserialize code. So memcpy is wrong but the grandparent point still stands. Defining a serialization format for float/double that's just 4/8 bytes in little-endian might be a better idea than the mess we sometimes have right now because IEE-754 is more of a standard than anything else in the space.
  - userbinator 7y ago
    Fortunately much of the world has already settled on an endianness, and the one that happens to be most logical to process (byte offset n has weight 256^n, much like bit x has weight 2^x.) In the future, hopefully big-endian machines will be as uncommon as bytes that are not 8 bits, and the only protocols still using it are the ones which were designed long ago.
- lelf 7y ago
  “Something in the middle” could be an option. E. g. (in C) > printf ("%a\n", M_PI); 0x1.921fb54442d18p+1 > printf ("%a\n", 42.0); 0x1.5p+5
  - 0815test 7y ago
    This should be a lot higher. Hexfloats are not just a C/C++ thing, plenty of languages and software packages support them by now. And they can very much be used as part of a text input format, to avoid the sizeable overhead of "human-friendly" float parsing. If you maintain a text-based format that has any chance of being a CPU/compute bottleneck in this way, you should definitely make sure that hexfloats are supported! Edit: someone else mentioned that roundtrip accuracy could also be an issue. Theoretically true, I guess, but really, if you want to use decimal-based float input you should just use an algorithm that roundtrips correctly, and eat that overhead. Anything else has a potential to impact reproducibility of results, etc. It's not worth it silently corrupting your data just for that saving in compute cost.
  - brandmeyer 7y ago
    Hear, hear! Sometimes you do need to reliably communicate a floating-point number across a text channel. Hex float is low-risk in the sense that both the encoding and decoding process are much simpler and therefore easier to verify than something that round-trips through decimal. Yes, there are some correct implementations of the decimal<->binary algorithms that round-trip correctly. But there also remain a number of incorrect implementations.
    - cbsmith 7y ago
      To be clear: human readable formats when you have humans reading the data makes sense. What is insane is having machines reading & writing human readable formats to talk to each other.
- tomxor 7y ago
  It also creates a lot of misconceptions of how accurate floating point math is. An interesting aspect of decimal formatting is how it frequently masks representation error (i.e encoding of 0.1 etc), because the error is symmetrical in the formatter/parser it makes such non-representable fractions appear to be stored perfectly to unsuspecting users. This can be quite deceptive, if more users were aware of just how many of the simple rational decimals they input were converted into imprecise representations they probably wouldn't trust computers as much as they do. To confuse things more, when operating upon periodic representations the result often matches the representation error of the the equivalent accurate decimal value encoded directly (i.e there were errors, but everything canceled out through formatting) - when they occasionally do not (e.g 0.1 + 0.2) it makes the problem appear all the more elusive. I think this detail is often lost in explanations of 0.1 + 0.2, that is: representation error is extremely common, 0.1 + 0.2 is merely one of the cases where it both persists through the formatter AND you notice it because the inputs were short decimals, and it's so obvious that the output should be a non-periodic decimal.. TL;DR formatting floats to decimals makes us trust floating point math far more than we should - it's healthy to remember that the formatting process is necessarily imprecise and that you are merely looking at a proxy for the underlying value. Remember that next time you look at _seemingly_ non-periodic decimal output.
  - bunderbunder 7y ago
    Or perhaps it makes us mistrust more than we should? How often are we working on problems where the difference between 0.1 and 0.100000000000000006 is of any practical importance? When I format a float out to 5 decimal places, I'm sort of making a statement that anything beyond that doesn't matter to me.
    - tomxor 7y ago
      > When I format a float out to 5 decimal places, I'm sort of making a statement that anything beyond that doesn't matter to me. Yes, it's true the vast majority of the time it doesn't actually matter. However decimal formatting does such a good job at giving us the impression that these errors are merely edge-cases, and calculators automatically formatting to 10sf etc further that illusion. If people are not aware it's only an illusion (or just how far the rabbit hole goes) it can be dangerous when they go on to create or use things where that fact matters.
- TorKlingberg 7y ago
  The "obsession" came about from all the problems with binary formats. Byte ordering. Unspecified signedness. Memcpy:ing structs with padding. Programmers micro-optimizing by choosing the smallest possible field size, and then you can't change it when it turns out to be too small. Format specs using WORD as if that's a well-defined size. Using int, long, etc, and assuming they are the same size everywhere. It's a trade-off of CPU usage versus flexibility. It's not surprising that textual serialization formats took off together with managed memory languages.
  - datenwolf 7y ago
    Byte ordering issues are easily addressed by still emitting text, but not converting to a base that differs in a prime factor. Just emit the mantissa and exponent in – say – hexadecimal form and the negative sign bit as a `-`. It avoids all the endianes issues and is trivially converted.
  - IshKebab 7y ago
    Rubbish. It's possible to have poorly defined text formats just as easily as binary formats. Remind me how to read CSV again? How do I store 64-bit integers in JSON? Text formats are popular because you don't have to use a special tool to view them. That's the only reason.
    - cbsmith 7y ago
      > Text formats are popular because you don't have to use a special tool to view them. That's the only reason. But you need a special tool to get a computer to read them. Seems like not a win. Throw in compression & encryption... and suddenly you need a special tool anyway.
  - cbsmith 7y ago
    Fortunately with text you can't have issues with byte ordering, unspecified signedness, or padding... oh wait. ;-)
- bunderbunder 7y ago
  I'm also not convinced they help human readability that much. e.g., when I've done my own binary formats, I typically also create a "dump" utility that converts the file to a readable text dump. I find the ergonomics of this are just fine for my purposes. less somefile.json isn't that much easier to type than dumpdat somefile.dat | less That said, different purposes are different. I'm not so worried about human-readability for short-lived stuff, but, if you're talking about data that may be sitting around for decades, then the human readability question becomes something you might better characterize as "future comprehensibility": If someone's trying to dust off 50-year-old business data from deep in the archives, they're going to have a much higher chance of success if it's CSV files than if it's in some custom binary format whose documentation was lost 40 years ago.
- roel_v 7y ago
  A few years ago I wrote a naive Java string-to-floating point conversion routine that only converted 'simple' numbers, i.e. no scientific notation, only one (fixed) decimal separator, etc. It was the first Java code I had written in 10 years and the approach was probably not very Java-esque (I imitated what I'd do in C++, using (IIRC) java.nio.ByteBuffer or something similar). Anyway this simple implementation was ~10 times faster than the 'officially' suggested way, using formatted string conversion routines, even after asking around (on SO and similar) on how to do high performance string-to-float conversion. There are probably similar issues in other programming languages, this is not to rag on Java; my point is that when you don't need the 'fancy' floating point formatting stuff, and you need high performance (in my case, I had to convert many billions of floating-points-as-strings and the conversion took ~50% of my program's runtime, which was measured in days), it can pay off to write a custom version of something as seemingly mundane as converting a string to a number.
  - buckminster 7y ago
    I had the same experience the other way. I halved the runtime of an ETL program by writing a custom float to string function.
  - chrchang523 7y ago
    The biggest win, in my experience, is simply recognizing when you don’t need all ~16 significant digits provided by the standard implementations. If you’re only printing e.g. six digits, and can afford to round in the wrong direction 0.00000001% of the time, you can skip a ton of work. And as you mention, it gets even easier when you don’t have to support scientific notation. The standard library functions occupy an awkward middle ground between this type of much faster, slightly sloppy float-to-string converter, and direct storage of the binary representation; in most applications where float serialization performance is actually relevant, at least one of these two alternatives is better.
    - Vindicis 7y ago
      Agreed. I deal with financial data which is in well-defined formats for the various asset classes. You can save a lot of time by just writing some parsing functions to deal with your exact needs and avoid needless work. And, hopefully avoid using the built-in functions for conversions as those will almost always be A LOT slower due to what they're required to handle. I prefer to store that type of data in csv files because there are times when you need to read through the data to find errors, adhoc analysis, etc....If you're loading those types of files very frequently, there are better formats of course. But, when the parsing time is peanuts compared to the runtime of your program, it's nice to be able to load the file into other programs when you need without having to convert it first.
- forgottenpass 7y ago
  >You're burning up a lot of CPU power here This is easy to write off as micro-optimizing, but it's no joke. I recently profiled some hard real-time software and was surprised to find that >50% of busy processor time was spent somewhere in the fcvt() family of functions. It's fine for the use case in the medium term (we're within deadline and not starving for more cycles) so I'm avoiding the serialization format transition headache, but it did send me down the rabbit hole of floating point conversion techniques for half a day.
- FabHK 7y ago
  Sometimes I wish one could configure REPLs, for example, to print floats not as the shortest input which maps to that float ("0.1"), but the actual number represented by the float ("0.1000000000000000055511151231257827021181583404541015625") by default. Somewhat annoying, but might avoid a lot of confusion ("Is floating point math broken?", https://stackoverflow.com/questions/588004/is-floating-point-math-broken https://stackoverflow.com/questions/588004/is-floating-point... ).
  - klodolph 7y ago
    Would you like 1e-100 to print as 1.00000000000000001999189980260288361964776078853415942018260300593659569925554346761767628861329298958274607481091185079852827053974965402226843604196126360835628314127871794272492894246908066589163059300043457860230145025079449986855914338755579873208034769049845635890960693359375e-100?
    - FabHK 7y ago
      Nice example! Makes sense that it can get quite long, though it was not present in my mind. But, hey, that's what the number represented actually is. As I said, make it optional...
  - firethief 7y ago
    IMO hex should be the default representation of binary fp. Printing hex gives the exact value, without giving the illusion of having precision in the hundreds of digits, and can be done way faster than conversion to decimal. >>> 0.1.hex() 0x1.999999999999ap-4 >>> 1e-100.hex() 0x1.bff2ee48e0530p-333
- userbinator 7y ago
  Indeed, "human readable" really means "in something similar to English" much of the time, and is a vague and quite subjective term; would someone who knows only English think Chinese is not "human readable"? Personally, I consider binary formats to be just as readable (from the hexdump, or sometimes even the ASCII directly) and in some ways even easier to parse without ambiguity --- it just requires a bit (pun intended) of learning, like any language. I've worked with someone who could "read" TCP/IP; and I can read much of Z80 and some x86 Asm as well as a few other binary formats.
ChrisMarshallNY 7y ago
This is interesting. I have learned to just use whatever operating system/RTL utilities are provided (like Apple's NumberFormatter class).
ramzeus 7y ago
To me the most complicated thing about formatting and parsing floating point numbers is usually if it uses decimal comma or decimal dot. It never seems to be what you expect if using a mix of different language operating systems.
- mort96 7y ago
  As someone from a country which uses commas as a decimal separator (Norway)... Just use a dot. If you're not going to make a _serious_ commitment to actually make your software work well in all the various locales, use a dot. People will understand it regardless. You're probably going to do something stupid like showing the user a comma-separated list of numbers at some point, which will be needlessly hard to parse for a human when your numbers use a comma as a decimal separator. You (or someone else, or your users if they are technical) will probably at some point make something which tries to parse some output, and that will break if you switch between points and commas arbitrarily. Your users will want to copy a number your software prints and paste it into a calculator or REPL or something, and that probably doesn't work with comma as a decimal separator. Half-assed "localization" from people who don't know anything about how other countries work is just needlessly annoying to be subjected to. That's at least my perspective as a Norwegian who experiences a lot of _bad_ localization even though I know English fairly well and configure all my computing devices to use English. The perspective of someone from a country where English is less well known might be different. <rant> Examples of horrible localization from clueless American companies or organizations include: * A lot of software will use your IP address to determine your language. That's annoying when I'm in Norway and want my computers to use English, but it's horrible when abroad. No, Google, I don't want French text just because I'm staying in France for a bit. * Software will translate error messages, but not provide an error code. All information about error messages online is in English on stackoverflow or whatever. If Debian prints an error message in Norwegian, there's absolutely no information about the error anywhere on the web. * There was a trend for a while where websites would tick the "localization" checkbox by adding a Google Translate widget, so English websites would automatically translate themselves into completely broken Norwegian automatically. That would've been useless if I didn't know English, and it's even worse considering I already know the source language just as well as Norwegian. Luckily, most websites seem to have stopped doing that. </rant>
nabla9 7y ago
Can this formatting provide round trip for all double floats? The article don't say it.
- ufo 7y ago
  I'm not sure, but generally speaking converting doubles to strings will fail to round trip at least the NaNs If round tripping is important, my recommendation would be to output something that directly corresponds to the binary representation of the float. For example, printf %a
  - theoh 7y ago
    See this article for an in-depth look at implementing these conversions: https://research.swtch.com/ftoa https://research.swtch.com/ftoa
- floitsch 7y ago
  Yes. These algorithms (Grisu, Ryu, ...) all satisfy the "internal identity requirement", which means that they can print a double and read it back in to the same double. The harder part is to also produce the shortest of all possible string-representations. (And then picking the closest if there are many).
- ryani 7y ago
  These are two separate problems. This is talking about printing floating point numbers, and does not talk about parsing algorithms at all. When considering the correctness of a floating point decimal printing algorithm, you could use "round trips with Y parsing algorithm", but that's flawed -- it ties the printing algorithm directly to a particular parsing algorithm. Instead what is usually considered is "what is the closest representable floating point value to the real value output by the printing algorithm?" If the printing algorithm outputs a string representation which is closer to the input float than it is to any other float, then it's correct. It's up to each parsing algorithm to provide the reverse condition -- that it parses each string to the float which is closest to the real value of the represented string. Modern float-print algorithms like Grisu / Dragon / etc. also add the additional restriction that they output the shortest possible string that meets that condition; for example, the real number 0.69999998 is closer to the 32-bit float (0b1.011_0011_0011_0011_0011_0011 * 2^-1, represented in memory as 0x3f333333) than any other float. The real number 0.7 is slightly further from that float, but it's still closer to it than any other float, and is much shorter -- those algorithms should print that float as "0.7". A correct parser should parse both the string "0.7" and "0.69999998" to the same 32-bit float result.
deleted 7y ago
[deleted]
ncmncm 7y ago
I don't understand why anyone would write a new Grisu conversion, with Ryu 3x as fast. It might have educational benefits, preparing you for a Ryu conversion, but shipping it?
- shereadsthenews 7y ago
  Ryu is only a year old. Grisu is 10 years old. It takes time for people to absorb these things.
jnordwick 7y ago
We had such floating point printing performance issues in java once that i needed to implement a grisu variant that didn't fall into bignum calculations and had few other tweaks to short circuit the printing and improve some common cases. It made a decent impact especially on garbage generation (it was specifically zero gc). Since been ported to a couple other languages, and I was thinking of redoing it lately for another project and using the newer algo. https://github.com/jnordwick/zerog-grisu https://github.com/jnordwick/zerog-grisu
floitsch 7y ago
Author of Grisu here. It's really surprising, how long it took to find the most efficient algorithms for double-conversions. In 1980 Coonen already published a good algorithm, but that one was kind-of lost. For a long time Steele & White's algorithm was the state-of-the-art (with some improvements here and there over time). Now, Ryu is by far the fastest algorithm out there, but that took ages... Unfortunately, there doesn't seem to be an easy-to-use, complete library for Ryu yet. The Grisu library (https://github.com/google/double-conversion https://github.com/google/double-conversion) is probably still the go-to library if you don't want to implement it again...
- shereadsthenews 7y ago
  What about libfmt? Frankly I find it a little easier to use than double-conversion and it's equal in speed.
  - floitsch 7y ago
    Looks like a great library. Not sure I actually knew about it. I will probably update the double-conversion library README to add a link. Internally it uses the same algorithm, Grisu, (with some additional optimizations) so there shouldn't be any difference in output. If it's easier to use for you, just go with it! I'm guessing the double-conversion library is a bit more flexible, but I could be wrong.
    - shereadsthenews 7y ago
      libdouble-conversion is indeed far more flexible. I think that's what leads to all the extra typing! I mean, just including it is almost more typing than I'm willing to undertake ;-) #include "third_party/double-conversion/double-conversion/double-conversion.h"
      - dunham 7y ago
        In emacs, Meta-/ might help. :) > Expands to the most recent, preceding word for which this is a prefix.
ChuckMcM 7y ago
Life is so much easier when you use decimal to represent your numbers [http://speleotrove.com/decimal/IEEE-cowlishaw-arith16.pdf http://speleotrove.com/decimal/IEEE-cowlishaw-arith16.pdf]

170 points by matt_d 7y ago

This highlights, for me, one of the reasons why our obsession with "human readable" serialization formats is so misplaced. You're burning up a lot of CPU power here, potentially creating a synchronization point, just to do something that could be addressed with a simple 4 or 8 byte memcpy.

taneq 7y ago
The thing is, "human readable" files aren't, once they get to a nontrivial size. Picking apart a megabyte XML file in a text editor is arguably harder than the same data as a blob in a hex editor. In fact, thinking about it now, I bet Wireshark would be awesome for that.
- otabdeveloper3 7y ago
  "Human readable" means "forward-compatible and debugabble without specialized tools". Humans aren't actually reading these things.
- renox 7y ago
  ??? Even integers are difficult to read in an hex editors thanks to little endianness..
  - taneq 7y ago
    Eh, once you're used to reading integers in hexadecimal, byte order isn't that important. If I told you that 1234 was going to be written right to left, you'd know how big 4321 was, right?
fluffything 7y ago
> that could be addressed with a simple 4 or 8 byte memcpy. This won't account for endianness.
- jgtrosh 7y ago
  Floating point formatting deals only with the default endianness of the hardware though. Afaik if you need to deal with that you have to do it yourself regardless (with bswap functions or similar).
- pedrocr 7y ago
  In a serialization format you should explicitly define the endianness to be used and then convert to and from it explicitly in the serialize/deserialize code. So memcpy is wrong but the grandparent point still stands. Defining a serialization format for float/double that's just 4/8 bytes in little-endian might be a better idea than the mess we sometimes have right now because IEE-754 is more of a standard than anything else in the space.
- userbinator 7y ago
  Fortunately much of the world has already settled on an endianness, and the one that happens to be most logical to process (byte offset n has weight 256^n, much like bit x has weight 2^x.) In the future, hopefully big-endian machines will be as uncommon as bytes that are not 8 bits, and the only protocols still using it are the ones which were designed long ago.
lelf 7y ago
“Something in the middle” could be an option. E. g. (in C) > printf ("%a\n", M_PI); 0x1.921fb54442d18p+1 > printf ("%a\n", 42.0); 0x1.5p+5
- 0815test 7y ago
  This should be a lot higher. Hexfloats are not just a C/C++ thing, plenty of languages and software packages support them by now. And they can very much be used as part of a text input format, to avoid the sizeable overhead of "human-friendly" float parsing. If you maintain a text-based format that has any chance of being a CPU/compute bottleneck in this way, you should definitely make sure that hexfloats are supported! Edit: someone else mentioned that roundtrip accuracy could also be an issue. Theoretically true, I guess, but really, if you want to use decimal-based float input you should just use an algorithm that roundtrips correctly, and eat that overhead. Anything else has a potential to impact reproducibility of results, etc. It's not worth it silently corrupting your data just for that saving in compute cost.
- brandmeyer 7y ago
  Hear, hear! Sometimes you do need to reliably communicate a floating-point number across a text channel. Hex float is low-risk in the sense that both the encoding and decoding process are much simpler and therefore easier to verify than something that round-trips through decimal. Yes, there are some correct implementations of the decimal<->binary algorithms that round-trip correctly. But there also remain a number of incorrect implementations.
  - cbsmith 7y ago
    To be clear: human readable formats when you have humans reading the data makes sense. What is insane is having machines reading & writing human readable formats to talk to each other.
tomxor 7y ago
It also creates a lot of misconceptions of how accurate floating point math is. An interesting aspect of decimal formatting is how it frequently masks representation error (i.e encoding of 0.1 etc), because the error is symmetrical in the formatter/parser it makes such non-representable fractions appear to be stored perfectly to unsuspecting users. This can be quite deceptive, if more users were aware of just how many of the simple rational decimals they input were converted into imprecise representations they probably wouldn't trust computers as much as they do. To confuse things more, when operating upon periodic representations the result often matches the representation error of the the equivalent accurate decimal value encoded directly (i.e there were errors, but everything canceled out through formatting) - when they occasionally do not (e.g 0.1 + 0.2) it makes the problem appear all the more elusive. I think this detail is often lost in explanations of 0.1 + 0.2, that is: representation error is extremely common, 0.1 + 0.2 is merely one of the cases where it both persists through the formatter AND you notice it because the inputs were short decimals, and it's so obvious that the output should be a non-periodic decimal.. TL;DR formatting floats to decimals makes us trust floating point math far more than we should - it's healthy to remember that the formatting process is necessarily imprecise and that you are merely looking at a proxy for the underlying value. Remember that next time you look at _seemingly_ non-periodic decimal output.
- bunderbunder 7y ago
  Or perhaps it makes us mistrust more than we should? How often are we working on problems where the difference between 0.1 and 0.100000000000000006 is of any practical importance? When I format a float out to 5 decimal places, I'm sort of making a statement that anything beyond that doesn't matter to me.
  - tomxor 7y ago
    > When I format a float out to 5 decimal places, I'm sort of making a statement that anything beyond that doesn't matter to me. Yes, it's true the vast majority of the time it doesn't actually matter. However decimal formatting does such a good job at giving us the impression that these errors are merely edge-cases, and calculators automatically formatting to 10sf etc further that illusion. If people are not aware it's only an illusion (or just how far the rabbit hole goes) it can be dangerous when they go on to create or use things where that fact matters.
TorKlingberg 7y ago
The "obsession" came about from all the problems with binary formats. Byte ordering. Unspecified signedness. Memcpy:ing structs with padding. Programmers micro-optimizing by choosing the smallest possible field size, and then you can't change it when it turns out to be too small. Format specs using WORD as if that's a well-defined size. Using int, long, etc, and assuming they are the same size everywhere. It's a trade-off of CPU usage versus flexibility. It's not surprising that textual serialization formats took off together with managed memory languages.
- datenwolf 7y ago
  Byte ordering issues are easily addressed by still emitting text, but not converting to a base that differs in a prime factor. Just emit the mantissa and exponent in – say – hexadecimal form and the negative sign bit as a `-`. It avoids all the endianes issues and is trivially converted.
- IshKebab 7y ago
  Rubbish. It's possible to have poorly defined text formats just as easily as binary formats. Remind me how to read CSV again? How do I store 64-bit integers in JSON? Text formats are popular because you don't have to use a special tool to view them. That's the only reason.
  - cbsmith 7y ago
    > Text formats are popular because you don't have to use a special tool to view them. That's the only reason. But you need a special tool to get a computer to read them. Seems like not a win. Throw in compression & encryption... and suddenly you need a special tool anyway.
- cbsmith 7y ago
  Fortunately with text you can't have issues with byte ordering, unspecified signedness, or padding... oh wait. ;-)
bunderbunder 7y ago
I'm also not convinced they help human readability that much. e.g., when I've done my own binary formats, I typically also create a "dump" utility that converts the file to a readable text dump. I find the ergonomics of this are just fine for my purposes. less somefile.json isn't that much easier to type than dumpdat somefile.dat | less That said, different purposes are different. I'm not so worried about human-readability for short-lived stuff, but, if you're talking about data that may be sitting around for decades, then the human readability question becomes something you might better characterize as "future comprehensibility": If someone's trying to dust off 50-year-old business data from deep in the archives, they're going to have a much higher chance of success if it's CSV files than if it's in some custom binary format whose documentation was lost 40 years ago.
roel_v 7y ago
A few years ago I wrote a naive Java string-to-floating point conversion routine that only converted 'simple' numbers, i.e. no scientific notation, only one (fixed) decimal separator, etc. It was the first Java code I had written in 10 years and the approach was probably not very Java-esque (I imitated what I'd do in C++, using (IIRC) java.nio.ByteBuffer or something similar). Anyway this simple implementation was ~10 times faster than the 'officially' suggested way, using formatted string conversion routines, even after asking around (on SO and similar) on how to do high performance string-to-float conversion. There are probably similar issues in other programming languages, this is not to rag on Java; my point is that when you don't need the 'fancy' floating point formatting stuff, and you need high performance (in my case, I had to convert many billions of floating-points-as-strings and the conversion took ~50% of my program's runtime, which was measured in days), it can pay off to write a custom version of something as seemingly mundane as converting a string to a number.
- buckminster 7y ago
  I had the same experience the other way. I halved the runtime of an ETL program by writing a custom float to string function.
- chrchang523 7y ago
  The biggest win, in my experience, is simply recognizing when you don’t need all ~16 significant digits provided by the standard implementations. If you’re only printing e.g. six digits, and can afford to round in the wrong direction 0.00000001% of the time, you can skip a ton of work. And as you mention, it gets even easier when you don’t have to support scientific notation. The standard library functions occupy an awkward middle ground between this type of much faster, slightly sloppy float-to-string converter, and direct storage of the binary representation; in most applications where float serialization performance is actually relevant, at least one of these two alternatives is better.
  - Vindicis 7y ago
    Agreed. I deal with financial data which is in well-defined formats for the various asset classes. You can save a lot of time by just writing some parsing functions to deal with your exact needs and avoid needless work. And, hopefully avoid using the built-in functions for conversions as those will almost always be A LOT slower due to what they're required to handle. I prefer to store that type of data in csv files because there are times when you need to read through the data to find errors, adhoc analysis, etc....If you're loading those types of files very frequently, there are better formats of course. But, when the parsing time is peanuts compared to the runtime of your program, it's nice to be able to load the file into other programs when you need without having to convert it first.
forgottenpass 7y ago
>You're burning up a lot of CPU power here This is easy to write off as micro-optimizing, but it's no joke. I recently profiled some hard real-time software and was surprised to find that >50% of busy processor time was spent somewhere in the fcvt() family of functions. It's fine for the use case in the medium term (we're within deadline and not starving for more cycles) so I'm avoiding the serialization format transition headache, but it did send me down the rabbit hole of floating point conversion techniques for half a day.
FabHK 7y ago
Sometimes I wish one could configure REPLs, for example, to print floats not as the shortest input which maps to that float ("0.1"), but the actual number represented by the float ("0.1000000000000000055511151231257827021181583404541015625") by default. Somewhat annoying, but might avoid a lot of confusion ("Is floating point math broken?", https://stackoverflow.com/questions/588004/is-floating-point-math-broken https://stackoverflow.com/questions/588004/is-floating-point... ).
- klodolph 7y ago
  Would you like 1e-100 to print as 1.00000000000000001999189980260288361964776078853415942018260300593659569925554346761767628861329298958274607481091185079852827053974965402226843604196126360835628314127871794272492894246908066589163059300043457860230145025079449986855914338755579873208034769049845635890960693359375e-100?
  - FabHK 7y ago
    Nice example! Makes sense that it can get quite long, though it was not present in my mind. But, hey, that's what the number represented actually is. As I said, make it optional...
- firethief 7y ago
  IMO hex should be the default representation of binary fp. Printing hex gives the exact value, without giving the illusion of having precision in the hundreds of digits, and can be done way faster than conversion to decimal. >>> 0.1.hex() 0x1.999999999999ap-4 >>> 1e-100.hex() 0x1.bff2ee48e0530p-333
userbinator 7y ago
Indeed, "human readable" really means "in something similar to English" much of the time, and is a vague and quite subjective term; would someone who knows only English think Chinese is not "human readable"? Personally, I consider binary formats to be just as readable (from the hexdump, or sometimes even the ASCII directly) and in some ways even easier to parse without ambiguity --- it just requires a bit (pun intended) of learning, like any language. I've worked with someone who could "read" TCP/IP; and I can read much of Z80 and some x86 Asm as well as a few other binary formats.

ChrisMarshallNY 7y ago

This is interesting. I have learned to just use whatever operating system/RTL utilities are provided (like Apple's NumberFormatter class).

ramzeus 7y ago

To me the most complicated thing about formatting and parsing floating point numbers is usually if it uses decimal comma or decimal dot. It never seems to be what you expect if using a mix of different language operating systems.

mort96 7y ago
As someone from a country which uses commas as a decimal separator (Norway)... Just use a dot. If you're not going to make a _serious_ commitment to actually make your software work well in all the various locales, use a dot. People will understand it regardless. You're probably going to do something stupid like showing the user a comma-separated list of numbers at some point, which will be needlessly hard to parse for a human when your numbers use a comma as a decimal separator. You (or someone else, or your users if they are technical) will probably at some point make something which tries to parse some output, and that will break if you switch between points and commas arbitrarily. Your users will want to copy a number your software prints and paste it into a calculator or REPL or something, and that probably doesn't work with comma as a decimal separator. Half-assed "localization" from people who don't know anything about how other countries work is just needlessly annoying to be subjected to. That's at least my perspective as a Norwegian who experiences a lot of _bad_ localization even though I know English fairly well and configure all my computing devices to use English. The perspective of someone from a country where English is less well known might be different. <rant> Examples of horrible localization from clueless American companies or organizations include: * A lot of software will use your IP address to determine your language. That's annoying when I'm in Norway and want my computers to use English, but it's horrible when abroad. No, Google, I don't want French text just because I'm staying in France for a bit. * Software will translate error messages, but not provide an error code. All information about error messages online is in English on stackoverflow or whatever. If Debian prints an error message in Norwegian, there's absolutely no information about the error anywhere on the web. * There was a trend for a while where websites would tick the "localization" checkbox by adding a Google Translate widget, so English websites would automatically translate themselves into completely broken Norwegian automatically. That would've been useless if I didn't know English, and it's even worse considering I already know the source language just as well as Norwegian. Luckily, most websites seem to have stopped doing that. </rant>

nabla9 7y ago

Can this formatting provide round trip for all double floats? The article don't say it.

ufo 7y ago
I'm not sure, but generally speaking converting doubles to strings will fail to round trip at least the NaNs If round tripping is important, my recommendation would be to output something that directly corresponds to the binary representation of the float. For example, printf %a
- theoh 7y ago
  See this article for an in-depth look at implementing these conversions: https://research.swtch.com/ftoa https://research.swtch.com/ftoa
floitsch 7y ago
Yes. These algorithms (Grisu, Ryu, ...) all satisfy the "internal identity requirement", which means that they can print a double and read it back in to the same double. The harder part is to also produce the shortest of all possible string-representations. (And then picking the closest if there are many).
ryani 7y ago
These are two separate problems. This is talking about printing floating point numbers, and does not talk about parsing algorithms at all. When considering the correctness of a floating point decimal printing algorithm, you could use "round trips with Y parsing algorithm", but that's flawed -- it ties the printing algorithm directly to a particular parsing algorithm. Instead what is usually considered is "what is the closest representable floating point value to the real value output by the printing algorithm?" If the printing algorithm outputs a string representation which is closer to the input float than it is to any other float, then it's correct. It's up to each parsing algorithm to provide the reverse condition -- that it parses each string to the float which is closest to the real value of the represented string. Modern float-print algorithms like Grisu / Dragon / etc. also add the additional restriction that they output the shortest possible string that meets that condition; for example, the real number 0.69999998 is closer to the 32-bit float (0b1.011_0011_0011_0011_0011_0011 * 2^-1, represented in memory as 0x3f333333) than any other float. The real number 0.7 is slightly further from that float, but it's still closer to it than any other float, and is much shorter -- those algorithms should print that float as "0.7". A correct parser should parse both the string "0.7" and "0.69999998" to the same 32-bit float result.

deleted 7y ago

[deleted]

ncmncm 7y ago

I don't understand why anyone would write a new Grisu conversion, with Ryu 3x as fast. It might have educational benefits, preparing you for a Ryu conversion, but shipping it?

shereadsthenews 7y ago
Ryu is only a year old. Grisu is 10 years old. It takes time for people to absorb these things.

jnordwick 7y ago

We had such floating point printing performance issues in java once that i needed to implement a grisu variant that didn't fall into bignum calculations and had few other tweaks to short circuit the printing and improve some common cases. It made a decent impact especially on garbage generation (it was specifically zero gc). Since been ported to a couple other languages, and I was thinking of redoing it lately for another project and using the newer algo. https://github.com/jnordwick/zerog-grisu https://github.com/jnordwick/zerog-grisu

floitsch 7y ago

Author of Grisu here. It's really surprising, how long it took to find the most efficient algorithms for double-conversions. In 1980 Coonen already published a good algorithm, but that one was kind-of lost. For a long time Steele & White's algorithm was the state-of-the-art (with some improvements here and there over time). Now, Ryu is by far the fastest algorithm out there, but that took ages... Unfortunately, there doesn't seem to be an easy-to-use, complete library for Ryu yet. The Grisu library (https://github.com/google/double-conversion https://github.com/google/double-conversion) is probably still the go-to library if you don't want to implement it again...

shereadsthenews 7y ago
What about libfmt? Frankly I find it a little easier to use than double-conversion and it's equal in speed.
- floitsch 7y ago
  Looks like a great library. Not sure I actually knew about it. I will probably update the double-conversion library README to add a link. Internally it uses the same algorithm, Grisu, (with some additional optimizations) so there shouldn't be any difference in output. If it's easier to use for you, just go with it! I'm guessing the double-conversion library is a bit more flexible, but I could be wrong.
  - shereadsthenews 7y ago
    libdouble-conversion is indeed far more flexible. I think that's what leads to all the extra typing! I mean, just including it is almost more typing than I'm willing to undertake ;-) #include "third_party/double-conversion/double-conversion/double-conversion.h"
    - dunham 7y ago
      In emacs, Meta-/ might help. :) > Expands to the most recent, preceding word for which this is a prefix.

ChuckMcM 7y ago

Life is so much easier when you use decimal to represent your numbers [http://speleotrove.com/decimal/IEEE-cowlishaw-arith16.pdf http://speleotrove.com/decimal/IEEE-cowlishaw-arith16.pdf]