[Python-Dev] PEP 393 Summer of Code Project

[Stefan Behnel]

"Martin v. Löwis", 26.08.2011 11:29:
> You seem to assume it is ok for Jython/IronPython to provide indexing in
> O(n). It is not.

I think we can leave this discussion aside. Jython and IronPython have 
their own platform specific constraints to which they need to adapt their 
implementation. For a Jython user, it means a lot to be able to efficiently 
pass strings (and other data) back and forth between Jython and other JVM 
code, and it's not hard to guess that the same is true for IronPython/.NET 
users. After all, the platform integration is the very *reason* for most 
users to select one of these implementations.

Besides, what if these implementations provided indexing in, say, O(log N) 
instead of O(1) or O(N), e.g. by building a tree index into each string? 
You could have an index that simply marks runs of surrogate pairs and BMP 
substrings, thus providing a likely-to-be-somewhat-compact index. That 
index would obviously have to be built, but so do the different string 
representations in post-PEP-393 CPython, especially on Windows, as I have 
learned.

Would such a less severe violation of the strict O(1) rule still be "not 
ok"? I think this is not such a clear black-and-white issue. Both 
implementations have notably different performance characteristics than 
CPython in some more or less important areas, as does PyPy. At some point, 
the language compliance label has to account for that.

Stefan