new double to string algorithm

[xjb714]

https://gitee.com/xjb714/dtoa-benchmark

English:
The source code is in this link src/d2sci/d2s.cpp/d2s_sse.

Sse implementation based on schubfach, the performance is about 1.5 times that of dragonbox or dtoa algorithm in yyjson at present. Please decide whether to adopt it after testing.

This project also includes the realization of other floating-point printing algorithms, which can be used if you are interested.

This project only contains double-precision floating-point printing algorithm.

中文：
源代码在这个链接src/d2sci/d2s.cpp/d2s_sse。

基于schubfach的sse实现，性能是dragonbox或目前yyjson中dtoa算法的1.5倍左右。请经过测试后决定是否采纳。

本项目还包含了其他浮点数打印算法的实现，如果感兴趣也可使用。

本项目中只包含双精度浮点数打印算法。

[ibireme]

Thanks! Your new algorithm looks great performance-wise. But yyjson focuses on portability, so I can't use SSE or AVX-specific code directly.

I also have a benchmark project for testing number conversion algorithms: https://github.com/ibireme/c_numconv_benchmark The benchmark results are there:

Intel Core i5 13600KF (does not support AVX512)
Clang 18.1.3
Ubuntu 24.04 LTS

The yy here is my new floating-point to string algorithm. I'm still working on a paper to prove the mathematical correctness of the algorithm, so it's not in yyjson yet.

It improves binary-to-decimal conversion, which might help with your algorithm too: https://github.com/ibireme/c_numconv_benchmark/blob/master/vendor/yy_double/yy_double.c

[xjb714]

English:
I use icpx 2025.0.4 -O3 to compile my code. clang++ seems to be a little less efficient than icpx, and g++ seems to be even less efficient. Generally speaking, the performance of icpx after compilation is better. The link I sent before contains the static library d2sci2 (compiled by AMD R7-7840H). You can use the benchmark program to link this library and try the result of d2s_sse algorithm again. I made a benchmark in my notebook, which is a little different from your result. The following is my benchmark result. After downloading, I changed the file suffix to html.

report_dtoa3.txt

The SSE instruction set is now included in almost all consumer-grade CPUs, and there are very few CPUs without SSE instruction set. Maybe you can provide SSE, AVX2, and even AVX512 APIs in later versions of yyjson to make the best use of CPU performance, or dynamically select the API with the best performance according to CPU at runtime, but it seems to be difficult to realize.

My link also includes the function d2s_32v, which is based on the AVX512 implementation of Schubfach, and uses the AVX512 instruction to calculate the ASCII results of 32 double values in parallel, that is, to generate the shortest significant number. At present, it takes about 2.4ns to print a single double value in AMD R9-9950X, but it needs to be proved and improved. This API application scenario is to print a large number of double-precision floating-point numbers, which has a great performance improvement when the data volume is particularly large.

thank you

中文：
我使用icpx 2025.0.4 -O3编译我的代码，使用clang++似乎效率会比icpx差一点点，g++似乎效率还要更低。一般来说icpx编译后的性能更好。我之前发的链接里包含了d2sci2这个静态库(由AMD R7-7840H编译)，你用benchmark程序链接这个库再试试d2s_sse算法结果。在我的笔记本上做了benchmark，和你的结果有一点点差别。下面是我的benchmark结果，下载后将文件后缀名改为html。

report_dtoa3.txt

SSE指令集几乎现在所有消费级CPU都包含，不包含SSE指令集的CPU已经很少了。也许你们可以在yyjson以后版本中提供SSE、AVX2、甚至AVX512的API去最大化利用CPU性能，也或者是在运行时去根据CPU动态选择性能最好的API，但这似乎实现起来会比较难。

我的链接中还包含了d2s_32v这个函数，这是基于Schubfach的AVX512实现，使用AVX512指令并行计算32个double值的ASCII结果，即生成最短有效数字，目前在AMD R9-9950X打印单个double值时间约2.4ns，但是还有待证明和完善，这个API应用场景是打印大量双精度浮点数，在数据量特别大时有非常大的性能提升。

谢谢！

[jk-jeon]

@ibireme Wow, it seems it performs 128-bit x 64-bit multiplication only once, in all cases. Looking forward to reading your paper. Did you by any chance try to compare it with Teju as well?

[xjb714]

@ibireme
Your f64_bin_to_dec function code can be optimized in this way. Testing on my CPU can probably reduce 3 to 4 cycle.

[ibireme]

Did you by any chance try to compare it with Teju as well?

@jk-jeon I did a quick test when teju_jagua first came out. It only handles binary-to-decimal and didn't seem to outperform Dragonbox. The author is still updating it, so I'll check it out again later.

[ibireme]

@xjb714 I figured out why there are performance differences.

I tested it on Amazon EC2 and added your new algorithm to the c_numconv_benchmark project. Here are the results:

