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/archive%40mail-archive.com
