Well, CPython at least still enforces the padding, even if it's ignoring the invalid characters. Here's Seo's repro 'simplified' to go straight to binascii (just to get to the root API):

...

...

import binascii binascii.a2b_base64('%') ''

And then sending a valid character, invalid padding:

...

...

binascii.a2b_base64('A') Traceback (most recent call last): File "<stdin>", line 1, in ? binascii.Error: Incorrect padding

and then throwing in random invalid characters, and CPython ignores the invalid characters:

...

...

binascii.a2b_base64('ABC=') '\x00\x10' binascii.a2b_base64('%%ABC=') '\x00\x10' binascii.a2b_base64('%%ABC=%!@##') '\x00\x10' binascii.a2b_base64('%%ABC=%!@##*#*()') '\x00\x10'

The documentation for binascii.a2b_base64 doesn't specify if it throws for anything either. I would suspect that there's a reason why CPython is ignoring the invalid characters here. If this is the expected behavior then I'm happy to make IronPython match this. And at the very least we HAVE to fix the exception that gets thrown - I'm with Seo that it should be a ValueError but line between ValueError and TypeError is blurry at times anyway, and TypeError is what's documented. Do you want to help develop Dynamic languages on CLR? (http://members.microsoft.com/careers/search/details.aspx?JobID=6D4754DE-11F0...) -----Original Message----- From: users-bounces@lists.ironpython.com [mailto:users-bounces@lists.ironpython.com] On Behalf Of Sanghyeon Seo Sent: Wednesday, April 05, 2006 10:45 PM To: python-dev@python.org; users@lists.ironpython.com Subject: [IronPython] base64 module Hello, base64 module documentation for b64decode function says, "TypeError is raised if s were incorrectly padded or if there are non-alphabet characters present in the string." But this doesn't seem to be the case. Testcase: import base64 base64.b64decode('%') Since % is a non-alphabet character, this should raise TypeError (btw, shouldn't this be ValueError instead?), but Python 2.4.3 silently ignores. I found this while experimenting with IronPython. IronPython 1.0 Beta 5 gives: Traceback (most recent call last): File base64, line unknown, in b64decode SystemError: cannot decode byte: '%' It's not TypeError, but it doesn't silently ignore either. Seo Sanghyeon _______________________________________________ users mailing list users@lists.ironpython.com http://lists.ironpython.com/listinfo.cgi/users-ironpython.com

2006/4/7, Aahz :

Please submit a bug report on SourceForge and report back the ID.

http://python.org/sf/1466065 Seo Sanghyeon

There exists various C and Python implementations of both AVL and Red-Black trees. For users of Python who want to use AVL and/or Red-Black trees, I would urge them to use the Python implementations. In the case of *needing* the speed of a C extension, there already exists a CPython extension module for AVL trees: http://www.python.org/pypi/pyavl/1.1 I would suggest you look through some suggested SoC projects in the wiki: http://wiki.python.org/moin/SummerOfCode - Josiah "Vladimir 'Yu' Stepanov" wrote:

I would like to participate in Google Summer of Code. The idea consists in creation of a specialized class for work with binary trees AVL and RB. The part of ideas is taken from Parrot (Perl6) where for pair values the specialized type is stipulated. As advantages it is possible to note: * High speed. On simple types at quantity of elements up to 10000 speed of work concedes to the standard dictionary of all in 2.7 times. * Safety of work in a multithread operating mode. * The method for frosts of object is stipulated. * The data storage is carried out in the sorted kind. * A high overall performance `item' and `iteritem' methods as it is not necessary to create new objects. * At lots of objects in a tree memory is used much less intensively. * Absence of collisions. As consequence, it is impossible to generate bad data for creation DoS of the attacks influencing the dictionary of transferred arguments. * For objects existence of a method __ hash __ is not necessary. * The same kind of the dictionary by means of the overloaded operations probably change of its behaviour so that it supported the multivariational representation based on stratification given and subsequent recoils.

Additional requirements to key objects: * The opportunity of comparison of key objects function cmp is necessary.

There are the reasons, braking development of this project: * Compulsion of heading of a module `gc' for each compound object (this structure is unessential to some objects, but updating `gc' the module is required). * Absence of standard object the pair, probably depends on the previous item.

Lacks of a binary tree: * Average time of search for hash - O (1), and for trees - O (log2 N). * A lot of memory under a single element of a tree: (3*sizeof (void *) + sizeof (int))*2, one element is used rather - the pair, the second site of memory is allocated under node of a tree.

In protection of object "pair": * The logic of methods of the given object noticeably is easier than tuple, that as a result can affect speed of work of the program in the best party. * Alignment on 8 bytes has no big sense at present architecture where in cache sample a minimum on 64 bytes is made. Use of type "pair" will give an appreciable prize at use of alignment in 4 bytes. Otherwise on 64-bit platforms it is much more favourable to use tuple object.

The given project can demand processing of the module `gcmodule.c' and `tupleobject.c'. It is necessary to reduce the size of static objects, for this purpose the opportunity is necessary is transparent to pass objects not having direct support from the module `gcmodule.c'.

Also it will be partially necessary to process the module `obmalloc.c' for more effective distribution of memory.

I shall be glad to answer questions on this theme.

_______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/jcarlson%40uci.edu

Josiah Carlson wrote:

There exists various C and Python implementations of both AVL and Red-Black trees. For users of Python who want to use AVL and/or Red-Black trees, I would urge them to use the Python implementations. In the case of *needing* the speed of a C extension, there already exists a CPython extension module for AVL trees: http://www.python.org/pypi/pyavl/1.1

I would suggest you look through some suggested SoC projects in the wiki: http://wiki.python.org/moin/SummerOfCode

- Josiah

Thanks for the answer! I already saw pyavl-1.1. But for this reason I would like to see the module in a standard package python. Functionality for pyavl and dict to compare difficultly. Functionality of my module will differ from functionality dict in the best party. I have lead some tests on for work with different types both for a package pyavl-1.1, and for the prototype of own module. The script of check is resulted in attached a file avl-timeit.py In files timeit-result-*-*.txt results of this test. The first in the name of a file means quantity of the added elements, the second - argument of a method timeit. There it is visible, that in spite of the fact that the module xtree is more combined in comparison with pyavl the module (for everyone again inserted pair [the key, value], is created two elements: python object - pair, and an internal element of a tree), even in this case it works a little bit more quickly. Besides the module pyavl is unstable for work in multithread appendices (look the attached file module-avl-is-thread-unsafe.py). I think, that creation of this type (together with type of pair), will make programming more convenient since sorting by function sort will be required less often. I can probably borrow in this module beyond the framework of the project google. The demand of such type of data is interesting. Because of necessity of processing `gcmodule.c' and `obmalloc.c' this module cannot be realized as the external module. #!/usr/local/bin/python # Initialize modules import avl import xtree import types import sys import timeit if len(sys.argv) != 3: iterations = 1000000 count = 10 else: iterations = int(sys.argv[1]) count = int(sys.argv[2]) print "Iterations", iterations print "Repeats", count print result_avl = timeit.Timer(""" import avl a = avl.new() for i in xrange(%d): a.insert(i) """ % iterations).timeit(count) print "object avl.new()", result_avl result_xtree = timeit.Timer(""" import xtree a = xtree.xtree() for i in xrange(%d): a[i] = True """ % iterations).timeit(count) print "object xtree.xtree()", result_xtree result_dict = timeit.Timer(""" import types a = dict() for i in xrange(%d): a[i] = True """ % iterations).timeit(count) print "object dict()", result_dict print " Dict Xtree AVL" print "Dict %.2f %.2f %.2f" % (float(result_dict)/result_dict, float(result_dict)/result_xtree, float(result_dict)/result_avl) print "Xtree %.2f %.2f %.2f" % (float(result_xtree)/result_dict, float(result_xtree)/result_xtree, float(result_xtree)/result_avl) print "AVL %.2f %.2f %.2f" % (float(result_avl)/result_dict, float(result_avl)/result_xtree, float(result_avl)/result_avl) fox:root!~/Downloads/Python/PYTHON/pyavl-1.1 > python setup.py install running install running build running build_ext building 'avl' extension creating build creating build/temp.freebsd-5.4-RELEASE-i386-2.4 cc -fno-strict-aliasing -DNDEBUG -O -pipe -D__wchar_t=wchar_t -DTHREAD_STACK_SIZE=0x20000 -O2 -fPIC -DHAVE_AVL_VERIFY -DAVL_FOR_PYTHON -I/usr/local/include/python2.4 -c avl.c -o build/temp.freebsd-5.4 -RELEASE-i386-2.4/avl.o -O2 -Wno-parentheses -Wno-uninitialized cc -fno-strict-aliasing -DNDEBUG -O -pipe -D__wchar_t=wchar_t -DTHREAD_STACK_SIZE=0x20000 -O2 -fPIC -DHAVE_AVL_VERIFY -DAVL_FOR_PYTHON -I/usr/local/include/python2.4 -c avlmodule.c -o build/temp.freeb sd-5.4-RELEASE-i386-2.4/avlmodule.o -O2 -Wno-parentheses -Wno-uninitialized creating build/lib.freebsd-5.4-RELEASE-i386-2.4 cc -shared -pthread -O2 build/temp.freebsd-5.4-RELEASE-i386-2.4/avl.o build/temp.freebsd-5.4-RELEASE -i386-2.4/avlmodule.o -o build/lib.freebsd-5.4-RELEASE-i386-2.4/avl.so -Wl,-x running install_lib copying build/lib.freebsd-5.4-RELEASE-i386-2.4/avl.so -> /usr/local/lib/python2.4/site-packages

"Vladimir 'Yu' Stepanov" wrote:

Josiah Carlson wrote:

...

There exists various C and Python implementations of both AVL and Red-Black trees. For users of Python who want to use AVL and/or Red-Black trees, I would urge them to use the Python implementations. In the case of *needing* the speed of a C extension, there already exists a CPython extension module for AVL trees: http://www.python.org/pypi/pyavl/1.1

I would suggest you look through some suggested SoC projects in the wiki: http://wiki.python.org/moin/SummerOfCode

- Josiah

Thanks for the answer!

I already saw pyavl-1.1. But for this reason I would like to see the module in a standard package python. Functionality for pyavl and dict to compare difficultly. Functionality of my module will differ from functionality dict in the best party. I have lead some tests on for work with different types both for a package pyavl-1.1, and for the prototype of own module. The script of check is resulted in attached a file avl-timeit.py In files timeit-result-*-*.txt results of this test. The first in the name of a file means quantity of the added elements, the second - argument of a method timeit. There it is visible, that in spite of the fact that the module xtree is more combined in comparison with pyavl the module (for everyone again inserted pair [the key, value], is created two elements: python object - pair, and an internal element of a tree), even in this case it works a little bit more quickly. Besides the module pyavl is unstable for work in multithread appendices (look the attached file module-avl-is-thread-unsafe.py).

I'm not concerned about the speed of the external AVL module, and I'm not concerned about the speed of trees in Python; so far people have found that dictionaries are generally sufficient. More specifically, while new lambda syntaxes are presented almost weekly, I haven't heard anyone complain about Python's lack of a tree module in months. As a result, I don't find the possible addition of any tree structure to the collections module as being a generally compelling addition. Again, I believe that the existance of 3rd party extension modules which implement AVL and red-black trees, regardless of their lack of thread safety, slower than your module by a constant, or lack of particular functionality to be basically immaterial to this discussion. In my mind, there are only two relevant items to this discussion: 1. Is having a tree implementation (AVL or Red-Black) important, and if so, is it important enough to include in the collections module? 2. Is a tree implementation important enough for google to pay for its inclusion, given that there exists pyavl and a collectionsmodule.c patch for a red-black tree implementation? Then again, you already have your own implementation of a tree module, and it seems as though you would like to be paid for this already-done work. I don't know how google feels about such things, but you should remember to include this information in your application.

I think, that creation of this type (together with type of pair), will make programming more convenient since sorting by function sort will be required less often.

How often are you sorting data? I've found that very few of my operations involve sorting data of any kind, and even if I did have need of sorting, Python's sorting algorithm is quite fast, likely faster by nearly a factor of 2 (in the number of comparisons) than the on-line construction of an AVL or Red-Black tree.

I can probably borrow in this module beyond the framework of the project google. The demand of such type of data is interesting. Because of necessity of processing `gcmodule.c' and `obmalloc.c' this module cannot be realized as the external module.

It seems to me (after checking collectionsmodule.c and a few others) that proper C modules only seem to import Python.h and maybe structmember.h . If you are manually including gcmodule.c and obmalloc.c, you may be doing something wrong; I'll leave it to others to further comment on this aspect. - Josiah

Josiah Carlson wrote:

"Vladimir 'Yu' Stepanov" wrote:

...

Josiah Carlson wrote:

...

There exists various C and Python implementations of both AVL and Red-Black trees. For users of Python who want to use AVL and/or Red-Black trees, I would urge them to use the Python implementations. In the case of *needing* the speed of a C extension, there already exists a CPython extension module for AVL trees: http://www.python.org/pypi/pyavl/1.1

I would suggest you look through some suggested SoC projects in the wiki: http://wiki.python.org/moin/SummerOfCode

- Josiah

Thanks for the answer!

I already saw pyavl-1.1. But for this reason I would like to see the module in a standard package python. Functionality for pyavl and dict to compare difficultly. Functionality of my module will differ from functionality dict in the best party. I have lead some tests on for work with different types both for a package pyavl-1.1, and for the prototype of own module. The script of check is resulted in attached a file avl-timeit.py In files timeit-result-*-*.txt results of this test. The first in the name of a file means quantity of the added elements, the second - argument of a method timeit. There it is visible, that in spite of the fact that the module xtree is more combined in comparison with pyavl the module (for everyone again inserted pair [the key, value], is created two elements: python object - pair, and an internal element of a tree), even in this case it works a little bit more quickly. Besides the module pyavl is unstable for work in multithread appendices (look the attached file module-avl-is-thread-unsafe.py).

I'm not concerned about the speed of the external AVL module, and I'm not concerned about the speed of trees in Python; so far people have found that dictionaries are generally sufficient. More specifically, while new lambda syntaxes are presented almost weekly, I haven't heard anyone complain about Python's lack of a tree module in months. As a result, I don't find the possible addition of any tree structure to the collections module as being a generally compelling addition.

The object dict is irreplaceable in most cases, it so. I do not assume, that binary trees can sometime replace standard `dict' object. Sorting of the list also is and will be irreplaceable function. But there is a number of problems which can be rather easily solved by means of binary trees. Most likely for them there will be an alternative. But, as a rule, it is less obvious to the programmer. And most likely realization will be not so fast. Probably that nobody mentioned necessity of binary trees. In my opinion it is not a reason in an estimation of necessity of the given type. To take for example PHP. The array and the dictionary there is realized as the list. There is no even a hint on hash object. Those users to whom was necessary hash already have chosen perl/python/ruby/etc. The similar situation can arise and concerning binary trees.

Again, I believe that the existance of 3rd party extension modules which implement AVL and red-black trees, regardless of their lack of thread safety, slower than your module by a constant, or lack of particular functionality to be basically immaterial to this discussion. In my mind, there are only two relevant items to this discussion:

1. Is having a tree implementation (AVL or Red-Black) important, and if so, is it important enough to include in the collections module? 2. Is a tree implementation important enough for google to pay for its inclusion, given that there exists pyavl and a collectionsmodule.c patch for a red-black tree implementation?

Then again, you already have your own implementation of a tree module, and it seems as though you would like to be paid for this already-done work. I don't know how google feels about such things, but you should remember to include this information in your application.

I have looked a patch for collectionsmodule.c. In my opinion it is fine realization of binary trees. If there is this class that to me there is no need to create one more copy. My persistence speaks a demand of this type of data. As to my message on the beginning of the project for SoC I ask to consider that this theme has not been lifted :) For me it was a minor question.

...

I think, that creation of this type (together with type of pair), will make programming more convenient since sorting by function sort will be required less often.

How often are you sorting data? I've found that very few of my operations involve sorting data of any kind, and even if I did have need of sorting, Python's sorting algorithm is quite fast, likely faster by nearly a factor of 2 (in the number of comparisons) than the on-line construction of an AVL or Red-Black tree.

Really it is not frequent. Only when there is one of problems which is difficult for solving by means of already available means, whether means it that I should look aside C, C ++? It not seems to me that presence of structures of self-balanced binary trees are distinctive feature of any language. Comparison of functions of sorting and binary trees not absolutely correctly. I think that function sort will lose considerably on greater lists. Especially after an insert or removal of all one element.

...

I can probably borrow in this module beyond the framework of the project google. The demand of such type of data is interesting. Because of necessity of processing `gcmodule.c' and `obmalloc.c' this module cannot be realized as the external module.

It seems to me (after checking collectionsmodule.c and a few others) that proper C modules only seem to import Python.h and maybe structmember.h . If you are manually including gcmodule.c and obmalloc.c, you may be doing something wrong; I'll leave it to others to further comment on this aspect.

Thanks that at once has not shot me :) I was not going to work directly neither with that, nor with another. There were difficulties with translation :) When I discussed obmalloc.c, I meant its internal code. Ways of its improvement: * To adapt allocation of blocks of memory with other alignment. Now alignment is rigidly set on 8 bytes. As a variant, it is possible to use alignment on 4 bytes. And this value can be set at start of the interpreter through arguments/variable environments/etc. At testing with alignment on 4 or 8 bytes difference in speed of work was not appreciable. * To expand the maximal size which can be allocated by means of the given module. Now the maximal size is 256 bytes. * At the size of the allocated memory close to maximal, the allocation of blocks becomes inefficient. For example, for the sizes of blocks 248 and 256 (blocksize), values of quantity of elements (PAGESIZE/blocksize) it is equal 16. I.e. it would be possible to use for the sizes of the block 248 same page, as for the size of the block 256.

