Opened 10 years ago

Last modified 10 years ago

#12808 closed enhancement

Optimize ClassCallMetaClass using Cython — at Version 14

Reported by: hivert Owned by: jason
Priority: major Milestone: sage-5.1
Component: misc Keywords: classcall UniqueRepresentation
Cc: nthiery, SimonKing Merged in:
Authors: Florent Hivert Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by SimonKing)

When a class C is an instance of ClasscallMetaclass, then for any constructor call, the system currently looks for __classcall__ and __classcall_private__ in C. This adds quite an overhead and this could be cached, assuming no one modifies C (which seems reasonable). Improving this speeds up, in particular, all call to the constructor of a subclass of UniqueRepresentation, eg. many parents, all categories...

Apply

trac_12808-classcall_speedup2.patch

Change History (14)

comment:1 Changed 10 years ago by hivert

  • Cc nthiery SimonKing added

Before

sage: %timeit ZZ in Rings()
625 loops, best of 3: 1.13 µs per loop

After the preliminary patch

sage: %timeit ZZ in Rings()
625 loops, best of 3: 448 ns per loops

comment:2 Changed 10 years ago by hivert

I'm finishing the patch, I've added a large optimization for the other branch where there is no __classcall__

Here are the results in the basis case (no __classcall__)::

sage: class Rien(object):
...       pass
sage: from sage.misc.classcall_metaclass import ClasscallMetaclass
sage: class NOCALL(object):
...      __metaclass__ = ClasscallMetaclass
...      pass

Standard Python class:

sage: %timeit [Rien() for i in range(10000)]
125 loops, best of 3: 1.7 ms per loop

Currently:

sage: %timeit [NOCALL() for i in range(10000)]
25 loops, best of 3: 15.9 ms per loop

Cython version:

sage: %timeit [NOCALL() for i in range(10000)]
125 loops, best of 3: 3.59 ms per loop

Cython optimized version:

sage: %timeit [NOCALL() for i in range(10000)]
125 loops, best of 3: 1.76 ms per loop

So I'm 5% only slower than normal class.

Here are the results in the basis case (no __classcall__)::

sage: class CALL(object):
...       __metaclass__ = ClasscallMetaclass
...       @staticmethod
...       def __classcall_private__(cls, arg):
...           arg = arg + arg
...           return arg

Currently:

sage: %timeit [CALL(i) for i in range(10000)]
25 loops, best of 3: 8.7 ms per loop

Cython version:

sage: %timeit [CALL(i) for i in range(10000)]
125 loops, best of 3: 4.33 ms per loop

Cython optimized version (no mesurable difference from the preceding):

sage: %timeit [CALL(i) for i in range(10000)]
125 loops, best of 3: 4.34 ms per loop

Here I'm twice as fast as before.

I'm cleanup the patch (doctests) an will post it shortly.

comment:3 Changed 10 years ago by SimonKing

Sorry, I can not do any serious work (reviewing), as I am in the middle of holidays. But it looks promising!

comment:4 Changed 10 years ago by SimonKing

Hi Florent!

I know the patch is preliminary, but here are two comments:

In the new file classcall_metaclass_cy.pyx, it is not explained what __classcall__ and __classcall_private__ do, and when to implement which. Actually, I have never used __classcall_private__ myself.

In the old python version of classcall_metaclass, you move __call__ to __call__disable. Why do you not completely remove the slow Python call method?

comment:5 follow-up: Changed 10 years ago by SimonKing

Also, why not going all the way and remove the python version completely? Or at least: Why not cythonizing (and caching?) the __contains__ method?

comment:6 follow-up: Changed 10 years ago by SimonKing

Or ideally, one could try to provide a generalised metaclass framework in Sage. Namely, one could think of having different small metaclasses, each providing a particular feature. For example:

  • We have NestedMetaclass.
  • We already have __classcall__ (perhaps resulting in a unique parent structure or in a dynamic class).
  • At #11794, I suggest a metaclass that provides a fast cached hash.
  • Just "brainstorming": Perhaps it would be a useful feature for debugging to print which Python methods are called of a particular instance. I could imagine a metaclass that could be used to temporarily switch that feature on.

