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
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/)
hi, everyone:
I want to compile python 3.3 with bz2 support on RedHat 5.5 but fail to do that. Here is how I do it:
1、download bzip2 and compile it(make、make -f Makefile_libbz2_so、make install)
2、chang to python 3.3 source directory : ./configure --with-bz2=/usr/local/include
3、make
4、make install
after installation complete, I test it：
[root@localhost Python-3.3.0]# python3 -c "import bz2"
Traceback (most recent call last):
File "<string>", line 1, in <module>
File "/usr/local/lib/python3.3/bz2.py", line 21, in <module>
from _bz2 import BZ2Compressor, BZ2Decompressor
ImportError: No module named '_bz2'
By the way, RedHat 5.5 has a built-in python 2.4.3. Would it be a problem?
Hi,
I suspect that this will be put into a proper PEP at some point, but I'd
like to bring this up for discussion first. This came out of issues 13429
and 16392.
http://bugs.python.org/issue13429http://bugs.python.org/issue16392
Stefan
The problem
===========
Python modules and extension modules are not being set up in the same way.
For Python modules, the module is created and set up first, then the module
code is being executed. For extensions, i.e. shared libraries, the module
init function is executed straight away and does both the creation and
initialisation. This means that it knows neither the __file__ it is being
loaded from nor its package (i.e. its FQMN). This hinders relative imports
and resource loading. In Py3, it's also not being added to sys.modules,
which means that a (potentially transitive) re-import of the module will
really try to reimport it and thus run into an infinite loop when it
executes the module init function again. And without the FQMN, it's not
trivial to correctly add the module to sys.modules either.
We specifically run into this for Cython generated modules, for which it's
not uncommon that the module init code has the same level of complexity as
that of any 'regular' Python module. Also, the lack of a FQMN and correct
file path hinders the compilation of __init__.py modules, i.e. packages,
especially when relative imports are being used at module init time.
The proposal
============
I propose to split the extension module initialisation into two steps in
Python 3.4, in a backwards compatible way.
Step 1: The current module init function can be reduced to just creating
the module instance and returning it (and potentially doing some simple C
level setup). Optionally, after creating the module (and this is the new
part), the module init code can register a C callback function that will be
called after setting up the module.
Step 2: The shared library importer receives the module instance from the
module init function, adds __file__, __path__, __package__ and friends to
the module dict, and then checks for the callback. If non-NULL, it calls it
to continue the module initialisation by user code.
The callback
============
The callback is defined as follows::
int (*PyModule_init_callback)(PyObject* the_module,
PyModuleInitContext* context)
"PyModuleInitContext" is a struct that is meant mostly for making the
callback more future proof by allowing additional parameters to be passed
in. For now, I can see a use case for the following fields::
struct PyModuleInitContext {
char* module_name;
char* qualified_module_name;
}
Both names are encoded in UTF-8. As for the file path, I consider it best
to retrieve it from the module's __file__ attribute as a Python string
object to reduce filename encoding problems.
Note that this struct argument is not strictly required, but given that
this proposal would have been much simpler if the module init function had
accepted such an argument in the first place, I consider it a good idea not
to let this chance pass by again.
The registration of the callback uses a new C-API function:
int PyModule_SetInitFunction(PyObject* module,
PyModule_init_callback callback)
The function name uses "Set" instead of "Register" to make it clear that
there is only one such function per module.
An alternative would be a new module creation function "PyModule_Create3()"
that takes the callback as third argument, in addition to what
"PyModule_Create2()" accepts. This would require users to explicitly pass
in the (second) version argument, which might be considered only a minor issue.
Implementation
==============
The implementation requires local changes to the extension module importer
and a new C-API function. In order to store the callback, it should use a
new field in the module object struct.
Open questions
==============
It is not clear how extensions should be handled that register more than
one module in their module init function, e.g. compiled packages. One
possibility would be to leave the setup to the user, who would have to know
all FQMNs anyway in this case, although not the import file path.
Alternatively, the import machinery could use a stack to remember for which
modules a callback was registered during the last init function call, set
up all of them and then call their callbacks. It's not clear if this meets
the intention of the user.
Alternatives
============
1) It would be possible to make extension modules optionally export another
symbol, e.g. "PyInit2_modulename", that the shared library loader would
call in addition to the required function "PyInit_modulename". This would
remove the need for a new API that registers the above callback. The
drawback is that it also makes it easier to write broken code because a
Python version or implementation that does not support this second symbol
would simply not call it, without error. The new C-API function would let
the build fail instead if it is not supported.
2) The callback could be made available as a Python function in the module
dict, thus also removing the need for an explicit registration API.
However, this approach would add overhead to both sides, the importer code
and the user provided module init code, as it would require additional
dictionary handling and the implementation of a one-time Python function in
user code. It would also suffer from the problem that missing support in
the runtime would pass silently.
3) The callback could be registered statically in the PyModuleDef struct by
adding a new field. This is not trivial to do in a backwards compatible way
because the struct would grow longer without explicit initialisation by
existing user code. Extending PyModuleDef_HEAD_INIT might be possible but
would still break at least binary compatibility.
4) Pass a new context argument into the module init function that contains
all information necessary to properly and completely set up the module at
creation time. This would provide a much simpler and cleaner solution than
the proposed solution. However, it will not be possible before Python 4 as
it breaks backwards compatibility with all existing extension modules at
both the source and binary level.
[No, I'm not interested in the port myself]
patches for a mingw32 port are floating around on the web and the python bug
tracker, although most of them as a set of patches in one issue addressing
several things, and which maybe outdated for the trunk. at least for me
re-reading a big patch in a new version is more work than having the patches in
different issues. So proposing to break down the patches in independent ones,
dealing with:
- mingw32 support (excluding any cross-build support). tested with
a native build with srcdir == builddir. The changes for distutils
mingw32 support should be a separate patch. Who could review these?
Asked Martin, but didn't get a reply yet.
- patches to cross-build for mingw32.
- patches to deal with a srcdir != builddir configuration, where the
srcdir is read-only (please don't mix with the cross-build support).
All work should be done on the tip/trunk.
So ok to close issue16526, issue3871, issue3754 and suggest in the reports to
start over with more granular changes?
Matthias
As discussed here, the python 2.5 binary distributed by Apple on mountain
lion is broken. Could someone file an official complaint? This is really
bad...
--Guido
--
--Guido van Rossum (python.org/~guido)
Hi. There are issue for subject: http://bugs.python.org/issue1207589
It has patches, implemented well and committed.
I've pushed it to versions 2.7, 3.2, 3.3 and 3.4.
My thoughts are: the issue is not brand new subject but improvement for
current IDLE functionality.
Added code cannot break any existing program/library I hope, it's related
to humans who use IDLE only.
It is desirable feature and probably IDLE users will be ok with new items
in context menu even they are still 2.7 users.
There are another opinion: it is new feature, not a bug, and the patch
should be applied to 3.4 only.
If you look on discussion for issue (http://bugs.python.org/issue1207589)
you can see we cannot make decision, votes are split.
I want to raise the question on this mailing list (as Terry Reedy
suggested) to ask for community opinion.
Thanks, Andrew Svetlov
Hello,
I guess a long time ago, threading support in operating systems wasn't
very widespread, but these days all our supported platforms have it.
Is it still useful for production purposes to configure
--without-threads? Do people use this option for something else than
curiosity of mind?
Regards
Antoine.
Say there, the Python core development community! Have I got
a question for you!
*ahem*
Which of the following four options do you dislike least? ;-)
1) CPython continues to provide no "function signature"
objects (PEP 362) or inspect.getfullargspec() information
for any function implemented in C.
2) We add new hand-coded data structures representing the
metadata necessary for function signatures for builtins.
Which means that, when defining arguments to functions in C,
we'd need to repeat ourselves *even more* than we already do.
3) Builtin function arguments are defined using some seriously
uncomfortable and impenetrable C preprocessor macros, which
produce all the various types of output we need (argument
processing code, function signature metadata, possibly
the docstrings too).
4) Builtin function arguments are defined in a small DSL; these
are expanded to code and data using a custom compile-time
preprocessor step.
All the core devs I've asked said "given all that, I'd prefer the
hairy preprocessor macros". But by the end of the conversation
they'd changed their minds to prefer the custom DSL. Maybe I'll
make a believer out of you too--read on!
I've named this DSL preprocessor "Argument Clinic", or Clinic
for short**. Clinic works similarly to Ned Batchelder's brilliant
"Cog" tool:
http://nedbatchelder.com/code/cog/
You embed the input to Clinic in a comment in your C file,
and the output is written out immediately after that comment.
The output's overwritten every time the preprocessor is run.
In short it looks something like this:
/*[clinic]
input to the DSL
[clinic]*/
... output from the DSL, overwritten every time ...
/*[clinic end:<checksum>]*/
The input to the DSL includes all the metadata about the
function that we need for the function signature:
* the name of the function,
* the return annotation (if any),
* each parameter to the function, including
* its name,
* its type (in C),
* its default value,
* and a per-parameter docstring;
* and the docstring for the function as a whole.
The resulting output contains:
* the docstring for the function,
* declarations for all your parameters,
* C code handling all argument processing for you,
* and a #define'd methoddef structure for adding the
function to the module.
I discussed this with Mark "HotPy" Shannon, and he suggested we break
our existing C functions into two. We put the argument processing
into its own function, generated entirely by Clinic, and have the
implementation in a second function called from the first. I like
this approach simply because it makes the code cleaner. (Note that
this approach should not cause any overhead with a modern compiler,
as both functions will be "static".)
But it also provides an optimization opportunity for HotPy: it could
read the metadata, and when generating the JIT'd code it could skip
building the PyObjects and argument tuple (and possibly keyword
argument dict), and the subsequent unpacking/decoding, and just call
the implementation function directly, giving it a likely-measurable
speed boost.
And we can go further! If we add a new extension type API allowing
you to register both functions, and external modules start using it,
sophisticated Python implementations like PyPy might be able to skip
building the tuple for extension type function calls--speeding those
up too!
Another plausible benefit: alternate implementations of Python could
read the metadata--or parse the input to Clinic themselves--to ensure
their reimplementations of the Python standard library conform to the
same API!
Clinic can also run general-purpose Python code ("/*[python]").
All output from "print" is redirected into the output section
after the Python code.
As you've no doubt already guessed, I've made a prototype of
Argument Clinic. You can see it--and some sample conversions of
builtins using it for argument processing--at this BitBucket repo:
https://bitbucket.org/larry/python-clinic
I don't claim that it's fabulous, production-ready code. But it's
a definite start!
To save you a little time, here's a preview of using Clinic for
dbm.open(). The stuff at the same indent as a declaration are
options; see the "clinic.txt" in the repo above for full documentation.
/*[clinic]
dbm.open -> mapping
basename=dbmopen
const char *filename;
The filename to open.
const char *flags="r";
How to open the file. "r" for reading, "w" for writing, etc.
int mode=0666;
default=0o666
If creating a new file, the mode bits for the new file
(e.g. os.O_RDWR).
Returns a database object.
[clinic]*/
PyDoc_STRVAR(dbmopen__doc__,
"dbm.open(filename[, flags=\'r\'[, mode=0o666]]) -> mapping\n"
"\n"
" filename\n"
" The filename to open.\n"
"\n"
" flags\n"
" How to open the file. \"r\" for reading, \"w\" for writing,
etc.\n"
"\n"
" mode\n"
" If creating a new file, the mode bits for the new file\n"
" (e.g. os.O_RDWR).\n"
"\n"
"Returns a database object.\n"
"\n");
#define DBMOPEN_METHODDEF \
{"open", (PyCFunction)dbmopen, METH_VARARGS | METH_KEYWORDS,
dbmopen__doc__}
static PyObject *
dbmopen_impl(PyObject *self, const char *filename, const char *flags,
int mode);
static PyObject *
dbmopen(PyObject *self, PyObject *args, PyObject *kwargs)
{
const char *filename;
const char *flags = "r";
int mode = 0666;
static char *_keywords[] = {"filename", "flags", "mode", NULL};
if (!PyArg_ParseTupleAndKeywords(args, kwargs,
"s|si", _keywords,
&filename, &flags, &mode))
return NULL;
return dbmopen_impl(self, filename, flags, mode);
}
static PyObject *
dbmopen_impl(PyObject *self, const char *filename, const char *flags,
int mode)
/*[clinic end:eddc886e542945d959b44b483258bf038acf8872]*/
As of this writing, I also have sample conversions in the following files
available for your perusal:
Modules/_cursesmodule.c
Modules/_dbmmodule.c
Modules/posixmodule.c
Modules/zlibmodule.c
Just search in C files for '[clinic]' and you'll find everything soon
enough.
As you can see, Clinic has already survived some contact with the
enemy. I've already converted some tricky functions--for example,
os.stat() and curses.window.addch(). The latter required adding a
new positional-only processing mode for functions using a legacy
argument processing approach. (See "clinic.txt" for more.) If you
can suggest additional tricky functions to support, please do!
Big unresolved questions:
* How would we convert all the builtins to use Clinic? I fear any
solution will involve some work by hand. Even if we can automate
big chunks of it, fully automating it would require parsing arbitrary
C. This seems like overkill for a one-shot conversion.
(Mark Shannon says he has some ideas.)
* How do we create the Signature objects? My current favorite idea:
Clinic also generates a new, TBD C structure defining all the
information necessary for the signature, which is also passed in to
the new registration API (you remember, the one that takes both the
argument-processing function and the implementation function). This
is secreted away in some new part of the C function object. At
runtime this is converted on-demand into a Signature object. Default
values for arguments are represented in C as strings; the conversion
process attempts eval() on the string, and if that works it uses the
result, otherwise it simply passes through the string.
* Right now Clinic paves over the PyArg_ParseTuple API for you.
If we convert CPython to use Clinic everywhere, theoretically we
could replace the parsing API with something cleaner and/or faster.
Does anyone have good ideas (and time, and energy) here?
* There's actually a fifth option, proposed by Brett Cannon. We
constrain the format of docstrings for builtin functions to make
them machine-readable, then generate the function signature objects
from that. But consider: generating *everything* in the signature
object may get a bit tricky (e.g. Parameter.POSITIONAL_ONLY), and
this might gunk up the docstring.
But the biggest unresolved question... is this all actually a terrible
idea?
//arry/
** "Is this the right room for an argument?"
"I've told you once...!"