[Vladimir 'Yu' Stepanov]

...

* To adapt allocation of blocks of memory with other alignment. Now alignment is rigidly set on 8 bytes. As a variant, it is possible to use alignment on 4 bytes. And this value can be set at start of the interpreter through arguments/variable environments/etc. At testing with alignment on 4 or 8 bytes difference in speed of work was not appreciable.

[Martin v. Löwis]

That depends on the hardware you use, of course. Some architectures absolutely cannot stand mis-aligned accesses, and programs will just crash if they try to perform such accesses.

Note that we _had_ to add a goofy "long double" to the PyGC_Head union because some Python platform required 8-byte alignment for some types ... see rev 25454. Any spelling of malloc() also needs to return memory aligned for any legitimate purpose, and 8-byte alignment is the strictest requirement we know of across current Python platforms.

So Python should err on the safe side, and only use a smaller alignment when it is known not to hurt.

OTOH, I don't see the *advantage* in reducing the alignment.

It could cut wasted bytes. There is no per-object memory overhead in a release-build obmalloc: the allocatable part of a pool is entirely used for user-visible object memory, except when the alignment requirement ends up forcing unused (by both the user and by obmalloc) pad bytes. For example, Python ints consume 12 bytes on 32-bit boxes, but if space were allocated for them by obmalloc (it's not), obmalloc would have to use 16 bytes per int to preserve 8-byte alignment. OTOH, obmalloc (unlike PyGC_Head) has always used 8-byte alignment, because that's what worked best for Vladimir Marangozov during his extensive timing tests. It's not an isolated decision -- e.g., it's also influenced by, and influences, "the best" pool size, and (of course) cutting alignment to 4 would double the number of "size classes" obmalloc has to juggle.

...

* To expand the maximal size which can be allocated by means of the given module. Now the maximal size is 256 bytes.

Right. This is somewhat deliberate, though; the expectation is that fragmentation will increase dramatically if even larger size classes are supported.

It's entirely deliberate ;-) obmalloc is no way trying to be a general-purpose allocator. It was designed specifically for the common memory patterns in Python, aiming at large numbers of small objects of the same size. That's extremely common in Python, and allocations larger than 256 bytes are not. The maximum size was actually 64 bytes at first. After that, dicts grew an embedded 8-element table, which vastly increased the size of the dict struct. obmalloc's limit was boosted to 256 then, although it could have stopped at the size of a dict (in the rough ballpark of 150 bytes). There was no reason (then or now) to go beyond 256.

...

* At the size of the allocated memory close to maximal, the allocation of blocks becomes inefficient. For example, for the sizesof blocks 248 and 256 (blocksize), values of quantity of elements (PAGESIZE/blocksize) it is equal 16. I.e. it would be possible to use for the sizes of the block 248 same page, as for the size of the block 256.

Good idea; that shouldn't be too difficult to implement: for sizes above 215, pools need to be spaced apart only at 16 bytes.

I'd rather drop the limit to 215 then <0.3 wink>. Allocations that large probably still aren't important to obmalloc, but it is important that finding a requested allocation's "size index" be as cheap as possible. Uniformity helps that. On modern boxes, it may be desirable to boost POOL_SIZE -- nobody has run timing experiments as comprehensive as Vladimir ran way back when, and there's no particular reason to believe that the same set of tradeoffs would look best on current architectures.

Tim Peters wrote:

[Vladimir 'Yu' Stepanov]

...

...

* To adapt allocation of blocks of memory with other alignment. Now alignment is rigidly set on 8 bytes. As a variant, it is possible to use alignment on 4 bytes. And this value can be set at start of the interpreter through arguments/variable environments/etc. At testing with alignment on 4 or 8 bytes difference in speed of work was not appreciable.

[Martin v. Löwis]

...

That depends on the hardware you use, of course. Some architectures absolutely cannot stand mis-aligned accesses, and programs will just crash if they try to perform such accesses.

Note that we _had_ to add a goofy "long double" to the PyGC_Head union because some Python platform required 8-byte alignment for some types ... see rev 25454. Any spelling of malloc() also needs to return memory aligned for any legitimate purpose, and 8-byte alignment is the strictest requirement we know of across current Python platforms. It is possible to receive the reference about these tests? I have lead some tests, which very small difference of speed of work at alignment on 4 and 8 byte (a maximum of 8%, and in the basic less than one percent).

In tests consecutive search of elements in one piece of memory was used. I understand, that it is necessary to lead still the test with a casual choice of addresses to minimize optimization of work cache the processor. And certainly not all platforms will show the same result (I shall try to not forget to attach a source code of the test and its result of work :) ). On the other hand reduction of a memory size by each separate copy of object is capable to increase speed by the same percent that is lost at change of displacement about 8 bytes up to 4 :) Besides begins to refuse probably superstructures on allocation of memory at some objects, since int.

