# Ticket #13501(closed defect: fixed)

Opened 8 months ago

## Fix two bugs in sage.misc.c3's implementation of the algorithm C3

Reported by: Owned by: nthiery major sage-5.5 categories method resolution order sage-combinat, SimonKing N/A Simon King Nicolas M. Thiéry, Simon King sage-5.5.beta1

The current implementation of C3's algorithm in sage.misc.c3 (which is used to compute the list of all the super categories of a category) is incorrect.

Define indeed the following classes::

```sage: class C(object): pass
....:
sage: class F(object): pass
....:
sage: class G(object): pass
....:
sage: class B(C,F): pass
....:
sage: class D(F,G): pass
....:
sage: class E(F): pass
....:
sage: class A(B,D,E): pass
....:
```

Which gives the following mro:

```sage: A.mro()
[<class '__main__.A'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.D'>, <class '__main__.E'>, <class '__main__.F'>, <class '__main__.G'>, <type 'object'>]
```

Here is now the same hierarchy using categories::

```class Cs(Category):
def super_categories(self): return []

class Fs(Category):
def super_categories(self): return []

class Gs(Category):
def super_categories(self): return []

class Bs(Category):
def super_categories(self): return [Cs(), Fs()]

class Ds(Category):
def super_categories(self): return [Fs(), Gs()]

class Es(Category):
def super_categories(self): return [Fs()]

class As(Category):
def super_categories(self): return [Bs(), Ds(), Es()]
```

The super categories are not given in the same order (g,e,f instead of e f g)::

```sage: As().all_super_categories()
[Category of as, Category of bs, Category of cs, Category of ds, Category of gs, Category of es, Category of fs]
```

This is due to popping X from the tail too early around line 186: O is a candidate for being the next in line, but has not yet been definitely chosen.

And indeed this is caught by the test suite::

```sage: TestSuite(As()).run()
Failure in _test_category_graph:
Traceback (most recent call last):
...
AssertionError: False is not true
```

Here is another hierarchy with an inconsistent MRO which is not detected by Sage's current C3::

```class B(object): pass

class C(B): pass

class A(B, C): pass

Traceback (most recent call last):
File "<ipython console>", line 1, in <module>
TypeError: Error when calling the metaclass bases
Cannot create a consistent method resolution
order (MRO) for bases C, B
```
```class Bs(Category):
def super_categories(self): return []

class Cs(Category):
def super_categories(self): return [Bs()]

class As(Category):
def super_categories(self): return [Bs(), Cs()]
class subcategory_class(object): # just to bypass the MRO error when building the subcategory class
pass

sage: As()
Category of as
sage: As().all_super_categories()
[Category of as, Category of cs, Category of bs]
```

Here the issue comes from the fact that the C3 algorithm is supposed to work on the mro's of the bases *together with* the list of the bases, which the current Sage's implementation does not.

Apply:

## Change History

### comment:1 Changed 8 months ago by nthiery

Hi Simon,

I'll be working on this ticket today or so. We are currently exploring with Florent the theoretical limits of C3, and ways to fix the MRO issues once for all for categories. For that, we need a clean C3 implementation for further instrumentation. More on that topic on sage-combinat-devel shortly!

### comment:2 Changed 8 months ago by nthiery

Here is a preliminary patch. It fixes the bug and simplifies a bit the logic. I now need to benchmark it, and reintroduce a couple PyList?... where timings will call for it.

### comment:3 Changed 8 months ago by nthiery

• Status changed from new to needs_review
• Reviewers set to Simon King
• Authors set to Nicolas M. Thiéry

Hi!

I optimized and cleaned a bit the code; here are some timings, using the following for benchmarking (better suggestions welcome):

```sage: l = GradedHopfAlgebrasWithBasis(GF(3)).all_super_categories() # to force preloading everything
sage: def f(n):
...       for i in range(5,n+5):
```

Before:

