Martin v. Löwis wrote:

"Brett C." writes:

...

So, anyone have any ideas? The best one that I can think of is optional type-checking. I am fairly open to ideas, though, in almost any area involving language design.

Did you explicitly mean language *design*?

Design/implementation. Basically something involving how a language either works or is created.

Because there might be areas of research relevant to language implementation, in terms of efficiency, portability, etc.

Here are some suggestions: - memory management: attempt to replace reference counting by "true" garbage collection

Maybe. Kind of happy with the way things work now, though. =)

- threading: attempt to provide free threading efficiently

Wow, that would be a challenge, to say the least. Might be too much for just a masters thesis.

- typing: attempt to provide run-time or static type inference, and see whether this could be used to implement some byte codes more efficiently (although there is probably overlap with the specializing compilers)

I was actually thinking of type-inference since I am planning on learning (or at least starting to learn) Standard ML next month.

- floating point: provide IEEE-794 (or some such) in a portable yet efficient way

You mean like how we have longs? So code up in C our own way of storing 794 independent of the CPU?

- persistency: provide a mechanism to save the interpreter state to disk, with the possibility to restart it later (similar to Smalltalk images)

Hmm. Interesting. Could be the start of continuations.

On language design, I don't have that many suggestions, as I think the language itself should evolve slowly if at all: - deterministic finalization: provide a way to get objects destroyed implicitly at certain points in control flow; a use case would be thread-safety/critical regions

I think you get what you mean by this, but I am not totally sure since I can't come up with a use beyond threads killing themselves properly when the whole program is shutting down.

- attributes: provide syntax to put arbitrary annotations to functions, classes, and class members, similar to .NET attributes. Use that facility to implement static and class methods, synchronized methods, final methods, web methods, transactional methods, etc (yes, there is a proposal, but nobody knows whether it meets all requirements - nobody knows what the requirements are)

Have no clue what this is since I don't know C#. Almost sounds like Michael's def func() [] proposal at the method level. Or just a lot of descriptors. =) Time to do some Googling.

- interfaces (this may go along with optional static typing)

Yeah, but that is Alex's baby. Thanks for the suggestions, Martin. -Brett

Martin v. Löwis wrote:

Brett C. wrote:

...

...

- floating point: provide IEEE-794 (or some such) in a portable yet efficient way

You mean like how we have longs? So code up in C our own way of storing 794 independent of the CPU?

Not longs, but floats. And you would not attempt to store it independent of the CPU, but instead, you would make as much use of the CPU as possible, and only implement things in C that the CPU gets wrong. The portion of emulation would vary from CPU to CPU.

OK, so in other words play cleanup for how the CPU handles floating point by having custom code that deals with its mix-ups.

As a starting point, you might look at the Java strictfpu mode (which got only added after the initial Java release). Java 1.0 was where Python is today: expose whatever the platform provides. In Java, they have the much stronger desire to provide bit-for-bit reproducability on all systems, so they added strictfpu as a trade-off of performance vs. write-once-run-anywhere.

Remembrances of Tim mentioning FPU exceptions start to flood back into my mind. =)

...

...

- deterministic finalization: provide a way to get objects destroyed implicitly at certain points in control flow; a use case would be thread-safety/critical regions

I think you get what you mean by this, but I am not totally sure since I can't come up with a use beyond threads killing themselves properly when the whole program is shutting down.

Not at all. In Python, you currently do

def bump_counter(self): self.mutex.acquire() try: self.counter = self.counter+1 more_actions() finally: self.mutex.release()

In C++, you do

void bump_counter(){ MutexAcquistion acquire(this); this->counter+=1; more_actions(); }

I.e. you can acquire the mutex at the beginning (as a local object), and it gets destroyed automatically at the end of the function. So they have the "resource acquisition is construction, resource release is destruction" design pattern. This is very powerful and convenient, and works almost in CPython, but not in Python - as there is no uarantee when objects get destroyed.

Ah, OK.

...

Have no clue what this is since I don't know C#. Almost sounds like Michael's def func() [] proposal at the method level. Or just a lot of descriptors. =)

Yes, the func()[] proposal might do most of it. However, I'm uncertain whether it puts in place all pieces of the puzzle - one would actually have to try to use that stuff to see whether it really works sufficiently. You would have to set goals first (what is it supposed to do), and then investigate, whether these things can actually be done with it. As I said: static, class, synchronized, final methods might all be candidates; perhaps along with some of the .NET features, like security evidence check (caller must have permission to write files in order to call this method), webmethod (method is automagically exposed as a SOAP/XML-RPC method), etc.