...

So Python should err on the safe side, and only use a smaller alignment when it is known not to hurt.

OTOH, I don't see the *advantage* in reducing the alignment.

It could cut wasted bytes. There is no per-object memory overhead in a release-build obmalloc: the allocatable part of a pool is entirely used for user-visible object memory, except when the alignment requirement ends up forcing unused (by both the user and by obmalloc) pad bytes. For example, Python ints consume 12 bytes on 32-bit boxes, but if space were allocated for them by obmalloc (it's not), obmalloc would have to use 16 bytes per int to preserve 8-byte alignment. Good note.

OTOH, obmalloc (unlike PyGC_Head) has always used 8-byte alignment, because that's what worked best for Vladimir Marangozov during his extensive timing tests. It's not an isolated decision -- e.g., it's also influenced by, and influences, "the best" pool size, and (of course) cutting alignment to 4 would double the number of "size classes" obmalloc has to juggle. Yes, the maximum quantity of buffers will really be doubled. But it should not to affect as that productivity of system, or on total amount of consumed memory. Change of a fragmentation of memory to count it is impossible, since it will depend on the concrete application.

...

...

* To expand the maximal size which can be allocated by means of the given module. Now the maximal size is 256 bytes.

...

Right. This is somewhat deliberate, though; the expectation is that fragmentation will increase dramatically if even larger size classes are supported.

It's entirely deliberate ;-) obmalloc is no way trying to be a general-purpose allocator. It was designed specifically for the common memory patterns in Python, aiming at large numbers of small objects of the same size. That's extremely common in Python, and allocations larger than 256 bytes are not. The maximum size was actually 64 bytes at first. After that, dicts grew an embedded 8-element table, which vastly increased the size of the dict struct. obmalloc's limit was boosted to 256 then, although it could have stopped at the size of a dict (in the rough ballpark of 150 bytes). There was no reason (then or now) to go beyond 256. See below.

...

...

* At the size of the allocated memory close to maximal, the allocation of blocks becomes inefficient. For example, for the sizesof blocks 248 and 256 (blocksize), values of quantity of elements (PAGESIZE/blocksize) it is equal 16. I.e. it would be possible to use for the sizes of the block 248 same page, as for the size of the block 256.

...

Good idea; that shouldn't be too difficult to implement: for sizes above 215, pools need to be spaced apart only at 16 bytes.

I'd rather drop the limit to 215 then <0.3 wink>. Allocations that large probably still aren't important to obmalloc, but it is important that finding a requested allocation's "size index" be as cheap as possible. Uniformity helps that. An available module on allocation of memory really does not approach for overall aims. And speed of work can "blink" in case of existing non-uniform realization on allocation of memory. In some cases allocation of memory in the module `obmalloc.c' work as function of a wrapper for standard malloc/free, that does not raise speed :) .