```sage: %prun f(200)
...
2800/200    0.189    0.000    1.298    0.006 {sage.misc.c3.C3_algorithm}
```
```sage: %prun f(200)
...
2800/200    0.249    0.000    1.430    0.007 {sage.misc.c3.C3_algorithm}
```
```sage: %prun f(200)
...
2800/200    0.249    0.000    1.429    0.007 {sage.misc.c3.C3_algorithm}
```

So, we have a 15% loss compared to the previous implementation. I am not sure exactly where it's slower, but I guess it's just the price for correctness (the previous implementation was popping out stuff too early). As the second attachment shows, using PyList?_GET_ITEM and friends does not seem to bring anything substantial, so I'd vote for sticking to more readable Python notations.

Apply:

Simon: let me know in case you are busy, I can possibly ask Florent for the review.

### comment:4 Changed 8 months ago by nthiery

• Description modified (diff)

### comment:5 follow-up: ↓ 6 Changed 8 months ago by SimonKing

I'll see whether using the low-level functions PyList_GET_ITEM and friends will help to reduce the slow-down. After all, when doing tailsets[j], we already now that j is not out of bounds. Hence, we can drop the checks done in O in tailsets[j] and could as well do O in <set>PyList_GET_ITEM(tailsets, j).

### comment:6 in reply to: ↑ 5 ; follow-up: ↓ 7 Changed 8 months ago by SimonKing

I'll see whether using the low-level functions PyList_GET_ITEM and friends will help to reduce the slow-down. After all, when doing tailsets[j], we already now that j is not out of bounds. Hence, we can drop the checks done in O in tailsets[j] and could as well do O in <set>PyList_GET_ITEM(tailsets, j).

Or perhaps this would be even faster: PySet_Contains(<object>PyList_GET_ITEM(tailsets, j), O) is int(1). Let me do some tests...

### comment:7 in reply to: ↑ 6 ; follow-up: ↓ 9 Changed 8 months ago by nthiery

I'll see whether using the low-level functions PyList_GET_ITEM and friends will help to reduce the slow-down. After all, when doing tailsets[j], we already now that j is not out of bounds. Hence, we can drop the checks done in O in tailsets[j] and could as well do O in <set>PyList_GET_ITEM(tailsets, j).

Or perhaps this would be even faster: PySet_Contains(<object>PyList_GET_ITEM(tailsets, j), O) is int(1). Let me do some tests...

That's basically what the second patch does, and it does not seem to do much of a change. But feel free to explore!

### comment:8 follow-up: ↓ 10 Changed 8 months ago by SimonKing

Another optimization:

```for j from 0 <= j < nbheads:
if j == i:
continue
if O in tailsets[j]:
next_item_found = False
if next_item_found:
...
```

Apparently, after the line next_item_found = False, one should insert a break, because otherwise the loop is finished to no avail.

### comment:9 in reply to: ↑ 7 Changed 8 months ago by SimonKing

Or perhaps this would be even faster: PySet_Contains(<object>PyList_GET_ITEM(tailsets, j), O) is int(1). Let me do some tests...

That's basically what the second patch does, and it does not seem to do much of a change. But feel free to explore!

Sorry, I didn't look at the second patch. Yes, if that doesn't help, it would probably be useless. But I think breaking the loop would make sense.

### comment:10 in reply to: ↑ 8 ; follow-up: ↓ 13 Changed 8 months ago by nthiery

Another optimization:

```for j from 0 <= j < nbheads:
if j == i:
continue
if O in tailsets[j]:
next_item_found = False
if next_item_found:
...
```

Apparently, after the line next_item_found = False, one should insert a break, because otherwise the loop is finished to no avail.

Good point; I am trying it right now!

### comment:11 Changed 8 months ago by SimonKing

Yes, the effect of using the C Api really seems marginal. I defined