I remember that static and classmethod were reasons cited why the func()[] proposal was desired. It's an idea. -Brett

Holger Krekel wrote:

Hi Brett,

Brett C. wrote:

...

Today I got the wheels turning on my masters thesis by getting an adviser. Now I just need a topic. =) The big goal is to do something involving Python for a thesis to be finished by fall of next year (about October) so as to have it done, hopefully published (getting into LL4 would be cool), and ready to be used for doctoral applications come January 2005.

So, anyone have any ideas? The best one that I can think of is optional type-checking. I am fairly open to ideas, though, in almost any area involving language design.

Maybe you have heard of PyPy, a reimplementation of Python in Python. We are employing quite some innovative approaches to language design and implementation and there are certainly a lot of open research areas. See our OSCON 2003 paper

http://codespeak.net/pypy/index.cgi?doc/oscon2003-paper.html

Read a while back. I keep an eye on PyPy from a distance by reading the stuff you guys put out.

or two interesting chapters out of our European Union proposal

http://codespeak.net/pypy/index.cgi?doc/funding/B1.0 http://codespeak.net/pypy/index.cgi?doc/funding/B6.0

I will have a read.

You are welcome to discuss stuff on e.g. the IRC channel #pypy on freenode

Nuts. Guess I can't keep my use of IRC down to PyCon discussions. =)

or on the mailing list

http://codespeak.net/mailman/listinfo/pypy-dev

in order to find out, if you'd like to join us and/or do some interesting thesis.

Will do. Thanks, Holger. -Brett

Hi Brett, I don't know how interested you are in scientific computing. But Pat Miller from Lawrence Livermore Lab (http://www.llnl.gov/CASC/people/pmiller/) presented at SciPy'03 some very interesting stuff for on-the-fly compilation of python code into C for numerical work. None of this has been publically released yet, but if that kind of thing sounds interesting to you, you might want to contact him. Just an idea. Best, f

On Wed, Oct 29, 2003 at 05:28:13PM -0800, Brett C. wrote:

Neil Schemenauer wrote:

...

* Finish of the AST compiler.

I actually wanted to originally do that, but there is no real research involved; its just coding at this point, right?

Right. It's a prerequite to doing real research. See Jeremy's web log. If you don't want to finish the AST compiler you could just use the Python implementation. It would be slow but good enough for testing ideas.

Huh, cool. Just looked at Dylan quickly.

The reference manual is a good reading: http://www.gwydiondylan.org/drm/drm_1.htm Some of the parts I like are the builtin classes (numbers and sealing especially) and the collection protocols. The module and library system is also interesting (although overkill for many programs).

...

* Look at making the GC mark-and-sweep.

I don't know if it is worth it, although having so far two people suggest changing the GC to something else is interesting.

Implementating yet a another M&S GC is not research, IMHO. What _would_ be interesting is comparing the performance of reference counting and a mark and sweep collector. CPU, cache and memory speeds have changed quite dramatically. Also, comparing how easily the runtime can be integrated with the rest of the world (e.g. C libraries) would also be valuable. That said, I'm not sure it's worth it either. I find the Chicken GC more interesting and would look into that further if I had the time. Neil

On Thursday 30 October 2003 06:39 am, Brett C. wrote: ...

...

...

Huh, cool. Just looked at Dylan quickly. ... So many languages to learn! Happen to have a book recommendation?

Besides the reference manual, which is also available as a book, there's a good book called "Dylan Programming", Addison-Wesley, Feinberg et al. There's a firm somewhat misleadingly called something like "functional programming" (misleadingly because Dylan's not a FP language...) which focuses on Dylan and used to have both books (reference and Feinberg) in stock and available for decently discounted prices, too. Alex

At 17:28 29.10.2003 -0800, Brett C. wrote:

...

* Implement an object system that supports multiple dispatch. You can look at Dylan and Goo for ideas.

Huh, cool. Just looked at Dylan quickly.

some bits on this: implementing one is probably not too hard apart from optimization but possible/relevant directions are also then - integration with the preexisting Python semantics - reflection. All of CLOS, Dylan, and Goo come with a rather low-level flavor of reflection, in contrast Python has a rather natural one. Once you have mmd what kind of idioms using reflection you can think of, how to best offer/package reflection for the language user? - multi methods cover some ground also coverd by interfaces and adaptation: *) a generic function/multi method is also an interface *) some of the things you can achieve with adaptation can be done with multi methods Once you have multimethods do you still need adaptation in some cases or, could one obtain the functionality otherwise or do you need dispatch on interfaces (not just classes), how would then interfaces look like and the dispatch on them? (Cecil type system and predicate dispatch would be thing to look at for example) Samuele