On modern boxes, it may be desirable to boost POOL_SIZE -- nobody has run timing experiments as comprehensive as Vladimir ran way back when, and there's no particular reason to believe that the same set of tradeoffs would look best on current architectures. As to speed of work it will be not less than in available systems of allocation of memory. Naturally, there are no pluses without what that of minuses. In my opinion available minuses can be made insignificant. Language Python has obviously expressed specificity on allocation of memory

For an example we shall assume, that two pieces of memory are allocated. One is allocated `obmalloc.c'. Another is allocated standard malloc. Both of a piece are small enough to be realized by similar methods. In a number of OS malloc will lose in speed of work for multi-thread programs, because of blocking the global lock on allocation of memory. Certainly it concerns not to all operational systems. that it is possible to use favourably, having developed system of allocation of memory is direct under it. The properties inherent in language Python: * At work in multi-thread a mode already there is blocking GIL which can be used and in case of with allocation of memory. * Objects which are often used, it is better to adapt on the real size, instead of on log2(size(ob)) therefore as function realloc is carried out extremely seldom or even less often :) . * Extremely seldom there are objects the size of the allocated memory multiple 512, 1024, 2048 since before them heading Python of object, and the parameters describing properties of object is placed still. First two items concern and to present `obmalloc.c', but for a narrow circle of allocated blocks of memory. In some interpreters own system of allocation of memory is used. Adjustment of a control system of memory not the latest step to acceleration Python. Thanks everyone who has answered. The theme on former is interesting. #include #include #include #include #include typedef union __genlink { struct { union __genlink *qcl_prev; union __genlink *qcl_next; } qcl; /* Queue of Cycle List */ void *point[2]; union __genlink *link[2]; } genlink; void qcl_init(genlink *root) { root->qcl.qcl_next = root; root->qcl.qcl_prev = root; } void qcl_insert_after(genlink *root, genlink *p) { genlink *next; p->qcl.qcl_prev = root; p->qcl.qcl_next = (next = root->qcl.qcl_next); root->qcl.qcl_next = p; next->qcl.qcl_prev = p; } #define COUNT 10000000 #define REPEAT 1000 long long rusage_print(const char *s, struct rusage *oru) { struct rusage ru; int sec; int usec; long long ret; getrusage(RUSAGE_SELF, &ru); sec = ru.ru_utime.tv_sec - oru->ru_utime.tv_sec; if ((usec = ru.ru_utime.tv_usec - oru->ru_utime.tv_usec) < 0) { sec--; usec = 1000000 + usec; } printf("%s: user time %d.%6.6d\n", s, sec, usec); fflush(stdout); ret = sec*1000000; ret += usec; return ret; } main() { genlink root; genlink *p; genlink *base; int i; int k; struct rusage ru; long long tm_normal; long long tm_align4; long long tm_align2; if ((base = malloc((COUNT + 1)*sizeof(genlink))) == NULL) { fprintf(stderr, "malloc failed\n"); exit(1); } bzero(base, (COUNT + 1)*sizeof(genlink)); getrusage(RUSAGE_SELF, &ru); bzero(base, (COUNT + 1)*sizeof(genlink)); qcl_init(&root); for (i = 0; i < COUNT; i++) { p = (genlink *)(((char *)(&base[i])) + sizeof(genlink)); // add compenstion. qcl_insert_after(&root, p); } for (k = 0, p = &root; k < REPEAT; k++) for (i = 0; i < COUNT; i++) p = p->qcl.qcl_next; tm_normal = rusage_print("align for two pointers", &ru); bzero(base, (COUNT + 1)*sizeof(genlink)); getrusage(RUSAGE_SELF, &ru); bzero(base, (COUNT + 1)*sizeof(genlink)); qcl_init(&root); for (i = 0; i < COUNT; i++) { p = (genlink *)(((char *)(&base[i])) + 4); qcl_insert_after(&root, p); } for (k = 0, p = &root; k < REPEAT; k++) for (i = 0; i < COUNT; i++) p = p->qcl.qcl_next; tm_align4 = rusage_print("align for 4 bytes", &ru); bzero(base, (COUNT + 1)*sizeof(genlink)); getrusage(RUSAGE_SELF, &ru); bzero(base, (COUNT + 1)*sizeof(genlink)); qcl_init(&root); for (i = 0; i < COUNT; i++) { p = (genlink *)(((char *)(&base[i])) + 2); qcl_insert_after(&root, p); } for (k = 0, p = &root; k < REPEAT; k++) for (i = 0; i < COUNT; i++) p = p->qcl.qcl_next; tm_align2 = rusage_print("align for 2 bytes", &ru); printf(" Normal Align4 Align2\n"); printf("Normal %8.2f %8.2f %8.2f\n", ((double)tm_normal*100)/tm_normal, ((double)tm_normal*100)/tm_align4, ((double)tm_normal*100)/tm_align2 ); printf("Align4 %8.2f %8.2f %8.2f\n", ((double)tm_align4*100)/tm_normal, ((double)tm_align4*100)/tm_align4, ((double)tm_align4*100)/tm_align2 ); printf("Align2 %8.2f %8.2f %8.2f\n", ((double)tm_align2*100)/tm_normal, ((double)tm_align2*100)/tm_align4, ((double)tm_align2*100)/tm_align2 ); } At once: fox:root!~/test > cc aligntest.c; a.out ----------------------------------------- align for two pointers: user time 42.819181 align for 4 bytes: user time 42.725775 align for 2 bytes: user time 59.198894 Normal Align4 Align2 Normal 100.00 100.22 72.33 Align4 99.78 100.00 72.17 Align2 138.25 138.56 100.00 ------------------------------------------ At second: fox:root!~/test > cc -O2 aligntest.c; a.out ------------------------------------------ align for two pointers: user time 10.152062 align for 4 bytes: user time 10.161598 align for 2 bytes: user time 10.145807 Normal Align4 Align2 Normal 100.00 99.91 100.06 Align4 100.09 100.00 100.16 Align2 99.94 99.84 100.00 ------------------------------------------ XXX:vys!~ > a.out align for two pointers: user time 0.228938 align for 4 bytes: user time 0.237644 align for 2 bytes: user time 0.235519 Normal Align4 Align2 Normal 100.00 96.34 97.21 Align4 103.80 100.00 100.90 Align2 102.87 99.11 100.00 XXX:vys!~ > a.out align for two pointers: user time 0.254978 align for 4 bytes: user time 0.236627 align for 2 bytes: user time 0.242168 Normal Align4 Align2 Normal 100.00 107.76 105.29 Align4 92.80 100.00 97.71 Align2 94.98 102.34 100.00 XXX:vys!~ >

