classification
Title: Find out what stdlib modules lack a pure Python implementation
Type: enhancement Stage:
Components: Library (Lib) Versions: Python 3.4
process
Status: open Resolution:
Dependencies: 16659 16694 16991 Superseder:
Assigned To: Nosy List: Arfrever, alex, amaury.forgeotdarc, asvetlov, brett.cannon, brian.curtin, chris.jerdonek, christian.heimes, eric.araujo, eric.snow, ezio.melotti, meador.inge, pitrou, pjenvey, rhettinger, serhiy.storchaka, terry.reedy, tshepang, zach.ware
Priority: low Keywords: easy

Created on 2012-12-09 18:39 by brett.cannon, last changed 2013-03-11 02:44 by rhettinger.

Messages (28)
msg177230 - (view) Author: Brett Cannon (brett.cannon) * (Python committer) Date: 2012-12-09 18:39
I'm wondering which modules in the stdlib lack pure Python implementations (and could legitimately have one, e.g. sqlite can't really have a pure Python implementation). Once we know how big/small the list is a decision could be made as to whether to take on the effort to bring over some pure Python version from another VM or something for any of these modules.

To start the list:

csv
itertools
msg177231 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-12-09 19:03
array
audioop
binascii
random
re
struct
xml.parsers.expat
cjkcodecs

zlib, bz2, lzma and crypts also can be implemented in pure Python.
msg177232 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2012-12-09 19:17
hashlib backends (md5, sha1, sha256 / 384 / 512) either through openssl wrappers or implementations based on libtomcrypt.
msg177247 - (view) Author: Chris Jerdonek (chris.jerdonek) * (Python committer) Date: 2012-12-10 01:32
Would it make sense for this list to be somehow reflected in or be reconstructible from the documentation?
msg177291 - (view) Author: Brett Cannon (brett.cannon) * (Python committer) Date: 2012-12-10 14:26
So expat doesn't count as that literally wraps the expat library. Random also requires accessing the system randomization libraries to work properly so I don't think that is a candidate either. As for the compression libraries, those could be re-implemented, but I view those as wrappers around the libraries (same as the crypto stuff). I mean it doesn't have to be that way, but I'm trying to keep this framed in a tractable problem to start.

So to summarize the non-contentious modules (including adding functools) in alphabetical order, that puts us at:

array
audioop
binascii
cjkcodecs
csv
functools
itertools
re
struct

I would be curious to see what frequency these modules are used to know what might be higher priority so that the least used modules could eventually be marked as CPython-specific.

And to answer Chris' question, there is no need to be able to generate this from the docs until there is some PEP listing what modules must be implemented by a VM in order to considers its stdlib complete.

And thanks for the help so far, everyone!
msg177293 - (view) Author: Amaury Forgeot d'Arc (amaury.forgeotdarc) * (Python committer) Date: 2012-12-10 14:37
PyPy has a pure Python implementation of sqlite (using ctypes):
https://bitbucket.org/pypy/pypy/src/default/lib_pypy/_sqlite3.py

It most probably works on CPython as well.
Does it belong to this list?
msg177294 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2012-12-10 14:40
All cryptographic hash function are available as pure Python implementations. Although the Python based variants are super slow (except maybe on PyPy), they still serve as an academic show case.

IIRC PyPy has pure Python implementations of MD5, SHA-1 and SHA-2 family.
msg177299 - (view) Author: Brett Cannon (brett.cannon) * (Python committer) Date: 2012-12-10 16:25
No, sqlite does not belong on this list as it wraps a C library. Plus there is an explicit block for ctypes-based modules in the stdlib which would prevent moving over the PyPy implementation.

And I'm sure pure Python versions of all the crypto libraries are out there, but I would be worried about them being implemented wrong, too slow to care, etc. Plus short of PyPy all of the other VMs have access to those crypto libraries in their own standard library so there is no need to provide it in Python's in pure Python.
msg177300 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2012-12-10 16:27
Agreed with Brett.
msg177302 - (view) Author: Philip Jenvey (pjenvey) * (Python committer) Date: 2012-12-10 18:35
zipimport
msg177303 - (view) Author: Brian Curtin (brian.curtin) * (Python committer) Date: 2012-12-10 18:50
winreg does not have a pure equivalent, nor could it
msg177309 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-12-10 19:53
> So expat doesn't count as that literally wraps the expat library.

