micro-optimization: increase our float parsing speed by Nx

[gpshead]

BPO	41310
Nosy	@tim-one, @rhettinger, @gpshead, @mdickinson, @pitrou, @ericvsmith, @serhiy-storchaka

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = None
created_at = <Date 2020-07-15.22:21:55.444>
labels = ['interpreter-core', 'type-feature', '3.10']
title = 'micro-optimization: increase our float parsing speed by Nx'
updated_at = <Date 2020-10-19.17:27:20.343>
user = 'https://github.com/gpshead'

bugs.python.org fields:

activity = <Date 2020-10-19.17:27:20.343>
actor = 'pitrou'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2020-07-15.22:21:55.444>
creator = 'gregory.p.smith'
dependencies = []
files = []
hgrepos = []
issue_num = 41310
keywords = []
message_count = 6.0
messages = ['373730', '373743', '373760', '373769', '373775', '378969']
nosy_count = 7.0
nosy_names = ['tim.peters', 'rhettinger', 'gregory.p.smith', 'mark.dickinson', 'pitrou', 'eric.smith', 'serhiy.storchaka']
pr_nums = []
priority = 'low'
resolution = None
stage = 'needs patch'
status = 'open'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue41310'
versions = ['Python 3.10']

[gpshead]

See https://lemire.me/blog/2020/03/10/fast-float-parsing-in-practice/ for inspiration and a reference (possibly a library to use, but if not the techniques still apply).

Primarily usable when creating the float objects from the string data as is common in python code and particularly common in JSON serialized data.

[serhiy-storchaka]

CPython is written on C, not C++, so we cannot use std::from_chars.

Note also that to parse a number in JSON we need first to scan the PyUnicode object character-by-character using PyUnicode_READ() which is slower than just reading a byte from a memory, then convert a substring to a nul-terminated bytes string, and finally use the conversion function which creates a new PyFloat or PyLong objects. The overhead of scanning a string and memory management may be larger than the parsing time itself.

[mdickinson]

Is there a description of the algorithms or ideas used anywhere? The blog post you link to has no details, and I don't see any useful descriptions in the GitHub README or the source; trawling through the source to figure out what the key ideas are is not ideal. I don't find the tests particularly convincing, either.

I think this is too immature to consider for CPython, right now. Maybe it would make sense to revisit some day in the future if/when the library is more mature.

[tim-one]

Gregory, care to take their code and time it against Python?

I'm not inclined to: reading the comments in the code, they're trying "fast paths" already described in papers by Clinger and - later - by Gay. When those fast paths don't apply, they fall back on the system strtod. But Python's current implementation builds on Gay's fastest code (and never falls back to the system).

It's possible they "improved" on Gay by building relatively giant tables of static data.

[ericvsmith]

I don't think we'd want to fall back to strtod, but rather to the code we already use (Gay's). So this would increase our maintenance burden.

I'm also not convinced that we actually spend a lot of time in this code, but of course profiling would be needed to make sure.

[pitrou]

FTR, no formal description of the algorithm seems to have been published, but the source code is amply commented:
https://github.com/lemire/fast_double_parser/blob/master/include/fast_double_parser.h

[lemire]

@pitrou Please see:

• Daniel Lemire, Number Parsing at a Gigabyte per Second, Software: Practice and Experience 51 (8), 2021.
• Noble Mushtak, Daniel Lemire, Fast Number Parsing Without Fallback, Software: Practice and Experience 53 (7), 2023.