```def test_pythonic(O,list L):
cdef int j
cdef int l = len(L)
next_item_found = True
for j from 0 <= j < l:
if O in L[j]:
next_item_found = False

def test_cythonic(O, list L):
cdef int j
cdef int l = len(L)
next_item_found = True
for j from 0 <= j < l:
if PySet_Contains(<object>PyList_GET_ITEM(L, j), O):
next_item_found = True
```

and obtained:

```sage: L = [set(range(i,i+1000)) for i in range(1000)]
sage: %timeit test_pythonic(1001,L)
625 loops, best of 3: 116 µs per loop
sage: %timeit test_cythonic(1001,L)
625 loops, best of 3: 111 µs per loop
```

### comment:12 Changed 8 months ago by SimonKing

PS: The difference being 5%, one could still argue that 5% is the lowest number that is called "significant".

### comment:13 in reply to: ↑ 10 Changed 8 months ago by nthiery

Apparently, after the line next_item_found = False, one should insert a break, because otherwise the loop is finished to no avail.

Good point; I am trying it right now!

Here it is: without the break:

``` 2800/200    0.247    0.000    1.417    0.007 {sage.misc.c3.C3_algorithm}
```

with the break:

``` 2800/200    0.243    0.000    1.413    0.007 {sage.misc.c3.C3_algorithm}
```

Tiny difference, but it's natural to put it here anyway. I am about to update the patch.

Note: I switched from 5.2 to 5.3 in the mean time, so the timings from this comment can't really be compared with the timings before.

Cheers,

Nicolas

Last edited 8 months ago by nthiery (previous) (diff)

### comment:14 Changed 8 months ago by nthiery

• Summary changed from Bugs in C3'salgorithm implementation in sage.misc.c3 to Fix two bugs in sage.misc.c3's implementation of the algorithm C3

### comment:15 Changed 8 months ago by SimonKing

For the record: With sage-5.4.beta0 and

```trac_715_combined.patch
trac_715_local_refcache.patch
trac_715_safer.patch
trac_715_specification.patch
trac_11521_homset_weakcache_combined.patch
trac_11521_callback.patch
13145.patch
trac_13447-sanitise_ring_refcount.patch
trac12215_weak_cached_function-sk.patch
trac12215_segfault_fixes.patch
trac_12313-mono_dict-combined-random-sk.patch
trac_12313_quit_sage.patch
trac13370_deprecate_is_field.patch
trac_13378-convert_map_shortcut.patch
trac_13412_category_for_power_series_rings.patch
```

and with %prun f(500) (because 200 may not be enough), I get

```   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
7000/500    0.212    0.000    0.773    0.002 {sage.misc.c3.C3_algorithm}
```

```   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
7000/500    0.307    0.000    0.848    0.002 {sage.misc.c3.C3_algorithm}
```

And with the optimization patch, I get

```   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
7000/500    0.304    0.000    0.853    0.002 {sage.misc.c3.C3_algorithm}
```

So, the slow-down is little and using the C Api is not noticeable.

### comment:16 Changed 8 months ago by SimonKing

With a little cdef'ing, namely

• ## sage/misc/c3.pyx

`diff --git a/sage/misc/c3.pyx b/sage/misc/c3.pyx`
 a nbheads = len(heads) cdef object O, X cdef bint next_item_found cdef set tail_set cdef list tail_list while nbheads: for i from 0 <= i < nbheads: for j from 0 <= j < nbheads: if j == i: continue if O in tailsets[j]: tail_set = tailsets[j] if O in tail_set: next_item_found = False break if next_item_found: # j goes down so that ``del heads[j]`` does not screw up the numbering for j from nbheads > j >= 0: if heads[j] is O: try: X = tails[j].pop() tail_list = tails[j] if tail_list: X = tail_list.pop() heads[j] = X tailsets[j].remove(X) except IndexError: tail_set = tailsets[j] tail_set.remove(X) else: del heads[j] del tails[j] del tailsets[j]

