Changes between Version 118 and Version 126 of Ticket #715


Ignore:
Timestamp:
01/09/12 16:43:06 (8 years ago)
Author:
SimonKing
Comment:

To answer my own question: I believe that comparison by equality does not make sense (yet), since it isn't used in the coercion model.

Therefore, I have produced a new patch. Idea: The TripleDict stores the addresses of the keys. In addition, there is a dictionary of weak references with callback function. The only purpose of these references is that their callback functions are erasing invalid dictionary items.

"Raw" speed

Patched:

sage: from sage.structure.coerce_dict import TripleDict
sage: D = TripleDict(113)
sage: L = []
sage: for p in prime_range(10^3):
....:     K = GF(p)
....:     P = K['x','y']
....:     L.append((K,P))
....:
sage: for i,(K,P) in enumerate(L):
....:     D[K,P,True] = i
....:
sage: cython("""
....: from sage.structure.coerce_dict cimport TripleDict
....: def testTriple(TripleDict D, list L):
....:     for K,P in L:
....:         n = D[K,P,True]
....: def testTripleGet(TripleDict D, list L):
....:     for K,P in L:
....:         n = D.get(K,P,True)
....: def testTripleSet(list L):
....:     cdef TripleDict D = TripleDict(113)
....:     for i,(K,P) in enumerate(L):
....:         D.set(K,P,True, i)
....: """)
sage: %timeit testTriple(D,L)
625 loops, best of 3: 42.4 µs per loop
sage: %timeit testTripleGet(D,L)
625 loops, best of 3: 28.3 µs per loop
sage: %timeit testTripleSet(L)
125 loops, best of 3: 2.66 ms per loop

Unpatched:

sage: %timeit testTriple(D,L)
625 loops, best of 3: 31.2 µs per loop
sage: %timeit testTripleGet(D,L)
625 loops, best of 3: 17.5 µs per loop
sage: %timeit testTripleSet(L)
625 loops, best of 3: 79.2 µs per loop

Doctest speed

Patched

sage -t  "devel/sage-main/sage/modules/free_module.py"
         [11.4 s]
sage -t  "devel/sage-main/sage/modules/free_module.py"
         [11.7 s]

Unpatched

sage -t  "devel/sage-main/sage/modules/free_module.py"
         [11.7 s]
sage -t  "devel/sage-main/sage/modules/free_module.py"
         [11.5 s]

Conclusion

Using weak references, things become a bit slower, but it is a lot better than with the previous patches. According to the timing of the doc tests, the regression doesn't matter in applications.

I guess there is no free lunch, and thus the regression is small enough, given that the memory leak is fixed (which is checked in a new test).

I have not run the full test suite yet, but I think it can be reviewed.

Apply trac715_one_triple_dict.patch

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #715

    • Property Status changed from needs_work to needs_review
    • Property Work issues changed from Get some timings to
  • Ticket #715 – Description

    v118 v126  
    2020So weak refs should be used in all these places if it does not slow things too much.
    2121
    22 Apply [attachment:trac715_tripledict_combined.patch]
     22Apply [attachment:trac715_one_tripledict.patch]