[HN Gopher] FastDoubleParser: Java port of Daniel Lemires fast_d...
___________________________________________________________________
FastDoubleParser: Java port of Daniel Lemires fast_double_parser
Author : mfiguiere
Score : 72 points
Date : 2021-03-22 14:57 UTC (8 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| gopalv wrote:
| Reading this code almost makes me want to think about how
| differently I review Java than C or C++. ch =
| ++index < strlen ? str.charAt(index) : 0;
|
| If I saw that code scattered across in some java code, I would
| immediately be like - "rewrite please".
|
| But the same code fragment in C would be like - yeah, we need a
| bounds check, good job, can you make it a macro please.
|
| The java default Float parser was somewhat of a complete perf
| headache when multi-threading, more than about single core
| consumption (till jdk8b96 - JDK-7032154), so in the past Hive has
| shipped with its own strod impl[1] to avoid the central lock in
| parseDouble.
|
| Also it worked off a raw utf8 byte[] stream, which is more common
| coming out of a disk file or network serialization rather than a
| CharSequence.
|
| [1] -
| https://github.com/apache/hive/blob/4446414f4478091db1eb20bc...
| RedShift1 wrote:
| I disagree, why exactly would it need to be re-written because
| it's in Java? Does the language matter at all? To me this piece
| of code is concise, I immediately recognized it as a bounds
| check. If you re-write this to add braces, newlines, the if
| statement... just creates more cognitive load in favor of? To
| me this little line is perfect, it does exactly what it is
| supposed to do and it doesn't hide its intent.
| Bjartr wrote:
| If being more concise was always better for cognitive load,
| we'd all be writing APL.
| mabbo wrote:
| The real question is why C/C++ programmers accept code like
| that. You can write that same code in an easier-to-follow way,
| and the compiler will turn it into an identical binary.
|
| Code should be written for humans.
| [deleted]
| ghanrt wrote:
| It is. Apart from ++index, this is literally the same as:
| let ch = if index < strlen then str.charAt(index) else 0
|
| Eminently readable and less boring than long if/else chains
| in Python.
| Twirrim wrote:
| You can write in a very similar way in python too if you
| want to. I think I'd argue this is cleaner syntax, even.
| >>> foo = 10 >>> bar = foo if foo > 5 else 0
| >>> bar 10 >>> bar = foo if foo < 5 else 0
| >>> bar 0
| dmos62 wrote:
| It's not. To be easily human-parsable you want to do one
| thing at a time. It's that incrementation that you've
| ommited that messes things up.
|
| On a side note, having gotten used to newer languages, an
| option type sure is a nice thing.
| [deleted]
| pjmlp wrote:
| Frameworks produced by Windows dev team are a very good
| example of that.
|
| They could produce something that looks like Qt, OWL/VCL, or
| nowadays .NET like but in C++.
|
| Instead they produce libraries where one is forced to use C
| low level details, mixed with Win32 and COM pointer handling
| and casts everywhere, not even MFC escapes it.
|
| Not to count how many interactions of COM smart pointers that
| have come up with since COM exists.
|
| C++/CX looked like they finally learned their way and would
| offer something similar to C++ Builder, but no that wasn't
| meant for us to enjoy it.
|
| So now anyone doing UWP with C++, gets to manually edit IDL
| files without tooling support, and merge the generated files
| manually.
|
| I really don't get their macho developer culture.
| dmos62 wrote:
| > I really don't get their macho developer culture.
|
| I'm inclined to not recognize that as a distinct culture
| and rather call it an infectious habit. Auditable,
| maintainable code is a skill, after all.
| slavik81 wrote:
| IDK. I like the C-style version better. bool
| found_minus = (*p == '-'); bool negative = false;
| if (found_minus) { ++p; negative = true;
| if (!is_integer(*p)) { // a negative sign must be followed by
| an integer return nullptr; } }
|
| vs. int strlen = str.length(); if
| (strlen == 0) { throw new
| NumberFormatException("empty String"); } int
| index = 0; char ch = str.charAt(index);
| boolean negative = false; if (ch == '-') {
| negative = true; ch = ++index < strlen ?
| str.charAt(index) : 0; if (ch == 0) {
| throw new NumberFormatException("'-' cannot stand alone");
| } }
| MaxBarraclough wrote:
| Agree, especially as there's so little upside to writing it
| this way. It isn't going to run any faster. The style
| emphasises code-density over readability, but density is only a
| virtue when it aids readability.
|
| I'd far prefer: ++index; ch = index <
| strlen ? str.charAt(index) : 0;
|
| I don't see a good reason to make it a macro, though.
| kuschku wrote:
| index += 1; if (index < strlen) { ch =
| str.charAt(index); } else { ch = 0;
| }
|
| If I was using kotlin, I'd do it even cleaner:
| inline fun String.at(index: Int): Char? = if (index
| >= 0 && index < length) charAt(index) else null
| [...] index += 1 ch = str.at(index) ?:
| 0;
|
| The bytecode is exactly the same, but I'd argue it's much
| cleaner
| astrange wrote:
| IME naming projects "fast" or things like that is bad karma. Over
| time something better comes out and now you're not fast anymore,
| or there were compromises people have to watch out for to make it
| fast and now the name is an attractive nuisance.
|
| Swift originally had an option named -Ofast that just turned off
| all the safety features - eventually it got renamed to
| -Ounchecked.
| ygra wrote:
| I guess Swift just adopted a similar thing to -ffast-math which
| some C compilers offer where guarantees about precision of
| floating-point operations are thrown away to get a similar
| result faster. Incidentally, that could deserve a better name
| as well (oh, there seems to be a -funsafe-math-optimizations,
| which reads a lot closer to what is intended).
| The_rationalist wrote:
| See also the port of Lemire's SIMD UTF8 validation in java:
| https://github.com/AugustNagro/utf8.java/blob/master/src/mai...
| Which is made possible since openjdk 16 (the Vector API) however
| the results aren't yet impressive, and the openjdk devs are
| currently optimizing the SIMD generation for it
| java-man wrote:
| Good job!
|
| Though I would have added a unit test to iterate over complete
| 2^64 set of values and compare the output to
| Double.parseDouble().
| haberman wrote:
| Even if you could parse a double in a single cycle, it would
| take 292 years to run through 2^64 cases on a 2GHz machine.
| https://www.google.com/search?q=2**64+%2F+2GHz&oq=2**64+%2F+...
|
| Also, while there are only 2^64 distinct double values, there
| are many more string representations than that. For example,
| "1" and "1.0" are the same underlying value, but a parser needs
| to be able to handle both.
| java-man wrote:
| My point is about comparing accelerated code behavior to the
| standard java Double.
| stefs wrote:
| your point is still invalid because it's pointless to
| attempt what you're suggesting. and that's not how unit
| tests work.
|
| unit testing doesn't mean that all possible values have to
| be tested. usually it's about code paths, i.e. standard,
| error and edge cases.
| surfsvammel wrote:
| Is there a downside to this? Or is it just a plain better
| algorithm? If so, why has it not been implemented in the Java
| standard libs?
| layer8 wrote:
| The bottleneck is usually I/O, or parsing into large object
| structures, not double parsing.
| thangalin wrote:
| Ryu algorithm, the converse (doubles to strings), is also much
| faster than using Java's number formatting classes.
|
| https://github.com/ulfjack/ryu/blob/master/src/main/java/inf...
|
| Aside, my JMathTeX fork uses Ryu to achieve real-time rendering
| of TeX in Java.
|
| https://github.com/DaveJarvis/JMathTeX/
| thoughtsimple wrote:
| M1 MacBook Air
|
| Apple M1 OpenJDK 64-Bit Server VM, Azul Systems, Inc., 16+36
|
| parsing random integers in the range [0,1)
|
| === number of trials 32 =====
|
| FastDoubleParser.parseDouble MB/s avg: 492.324205, min: 479.57,
| max: 516.26
|
| Double.parseDouble MB/s avg: 111.509085, min: 110.63, max: 114.65
|
| Speedup FastDoubleParser vs Double: 4.415104
|
| Apple M1 OpenJDK 64-Bit Server VM, Azul Systems, Inc., 16+36
|
| parsing integers in file data/canada.txt
|
| read 111126 lines
|
| === number of trials 32 =====
|
| FastDoubleParser.parseDouble MB/s avg: 483.642065, min: 420.43,
| max: 502.15
|
| Double.parseDouble MB/s avg: 104.347746, min: 99.03, max: 116.91
|
| Speedup FastDoubleParser vs Double: 4.634907
| The_rationalist wrote:
| See also the work on jsoniter-scala, which is the fastest
| serialization library on the JVM
| https://github.com/plokhotnyuk/jsoniter-scala/pull/542 I wonder
| how they compare and whether some of the optimization tricks
| could be shared.
|
| more on the optimization techniques here:
| https://github.com/FasterXML/jackson-core/issues/577
| jeffbee wrote:
| It's been fascinating to watch these developments because in my
| career I've never encountered a performance-sensitive application
| that wasn't fixed by just eliminating the parsing of doubles from
| text format. Parsing them faster never seemed to be a good
| choice. On the other hand producing human-readable doubles (for
| debug logs or whatever) is a pretty frequent bottleneck that has
| also seen great improvements recently (Grisu, then Ryu).
|
| Anyway, it's all great programming but it seems to me a symptom
| or a larger social failure, where we are making bad protocols
| faster instead of making the protocols better.
| jcelerier wrote:
| Have you never been in projects where a _hard_ requirement was
| "save files must be editable with notepad.exe" ? If so, lucky
| you
| The_rationalist wrote:
| Any body wanting to port the fast float parser in java too ?
| https://github.com/fastfloat/fast_float
|
| Lemire's really has made a huge contribution to computer science
| spullara wrote:
| This is the port of fast_float, at least that is what
| fast_float's README says.
| The_rationalist wrote:
| Well this doesn't make sense. This port is for 64 bit aka
| double precision floating points. I am talking about
| supporting 32 bit floats. Maybe this can be achieved in the
| same codebase, I don't know
| haberman wrote:
| A surprising fact I just learned about float parsing is that it
| is absolutely trivial (and, I expect, very fast) if you are
| willing to tolerate a 1 ULP inaccuracy:
| https://www.exploringbinary.com/quick-and-dirty-decimal-to-f...
|
| (Though 1/100M randomly tested conversions had a 14ULP
| inaccuracy, so I guess the inaccuracy is a bit unpredictable).
| ValleZ wrote:
| This is awesome!
___________________________________________________________________
(page generated 2021-03-22 23:01 UTC)