XML parser can be implemented in pure Python. There are a lot of XML parsers 
implemented in different programming languages.

> Random
> also requires accessing the system randomization libraries to work
> properly so I don't think that is a candidate either.

No, random have C implemented some basic methods only for speed. It uses 
time() system function for initial seeding, but time() is accessible from pure 
Python too.

Some OS-specific modules (pwd, grp, spwd, resource, ossaudiodev, etc) can be 
implemented in pure Python on some platforms (using I/O and ioctl on special 
files in /etc, /dev or /proc).
msg177310 - (view) Author: Brett Cannon (brett.cannon) * (Python committer) Date: 2012-12-10 20:06
Sure, a general XML parsing library could be written in Python, but they wouldn't be named expat. =) The expat module wraps a specific XML parser (expat) so I still do not consider it applicable for this list.

As for random, you are right that it doesn't use platform-specific random code.
msg177316 - (view) Author: Alex Gaynor (alex) * (Python committer) Date: 2012-12-10 23:12
A lot of builtins :)
msg177332 - (view) Author: Amaury Forgeot d'Arc (amaury.forgeotdarc) * (Python committer) Date: 2012-12-11 11:03
What's the purpose of these alternate implementations?  For education, experiments?  As a replacement for other VMs?

Other modules that could be considered:
marshal
operator
unicodedata
msg177338 - (view) Author: Brett Cannon (brett.cannon) * (Python committer) Date: 2012-12-11 14:16
Alex: yes, the builtins could almost all be re-implemented in pure Python, but there is a performance consideration vs. benefit (e.g. if we re-implemented map() in Python which VMs would use it vs. implement it in some native way for performance?).

But one place I think there could be a benefit w/o performance issues is the built-in exceptions as you should be able to store references to the classes to help minimize the added cost of startup creating the exceptions from Python code.

Amaury: other VMs and easier extensibility in the future. We might as well all share the burden of maintaining pure Python versions instead of re-implementing the same thing over and over in little VM silos. And if some new thing needs to be added for a module it's easier to do it in Python than C (which then also continues to benefit other VMs).
msg177419 - (view) Author: Éric Araujo (eric.araujo) * (Python committer) Date: 2012-12-13 17:04
Should itertools be in the list, as its stated purpose is to provide highly efficient functions?
msg177431 - (view) Author: Brett Cannon (brett.cannon) * (Python committer) Date: 2012-12-13 18:46
Eric, I know you didn't just mean to suggest Python != efficient. =)

Yes, it should be in the list because other VMs might not want to re-implement that code in some native language to the VM. And I assume all code in the stdlib tries to be efficient, so that label holds no sway with me.
msg177520 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2012-12-14 23:38
itertools should be fairly easy as the docs already contain Python equivalents (or near equivalents).
msg177521 - (view) Author: Philip Jenvey (pjenvey) * (Python committer) Date: 2012-12-14 23:51
PyPy had a pure python itertools until recently (it's been deleted):

https://bitbucket.org/pypy/pypy/src/c1aa74c06e86/lib_pypy/itertools.py?at=py3k
msg177887 - (view) Author: Éric Araujo (eric.araujo) * (Python committer) Date: 2012-12-21 17:26
Oops, sorry I slipped :)
msg177891 - (view) Author: Meador Inge (meador.inge) * (Python committer) Date: 2012-12-21 20:02
I noticed functools in the list.  issue14373 was opened somewhat recently to reimplement functools.lru_cache in C.  This issue seems to be promoting have more things implemented in pure Python.  Someone involved in this issue might want to weigh in on issue14373 if that is the case.
msg177892 - (view) Author: Philip Jenvey (pjenvey) * (Python committer) Date: 2012-12-21 20:10
The guidelines for this are in PEP 399. Basically, adding 'accelerated' implementations when necessary isn't a bad thing as long as there are pure Python equivalents (unless it's a special case) and both are tested.