"Vladimir 'Yu' Stepanov" wrote:

Josiah Carlson wrote:

...

However, as I just said, people usually don't remove items from just-sorted lists, they tend to iterate over them via 'for i in list:' .

Such problem arises at creation of the list of timers.

I've never seen that particular use-case. Please understand something. I believe that trees can be useful in some cases. However, I don't believe that they are generally useful enough in Python, given that we already have key,value dictionaries and sortable lists. They become even less worthwhile in Python, given the total ordering problem that I describe later in this message.

Except for that function of binary search is absent in standard package Python.

Binary search exists in the standard library as the bisect module.

Here that I have found through Google on a line " order statistic binary tree ":

http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic20/

Yes, that link does describe what an 'order statistic tree' is. One thing to note is that you can add order statistics to any tree wih one more field on each tree node. That is, you can have your AVL or Red-Black tree, and add order statistics to it. Allowing tree['x'] to return the associated value for the key 'x' (the same as a dictionary), as well as offer the ability to do tree.select(10) to get the 10th (or 11th if one counts from 0) smallest key (or key,value), or get the 'rank' of a key with tree.rank('x').

...

Of course all of this discussion about trees in Python is fine, though there is one major problem. With minimal work, one can construct 3 values such that ((a < b < c) and (c < a)) is true.

