Mailman 3 August 1999 - Python-Dev

Re: why
by Greg Stein 15 Aug '99

15 Aug '99

David Ascher wrote: > > Why does buffer(array('c', 'test')) return a read-only buffer? Simply because the buffer() builtin always creates a read-only object, rather than selecting read/write when possible. Shouldn't be hard to alter the semantics of buffer() to do so. Maybe do this at the same time as updating it to create read/write buffers out of the blue. Cheers, -g -- Greg Stein, http://www.lyra.org/

1 0

RE: [Python-Dev] shrinking dicts
by Tim Peters 12 Aug '99

12 Aug '99

[Vladimir Marangozov, *almost* seems ready to give up on a counter- productive dict pessimization <wink>] > ... > There is, however, a small percentage of dicts which are used > below 1/3 of their size. I must say, below 1/3 of their peek size, > because dowsizing is also rare. To trigger a downsize, 1/3 new > entries of the peek size must be inserted. Not so, although "on average" 1/6 may be correct. Look at an extreme: Say a dict has size 333 (it can't, but it makes the math obvious ...). Say it contains 221 items. Now someone deletes them all, one at a time. used==0 and fill==221 at this point. They insert one new key that happens to hit one of the 333-221 = 112 remaining NULL keys. Then used==1 and fill==222. They insert a 2nd key, and before the dict is searched the new fill of 222 triggers the 2/3rds load-factor resizing -- which asks for a new size of 1*2 == 2. For the minority of dicts that go up and down in size wildly many times, the current behavior is fine. > Besides these observations, after looking at the code one more > time, I can't really understand why the resize logic is based on > the "fill" watermark and not on "used". fill = used + dummy, but > since lookdict returns the first free slot (null or dummy), I don't > really see what's the point of using a fill watermark... Let's just consider an unsuccessful search. Then it does return "the first" free slot, but not necessarily at the time it *sees* the first free slot. So long as it sees a dummy, it has to keep searching; the search doesn't end until it finds a NULL. So consider this, assuming the resize triggered only on "used": d = {} for i in xrange(50000): d[random.randrange(1000000)] = 1 for k in d.keys(): del d[k] # now there are 50000 dummy dict keys, and some number of NULLs # loop invariant: used == 0 for i in xrange(sys.maxint): j = random.randrange(10000000) d[j] = 1 del d[j] assert not d.has_key(i) However many NULL slots remained, the last loop eventually transforms them *all* into dummies. The dummies act exactly like "real keys" with respect to expected time for an unsuccessful search, which is why it's thoroughly appropriate to include dummies in the load factor computation. The loop will run slower and slower as the percentage of dummies approaches 100%, and each failing has_key approaches O(N) time. In most hash table implementations that's the worst that can happen (and it's a disaster), but under Python's implementation it's worse: Python never checks to see whether the probe sequence "wraps around", so the first search after the last NULL is changed to a dummy never ends. Counting the dummies in the load-factor computation prevents all that: no matter how much inserts and deletes are intermixed, the "effective load factor" stays under 2/3rds so gives excellent expected-case behavior; and it also protects against an all-dummy dict, making the lack of an expensive inner-loop "wrapped around?" check safe. > Perhaps you can enlighten me on this. Using only the "used" metrics > seems fine to me. I even deactivated "fill" and replaced it with "used" > to see what happens -- no visible changes, except a tiny speedup I'm > willing to neglect. You need a mix of deletes and inserts for the dummies to make a difference; dicts that always grow don't have dummies, so they're not likely to have any dummy-related problems either <wink>. Try this (untested): import time from random import randrange N = 1000 thatmany = [None] * N while 1: start = time.clock() for i in thatmany: d[randrange(10000000)] = 1 for i in d.keys(): del d[i] finish = time.clock() print round(finish - start, 3) Succeeding iterations of the outer loop should grow dramatically slower, and finally get into an infinite loop, despite that "used" never exceeds N. Short course rewording: for purposes of predicting expected search time, a dummy is the same as a live key, because finding a dummy doesn't end a search -- it has to press on until either finding the key it was looking for, or finding a NULL. And with a mix of insertions and deletions, and if the hash function is doing a good job, then over time all the slots in the table will become either live or dummy, even if "used" stays within a very small range. So, that's why <wink>. dictobject-may-be-the-subtlest-object-there-is-ly y'rs - tim

1 0

Re: [Python-Dev] about line numbers
by Jack Jansen 12 Aug '99

12 Aug '99

The only possible problem I can see with folding linenumbers is if someone sets a breakpoint on such a line. And I think it'll be difficult to explain the missing line numbers to pdb, so there isn't an easy workaround (at least, it takes more than my 30 seconds of brainpoewr to come up with one:-). -- Jack Jansen | ++++ stop the execution of Mumia Abu-Jamal ++++ Jack.Jansen(a)oratrix.com | ++++ if you agree copy these lines to your sig ++++ www.oratrix.nl/~jack | see http://www.xs4all.nl/~tank/spg-l/sigaction.htm

2 1

shrinking dicts
by Vladimir Marangozov 12 Aug '99

12 Aug '99

Currently, dictionaries always grow until they are deallocated from memory. This happens in PyDict_SetItem according to the following code (before inserting the new item into the dict): /* if fill >= 2/3 size, double in size */ if (mp->ma_fill*3 >= mp->ma_size*2) { if (dictresize(mp, mp->ma_used*2) != 0) { if (mp->ma_fill+1 > mp->ma_size) return -1; } } The symmetric case is missing and this has intrigued me for a long time, but I've never had the courage to look deeply into this portion of code and try to propose a solution. Which is: reduce the size of the dict by half when the nb of used items <= 1/6 the size. This situation occurs far less frequently than dict growing, but anyways, it seems useful for the degenerate cases where a dict has a peek usage, then most of the items are deleted. This is usually the case for global dicts holding dynamic object collections, etc. A bonus effect of shrinking big dicts with deleted items is that the lookup speed may be improved, because of the cleaned <dummy> entries and the reduced overall size (resulting in a better hit ratio). The (only) solution I could came with for this pb is the appended patch. It is not immediately obvious, but in practice, it seems to work fine. (inserting a print statement after the condition, showing the dict size and current usage helps in monitoring what's going on). Any other ideas on how to deal with this? Thoughts, comments? -- Vladimir MARANGOZOV | Vladimir.Marangozov(a)inrialpes.fr http://sirac.inrialpes.fr/~marangoz | tel:(+33-4)76615277 fax:76615252 -------------------------------[ cut here ]--------------------------- *** dictobject.c-1.5.2 Fri Aug 6 18:51:02 1999 --- dictobject.c Tue Aug 10 12:21:15 1999 *************** *** 417,423 **** ep->me_value = NULL; mp->ma_used--; Py_DECREF(old_value); ! Py_DECREF(old_key); return 0; } --- 417,430 ---- ep->me_value = NULL; mp->ma_used--; Py_DECREF(old_value); ! Py_DECREF(old_key); ! /* For bigger dictionaries, if used <= 1/6 size, half the size */ ! if (mp->ma_size > MINSIZE*4 && mp->ma_used*6 <= mp->ma_size) { ! if (dictresize(mp, mp->ma_used*2) != 0) { ! if (mp->ma_fill > mp->ma_size) ! return -1; ! } ! } return 0; }