I get

```   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
7000/500    0.277    0.000    0.819    0.002 {sage.misc.c3.C3_algorithm}
```

The differences really are tiny. However, here is why I removed the try: ... except IndexError::

```sage: cython("""
....: def test1(list L):
....:     cdef list l
....:     for l in L:
....:         try:
....:             l.pop()
....:         except IndexError:
....:             l.append(0)
....: def test2(list L):
....:     cdef list l
....:     for l in L:
....:         if l:
....:             l.pop()
....:         else:
....:             l.append(0)
....: """)
sage: L = [[] for _ in range(10000)]
sage: %timeit test1(L)
125 loops, best of 3: 7.07 ms per loop
sage: L = [[] for _ in range(10000)]
sage: %timeit test2(L)
125 loops, best of 3: 1.94 ms per loop
```

### comment:17 follow-up: ↓ 18 Changed 8 months ago by SimonKing

Another thought: We want to compare the entries on the list by identity, not by equality, isn't it? But isn't then if O in tail_set unnecessarily slow, because it compares by equality rather than identity?

I wonder if one could instrument MonoDict from #12313.

### comment:18 in reply to: ↑ 17 Changed 8 months ago by SimonKing

I wonder if one could instrument MonoDict from #12313.

I tested: MonoDict is slower than a set. But if we want to compare by identity, then perhaps the tailsets should store the memory addresses of the objects, rather than the objects?

### comment:19 Changed 8 months ago by SimonKing

• Owner nthiery deleted

Here is evidence that using a set of memory locations is way faster than a set of objects, if what we actually want is comparison by identity.

Namely:

```sage: cython("""
....: def test1(set S, object O):
....:     return O in S
....: def test2(set S, object O):
....:     return <size_t><void *>O in S
....: """)
sage: S = set(Algebras(GF(p)) for p in prime_range(10000))
sage: Sid = set(id(O) for O in S)
sage: len(S)
1229
sage: len(Sid)
1229
sage: O = Algebras(GF(151))
sage: test1(S,O)
True
sage: test2(Sid,O)
True
sage: %timeit test1(S,O)
625 loops, best of 3: 507 ns per loop
sage: %timeit test2(Sid,O)
625 loops, best of 3: 186 ns per loop
```

### comment:20 Changed 8 months ago by SimonKing

Using <size_t><void *> rather than the objects seems to work, speed-wise! With your benchmark, I get

```   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
7000/500    0.197    0.000    0.671    0.001 {sage.misc.c3.C3_algorithm}
```

using the following patch:

• ## sage/misc/c3.pyx

`diff --git a/sage/misc/c3.pyx b/sage/misc/c3.pyx`

I am now running make ptest with that patch, and if it works, then I'll post it here "officially", and we can start cross-reviewing.

Last edited 8 months ago by SimonKing (previous) (diff)

### comment:21 Changed 8 months ago by SimonKing

PS: Note that according to the timing from my previous post, my patch would even yield a small speed-up, compared with vanilla sage.

### comment:22 follow-up: ↓ 23 Changed 8 months ago by SimonKing

• Description modified (diff)
• Authors changed from Nicolas M. Thiéry to Nicolas M. Thiéry, Simon King

It seems to work!

Hence, time for a cross-review...

Apply trac_13501-categories-c3_fix-nt.patch trac_13501-c3-speedup-sk.patch

### comment:23 in reply to: ↑ 22 ; follow-up: ↓ 24 Changed 8 months ago by nthiery

It seems to work!

Hence, time for a cross-review...

Apply trac_13501-categories-c3_fix-nt.patch trac_13501-c3-speedup-sk.patch

I am almost ready for a postive review (assuming the patchbot goes green). Two little questions: what happens if

• we use id(cat) rather than the obscure <size_t><void *> cat ?
• we use O in <set>tailsets[j] rather than assigning to a temporary variable?