The same problem is inherent in the standard dictionary - dict (), only roots at it, it is others. For example:

This problem has nothing to do with dictionaries and hashing, it has to do with the fact that there may not be a total ordering on the elements of a sequence.

...

...

'b' < (0,) < u'a' < 'b' True x = ['b', (0,), u'a'] random.shuffle(x) x.sort() x [u'a', 'b', (0,)] random.shuffle(x) x.sort() x ['b', (0,), u'a']

What effect does this have on trees? Imagine, for a moment, that your tree looked like: (0,) / \ 'b' u'a' Then you added sufficient data so that your tree was rebalanced to be something like: u'a' / \ (0,) (stuff) / 'b' If you were searching for 'b', you would never find it, because in your search, you would compare 'b' against u'a', and take the right branch, where 'b' isn't. - Josiah

Josiah Carlson wrote:

"Vladimir 'Yu' Stepanov" wrote:

...

Josiah Carlson wrote:

...

However, as I just said, people usually don't remove items from just-sorted lists, they tend to iterate over them via 'for i in list:' .

Such problem arises at creation of the list of timers.

I've never seen that particular use-case.

Please understand something. I believe that trees can be useful in some cases. However, I don't believe that they are generally useful enough in Python, given that we already have key,value dictionaries and sortable lists. They become even less worthwhile in Python, given the total ordering problem that I describe later in this message.

