abolz / drachennest Goto Github PK
View Code? Open in Web Editor NEWDifferent algorithms for converting binary to decimal floating-point numbers
License: Boost Software License 1.0
Different algorithms for converting binary to decimal floating-point numbers
License: Boost Software License 1.0
Hi, am running into some issues compiling this library and wanted to post them in case you were not aware.
/home/brownjs/software/Drachennest/bench/bench_dtoa.cc:177:22: error: ‘JenkinsRandom random’ redeclared as different kind of entity
177 | static JenkinsRandom random;
| ^~~~~~
In file included from /usr/include/c++/9/cstdlib:75,
from /usr/include/c++/9/bits/stl_algo.h:59,
from /usr/include/c++/9/algorithm:62,
from /home/brownjs/software/Drachennest/ext/google_benchmark/include/benchmark/benchmark.h:172,
from /home/brownjs/software/Drachennest/bench/bench_dtoa.cc:1:
/usr/include/stdlib.h:401:17: note: previous declaration ‘long int random()’
401 | extern long int random (void) __THROW;
| ^~~~~~
/home/brownjs/software/Drachennest/bench/bench_strtod.cc:144:22: error: ‘JenkinsRandom random’ redeclared as different kind of entity
144 | static JenkinsRandom random;
| ^~~~~~
In file included from /usr/include/c++/9/cstdlib:75,
from /usr/include/c++/9/bits/stl_algo.h:59,
from /usr/include/c++/9/algorithm:62,
from /home/brownjs/software/Drachennest/ext/google_benchmark/include/benchmark/benchmark.h:172,
from /home/brownjs/software/Drachennest/bench/bench_strtod.cc:1:
/usr/include/stdlib.h:401:17: note: previous declaration ‘long int random()’
401 | extern long int random (void) __THROW;
| ^~~~~~
In file included from /usr/include/c++/9/bits/stl_algo.h:66,
from /usr/include/c++/9/algorithm:62,
from /home/brownjs/software/Drachennest/ext/google_benchmark/include/benchmark/benchmark.h:172,
from /home/brownjs/software/Drachennest/bench/bench_dtoa.cc:1:
/usr/include/c++/9/bits/uniform_int_dist.h: In instantiation of ‘std::uniform_int_distribution<_IntType>::result_type std::uniform_int_distribution<_IntType>::operator()(_UniformRandomNumberGenerator&, const std::uniform_int_distribution<_IntType>::param_type&) [with _UniformRandomNumberGenerator = long int() noexcept; _IntType = long unsigned int; std::uniform_int_distribution<_IntType>::result_type = long unsigned int]’:
/usr/include/c++/9/bits/uniform_int_dist.h:173:51: required from ‘std::uniform_int_distribution<_IntType>::result_type std::uniform_int_distribution<_IntType>::operator()(_UniformRandomNumberGenerator&) [with _UniformRandomNumberGenerator = long int() noexcept; _IntType = long unsigned int; std::uniform_int_distribution<_IntType>::result_type = long unsigned int]’
/home/brownjs/software/Drachennest/bench/bench_dtoa.cc:262:98: required from here
/usr/include/c++/9/bits/uniform_int_dist.h:230:4: error: ‘long int() noexcept’ is not a class, struct, or union type
230 | _Gresult_type;
| ^~~~~~~~~~~~~
/usr/include/c++/9/bits/uniform_int_dist.h:233:4: error: ‘long int() noexcept’ is not a class, struct, or union type
233 | __uctype;
| ^~~~~~~~
/usr/include/c++/9/bits/uniform_int_dist.h: In instantiation of ‘std::uniform_int_distribution<_IntType>::result_type std::uniform_int_distribution<_IntType>::operator()(_UniformRandomNumberGenerator&, const std::uniform_int_distribution<_IntType>::param_type&) [with _UniformRandomNumberGenerator = long int() noexcept; _IntType = unsigned int; std::uniform_int_distribution<_IntType>::result_type = unsigned int]’:
/usr/include/c++/9/bits/uniform_int_dist.h:173:51: required from ‘std::uniform_int_distribution<_IntType>::result_type std::uniform_int_distribution<_IntType>::operator()(_UniformRandomNumberGenerator&) [with _UniformRandomNumberGenerator = long int() noexcept; _IntType = unsigned int; std::uniform_int_distribution<_IntType>::result_type = unsigned int]’
/home/brownjs/software/Drachennest/bench/bench_dtoa.cc:272:97: required from here
/usr/include/c++/9/bits/uniform_int_dist.h:230:4: error: ‘long int() noexcept’ is not a class, struct, or union type
230 | _Gresult_type;
| ^~~~~~~~~~~~~
/usr/include/c++/9/bits/uniform_int_dist.h:233:4: error: ‘long int() noexcept’ is not a class, struct, or union type
233 | __uctype;
| ^~~~~~~~
/usr/include/c++/9/bits/uniform_int_dist.h: In instantiation of ‘std::uniform_int_distribution<_IntType>::result_type std::uniform_int_distribution<_IntType>::operator()(_UniformRandomNumberGenerator&, const std::uniform_int_distribution<_IntType>::param_type&) [with _UniformRandomNumberGenerator = long int() noexcept; _IntType = long int; std::uniform_int_distribution<_IntType>::result_type = long int]’:
/usr/include/c++/9/bits/uniform_int_dist.h:173:51: required from ‘std::uniform_int_distribution<_IntType>::result_type std::uniform_int_distribution<_IntType>::operator()(_UniformRandomNumberGenerator&) [with _UniformRandomNumberGenerator = long int() noexcept; _IntType = long int; std::uniform_int_distribution<_IntType>::result_type = long int]’
/home/brownjs/software/Drachennest/bench/bench_dtoa.cc:328:31: required from here
/usr/include/c++/9/bits/uniform_int_dist.h:230:4: error: ‘long int() noexcept’ is not a class, struct, or union type
230 | _Gresult_type;
| ^~~~~~~~~~~~~
/usr/include/c++/9/bits/uniform_int_dist.h:233:4: error: ‘long int() noexcept’ is not a class, struct, or union type
233 | __uctype;
| ^~~~~~~~
/usr/include/c++/9/bits/uniform_int_dist.h: In instantiation of ‘std::uniform_int_distribution<_IntType>::result_type std::uniform_int_distribution<_IntType>::operator()(_UniformRandomNumberGenerator&, const std::uniform_int_distribution<_IntType>::param_type&) [with _UniformRandomNumberGenerator = long int() noexcept; _IntType = int; std::uniform_int_distribution<_IntType>::result_type = int]’:
/usr/include/c++/9/bits/uniform_int_dist.h:173:51: required from ‘std::uniform_int_distribution<_IntType>::result_type std::uniform_int_distribution<_IntType>::operator()(_UniformRandomNumberGenerator&) [with _UniformRandomNumberGenerator = long int() noexcept; _IntType = int; std::uniform_int_distribution<_IntType>::result_type = int]’
/home/brownjs/software/Drachennest/bench/bench_dtoa.cc:372:31: required from here
/usr/include/c++/9/bits/uniform_int_dist.h:230:4: error: ‘long int() noexcept’ is not a class, struct, or union type
230 | _Gresult_type;
| ^~~~~~~~~~~~~
/usr/include/c++/9/bits/uniform_int_dist.h:233:4: error: ‘long int() noexcept’ is not a class, struct, or union type
233 | __uctype;
| ^~~~~~~~
In file included from /usr/include/c++/9/random:51,
from /home/brownjs/software/Drachennest/bench/bench_dtoa.cc:14:
/usr/include/c++/9/bits/random.tcc: In instantiation of ‘_RealType std::generate_canonical(_UniformRandomNumberGenerator&) [with _RealType = double; long unsigned int __bits = 53; _UniformRandomNumberGenerator = long int() noexcept]’:
/usr/include/c++/9/bits/random.h:181:38: required from ‘_DInputType std::__detail::_Adaptor<_Engine, _DInputType>::operator()() [with _Engine = long int() noexcept; _DInputType = double]’
/usr/include/c++/9/bits/random.h:1862:19: required from ‘std::uniform_real_distribution<_RealType>::result_type std::uniform_real_distribution<_RealType>::operator()(_UniformRandomNumberGenerator&, const std::uniform_real_distribution<_RealType>::param_type&) [with _UniformRandomNumberGenerator = long int() noexcept; _RealType = double; std::uniform_real_distribution<_RealType>::result_type = double]’
/usr/include/c++/9/bits/random.h:1853:51: required from ‘std::uniform_real_distribution<_RealType>::result_type std::uniform_real_distribution<_RealType>::operator()(_UniformRandomNumberGenerator&) [with _UniformRandomNumberGenerator = long int() noexcept; _RealType = double; std::uniform_real_distribution<_RealType>::result_type = double]’
/home/brownjs/software/Drachennest/bench/bench_dtoa.cc:404:36: required from here
/usr/include/c++/9/bits/random.tcc:3327:63: error: request for member ‘max’ in ‘__urng’, which is of non-class type ‘long int() noexcept’
3327 | const long double __r = static_cast<long double>(__urng.max())
| ~~~~~~~^~~
/usr/include/c++/9/bits/random.tcc:3328:42: error: request for member ‘min’ in ‘__urng’, which is of non-class type ‘long int() noexcept’
3328 | - static_cast<long double>(__urng.min()) + 1.0L;
| ~~~~~~~^~~
/usr/include/c++/9/bits/random.tcc:3337:41: error: request for member ‘min’ in ‘__urng’, which is of non-class type ‘long int() noexcept’
3337 | __sum += _RealType(__urng() - __urng.min()) * __tmp;
| ~~~~~~~^~~
/usr/include/c++/9/bits/random.tcc: In instantiation of ‘_RealType std::generate_canonical(_UniformRandomNumberGenerator&) [with _RealType = float; long unsigned int __bits = 24; _UniformRandomNumberGenerator = long int() noexcept]’:
/usr/include/c++/9/bits/random.h:181:38: required from ‘_DInputType std::__detail::_Adaptor<_Engine, _DInputType>::operator()() [with _Engine = long int() noexcept; _DInputType = float]’
/usr/include/c++/9/bits/random.h:1862:19: required from ‘std::uniform_real_distribution<_RealType>::result_type std::uniform_real_distribution<_RealType>::operator()(_UniformRandomNumberGenerator&, const std::uniform_real_distribution<_RealType>::param_type&) [with _UniformRandomNumberGenerator = long int() noexcept; _RealType = float; std::uniform_real_distribution<_RealType>::result_type = float]’
/usr/include/c++/9/bits/random.h:1853:51: required from ‘std::uniform_real_distribution<_RealType>::result_type std::uniform_real_distribution<_RealType>::operator()(_UniformRandomNumberGenerator&) [with _UniformRandomNumberGenerator = long int() noexcept; _RealType = float; std::uniform_real_distribution<_RealType>::result_type = float]’
/home/brownjs/software/Drachennest/bench/bench_dtoa.cc:430:35: required from here
/usr/include/c++/9/bits/random.tcc:3327:63: error: request for member ‘max’ in ‘__urng’, which is of non-class type ‘long int() noexcept’
3327 | const long double __r = static_cast<long double>(__urng.max())
| ~~~~~~~^~~
/usr/include/c++/9/bits/random.tcc:3328:42: error: request for member ‘min’ in ‘__urng’, which is of non-class type ‘long int() noexcept’
3328 | - static_cast<long double>(__urng.min()) + 1.0L;
| ~~~~~~~^~~
/usr/include/c++/9/bits/random.tcc:3337:41: error: request for member ‘min’ in ‘__urng’, which is of non-class type ‘long int() noexcept’
3337 | __sum += _RealType(__urng() - __urng.min()) * __tmp;
| ~~~~~~~^~~
make[2]: *** [bench/CMakeFiles/bench_dtoa.dir/build.make:63: bench/CMakeFiles/bench_dtoa.dir/bench_dtoa.cc.o] Error 1
make[1]: *** [CMakeFiles/Makefile2:252: bench/CMakeFiles/bench_dtoa.dir/all] Error 2
make[1]: *** Waiting for unfinished jobs....
In file included from /usr/include/c++/9/random:51,
from /home/brownjs/software/Drachennest/bench/bench_strtod.cc:6:
/usr/include/c++/9/bits/random.tcc: In instantiation of ‘_RealType std::generate_canonical(_UniformRandomNumberGenerator&) [with _RealType = double; long unsigned int __bits = 53; _UniformRandomNumberGenerator = long int() noexcept]’:
/usr/include/c++/9/bits/random.h:181:38: required from ‘_DInputType std::__detail::_Adaptor<_Engine, _DInputType>::operator()() [with _Engine = long int() noexcept; _DInputType = double]’
/usr/include/c++/9/bits/random.h:1862:19: required from ‘std::uniform_real_distribution<_RealType>::result_type std::uniform_real_distribution<_RealType>::operator()(_UniformRandomNumberGenerator&, const std::uniform_real_distribution<_RealType>::param_type&) [with _UniformRandomNumberGenerator = long int() noexcept; _RealType = double; std::uniform_real_distribution<_RealType>::result_type = double]’
/usr/include/c++/9/bits/random.h:1853:51: required from ‘std::uniform_real_distribution<_RealType>::result_type std::uniform_real_distribution<_RealType>::operator()(_UniformRandomNumberGenerator&) [with _UniformRandomNumberGenerator = long int() noexcept; _RealType = double; std::uniform_real_distribution<_RealType>::result_type = double]’
/home/brownjs/software/Drachennest/bench/bench_strtod.cc:167:52: required from here
/usr/include/c++/9/bits/random.tcc:3327:63: error: request for member ‘max’ in ‘__urng’, which is of non-class type ‘long int() noexcept’
3327 | const long double __r = static_cast<long double>(__urng.max())
| ~~~~~~~^~~
/usr/include/c++/9/bits/random.tcc:3328:42: error: request for member ‘min’ in ‘__urng’, which is of non-class type ‘long int() noexcept’
3328 | - static_cast<long double>(__urng.min()) + 1.0L;
| ~~~~~~~^~~
/usr/include/c++/9/bits/random.tcc:3337:41: error: request for member ‘min’ in ‘__urng’, which is of non-class type ‘long int() noexcept’
3337 | __sum += _RealType(__urng() - __urng.min()) * __tmp;
| ~~~~~~~^~~
make[2]: *** [bench/CMakeFiles/bench_strtod.dir/build.make:63: bench/CMakeFiles/bench_strtod.dir/bench_strtod.cc.o] Error 1
make[1]: *** [CMakeFiles/Makefile2:222: bench/CMakeFiles/bench_strtod.dir/all] Error 2
[ 95%] Linking CXX executable test_all
[ 95%] Built target test_all
make: *** [Makefile:84: all] Error 2
For experiments with ryu and dragonbox and possibly programming experiments I would like to have concrete evaluation what works faster or slower.
[ edit 2022-06-09 ] the observed 'jumpy' performance differences are not a special problem of ryu or dragonbox, but occur with other 'normal' computing operations as well. I have put the question here because I think that for qualified tests / qualified comparisons / qualified further developments a more exact understanding is necessary what the computer does, and why! As long as we do not understand the processes, we can see them only through criss-cross glass, and - try to - help ourselves with the interpretation of averaged measurements, we do more 'gaming' than analytical development? [ /edit ]
I have experimented a bit with 'micro timing', with a few conversions of specific - i.e. not random! - values, which should actually result in uniform execution times? However, I have seen that:
I.) the same conversion is sometimes performed fast and sometimes slow, that seems like randomly scattered,
as well as that:
II.) different conversions are mostly executed similarly fast during one run, but with changing performance from call to call ( same program, same test values and parameters, sometimes all conversions fast, sometimes medium, sometimes slow ).
The scatter range is in the order of 1:10!
This looks to me as if some conditions or 'side effects' have influence on the performance, but I don't know which ones.
My guesses range from 'alignment', to differences between cores due to spatial arrangement of cache and CPU / FPU on the chip ( I saw a report the other day that on a game console? due to different length lines on the 'die' delays / errors occurred for one of three cores) ... or could my CPU be defective? .
III.) it looks as if running the below test program with few turns - e.g. 'timing_dragonbox 3' - results in more scattering, while with plenty rounds - e.g. 'timing_dragonbox 100' - outliers become rare.
It is beyond my competence to clarify this in detail, but I would be immensely curious if it occurs on other systems as well, what it is, and if you can somehow influence it positively.
Attached the used program timing_dragonbox.cpp.tar.gz, for build and call see pretext.
I think the peculiarities fit quite well to the chart 'subproject/benchmark/results/uniform_benchmark_binary64_clang.png', I see and suspect there 'stripes' of approximately discrete execution times that fit to the observed stepped times, no randomly scattered distribution.
And 'now and then values with a few digits are generated and that takes longer' IMHO does not fit as an explanation, certainly not for dragonbox. And I don't see difficulties for certain numbers or substantially more loop passes either ... but ... these are considerations above my knowledge, I would be glad if others can shed some light into this corner.
With which program part were the values for the graphic determined?
With ryu I observe similar behaviour, but with - it feels - stronger effect.
( my system: 8-core xeon, debian linux. )
How does this change with decimals and other binary bit sizes? Can they be added?
Hi,
This is a really neat implementation, I was wanting to use this repository as a dependency, but noticed you don't have a versioning system set up, are there any plans to do that? Best!
With a double-precision value corresponding to the minimum value (hex representation 0x0000000000000001
),
4.9E-324
"5e-324
"The expected string is coming from the Java implementation from the algorithm's author, Raffaello Giulietti.
I haven't done a more thorough test to see if there were other discrepancies. Most of the results are definitely fine but finding different values, and seeing the algorithm has been adapted, is not reassuring. Perhaps were there small adaptations in the original algorithm? There are several versions of the article.
Quick and dirty test file (requires schubfach_64.cpp and schubfach_64.h)
#include <cstdint>
#include <cstdio>
#include <cstring>
#include "schubfach_64.h"
using namespace std;
using namespace schubfach;
char BUFFER[DtoaMinBufferLength];
char *dtoa(double value)
{
char *end = Dtoa(BUFFER, value);
*end = 0;
return BUFFER;
}
template <typename Dest, typename Source>
static inline Dest ReinterpretBits(Source source)
{
static_assert(sizeof(Dest) == sizeof(Source), "size mismatch");
Dest dest;
std::memcpy(&dest, &source, sizeof(Source));
return dest;
}
int main()
{
uint64_t min_value_bits = 0x0000000000000001;
double min_value = ReinterpretBits<double>(min_value_bits);
double values[] = { 1.0, 10.0, 0.5, min_value };
for (double i: values) {
printf("%g: %s\n", i, dtoa(i));
}
}
I noticed a few issues in my environment
Maybe the current config only happens to work if the C++ compiler defaults to 17?
I had to add this to top level CMakeLists.txt:
set(CMAKE_CXX_STANDARD 17)
ext/google_benchmark
assumes Windowsneeded to disable hard-coded lib shlwapi
in ext/google_benchmark/CMakeLists.txt
Hi @abolz ,
I just looked for available grisu implementations and I saw you just wrote this one. Is it possible to use your code as basis for my studies? I am experimenting with floating point compression.
Roman
I get the following error when compiling the tests:
In file included from /usr/include/signal.h:328,
from /home/projects/c/Drachennest/test/catch.hpp:6456,
from /home/projects/c/Drachennest/test/catch_main.cc:2:
/home/projects/c/Drachennest/test/catch.hpp:6631:45: error: size of array ‘altStackMem’ is not an integral constant-expression
6631 | char FatalConditionHandler::altStackMem[SIGSTKSZ] = {};
| ^~~~~~~~
I saw this notice for glibc 2.34, which seems relevant to the issue:
12 * Add _SC_MINSIGSTKSZ and _SC_SIGSTKSZ. When _SC_SIGSTKSZ_SOURCE or
13 _GNU_SOURCE are defined, MINSIGSTKSZ and SIGSTKSZ are no longer
14 constant on Linux. MINSIGSTKSZ is redefined to sysconf(_SC_MINSIGSTKSZ)
15 and SIGSTKSZ is redefined to sysconf (_SC_SIGSTKSZ).
So this problem is bound to creep in projects using those #defines.
git clone https://github.com/abolz/Drachennest.git
cd Drachennest/
mkdir build
cd build/
cmake ..
cd test
cmake --build .
diff --git a/test/catch.hpp b/test/catch.hpp
index 1106e46..cdbe953 100644
--- a/test/catch.hpp
+++ b/test/catch.hpp
@@ -6628,6 +6628,11 @@ namespace Catch {
bool FatalConditionHandler::isSet = false;
struct sigaction FatalConditionHandler::oldSigActions[sizeof(signalDefs)/sizeof(SignalDefs)] = {};
stack_t FatalConditionHandler::oldSigStack = {};
+
+// FIXME: temporary fix
+# undef SIGSTKSZ
+# define SIGSTKSZ _SC_SIGSTKSZ
+
char FatalConditionHandler::altStackMem[SIGSTKSZ] = {};
} // namespace Catch
ldd (GNU libc) 2.36
gcc (GCC) 12.2.0
Linux manj 5.15.74-3-MANJARO x86_64 GNU/Linux
Trying to compile everything in build shows many other errors that I didn't investigate.
The first was:
[ 85%] Building CXX object bench/CMakeFiles/bench_dtoa.dir/bench_dtoa.cc.o
/home/projects/c/Drachennest/bench/bench_dtoa.cc:177:22: error: ‘JenkinsRandom random’ redeclared as different kind of entity
177 | static JenkinsRandom random;
| ^~~~~~
In file included from /usr/include/c++/12.2.0/cstdlib:75,
from /usr/include/c++/12.2.0/bits/stl_algo.h:69,
from /usr/include/c++/12.2.0/algorithm:61,
from /home/projects/c/Drachennest/ext/google_benchmark/include/benchmark/benchmark.h:172,
from /home/projects/c/Drachennest/bench/bench_dtoa.cc:1:
/usr/include/stdlib.h:402:17: note: previous declaration ‘long int random()’
402 | extern long int random (void) __THROW;
| ^~~~~~
Thank you!!! LOVE U!!
Very useful comparisons! Thanks to you I integrated Dragonbox into my own project and saw a massive speedup.
One improvement would be to put labels on the plots. At first glace it's not clear what the axes are, and one is tempted to think "higher is better" and hence std::to_chars
appears to be the winner. After more insight one assumes the y-axis is "average runtime in nanoseconds" and reaches the opposite conclusion.
The x-axes are still confounding me. I'm guessing the last plots' x-axes are run numbers? I've no idea about the first few.
There are some new versions:
https://drive.google.com/file/d/1JoQBN5igZ8bMI3ua7l5DrHx_GYsjF0Dy
https://drive.google.com/file/d/1IEeATSVnEE6TkrHlCYNY2GjaraBjOT4f
Drachennest/src/schubfach_64.cc
Line 912 in e6714a3
BTW, it may be worth nothing the reason of using different h
to the paper (9.10 (10) in v2).
Hello, I'm also the author of yet another floating-point format algorithm which I call Grisu-Exact (https://github.com/jk-jeon/Grisu-Exact), which originally started as a variant of Grisu but eventually evolved into something more than that.
It seems your implementations are super fast and I'm very impressed. Especially, I didn't know there already was an algorithm with the shortest and correct rounding guarantees, yet is faster than Grisu-Exact (Schubfach! I have no idea why Ryu got much more attention when Schubfach already have existed). I've run a dtoa benchmark of your implementation of Schubfach and Ulf's implementation of Ryu together with my implementation of Grisu-Exact, and the result looks like the following.
(The benchmark might be not fair in the sense that Ryu and Grisu-Exact's string outputs are always in scientific format while yours seem to generate the shorter one between the fixed-point and scientific formats, though I'm not sure how much it might affect. My string generation routine is actually a copy of that of Ryu.)
So Schubfach is indeed faster than Grisu-Exact!
I would be very happy if you take a look at my algorithm and possibly add it into your benchmark.
I'm curious of several things:
Thanks!
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.