In both cases, if the speed is roughly equivalent, then I vote for the more readable version.

Cheers,

### comment:24 in reply to: ↑ 23 Changed 8 months ago by SimonKing

I am almost ready for a postive review (assuming the patchbot goes green).

Will it ever go green? Does the patchbot work at all.

Two little questions: what happens if

• we use id(cat) rather than the obscure <size_t><void *> cat ?
• we use O in <set>tailsets[j] rather than assigning to a temporary variable?

I guess you mean id(O) in <set>tailsets[j]?

One obtains

```   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
7000/500    0.207    0.000    0.672    0.001 {sage.misc.c3.C3_algorithm}
```

```   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
7000/500    0.196    0.000    0.663    0.001 {sage.misc.c3.C3_algorithm}
```

In both cases, if the speed is roughly equivalent, then I vote for the more readable version.

Is the difference (again 5%) marginal? Anyway, I can only do it tomorrow.

Last edited 8 months ago by SimonKing (previous) (diff)

### comment:25 Changed 8 months ago by SimonKing

The following "raw data" should advise us what syntax to use.

I defined

```include "sage/ext/python_list.pxi"

def test1(list L, object O):
cdef set S
cdef size_t i
cdef size_t l = len(L)
cdef bint b
for i from 0<=i<l:
S = <set>PyList_GET_ITEM(L,i)
b = <size_t><void *>O in S

def test2(list L, object O):
cdef size_t i
cdef size_t l = len(L)
cdef bint b
for i from 0<=i<l:
b = <size_t><void *>O in <set>PyList_GET_ITEM(L,i)

def test3(list L, object O):
cdef size_t i
cdef size_t l = len(L)
cdef bint b
for i from 0<=i<l:
b = <size_t><void *>O in <set>L[i]

def test4(list L, object O):
cdef size_t i
cdef size_t l = len(L)
cdef bint b
for i from 0<=i<l:
b = id(O) in <set>L[i]

def test5(list L, object O):
cdef size_t i
cdef size_t l = len(L)
cdef bint b
for i from 0<=i<l:
b = id(O) in <set>PyList_GET_ITEM(L,i)
```

and obtain

```sage: L = [set(id(GF(p)) for p in prime_range(n,n+500)) for n in range(1,1000)]
sage: O = GF(next_prime(500))
sage: timeit("test1(L,O)", number=2000)
2000 loops, best of 3: 48.9 µs per loop
sage: timeit("test2(L,O)", number=2000)
2000 loops, best of 3: 45.7 µs per loop
sage: timeit("test3(L,O)", number=2000)
2000 loops, best of 3: 70.9 µs per loop
sage: timeit("test4(L,O)", number=2000)
2000 loops, best of 3: 107 µs per loop
sage: timeit("test5(L,O)", number=2000)
2000 loops, best of 3: 87.1 µs per loop
```

So, I would say that it really matters whether or not we should do <set>PyList_GET_ITEM(L,i) or <set>L[i] (see test2 versus test3), and it also matters whether we do <size_t><void *>O or id(O) (see test3 versus test4 and test2 versus test5). Assigning to a temporary variable is not good (unless we need the same set twice, of course).

Seeing these data, I think a syntax as in test2 is best. Sure, C3 does more than an element test in a list of sets. But I do think it is a critical step.

Last edited 8 months ago by SimonKing (previous) (diff)

### comment:26 Changed 8 months ago by SimonKing

This time, I used %prun f(1000) for the timings.

When I change the syntax, as suggested in the previous post, I get

```   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
14000/1000    0.385    0.000    1.330    0.001 {sage.misc.c3.C3_algorithm}
```

With the current version of trac_13501-c3-speedup-sk.patch, I get

```   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
14000/1000    0.380    0.000    1.297    0.001 {sage.misc.c3.C3_algorithm}
```

So, a further "complication" of the syntax is not good.