4 9

preferred conference date?
by Guido van Rossum 11 Aug '99

11 Aug '99

I need your input about the date of the next Python conference. Foretec is close to a deal for a Python conference in January 2000 at the Alexandria Old Town Hilton hotel. Given our requirement of a good location in the DC area, this is a very good deal (it's a brand new hotel). The prices are high (they tell me that the whole conference will cost $900, with a room rate of $129) but it's a class A location (metro, tons of restaurants, close to National Airport, etc.) and we have found no cheaper DC hotel suitable for our purposes (even in drab suburban locations). I'm worried that I'll be flamed to hell for this by the PSA members, but I don't think we can get the price any lower without starting all over in a different location, probably causing several months of delay. If people won't come, Foretec (and I) will have learned a valuable lesson and we'll rethink the issue for the 2001 conference. Anyway, given that Foretec is likely to go with this hotel, we have a choice of two dates: January 16-19, or 23-26 (both starting on a Sunday with the tutorials). This is where I need your help: which date would you prefer? Please mail me personally. --Guido van Rossum (home page: http://www.python.org/~guido/)

3 3

Some more constants for the socket module
by M.-A. Lemburg 09 Aug '99

09 Aug '99

Following the recent discussion on c.l.p about socket options, I found that the socket module does not define all constants defined in the (Linux) socket header file. Below is a patch that adds a few more (note that the SOL_* constants should be used for the setsockopt() level, not the IPPROTO_* constants). --- socketmodule.c~ Sat Aug 7 17:56:05 1999 +++ socketmodule.c Sat Aug 7 18:10:07 1999 @@ -2005,14 +2005,48 @@ initsocket() PySocketSock_Type.tp_doc = sockettype_doc; Py_INCREF(&PySocketSock_Type); if (PyDict_SetItemString(d, "SocketType", (PyObject *)&PySocketSock_Type) != 0) return; + + /* Address families (we only support AF_INET and AF_UNIX) */ +#ifdef AF_UNSPEC + insint(moddict, "AF_UNSPEC", AF_UNSPEC); +#endif insint(d, "AF_INET", AF_INET); #ifdef AF_UNIX insint(d, "AF_UNIX", AF_UNIX); #endif /* AF_UNIX */ +#ifdef AF_AX25 + insint(moddict, "AF_AX25", AF_AX25); /* Amateur Radio AX.25 */ +#endif +#ifdef AF_IPX + insint(moddict, "AF_IPX", AF_IPX); /* Novell IPX */ +#endif +#ifdef AF_APPLETALK + insint(moddict, "AF_APPLETALK", AF_APPLETALK); /* Appletalk DDP */ +#endif +#ifdef AF_NETROM + insint(moddict, "AF_NETROM", AF_NETROM); /* Amateur radio NetROM */ +#endif +#ifdef AF_BRIDGE + insint(moddict, "AF_BRIDGE", AF_BRIDGE); /* Multiprotocol bridge */ +#endif +#ifdef AF_AAL5 + insint(moddict, "AF_AAL5", AF_AAL5); /* Reserved for Werner's ATM */ +#endif +#ifdef AF_X25 + insint(moddict, "AF_X25", AF_X25); /* Reserved for X.25 project */ +#endif +#ifdef AF_INET6 + insint(moddict, "AF_INET6", AF_INET6); /* IP version 6 */ +#endif +#ifdef AF_ROSE + insint(moddict, "AF_ROSE", AF_ROSE); /* Amateur Radio X.25 PLP */ +#endif + + /* Socket types */ insint(d, "SOCK_STREAM", SOCK_STREAM); insint(d, "SOCK_DGRAM", SOCK_DGRAM); #ifndef __BEOS__ /* We have incomplete socket support. */ insint(d, "SOCK_RAW", SOCK_RAW); @@ -2048,11 +2082,10 @@ initsocket() insint(d, "SO_OOBINLINE", SO_OOBINLINE); #endif #ifdef SO_REUSEPORT insint(d, "SO_REUSEPORT", SO_REUSEPORT); #endif - #ifdef SO_SNDBUF insint(d, "SO_SNDBUF", SO_SNDBUF); #endif #ifdef SO_RCVBUF insint(d, "SO_RCVBUF", SO_RCVBUF); @@ -2111,14 +2144,43 @@ initsocket() #ifdef MSG_ETAG insint(d, "MSG_ETAG", MSG_ETAG); #endif /* Protocol level and numbers, usable for [gs]etsockopt */ -/* Sigh -- some systems (e.g. Linux) use enums for these. */ #ifdef SOL_SOCKET insint(d, "SOL_SOCKET", SOL_SOCKET); #endif +#ifdef SOL_IP + insint(moddict, "SOL_IP", SOL_IP); +#else + insint(moddict, "SOL_IP", 0); +#endif +#ifdef SOL_IPX + insint(moddict, "SOL_IPX", SOL_IPX); +#endif +#ifdef SOL_AX25 + insint(moddict, "SOL_AX25", SOL_AX25); +#endif +#ifdef SOL_ATALK + insint(moddict, "SOL_ATALK", SOL_ATALK); +#endif +#ifdef SOL_NETROM + insint(moddict, "SOL_NETROM", SOL_NETROM); +#endif +#ifdef SOL_ROSE + insint(moddict, "SOL_ROSE", SOL_ROSE); +#endif +#ifdef SOL_TCP + insint(moddict, "SOL_TCP", SOL_TCP); +#else + insint(moddict, "SOL_TCP", 6); +#endif +#ifdef SOL_UDP + insint(moddict, "SOL_UDP", SOL_UDP); +#else + insint(moddict, "SOL_UDP", 17); +#endif #ifdef IPPROTO_IP insint(d, "IPPROTO_IP", IPPROTO_IP); #else insint(d, "IPPROTO_IP", 0); #endif @@ -2266,10 +2328,32 @@ initsocket() #ifdef IP_ADD_MEMBERSHIP insint(d, "IP_ADD_MEMBERSHIP", IP_ADD_MEMBERSHIP); #endif #ifdef IP_DROP_MEMBERSHIP insint(d, "IP_DROP_MEMBERSHIP", IP_DROP_MEMBERSHIP); +#endif +#ifdef IP_DEFAULT_MULTICAST_TTL + insint(moddict, "IP_DEFAULT_MULTICAST_TTL", IP_DEFAULT_MULTICAST_TTL); +#endif +#ifdef IP_DEFAULT_MULTICAST_LOOP + insint(moddict, "IP_DEFAULT_MULTICAST_LOOP", IP_DEFAULT_MULTICAST_LOOP); +#endif +#ifdef IP_MAX_MEMBERSHIPS + insint(moddict, "IP_MAX_MEMBERSHIPS", IP_MAX_MEMBERSHIPS); +#endif + + /* TCP options */ +#ifdef TCP_NODELAY + insint(moddict, "TCP_NODELAY", TCP_NODELAY); +#endif +#ifdef TCP_MAXSEG + insint(moddict, "TCP_MAXSEG", TCP_MAXSEG); +#endif + + /* IPX options */ +#ifdef IPX_TYPE + insint(moddict, "IPX_TYPE", IPX_TYPE); #endif /* Initialize gethostbyname lock */ #ifdef USE_GETHOSTBYNAME_LOCK gethostbyname_lock = PyThread_allocate_lock(); -- Marc-Andre Lemburg ______________________________________________________________________ Y2000: 146 days left Business: http://www.lemburg.com/ Python Pages: http://www.lemburg.com/python/

2 2

Re: [Python-Dev] marshal (was:Buffer interface in abstract.c? )
by Jack Jansen 09 Aug '99

09 Aug '99

> Aside: wouldn't it make sense to move from marshal to pickle and > depreciate marshal altogether ? cPickle is quite fast and much more > flexible than marshal, plus it already provides mechanisms for > registering new types. This is probably the best idea so far. Just remove the buffer-workaround in marshall, keep it functioning for the things it is used for now (like pyc files) and refer people to (c)Pickle for new development. -- Jack Jansen | ++++ stop the execution of Mumia Abu-Jamal ++++ Jack.Jansen(a)oratrix.com | ++++ if you agree copy these lines to your sig ++++ www.oratrix.nl/~jack | see http://www.xs4all.nl/~tank/spg-l/sigaction.htm

1 0

Re: [Python-Dev] marshal (was:Buffer interface in abstract.c? )
by Jack Jansen 09 Aug '99

09 Aug '99

Recently, Greg Stein <gstein(a)lyra.org> said: > I would suggest backing out the marshalling of buffer-interface objects > and adding a mechanism for arbitrary type objects to marshal themselves. > Without the second part, arrays and Unicode objects aren't marshallable > at all (seems bad). This sounds like the right approach. It would require 2 slots in the tp_ structure and a little extra glue for the typecodes (currently marshall knows all the 1-letter typecodes for all objecttypes it can handle, but types marshalling their own objects would require a centralized registry of object types. For the time being it would probably suffice to have the mapping of type<->letter be hardcoded in marshal.h, but eventually you probably want a more extensible scheme, where Joe R. Extension-Writer could add a marshaller to his objects and know it won't collide with someone else's. -- Jack Jansen | ++++ stop the execution of Mumia Abu-Jamal ++++ Jack.Jansen(a)oratrix.com | ++++ if you agree copy these lines to your sig ++++ www.oratrix.nl/~jack | see http://www.xs4all.nl/~tank/spg-l/sigaction.htm

2 1

mmapfile module
by Andrew M. Kuchling 06 Aug '99

06 Aug '99

A while back the suggestion was made that the mmapfile module be added to the core distribution, and there was a guardedly positive reaction. Should I go ahead and do that? No one reported any problems when I asked for bug reports, but that was probably because no one tried it; putting it in the core would cause more people to try it. I suppose this leads to a more important question: at what point should we start checking 1.6-only things into the CVS tree? For example, once the current alphas of the re module are up to it (they're not yet), when should they be checked in? -- A.M. Kuchling http://starship.python.net/crew/amk/ Kids! Bringing about Armageddon can be dangerous. Do not attempt it in your home. -- Terry Pratchett & Neil Gaiman, _Good Omens_

5 4

Re: [Python-Dev] Buffer interface in abstract.c?
by Jack Jansen 05 Aug '99

05 Aug '99

Why not pass the index to the As*Buffer routines as well and make getsegcount available too? Then you could code things like for(i=0; i<PyObject_GetBufferCount(obj); i++) { if ( PyObject_AsCharBuffer(obj, &buf, &count, i) < 0 ) return -1; write(fp, buf, count); } -- Jack Jansen | ++++ stop the execution of Mumia Abu-Jamal ++++ Jack.Jansen(a)oratrix.com | ++++ if you agree copy these lines to your sig ++++ www.oratrix.nl/~jack | see http://www.xs4all.nl/~tank/spg-l/sigaction.htm

5 4