I tiresome. It so :) Sorry for that.

...

Here that I have found through Google on a line " order statistic binary tree ":

http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic20/

Yes, that link does describe what an 'order statistic tree' is. One thing to note is that you can add order statistics to any tree wih one more field on each tree node. That is, you can have your AVL or Red-Black tree, and add order statistics to it. Allowing tree['x'] to return the associated value for the key 'x' (the same as a dictionary), as well as offer the ability to do tree.select(10) to get the 10th (or 11th if one counts from 0) smallest key (or key,value), or get the 'rank' of a key with tree.rank('x').

Thanks.

This problem has nothing to do with dictionaries and hashing, it has to do with the fact that there may not be a total ordering on the elements of a sequence.

It is sad. I did not know it. Therefore and have not understood. I have looked in Google on "python dev total ordering". On intentions to correct this problem I have not found anything. It already earlier was discussed ? -- Vladimir Stepanov

"Vladimir 'Yu' Stepanov" wrote:

Martin v. Löwis wrote:

...

Vladimir 'Yu' Stepanov wrote:

...

Yes. I understood it when resulted a set example.

...

However, as I just said, people usually don't remove items from just-sorted lists, they tend to iterate over them via 'for i in list:' .

Such problem arises at creation of the list of timers.

For a list of timers/timeout events, a priority queue is often the best data structure, which is already available through the heapq module.

It is in most cases valid so. heapq very much approaches for these purposes. The unique problem is connected with removal of an any element from the list.

For this particular problem, usually you don't want to say, "remove time 4.34252 from the heap", you want to say "remove the (time,event) pair given the event X, from the heap", where you have in your heap (time, event) pairs. For hashable events, you can create a class which implements enough list-like semantics to allow it to work like a heap for event timing (__getitem__, __setitem__, __len__, .pop(-1) is about it, if I remember correctly), but also allows you to remove arbitrary events (as items are shifted around in the heap, you update pointers from a dictionary). The details are a bit annoying to get right, but it is possible. - Josiah

On Sat, May 06, 2006 at 03:12:11AM -0700, Josiah Carlson wrote:

"Vladimir 'Yu' Stepanov" wrote:

...

Josiah Carlson wrote:

...

This problem has nothing to do with dictionaries and hashing, it has to do with the fact that there may not be a total ordering on the elements of a sequence.

It is sad. I did not know it. Therefore and have not understood.

I have looked in Google on "python dev total ordering". On intentions to correct this problem I have not found anything. It already earlier was discussed ?

Not really. It has to do with how non-comparable instances compare to each other. Generally speaking, when instances aren't comparable, Python compares their type, which is actually comparing the names of types. This wouldn't be a big deal, except that:

...

...

...

str < tuple < unicode True

And you can actually compare str and unicode, so, if you have a str that is greater than the unicode, you run into this issue. With unicode becoming str in Py3k, we may not run into this issue much then, unless bytes are comparable to str, in which case we end up witht the same problems.

Actually, according to my google of "python dev total ordering", it gives me...

http://mail.python.org/pipermail/python-dev/2003-March/034169.html http://mail.python.org/pipermail/python-list/2003-March/154142.html

