#13387: Improve MonoDict and TripleDict data structures
----------------------------------+-----------------------------------------
Reporter: nbruin | Owner: Nils Bruin
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.4
Component: memleak | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Nils Bruin | Merged in:
Dependencies: #11521, #12313 | Stopgaps:
----------------------------------+-----------------------------------------
Comment (by nbruin):
Excellent work! Looks promising. I tested `IdKeyDict` against the revamped
classes here with the same tests you posted there. The `MonoDict` wins of
course:
{{{
sage: %timeit K in W
625 loops, best of 3: 38.1 µs per loop
sage: %timeit K in M
625 loops, best of 3: 112 ns per loop
sage: %timeit K in I
625 loops, best of 3: 160 ns per loop
sage: %timeit K2 in W
625 loops, best of 3: 680 ns per loop
sage: %timeit K2 in M
625 loops, best of 3: 64.1 ns per loop
sage: %timeit K2 in I
625 loops, best of 3: 104 ns per loop
sage: %timeit W[K]
625 loops, best of 3: 36.7 µs per loop
sage: %timeit M[K]
625 loops, best of 3: 99.2 ns per loop
sage: %timeit I[K]
625 loops, best of 3: 146 ns per loop
}}}
but already for the `TripleDict` it seems a reasonable choice:
{{{
sage: %timeit (K,K,True) in I
625 loops, best of 3: 392 ns per loop
sage: %timeit (K,K,True) in T
625 loops, best of 3: 451 ns per loop
sage: %timeit (K2,K,True) in I
625 loops, best of 3: 133 ns per loop
sage: %timeit (K2,K,True) in T
625 loops, best of 3: 541 ns per loop
sage:
sage: %timeit I[K,K,True]
625 loops, best of 3: 366 ns per loop
sage: %timeit T[K,K,True]
625 loops, best of 3: 432 ns per loop
}}}
I don't think I'll even understand modern CPU's ... (that or `TripleDict`
can be further tuned. It was a first try. I think I did use some ideas
that might be useful for you, though.
Anyway, at least the iteration needs some work (nice that cython
generators now work!)
{{{
sage: from sage.structure.idkey_dict import IdKeyDict
sage: I = IdKeyDict(3,53, threshold=0.7)
sage: L = []
sage: for p in prime_range(10000):
....: L.append(GF(p)['x','y'])
....:
sage: for i,K in enumerate(L):
....: I[K,K,True] = i
....:
sage: from collections import Counter
sage: Counter([k in I for k,v in I.iteritems()])
Counter({False: 1229})
sage: Counter([(k,k,True) in I for k in L])
Counter({True: 1229})
sage: Counter([(k[3](),k[4](),k[5]) in I for k,v in I.iteritems()])
Counter({True: 1229})
}}}
but as you see, that's easily fixed. You just have to extract the actual
keys. Doing it this way might report errors a bit better than with the
unsafe casting of `k[:3]` (dead weakrefs etc.)
{{{
sage: Counter([(id(k[3]()),id(k[4]()),id(k[5])) == k[:3] for k,v in
I.iteritems()])
Counter({True: 1229})
}}}
Pitfall, by the way:
{{{
sage: import weakref
sage: W=weakref.ref(ZZ)
sage: weakref.ref(W)
TypeError: cannot create weak reference to 'weakref' object
}}}
So:
{{{
sage: from sage.structure.idkey_dict import IdKeyDict
sage: import weakref
sage: class D(object): pass
....:
sage: d = D()
sage: W = weakref.KeyedRef(d,None,None)
sage: I = IdKeyDict(1,53, threshold=0.7)
sage: I[W]= 10
sage: I[W]
10
sage: del d
sage: len(I)
1
sage: I[W]
KeyError: <weakref at 0x5f6c4d0; dead>
sage: len(I)
0
sage: W
<weakref at 0x5f6c4d0; dead>
}}}
Note that my key, `W` still exists! Also note that an `IdKeyDict` would
accept mutable (unhashable) objects.
That might be a selling point beyond its "weak" and speed properties.
So we should document that one should not use `KeyedRef`s as key elements
and probably forbid them. For key construction, after weakreffing has
failed, doing a little `isinstance(k,KeyedRef)` shouldn't be so bad
(that's not the code path we really care about anyway)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13387#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