At 06:33 PM 10/29/03 +0000, Michael Hudson wrote:

"Phillip J. Eby" writes:

...

* Direct use of positional arguments on the stack as the "locals" of the next function called, without creating (and then unpacking) an argument tuple, in the case where there are no */** arguments provided by the caller.

Already done, unless I misunderstand your idea. Well, the arguments might still get copied into the new frame's locals area but I'm pretty sure no tuple is involved.

Hm. I thought that particular optimization only could take place when the function lacks default arguments. But maybe I've misread that part. If it's true in all cases, then argument tuple creation isn't where the overhead is coming from. Anyway... it wouldn't be a good thesis idea if the answer were as obvious as my speculations, would it? ;)

On Thursday, Oct 30, 2003, at 05:24 Europe/Stockholm, Jeremy Hylton wrote: [function calls]

There is an optimization that depends on having no default arguments (or keyword arguments or free variables).

Why does it depend on not having default arguments? If you supply the right number of arguments (something that's obviously already checked) why does the function having defaults make a jot of difference?

It copies the arguments directly from the caller's frame into the callee's frame without creating an argument tuple.

It's interesting to avoid the copy from caller to callee, but I don't think it's a big cost relative to everything else we're doing to set up a frame for calling. (I expect the number of arguments is usually small.) You would need some way to encode what variables are loaded from the caller stack and what variables are loaded from the current frame. Either a different opcode or some kind of flag in the current LOAD/STORE argument.

As I think Phillip managed to convince himself recently, some kind of JIT functionality seems to be needed to do function calls really efficiently. I wonder if libffi does enough... it would be nice if the body of CALL_FUNCTION could look a bit like this: x = POP() PUSH(((some_cast_or_other)x)(f, stack_pointer, oparg)) Gah, this doesn't really seem to work out, on thinking about it. Wins seem more likely to come from knowing with some certainly at the call site that you've not messed the arguments up (and so we're back to wanting a JIT, it seems to me).

One other possibility for optimization is this XXX comment in fast_function(): /* XXX Perhaps we should create a specialized PyFrame_New() that doesn't take locals, but does take builtins without sanity checking them. */ f = PyFrame_New(tstate, co, globals, NULL);

PyFrame_New() does a fair amount of work that is unnecessary in the common case.

Fair amount? I have a patch that gets ~1.5% on pystone along these lines, but it's a bit scary (makes a "lightweight-frame" subclass that assumes more about things on it's freelist, and so on). I'm not sure the modest gains are worth the complexity, but I'll post it to SF... Cheers, mwh

Dennis Allison wrote:

Brett --

You might put together a list of all the ideas (maybe even a ranked list) and post it as a unit to the list for archival purposes. Thanks.

Way ahead of you, Dennis. I have already started to come up with a reST doc for writing up all of these suggestions. It just might be a little while before I get it up since I will need to do some preliminary research on each idea to measure the amount of work they will be. -Brett

Michael Hudson wrote:

"Brett C." writes:

...

Dennis Allison wrote:

...

Brett -- You might put together a list of all the ideas (maybe even a ranked list) and post it as a unit to the list for archival purposes. Thanks.

Way ahead of you, Dennis. I have already started to come up with a reST doc for writing up all of these suggestions. It just might be a little while before I get it up since I will need to do some preliminary research on each idea to measure the amount of work they will be.

Could go on the Python Wiki?

Could. Let me get it done in reST locally, then I can look at adding it to the wiki.

I take it from your posting of last week that you've thought about other ways of implementing exception handling? I guess a non-reference count based GC is a prerequisite for that...

Yeah, I have tossed the exception handling idea around in my head a little, but the culmination was what I posted. And a non-refcount GC would definitely help, even if the exception handling wasn't changed. More places where you could just return NULL instead of having to deal with DECREFing objects. -Brett

At 11:42 AM 10/31/03 +0000, Michael Hudson wrote:

"Brett C." writes:

...

...

I take it from your posting of last week that you've thought about other ways of implementing exception handling? I guess a non-reference count based GC is a prerequisite for that...