And if we have different "small" metaclasses then it would be useful to combine them. But that's a problem for Python: If A, B and C have different metaclasses, you can not simply have a class definition like

    class D(A,B,C): pass

This is (I guess) why ClasscallMetaclass inherits from NestedMetaclass. But Ticket #11794 provides examples for a different and more skalable solution: Make metaclasses dynamic''

So, what I mean by a generalised metaclass framework in Sage is:

  • Implement a base class SageMetaclass, from which all metaclasses (such as NestedMetaclass and ClasscallMetaclass and FastHashMetaclass) are derived.
  • Make it so that if A, B, C are classes with different metaclasses (all derived from SageMetaclass) can be used as base classes for a new class. In that way, the features provided by metaclasses could be freely combined.

But I guess that's a topic for a different ticket...

comment:7 Changed 10 years ago by SimonKing

PS: If that works, one could also get rid of the DynamicClasscallMetaclass, which seems like a hack that became necessary since one can not freely combine base classes with different metaclasses.

comment:8 in reply to: ↑ 5 Changed 10 years ago by hivert

Hi Simon,

Thanks for all those remarks and sorry for not having finished this one as fast as I wanted.

Replying to SimonKing:

Also, why not going all the way and remove the python version completely? Or at least: Why not cythonizing (and caching?) the __contains__ method?

Obviously. Please see my patch on sage combinat's queue which already adresses all those remarks. I'm currently doing intensive timing to be sure that we have the fastest way.

Florent

comment:9 in reply to: ↑ 6 Changed 10 years ago by hivert

Replying to SimonKing:

This is (I guess) why ClasscallMetaclass inherits from NestedMetaclass. But Ticket #11794 provides examples for a different and more skalable solution: Make metaclasses dynamic''

Yes it is. We discussed last week with Nicolas of switching the inheritance order here. That is using only NestedMetaclass for Categories. I still have to check that this doesn't break pickling of Parent with a nested Element.

So, what I mean by a generalised metaclass framework in Sage is:

  • Implement a base class SageMetaclass, from which all metaclasses (such as NestedMetaclass and ClasscallMetaclass and FastHashMetaclass) are derived.
  • Make it so that if A, B, C are classes with different metaclasses (all derived from SageMetaclass) can be used as base classes for a new class. In that way, the features provided by metaclasses could be freely combined.

But I guess that's a topic for a different ticket...

+1 for this and for keeping it for a different ticket.

comment:10 Changed 10 years ago by hivert

Hi Simon,

I just uploaded an updated patch. I still have to lauch the tests (but I've to run for a train now) and to check the documentation. The code together with the timings should hopefully be the final version here. I'll put the needs review after the tests and doc rereading.

Thanks for your remarks.

Florent

comment:11 Changed 10 years ago by hivert

  • Status changed from new to needs_review

comment:12 Changed 10 years ago by SimonKing

Could it be that the patch was created by something like "hg remove sage/misc/classcall_metaclass.py" followed by "hg add sage/misc/classcall_metaclass.pyx"?

I am no mercurial expert, but I was told that one should better use "hg rename sage/misc/classcall_metaclass.py sage/misc/classcall_metaclass.pyx".

comment:13 Changed 10 years ago by SimonKing

While we are at it: Shouldn't we also try whether changing unique_representation.py into unique_representation.pyx yields a speedup (but not changing "class" into "cdef class", I guess that won't work)?

comment:14 Changed 10 years ago by SimonKing

  • Description modified (diff)

I have created an alternative patch (using hg rename). It is smaller than the original patch, but should result in identical code. So, either of the patches could be used, but I guess the smaller patch is easier to read (because one sees more easily the additional differences between classcall_metaclass.py and classcall_metaclass.pyx)

Apply trac_12808-classcall_speedup2.patch

Note: See TracTickets for help on using tickets.