Which were earlier discussions on this topic, which are quite topical. The ultimate solution is to choose a total ordering on types and consider the problem solved. Then list.sort() and binary trees will work properly.

Thanks for so detailed answer. Under these references discussion is conducted is presented in the form of "so is", instead of "as it to correct". Therefore I would like to mention a question "as it to correct". In case of incomparability of types can be it is meaningful compare the identifiers compared to each concrete type. More truly on them to calculate weight which will play a direct role in case of impossibility of comparison of types. Below one of variants of the decision of this problem is resulted. To each type of data in Python to add three fields: .. int tp_id; int tp_qualifier; int tp_weight; .. Rigidly to appoint some built in and external to types identifiers (tp_id). The others receive free identifiers on their initialization. Except for that types should be classified on their basic properties - tp_qualifier. The type can be classified as: 0 = None 1 = integer (bool, int, long, etc..) 2 = float (decimal, float, etc..) 3 = math (complex, matrix may be ?? ) 4 = string (str, unicode, splice, etc..) 5 = sequence (iterators, deque, xrange, enumerate, etc..) 6 = array (tuple, list, bytes, array, etc..) 7 = dictionary (dict, defdict, etc..) 8 = set (set, etc..) 9 = file (file, socket.socket, cStringIO.StringIO) .. 127 = non qualifier (sre.*, datetime.*, ClassType, IntsenceType, etc..) It is the approximate list on which it will be convenient to classify types (in my opinion). The weight can be precisely set in structure or if be equal -1 should is calculated under the formula: ob_type->tp_weight = (ob_type->tp_qualifier<<24) + (ob_type->tp_id<<8) Thus objects with similar properties will follow one after another. A problem can make external types. But if to develop further classification, problems to arise should not. -- SY. Vladimir Stepanov

On 5/6/06, Vladimir Yu. Stepanov wrote: [proposing a total ordering between types] It Ain't Gonna Happen. (From now on, I'll write this as IAGH.) In Python 3000, we'll actually *remove* ordering between arbitrary types as a feature; only types that explicitly care to be ordered with respect to one another will be ordered. Equality tests are unaffected, x==y will simply return False if x and y are of incomparable types; but xhttp://www.python.org/~guido/)

Josiah Carlson wrote:

And you can actually compare str and unicode, so, if you have a str that is greater than the unicode, you run into this issue. With unicode becoming str in Py3k, we may not run into this issue much then, unless bytes are comparable to str, in which case we end up witht the same problems.

Actually, according to my google of "python dev total ordering", it gives me...

http://mail.python.org/pipermail/python-dev/2003-March/034169.html http://mail.python.org/pipermail/python-list/2003-March/154142.html

Which were earlier discussions on this topic, which are quite topical. The ultimate solution is to choose a total ordering on types and consider the problem solved. Then list.sort(

Under the second reference there was a question. complex it can be partially comparable with int, long, float? In fact 1 == 1+0j?

Guido van Rossum wrote:

On 5/11/06, Vladimir 'Yu' Stepanov wrote:

...

If for Python-3000 similar it will be shown concerning types str(), int(), complex() and so on, and the type of exceptions will strongly vary, it will make problematic redefinition of behavior of function of sorting.

Not really. We'll just document that sort() should only be used on a list of objects that implement a total ordering. [...]

It might be useful in some cases to have a keyword argument to sort/sorted that says to ignore exceptions arising from comparing elements, and leaves the ordering of non-comparable values undefined. -Edward

On 5/11/06, Vladimir 'Yu' Stepanov wrote:

If for Python-3000 similar it will be shown concerning types str(), int(), complex() and so on, and the type of exceptions will strongly vary, it will make problematic redefinition of behavior of function of sorting.

I don't see what you mean by "redefinition of behavior of function of sorting". Is this something a Python programmer might want to do? Can you give an example? On 5/16/06, Vladimir 'Yu' Stepanov wrote:

It will be possible it conveniently to use as exception of management by a stream, for indication of necessity to involve `.__r(eq|ne|le|lt|ge|gt|cmp)__()' a method. This kind of a class can carry out function, similarly to StopIteration for `.next()'.

There are no .__r(eq|ne|le|lt|ge|gt|cmp)__() methods, for a logical reason which you might enjoy deducing yourself...

At present time similar function is carried out with exception NotImplemented. This exception is generated in a number of mathematical operations. For this reason I ask to consider an opportunity of creation of a new class.

Can you explain this? NotImplemented isn't an exception. (NotImplementedError is, but that's something quite different.) NotImplemented has exactly one purpose in Python, as far as I can tell. What mathematical operations do you mean? -j

Vladimir, Your examples seem to indicate that you've misunderstood the change that's proposed for Python 3000. Especially this: On 5/17/06, Vladimir 'Yu' Stepanov wrote:

# BEGIN: Emulation python3000 if type(a) is not type(b) and ( not operator.isNumberType(a) or not operator.isNumberType(b) ): raise TypeError("python3000: not-comparable types", (a,b)) # END: Emulation python3000

Python 3000 will not do anything like this. It'll try a.__cmp__(b), and failing that b.__cmp__(a) (but imagine this using tp_ slots instead of actual Python method calls), and if both return NotImplemented, it'll throw a TypeError (rather than guess, which is what it does now). There's a lot of legacy oddness in PyObject_RichCompare() and its many helper functions; presumably they'll delete some of that, but it won't be anything you care about. Comparison with None should also continue to work as it does now, unless I missed something. -j