Yeah, I have tossed the exception handling idea around in my head a little, but the culmination was what I posted.

And a non-refcount GC would definitely help, even if the exception handling wasn't changed. More places where you could just return NULL instead of having to deal with DECREFing objects.

And reducing the memory overhead of objects.

OTOH, maybe you could see whether INCREF/DECREF can be used to control synchronization of objects between threads, and thus get a multiprocessor Python. Note that if an object's refcount is 1, it's not being shared between threads. INCREF could be looked at as, "I'm about to use this object", so if the object isn't "owned" by the current thread, then lock it and increment an ownership count. Or was that how the experimental free-threading Python worked?

Here's my crazy idea that's been knocking around my head for a while. I wonder if anyone can shoot in down in flames.

Remove the ob_type field from all PyObjects. Make pymalloc mandatory, make it use type specific pools and store a pointer to the type object at the start of each pool.

How would you get from the pointer to the pool head?

At 02:10 PM 10/31/03 +0000, Michael Hudson wrote:

"Phillip J. Eby" writes:

...

...

Here's my crazy idea that's been knocking around my head for a while. I wonder if anyone can shoot in down in flames.

Remove the ob_type field from all PyObjects. Make pymalloc mandatory, make it use type specific pools and store a pointer to the type object at the start of each pool.

How would you get from the pointer to the pool head?

Did you read the rest of my mail? Maybe I was too terse, but my

Yes, and yes. :)

thinking was that the pools are aligned on a known size boundary (e.g. 4K) so to get to the head you just mask off the 12 (or whatever) least significant bits.

Ah. But since even the most trivial of Python operations require access to the type, wouldn't this take longer? I mean, for every ob->ob_type->tp_whatever you'll now have something like *(ob & mask)->tp_whatever. So there are still two memory acesses, but now there's a bitmasking operation added in. I suppose that for some object types you could be getting a 12-25% decrease in memory use for the base object, though.

Hello Michael, On Fri, Oct 31, 2003 at 05:08:36PM +0000, Michael Hudson wrote:

...

be getting a 12-25% decrease in memory use for the base object, though.

More than that in the good cases. Something I forgot was that you'd probably have to knock variable length types on the head.

Why? Armin

Hello Martin, On Sun, Nov 02, 2003 at 08:05:55PM +0100, Martin v. L?wis wrote:

...

...

More than that in the good cases. Something I forgot was that you'd probably have to knock variable length types on the head.

Why?

Assuming "to knock on the head" means "to put an end to":

If you put all objects of the same type into a pool, you really want all objects to have the same side, inside a pool. With that assumption, garbage objects can be reallocated without causing fragmentation. If objects in a pool have different sizes, it is not possible to have an efficient reallocation strategy.

"Not easy" would have been more appropriate. It is still basically what malloc() does. One way would be to use Python's current memory allocator, by adapting it to sort objects into pools not only according to size but also according to type. What seems to me like a good solution would be to use one relatively large "arena" per type and Python's memory allocator to subdivide each arena. If each arena starts at a pointer address which is properly aligned, then *(p&MASK) gives you the type of any object, and possibly even without much cache-miss overhead because there are not so many arenas in total (probably only 1-2 per type in common cases, and arenas can be large). A bientot, Armin.

[Martin v. Löwis, on schemes to segregate object memory by type, with the type pointer shared at a calculated address]

... So where do you put strings with 100,000 elements (characters)? Or any other object that exceeds an arena in size?

You allocate enough extra memory so that there's room to stick a type pointer at the calculated address; or, IOW, it becomes a one-object pool but of unusually large size. Somes bytes may be lost at the start of the allocated region to allow planting a type pointer at a pool-aligned address; but by assumption the object is "very large", so the wastage can be small in percentage terms. That said, the current pymalloc is relentlessy about speeding alloc/free of exactly-the-same-size small blocks -- there's not much code that could be reused in a type-segregated scheme (the debug pymalloc wrapper is a different story -- it can wrap any malloc/free).

Armin Rigo writes:

Hello Martin,

On Sun, Nov 02, 2003 at 08:05:55PM +0100, Martin v. L?wis wrote:

...

...

...

More than that in the good cases. Something I forgot was that you'd probably have to knock variable length types on the head.

Why?

Assuming "to knock on the head" means "to put an end to":

