The current memory layout for dictionaries is
unnecessarily inefficient. It has a sparse table of
24-byte entries containing the hash value, key pointer,
and value pointer.
Instead, the 24-byte entries should be stored in a
dense table referenced by a sparse table of indices.
For example, the dictionary:
d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}
is currently stored as:
entries = [['--', '--', '--'],
[-8522787127447073495, 'barry', 'green'],
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
[-9092791511155847987, 'timmy', 'red'],
['--', '--', '--'],
[-6480567542315338377, 'guido', 'blue']]
Instead, the data should be organized as follows:
indices = [None, 1, None, None, None, 0, None, 2]
entries = [[-9092791511155847987, 'timmy', 'red'],
[-8522787127447073495, 'barry', 'green'],
[-6480567542315338377, 'guido', 'blue']]
Only the data layout needs to change. The hash table
algorithms would stay the same. All of the current
optimizations would be kept, including key-sharing
dicts and custom lookup functions for string-only
dicts. There is no change to the hash functions, the
table search order, or collision statistics.
The memory savings are significant (from 30% to 95%
compression depending on the how full the table is).
Small dicts (size 0, 1, or 2) get the most benefit.
For a sparse table of size t with n entries, the sizes are:
curr_size = 24 * t
new_size = 24 * n + sizeof(index) * t
In the above timmy/barry/guido example, the current
size is 192 bytes (eight 24-byte entries) and the new
size is 80 bytes (three 24-byte entries plus eight
1-byte indices). That gives 58% compression.
Note, the sizeof(index) can be as small as a single
byte for small dicts, two bytes for bigger dicts and
up to sizeof(Py_ssize_t) for huge dict.
In addition to space savings, the new memory layout
makes iteration faster. Currently, keys(), values, and
items() loop over the sparse table, skipping-over free
slots in the hash table. Now, keys/values/items can
loop directly over the dense table, using fewer memory
accesses.
Another benefit is that resizing is faster and
touches fewer pieces of memory. Currently, every
hash/key/value entry is moved or copied during a
resize. In the new layout, only the indices are
updated. For the most part, the hash/key/value entries
never move (except for an occasional swap to fill a
hole left by a deletion).
With the reduced memory footprint, we can also expect
better cache utilization.
For those wanting to experiment with the design,
there is a pure Python proof-of-concept here:
http://code.activestate.com/recipes/578375
YMMV: Keep in mind that the above size statics assume a
build with 64-bit Py_ssize_t and 64-bit pointers. The
space savings percentages are a bit different on other
builds. Also, note that in many applications, the size
of the data dominates the size of the container (i.e.
the weight of a bucket of water is mostly the water,
not the bucket).
Raymond
Hi all,
https://github.com/python/cpython is now live as a semi-official, *read
only* Github mirror of the CPython Mercurial repository. Let me know if you
have any problems/concerns.
I still haven't decided how often to update it (considering either just N
times a day, or maybe use a Hg hook for batching). Suggestions are welcome.
The methodology I used to create it is via hg-fast-export. I also tried to
pack and gc the git repo as much as possible before the initial Github push
- it went down from almost ~2GB to ~200MB (so this is the size of a fresh
clone right now).
Eli
P.S. thanks Jesse for the keys to https://github.com/python
I've received some enthusiastic emails from someone who wants to
revive restricted mode. He started out with a bunch of patches to the
CPython runtime using ctypes, which he attached to an App Engine bug:
http://code.google.com/p/googleappengine/issues/detail?id=671
Based on his code (the file secure.py is all you need, included in
secure.tar.gz) it seems he believes the only security leaks are
__subclasses__, gi_frame and gi_code. (I have since convinced him that
if we add "restricted" guards to these attributes, he doesn't need the
functions added to sys.)
I don't recall the exploits that Samuele once posted that caused the
death of rexec.py -- does anyone recall, or have a pointer to the
threads?
--
--Guido van Rossum (home page: http://www.python.org/~guido/)
The Py_CLEAR macros is used as safe alternative for following unsafe
idiomatic code:
Py_XDECREF(ptr);
ptr = NULL;
But other unsafe idiomatic code is widely used in the sources:
Py_XDECREF(ptr);
ptr = new_value;
Every occurrence of such code is potential bug for same reasons as for
Py_CLEAR.
It was offered [1] to introduce new macros Py_REPLACE and Py_XREPLACE
for safe replace with Py_DECREF and Py_XDECREF respectively.
Automatically generated patch contains about 50 replaces [2].
[1] http://bugs.python.org/issue16447
[2] http://bugs.python.org/issue20440
It appears there's no obvious link from bugs.python.org to the contributor
agreement - you need to go via the unintuitive link Foundation ->
Contribution Forms (and from what I've read, you're prompted when you add a
patch to the tracker).
I'd suggest that if the "Contributor Form Received" field is "No" in user
details, there be a link to http://www.python.org/psf/contrib/.
Tim Delaney
Dear friends,
This is related with ticket 19717: "resolve() fails when the path
doesn't exist".
Assuming /home/cutecat exists but not /home/cutecat/aa,
what is the desired output of
Path('/home/cutecat/aa/bb/cc').resolve(strict=False)?
Should it be:
"/home/cutecat" (the existed path only),
"/home/cutecat/aa" (the first non-existed path; my current strategy), or
"/home/cutecat/aa/bb/cc" (the default behaviour of os.path.realpath)?
Vajrasky
Hi,
I'm working for eNovance on the asyncio module, the goal is to use it
in the huge OpenStack project (2.5 millions line of code) which
currently uses eventlet. I'm trying to fix remaining issues in the
asyncio module before Python 3.4 final.
The asyncio project is very active but discussions are splitted
between its own dedicated mailing list (python-tulip Google group),
Tulip bug tracker and Python bug tracker. Please join Tulip mailing
list if you are interested to contribute.
http://code.google.com/p/tulip/
I would like to share with you the status of the module. Many bugs
have been fixed recently. I suppose that new bugs are found because
new developers started to play with asyncio since Python 3.4 beta 1.
asyncio issues fixed in Python 3.4 beta 3, in a random order:
- I wrote most of the asyncio documentation, please help me to improve
it! I tried to add many short examples, each time explaining one
feature or concept (ex: callbacks, signals, futures, etc.):
http://docs.python.org/dev/library/asyncio.html
- Characters devices (TTY/PTY) are now supported, useful to control
real terminal (not pipes) for subprocesses. On Mac OS X older than
Maverick (10.9), the SelectSelector should be used instead of
KqueueSelector (kqueue didnd't support character devices)
- Tulip #111: StreamReader.readexactly() now raises an
IncompleteReadError if the
end of stream is reached before we received enough bytes, instead of returning
less bytes than requested.
- Python #20311: asyncio had a performance issue related to the
resolution of selectors and clocks. For example,
selectors.EpollSelector has a resolution of 1 millisecond (10^-3),
whereas asyncio uses arbitrary timestamps. The issue was fixed by
adding a resolution attribute to selectors and a private granularity
attribute to asyncio.BaseEventLoop, and use the granularity in asyncio
event loop to round times.
- New Task.current_task() class method
- Guido wrote a web crawler, see examples/crawl.py in Tulip
- More symbols are exported in the main asyncio module (ex: Queue,
iscouroutine(), etc.)
- Charles-François improved the signal handlers: SA_RESTART flag is
now set to limit EINTR errors in syscalls
- Some optimizations (ex: don't call logger.log() when it's not needed)
- Many bugfixes
- (sorry if I forgot other changes, see also Tulip history and history
of the asyncio module in Python)
I also would like to change asyncio to support a "stream-like" API for
subprocesses, see Tulip issue #115 (and Python issue #20400):
http://code.google.com/p/tulip/issues/detail?id=115
I ported ayncio on Python 2.6 and 2.7, because today OpenStack only
uses these Python versions. I created a new project called "Trollius"
(instead of "Tulip") because the syntax is a little bit different.
"yield from" becomes "yield", and "return x" becomes "raise
Return(x)":
https://bitbucket.org/enovance/trolliushttps://pypi.python.org/pypi/trollius
If you are interested by the OpenStack part, see my blueprint
(something similar to PEPs but for smaller changes) for Oslo Messaing:
https://wiki.openstack.org/wiki/Oslo/blueprints/asyncio
There is an ongoing effort to port OpenStack to Python 3, eNovance is
also working on the portage:
https://wiki.openstack.org/wiki/Python3
Victor
Dear comrades,
I would like to bring to your attention my disagreement with Larry
Hastings in this ticket: http://bugs.python.org/issue19145
(Inconsistent behaviour in itertools.repeat when using negative
times).
Let me give you the context:
>>> from itertools import repeat
>>> repeat('a')
repeat('a')
>>> repeat('a', times=-1)
repeat('a')
>>> repeat('a', -1)
repeat('a', 0)
>>> repeat('a', times=-4)
repeat('a', -4)
>>> repeat('a', -4)
repeat('a', 0)
Right now, the only way you can tell repeat to do endless repetitions
is to omit the `times` argument or by setting `times` argument to -1
via keyword.
Larry intends to fix this in Python 3.5 by making None value to
`times` argument as a representative of unlimited repetitions and
negative `times` argument (either via keyword or positional) ALWAYS
means 0 repetitions. This will ensure repeat has the appropriate
signature. I have no qualms about it. All is well.
My disagreement is related to Larry's decision not to fix this bug in
Python 2.7, 3.3, and 3.4. Both of us agree that we should not let
Python 2.7, 3.3, and 3.4 happily accepts None value because that is
more than bug fix. What we don't agree is whether we should make
negative `times` argument via keyword behaviour needs to be changed or
not. He prefer let it be. I prefer we change the behaviour so that
negative `times` argument in Python 2.7, 3.3, and 3.4 ALWAYS means 0
repetitions.
My argument is that, on all circumstances, argument sent to function
via positional or keyword must mean the same thing.
Let's consider this hypothetical code:
# 0 means draw, positive int means win, negative int means lose
result = goals_result_of_the_match()
# For every goal of the winning match, we donate money to charity.
# Every donation consists of 10 $.
import itertools
itertools.repeat(donate_money_to_charity(), result)
Later programmer B refactor this code:
# 0 means draw, positive int means win, negative int means lose
result = goals_result_of_the_match()
# For every goal of the winning match, we donate money to charity.
# Every donation consists of 10 $
from itertools import repeat
repeat(object=donate_money_to_charity(), times=result)
They use Python 2.7 (remember Python 2.7 is here to stay for a long
long time). And imagine the match is lost 0-1 or 1-2 or 2-3 (so the
goal difference is negative one / -1). It means they donate money to
charity endlessly!!! They can go bankrupt.
So I hope my argument is convincing enough. We need to fix this bug in
Python 2.7, 3.3, and 3.4, by making `times` argument sent via
positional or keyword in itertools.repeat ALWAYS means the same thing,
which is 0 repetitions.
If this is not possible, at the very least, we need to warn this
behaviour in the doc.
Whatever decision that comes up from this discussion, I will make peace with it.
Vajrasky
I'd like to resolve a long-standing issue of the stable ABI in 3.4:
http://bugs.python.org/issue17162
The issue is that, since PyTypeObject is opaque, module authors cannot
get at tp_free, which they may need to in order to implement tp_dealloc
properly.
Rather than providing the proposed specific wrapper for tp_dealloc, I
propose to add a generic PyType_GetSlot function. From a stability point
of view, exposing slot values is uncritical - it's just that the layout
of the type object is hidden.
Any objection to adding this before RC1?
Regards,
Martin