If I use a more readable syntax, hence replace <sizt_t><void *> by id and avoid the temporary variable, I get roughly 10% slow-down:

```   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
14000/1000    0.427    0.000    1.364    0.001 {sage.misc.c3.C3_algorithm}
```

Without the optimization patch (only your main patch), I get

```   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
14000/1000    0.615    0.000    1.706    0.002 {sage.misc.c3.C3_algorithm}
```

Without your main patch (hence, the old buggy C3 version in Sage), I get

```   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
14000/1000    0.442    0.000    1.558    0.002 {sage.misc.c3.C3_algorithm}
```

Hence, apparently the current version of my speedup patch is just fine.

### comment:27 Changed 8 months ago by nthiery

Thanks for the detailed analysis! Positive review on my behalf, assuming the tests pass (I am running them now on 5.4 beta1)

Cheers,

PS: maybe we should use the same trick for category containment using all_super_categories_as_set (if this is still in use). This also means that we should investigate whether we could optimize further UniqueRepresentation? to speedify sets and dictionaries of such objects!

### comment:28 follow-up: ↓ 29 Changed 8 months ago by nthiery

There is a failure in sage_object, probably trivial/unrelated, but I haven't looked at it yet; I need to take of now!

### comment:29 in reply to: ↑ 28 Changed 8 months ago by SimonKing

There is a failure in sage_object, probably trivial/unrelated, but I haven't looked at it yet; I need to take of now!

The error is when unpickling stuff. In principle, a different mro could change things. On the other hand, this should only affect parent and element classes of categories - and they are pickled by construction (hence, it is not the case that the mro is stored in the pickle).

Anyway, I get:

```./sage -t devel/sage/sage/structure/sage_object.pyx
sage -t  "devel/sage/sage/structure/sage_object.pyx"
[11.5 s]

----------------------------------------------------------------------
All tests passed!
Total time for all tests: 11.5 seconds
```

with

```trac_715_combined.patch
trac_715_local_refcache.patch
trac_715_safer.patch
trac_715_specification.patch
trac_11521_homset_weakcache_combined.patch
trac_11521_callback.patch
13145.patch
trac_13447-sanitise_ring_refcount.patch
trac12215_weak_cached_function-sk.patch
trac12215_segfault_fixes.patch
trac_12313-mono_dict-combined-random-sk.patch
trac_12313_quit_sage.patch
trac13370_deprecate_is_field.patch
trac_13378-convert_map_shortcut.patch
trac_13412_category_for_power_series_rings.patch
trac_13501-categories-c3_fix-nt.patch
trac_13501-c3-speedup-sk.patch
trac_12876_category_abstract_classes_for_hom.patch
trac_12876_r_test.patch
```

applied on top of sage-5.4.beta0.

### comment:30 Changed 8 months ago by nthiery

• Status changed from needs_review to positive_review

I looked at the log, and it's indeed due to another patch (I ran the test with 5.3 + the sage-combinat patches merged in 5.4, but without the correponing updated pickle jar).

So Positive Review!

Thanks Simon :-)

### comment:31 Changed 8 months ago by nthiery

• Dependencies #12895 deleted

Running the tests just made me realize that this patch commutes with #12895. I thus remove the dependency.

### comment:32 follow-up: ↓ 33 Changed 8 months ago by jdemeyer

• Status changed from positive_review to needs_work

I'm getting a long doctest error:

```sage -t  --long -force_lib devel/sage/sage/misc/c3.pyx
**********************************************************************
File "/release/merger/sage-5.4.beta2/devel/sage-main/sage/misc/c3.pyx", line 152:
sage: class A(B, C): pass
Expected:
Traceback (most recent call last):
...
TypeError: Error when calling the metaclass bases
Cannot create a consistent method resolution
order (MRO) for bases B, C
Got:
Traceback (most recent call last):
File "/release/merger/sage-5.4.beta2/local/bin/ncadoctest.py", line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/release/merger/sage-5.4.beta2/local/bin/sagedoctest.py", line 38, in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
File "/release/merger/sage-5.4.beta2/local/bin/ncadoctest.py", line 1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_1[35]>", line 1, in <module>
class A(B, C): pass###line 152:
sage: class A(B, C): pass
TypeError: Error when calling the metaclass bases
Cannot create a consistent method resolution
order (MRO) for bases C, B
**********************************************************************
```