If you put all objects of the same type into a pool, you really want all objects to have the same side, inside a pool. With that assumption, garbage objects can be reallocated without causing fragmentation. If objects in a pool have different sizes, it is not possible to have an efficient reallocation strategy.

"Not easy" would have been more appropriate. It is still basically what malloc() does.

Well, yeah, but as Tim said pymalloc gets its wins from assuming that each allocation is the same size. You could combine my idea with some other allocation scheme, certainly, but given the relative paucity of variable length types and the reduction in allocator overhead using something like pymalloc gives us, I think it might just be easier to not do them any more. Of course, I don't see myself having any time to play with this idea any time soon, and it's probably not really beefy enough to get a masters thesis from, so maybe we'll never know.

One way would be to use Python's current memory allocator, by adapting it to sort objects into pools not only according to size but also according to type.

That's pretty much what I was suggesting.

What seems to me like a good solution would be to use one relatively large "arena" per type and Python's memory allocator to subdivide each arena. If each arena starts at a pointer address which is properly aligned, then *(p&MASK) gives you the type of any object, and possibly even without much cache-miss overhead because there are not so many arenas in total (probably only 1-2 per type in common cases, and arenas can be large).

Hmm, maybe. I'm not going to make guesses about that one :-) Cheers, mwh -- ... Windows proponents tell you that it will solve things that your Unix system people keep telling you are hard. The Unix people are right: they are hard, and Windows does not solve them, ... -- Tim Bradshaw, comp.lang.lisp

Armin Rigo writes:

Hello Michael,

On Mon, Nov 03, 2003 at 11:35:05AM +0000, Michael Hudson wrote:

...

...

"Not easy" would have been more appropriate. It is still basically what malloc() does.

Well, yeah, but as Tim said pymalloc gets its wins from assuming that each allocation is the same size. You could combine my idea with some other allocation scheme, certainly, but given the relative paucity of variable length types and the reduction in allocator overhead using something like pymalloc gives us, I think it might just be easier to not do them any more. Of course, I don't see myself having any time to play with this idea any time soon, and it's probably not really beefy enough to get a masters thesis from, so maybe we'll never know.

Ok. I expect it to be much easier to experiment with with PyPy anyway.

This had occured to me too :-) Cheers, mwh -- Never meddle in the affairs of NT. It is slow to boot and quick to crash. -- Stephen Harris -- http://home.xnet.com/~raven/Sysadmin/ASR.Quotes.html

"Phillip J. Eby" writes:

At 11:35 AM 11/3/03 +0000, Michael Hudson wrote:

...

Armin Rigo writes:

...

What seems to me like a good solution would be to use one relatively large "arena" per type and Python's memory allocator to subdivide each arena. If each arena starts at a pointer address which is properly aligned, then *(p&MASK) gives you the type of any object, and possibly even without much cache-miss overhead because there are not so many arenas in total (probably only 1-2 per type in common cases, and arenas can be large).

Hmm, maybe. I'm not going to make guesses about that one :-)

You guys do realize that this scheme would make it impossible to change an object's type, right? Unless of course you have some way to "search and replace" all references to an object.

I'd got this far...

And if you were to say, "well, we'll only use this trick for non-heap types", my question would be, how's the code doing *(p&MASK) going to know how *not* to do that? If heap types have a different layout, how can you inherit from a builtin type in pure Python? And so on.

... but somehow this point had escaped me. Well, you could do something like having a cookie[1] at the start of heap type pools that says "the pointer to the type object is actually at *(p-4)" but that's pretty sick (and puts branches in every type access). Darn. Oh well, I suspected my idea had to have some large problem, it just took longer that I expected for someone to spot it :-) Cheers, mwh [1] e.g. NULL... -- Presumably pronging in the wrong place zogs it. -- Aldabra Stoddart, ucam.chat

Jeremy Fincher wrote:

That's something I've always wondered about -- what exactly is a "variable length type" and why are they special? From what I gather, they're types (long, str, and tuple are the main ones I know of) whose struct is actually of variable size -- rather than contain a pointer to a variable-size thing, they contain the variable-size thing themselves.

Correct. Examples include strings and tuples, but not lists and dictionaries.

What do we gain from them?

Speed, by saving an extra allocation upon creation; also some speed by saving an indirection upon access. It only works if the number of items in the object is not going to change over the lifetime of the object - in particular, for immutable objects. There is actually an exception to this rule: If you own the only reference to the object, you can afford to change its size (available for strings only). Regards, Martin