Repository navigation
Optimize str.translate() for replacement with substrings and non-ASCII strings #65364
Description
| BPO | 21165 |
|---|---|
| Nosy | @vstinner, @ezio-melotti, @serhiy-storchaka, @MojoVampire, @sir-sigurd |
| Files |
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 = <Date 2015-10-14.16:20:20.588>
created_at = <Date 2014-04-07.09:10:44.758>
labels = ['performance']
title = 'Optimize str.translate() for replacement with substrings and non-ASCII strings'
updated_at = <Date 2018-10-01.10:26:58.755>
user = 'https://github.com/vstinner'bugs.python.org fields:
activity = <Date 2018-10-01.10:26:58.755>
actor = 'vstinner'
assignee = 'none'
closed = True
closed_date = <Date 2015-10-14.16:20:20.588>
closer = 'vstinner'
components = []
creation = <Date 2014-04-07.09:10:44.758>
creator = 'vstinner'
dependencies = []
files = ['34745']
hgrepos = []
issue_num = 21165
keywords = []
message_count = 6.0
messages = ['215677', '215681', '218233', '253002', '253026', '326788']
nosy_count = 5.0
nosy_names = ['vstinner', 'ezio.melotti', 'serhiy.storchaka', 'josh.r', 'sir-sigurd']
pr_nums = []
priority = 'normal'
resolution = 'out of date'
stage = 'patch review'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue21165'
versions = ['Python 3.5']
Activity
vstinner commentedon Apr 7, 2014
In issue bpo-21118, I optimized str.translate() in Python 3.5 for ASCII 1:1 mapping and ASCII deletion. My optimization is not used if a character is replaced with a string (ex: "abc".translate({ord('a'): "xxx"})) and for non-ASCII strings.
translate_script.py is a simple benchmark for 1:1 mapping. It should be enhanced to benchmark also replacement strings.
vstinner commentedon Apr 7, 2014
codecs.charmap_build() (PyUnicode_BuildEncodingMap()) creates a C array ("a three-level trie") for fast lookup. It is used with codecs.charmap_encode() for 8-bit encodings. We may reuse it.
ezio-melotti commentedon May 10, 2014
Aren't there similar benchmarks in the benchmarks repo?
If not, would it be reasonable to add this there?
vstinner commentedon Oct 14, 2015
This issue was more a reminder for myself, and I'm not more interested to implement this optimization. The method is already fast enough.
MojoVampire commentedon Oct 15, 2015
I actually have a patch (still requires a little cleanup) that makes translations for non-ASCII and 1-n translations substantially faster. I've been delaying posting it largely because it makes significant changes to str.maketrans so it returns a special mapping that can be used far more efficiently than Python dicts. The effects of this are:
Under the current design, the mapping uses ~2x the space as the old dict (largely because it actually stores the dict internally to preserve references and simplify basic lookups).
In exchange for the longer time to do str.maketrans and the slightly higher memory, it provides:
I don't know how to float changes that would make fairly substantial changes to existing APIs though, so I'm not sure how to proceed. I'd like translation to be beneficial (the optimization made in bpo-21118 didn't actually improve my use case of stripping diacritics to convert to ASCII equivalent characters from latin-1 and related characters), but I have no good solutions that don't mess around with the API (I'd considered trying to internally cache "compiled" translation tables like the re module does, but the tables are mutable dicts, so caching can't be based on identity, and can't use the dicts as keys, which makes it difficult).
vstinner commentedon Oct 1, 2018
Please open a new issue, since that one is closed. You can reference this issue from your new issue.