#15367: Empty lists while creating parents
---------------------------+-------------------------
Reporter: roed | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-5.13
Component: memleak | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
---------------------------+-------------------------
Comment (by nbruin):
Replying to [comment:15 SimonKing]:
> So, do you think we should have `MonoDict` and `TripleDict` for hard-
coded key length and then (on a different ticket?) `KeytupleDict` for
arbitrary fixed key length?
I do not think so. With the previous code you had a prototype that
performed well and offered this feature and we didn't put it in. That
suggests to me we don't have a need for it.
In any case, If you would do this I don't think you'd want to add an extra
layer of indirection in the key fields. Hence, you'd have a dynamic length
structure:
{{{
cdef struct tuple_cell:
void* key_ids[length]
PyObject* key_weakrefs[length]
PyObject* value
}}}
which of course you cannot define, but you need the sizeof, which should
fairly safely be `sizeofcell=(2*length+1)*sizeof(void*)` Then you can have
your table allocated as
{{{
table=<void**>PyMem_Malloc(newsize * sizeofcell)
}}}
and addressing entry `i` would be addressed as
{{{
cursor=<void**>&(table[(i&mask)*(2*length+1)])
key_id1=cursor[0]
key_id2=cursor[1]
key_wr1=<PyObject*> cursor[length]
key_wr2=<PyObject*> cursor[length+1]
value =<PyObject*> cursor[2*length]
}}}
One problem with open addressing is that it has no cache locality at all.
That's not a huge problem if the table is compact (and your hits are
almost always immediate). Since the weakrefs and value are only used for
validation, not searching, you could consider storing 'those' under an
indirection.
I think we should only generalize the design if we know we have a need for
it. I think first we should establish if this implementation is really an
advantage, if the hash functions perform well, and if the resizing amount
is reasonable.
One way would be to let lookup keep statistics:
- number of iterations needed
- mask,fill,used statistics
and perhaps also for the dictionaries themselves:
- calls to resize
- calls to iteritems (especially with what mask:used:fill ratio that gets
called)
See: [http://code.activestate.com/recipes/578375/] for a proposal that
makes a much more compact search table with compact iteration.
And as well: profiling data on how much time one typically in this code.
If that's 2%, even doubling the speed would not have much effect. We may
be hitting this code fairly often, but it's still pretty specialized: not
like a `dict` of which several get queried for any method lookup.
--
Ticket URL: <http://trac.sagemath.org/ticket/15367#comment:16>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