EC2 7a.xlarge AMD EPYC 9R14 (Zen 4)
clang 18.1.3 -march=native

EC2 c7i.xlarge Intel Xeon Platinum 8488C (Sapphire Rapids)
clang 18.1.3 -march=native

Apple M1 Pro
Apple clang 16.0.0

As you can see, your algorithm performs the best on AMD CPU, and the results are similar even with the same binary.
I think the difference might be related to the specific microarchitecture, I'll look into it more later.

The SSE instruction set is now included in almost all consumer-grade CPUs, and there are very few CPUs without SSE instruction set. Maybe you can provide SSE, AVX2, and even AVX512 APIs in later versions of yyjson to make the best use of CPU performance, or dynamically select the API with the best performance according to CPU at runtime, but it seems to be difficult to realize.

I mainly work on Mac and mobile devices, so I don't focus much on x86. For yyjson, I want to keep it architecture-independent. When optimizing for performance, I try to keep things balanced so it doesn't perform too badly on any platform.

[ibireme]

Your f64_bin_to_dec function code can be optimized in this way. Testing on my CPU can probably reduce 3 to 4 cycle.

@xjb714
I tried tuning for ARM64/X64 with GCC/Clang/MSVC on Compiler Explorer, and I kept running into cases where a change worked as expected in one compiler, but actually made things worse in another.

For example, replacing three breaks with one break works fine in ICX, which generates the right assembly. But Clang/GCC still optimize it into three branches with some extra instructions.

[xjb714]

@ibireme
Thank you for your information. Your algorithm does perform better on most hardware and does not depend on a specific instruction set. Your algorithm is really ingenious, and I look forward to your correctness proof. I have implemented the corresponding AVX-512 code according to the full path code in your f64_bin_to_dec function, and passed the random number test. At present, the performance is 10% higher than that of schubfach's AVX-512 implementation, but some intermediate calculation steps at present should be optimized and have better performance. Implement d2s_yy_32v function with code address in https://gitee.com/xjb714/dtoa-benchmark/blob/master/src/d2sci/d2s_32v.cpp. However, the print results need to be optimized when the absolute value of exp_decimal is in a relatively small range, such as [-7,8]. Maybe you can use the simd instruction set in the arm architecture to realize your algorithm, but I am not familiar with the simd instruction set of arm, and I don't have an arm architecture CPU.

The following are the test results of random double :

AMD R7 7840H(with AVX-512)
icpx 2025.0.4
Ubuntu 24.04.2 LTS

the d2s_yy_32v function is the AVX-512 implementation of your algorithm.
the d2s_32v function is the AVX-512 implementation of shubfach algorithm.

[xjb714]

@ibireme
Performance optimization of yy_double_to_string.
The source code link is as follows.

yy_double copy.txt

Improve the performance under random length test.

[xjb714]

@ibireme There is a mistake in the above code. Use this file.

yy_double copy.txt

[ibireme]

@xjb714 Your code works really well, but portability is still an issue. The result of __builtin_clzll(0) is undefined. For example, on x86_64, the default compiler options generate the bsr instead of lzcnt, which gives the wrong result. You can check it here: https://godbolt.org/z/bW9zj81Wv.

This code performs best on newer CPUs like Intel Haswell, AMD Excavator, and ARM64. To support older CPUs, you'll need to add extra checks, which might slightly hurt performance for full-length numbers.

[xjb714]

@ibireme.
It seems that there is no problem to use the following code instead, and calculate the number of trailing zeros in the lower 16 digits. num8_1

u64 tz1 = __builtin_clzll(num8_1) >> 3; 
u64 tz2 = __builtin_clzll(num8_2) >> 3;
if(num8_1 == 0) tz1 = 8; 
u64 tz = ((num8_2 == 0) ? ( tz1 + 8) : tz2);

num8_1 is the ascii value of high 8 of the lower 16 digits minus 0x3030303030303030; num8_2 is the same.

[xjb714]

@ibireme This code achieves the same function and the compiled result has no branch instructions. The penalty of branch prediction failure can be avoid. click this link: https://godbolt.org/z/fEa5oGcjo

[ibireme]

@xjb714 Yes, what I mean is that these checks can slightly slow down full-length numbers.

For example, I tested with an Intel 13700 using clang -O3, making sure the new code uses cmov. Here's how the cycles changed compared to the original:

random binary: 65 -> 73
random length: 93 -> 73
fixed length: [54,68] -> [72,73]
normalized: 60 -> 67

random length and fixed length represent two extremes. Random length is harder on branch prediction, so removing branches leads to a big speedup. Fixed length is well-predicted by the CPU, so no penalty for misprediction, which means your branchless code could actually be slower because it has more instructions.

In real-world cases, data usually falls somewhere in between, but for structured JSON, it tends to be closer to the fixed-length (or normalized) scenario.