Support floating-point formatting

[Viatorus]

• Check if dragonbox has an acceptable binary size (for single and double precision)
• If not, find an alternative
• implement the low-level writer API
• implement the high-level format API
  • support hexfloat
  • float is upcasted to double (is this a real issue?)

[Viatorus]

• Dragonbox can "only" find the shortest representation but not with arbitrary precision.
• There exist some other newer algorithm like floff, Ryu or Grisu3. They are all faster than Dragon4.
• Dragon4 does use way less binary size so I went with this one. But the current implementation requires much stack size (~1 - 1.5 kByte)

[Viatorus]

Some more questions occurred, why I choose Dragon4.

My selection criteria were:

1. it should be possible to format and scan floating-point values
2. it should be possible to format the shortest form and the fixed-precision form
3. it should not take up much binary size
4. it should be fast

Results for 4., shortest form

dragonbox > (is faster than) ryu > grisu-exact > dragon4

Reference:

• https://github.com/jk-jeon/dragonbox

Results for 4., fixed-precision form

floff> (is faster than) ryu > grisu2 > dragon4

Reference:

• https://github.com/jk-jeon/floff
• https://github.com/miloyip/dtoa-benchmark#results

Results for 3., binary code size

• fmtlib's implementation with Dragonbox and Grisu2 requires 7.5 kB
• floff's implementation requires 25.8 kB
• floff's compressed implementation requires 12.5 kB
• emio's Dragon4 implementation requires 3.7 kB
• No test result of ryu available anymore but if I remember correctly, it was much huger than floff

Reference:

• https://github.com/Viatorus/emio/actions/runs/6499455368/job/17652837377?pr=73
• https://github.com/Viatorus/emio/actions/runs/6499455368/job/17652837106?pr=73 (for snprintf since nano-spec doesn't have a full floating point implementation)

Results for 2., shortest form and fixed-precision form

• both forms:
  • Dragon4
  • ryu
• shortest form:
  • Dragonbox only for
  • Grisu-Exact for shortest form
• fixed-precision form:
  • Grisu2 for fixed-precision form
  • floff only for fixed-precision form

Conclusion: To offer both forms, I would have to combine different algorithms, which in turn increases the binary size.

Results for 1., format and scan

As far as I am aware of, only with arbitrary integer arithmetic a string can be exactly parsed into a double. Please correct me if a am wrong!

So with Dragon4, which already uses arbitrary integer arithmetic, I can save binary code size. But I also don't know a good algorithm & implementation of the parsing part yet...

Current Winner

Dragon4, because the code reuse decreases the required binary size significant.

The downsides of Dragon4:

The current implementation is based on https://github.com/rust-lang/rust/blob/71ef9ecbdedb67c32f074884f503f8e582855c2f/library/core/src/num/flt2dec/strategy/dragon.rs because it was the cleanest I have found.

it is a slow algorithm

• shortest form is ~8.5 (gcc), ~10 (clang) times slower than dragonbox (from fmtlib)
• fixed-precsion form is ~2.5 times slower than Grisu2 (from fmtlib)
• fixed-precsion form is ~1.5 times slower than printf's Dragon4 implementation

Reference:

• https://github.com/Viatorus/emio/actions/runs/6499455368/job/17652836162?pr=73
• https://github.com/Viatorus/emio/actions/runs/6499455368/job/17652836927?pr=73

requires much stack size

Embedded devices often have less RAM (128 kB - 2 MB). If an RTOS is used, each task stack is a fraction of it.
To avoid heap allocation (not like the printf implementation is doing it), the big integers are allocated on the stack.

One big integer object requires 140 bytes (size_t + 34 * 4 bytes) (32 bit system).

• emio::detail::format::format_exact requires 0.8 kB of stack
• emio::detail::format::format_shortest requires 1.2 kB of stack
• (floff e.g. only requires ~0.2 kB)