issue14373's latest patch seems to be following the PEP
msg177898 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-12-21 21:37
I'm involved in both issues and I think it's good to have so much simple Python implementations as possible and to have C accelerators for any performance critical code.
msg178674 - (view) Author: Brett Cannon (brett.cannon) * (Python committer) Date: 2012-12-31 13:55
One thing I should say about this list of modules is please don't go nuts porting every single module blindly. There is always a possibility that another VM has already ported the code and has simply not contributed it back and so there is no need to write it from scratch and more just political wrangling to get contributions pushed upstream from other VMs. There might also be reasons to not worry about porting something. Always start a conversation first before starting a port; last thing I want is someone putting in the time to port some code that no one will necessarily use for a while.
msg178688 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-12-31 15:01
There is one additional benefit. I have already implemented audioop module in Python, and due to this it has found many bugs in the current C implementation (issue16686).
msg180625 - (view) Author: Eric Snow (eric.snow) * (Python committer) Date: 2013-01-25 21:18
Also missing a pure-Python implementation:

collections.defaultdict (relatively trivial)
collections.deque

In the spirit of what Brett said, I found that PyPy has an implementation already:

  https://bitbucket.org/pypy/pypy/src/default/lib_pypy/_collections.py

Jython and IronPython do not have pure Python implentations:
  http://hg.python.org/jython/file/default/src/org/python/modules/_collections
  http://ironpython.codeplex.com/SourceControl/changeset/view/99885#1091023
msg183914 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-03-11 02:44
I don't think itertools or collections.deque should go on this list.  The other implementations already have these and a pure python versions miss the point of these being high performance tools.  AFAICT, there is zero benefit to adding a bunch of extra code that will never get used.  It will only complicate my maintenance of those modules.
History
Date User Action Args
2013-03-11 02:44:48rhettingersetnosy: + rhettinger
messages: + msg183914
2013-02-27 20:06:27tshepangsetnosy: + tshepang
2013-01-26 02:04:27ezio.melottisetnosy: + ezio.melotti
dependencies: + Add OrderedDict written in C
type: enhancement
2013-01-25 21:18:19eric.snowsetnosy: + eric.snow
messages: + msg180625
2012-12-31 15:01:30serhiy.storchakasetmessages: + msg178688
2012-12-31 13:55:28brett.cannonsetmessages: + msg178674
2012-12-21 21:37:00serhiy.storchakasetmessages: + msg177898
2012-12-21 20:10:43pjenveysetmessages: + msg177892
2012-12-21 20:02:42meador.ingesetnosy: + meador.inge
messages: + msg177891
2012-12-21 17:26:41eric.araujosetmessages: + msg177887
2012-12-16 09:05:53serhiy.storchakasetdependencies: + Add pure Python operator module
2012-12-14 23:51:06pjenveysetmessages: + msg177521
2012-12-14 23:38:10terry.reedysetnosy: + terry.reedy
messages: + msg177520
2012-12-14 01:31:35zach.waresetnosy: + zach.ware
2012-12-13 18:46:03brett.cannonsetmessages: + msg177431
2012-12-13 17:04:30eric.araujosetnosy: + eric.araujo
messages: + msg177419
2012-12-11 14:16:43brett.cannonsetmessages: + msg177338
2012-12-11 11:03:13amaury.forgeotdarcsetmessages: + msg177332
2012-12-11 10:42:16serhiy.storchakasetdependencies: + Pure Python implementation of random
2012-12-10 23:12:17alexsetmessages: + msg177316
2012-12-10 20:06:33brett.cannonsetmessages: + msg177310
2012-12-10 19:53:13serhiy.storchakasetmessages: + msg177309
2012-12-10 18:50:52brian.curtinsetnosy: + brian.curtin
messages: + msg177303
2012-12-10 18:35:54pjenveysetnosy: + pjenvey
messages: + msg177302
2012-12-10 16:27:05pitrousetnosy: + pitrou
messages: + msg177300
2012-12-10 16:25:33brett.cannonsetmessages: + msg177299
2012-12-10 14:40:07christian.heimessetmessages: + msg177294
2012-12-10 14:37:33amaury.forgeotdarcsetnosy: + amaury.forgeotdarc
messages: + msg177293
2012-12-10 14:32:58Arfreversetnosy: + Arfrever
2012-12-10 14:26:27brett.cannonsetmessages: + msg177291
2012-12-10 01:32:56chris.jerdoneksetnosy: + chris.jerdonek
messages: + msg177247
2012-12-09 21:21:51asvetlovsetnosy: + asvetlov
2012-12-09 19:17:57christian.heimessetnosy: + christian.heimes
messages: + msg177232
2012-12-09 19:03:52alexsetnosy: + alex
2012-12-09 19:03:06serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg177231
2012-12-09 18:39:53brett.cannoncreate