### comment:33 in reply to: ↑ 32 ; follow-up: ↓ 34 Changed 8 months ago by SimonKing

I'm getting a long doctest error:

```    sage: class A(B, C): pass
Expected:
Traceback (most recent call last):
...
TypeError: Error when calling the metaclass bases
Cannot create a consistent method resolution
order (MRO) for bases B, C
Got:
```

But that's pure Python, and unrelated with our implementation of C3!

Could it be that the error message randomly choses between "Cannot create ... for bases B, C" and "Cannot create ... for bases C, B"?

If that is the case, I suggest to change the expected error message into "Cannot create a consistent method resolution order (MRO) for bases ..."

### comment:34 in reply to: ↑ 33 ; follow-up: ↓ 36 Changed 8 months ago by nthiery

Could it be that the error message randomly choses between "Cannot create ... for bases B, C" and "Cannot create ... for bases C, B"?

That sounds a bit strange indeed (I would have expected C3 to be completely deterministic, including in its error messages), but I vaguely remember having to change this order once.

If that is the case, I suggest to change the expected error message into "Cannot create a consistent method resolution order (MRO) for bases ..."

+1

I just did that. I used the occasion to avoid using a temporary tail_set variable, as recommended by your benchmark. See trac_13501-c3-review-nt.patch for the changes. The updated trac_13501-categories-c3_fix-nt.patch contains all three patches folded together.

Apply:

Cheers,

Nicolas

### comment:35 Changed 8 months ago by nthiery

• Status changed from needs_work to needs_review

### comment:36 in reply to: ↑ 34 Changed 8 months ago by nthiery

I used the occasion to avoid using a temporary tail_set variable, as recommended by your benchmark.

I just ran a benchmark, and it actually seems to make no difference ... But it's slighly more readable.

### comment:37 Changed 7 months ago by nthiery

Hi Simon!

Could you give it a quick look at my little change and set it back to positive review if that's ok?

Thanks!

### comment:38 Changed 7 months ago by SimonKing

• Status changed from needs_review to positive_review

The patch looks fine, and all doctests (except the one for cmdline.py, which has been disabled for security reasons) pass on bsd.math. So, I can set it back to a positive review.

### comment:39 Changed 7 months ago by jdemeyer

• Milestone changed from sage-5.4 to sage-5.5

### comment:40 Changed 7 months ago by jdemeyer

• Status changed from positive_review to needs_work

This doesn't apply to sage-5.4.rc2:

```applying /release/merger/patches/trac_13501-categories-c3_fix-nt.patch
applying /release/merger/patches/trac_13501-c3-speedup-sk.patch
patching file sage/misc/c3.pyx
Hunk #1 FAILED at 185
Hunk #2 FAILED at 204
Hunk #3 FAILED at 214
3 out of 3 hunks FAILED -- saving rejects to file sage/misc/c3.pyx.rej
abort: patch failed to apply
```

### comment:41 Changed 7 months ago by nthiery

• Status changed from needs_work to positive_review
• Description modified (diff)

### comment:42 Changed 7 months ago by nthiery

Oops, sorry, Jeroen. I forgot to update the Apply list in the description. As noted in comment 33, Simon's c3-speedup-sk.patch is already folded in the main patch. Fixed and back to positive review.

### comment:43 Changed 7 months ago by jdemeyer

• Status changed from positive_review to closed
• Resolution set to fixed
• Merged in set to sage-5.5.beta1
Note: See TracTickets for help on using tickets.