#18109: Restructure IntegerListLex code
-------------------------------------+-------------------------------------
Reporter: vdelecroix | Owner:
Type: defect | Status: needs_review
Priority: major | Milestone: sage-6.6
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Jeroen Demeyer | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/jdemeyer/ticket/18109 | 9582a7a5248f609a2d2de02497b4b1d36d9dd96e
Dependencies: #18181, #18184 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by nthiery):
Replying to [comment:51 jdemeyer]:
> That's not a fair benchmark, since that's Python, not Cython. The real
benchmark is this:
> {{{
> sage: cython("cdef class A(object): pass")
> sage: cython("from sage.structure.parent cimport Parent\ncdef class
B(Parent): pass")
> sage: timeit("A()", number=10^4, repeat=20)
> 10000 loops, best of 20: 68.9 ns per loop
> sage: timeit("B()", number=10^4, repeat=20)
> 10000 loops, best of 20: 14.5 µs per loop
> }}}
Thanks Vincent and Jeroen. For fairness, we should also initialize the
category. Here it is:
{{{
sage: %timeit B()
The slowest run took 4.13 times longer than the fastest. This could mean
that an intermediate result is being cached
100000 loops, best of 3: 13.3 µs per loop
sage: %timeit B(category=C)
The slowest run took 7.14 times longer than the fastest. This could mean
that an intermediate result is being cached
10000 loops, best of 3: 21.7 µs per loop
}}}
Those benchmarks teach us that constructing a `Parent` costs 24 times
more than a trivial object. Not quite surprising, but it's a
start. Now what I really had in mind was a benchmark in a real use
case, to estimate what's the relative overhead in a typical situation.
Let's take something really trivial:
{{{
sage: sage: %timeit IntegerListsLex(n=1, max_length=1).an_element()
The slowest run took 6.67 times longer than the fastest. This could mean
that an intermediate result is being cached
10000 loops, best of 3: 113 µs per loop
}}}
Now we start to have some concrete ground to start discussions: what
we are speaking about is an overhead of 13% in the case of the most
trivial operation. There probably is some room for improvements in the
initialization of `IntegerListsLex` objects; but not so much either:
there is some unavoidable option parsing and initialization work to
do. Similarly, there may be room for improvement in the initialization
of a `Parent` (I am surprised that initializing the category is
costly, since for a Cython parent it does nothing but set an
attribute). Altogether, the 13% has to be taken with a grain of salt
at this point.
For additional insight, I believe we would be need to have some
typical concrete use case, like the one Vincent has for matrices or
flat surfaces. And see, then, what's the actual overhead. With that,
we will be able to take an informed decision; not just out of fear
that "parents are slow".
Vincent, could you pickup such a situation and make a benchmark?
In general I would like to follow this rule of thumb for our
enumerated sets:
- On one hand, implement super optimized standalone iterators with
bare bone API, whenever there is a proven need for them.
- On the other hand, when modeling an enumerated set, implement it as
a `Parent`s with nice input parsing and a full fledged API; and
typically using the above iterators under the hood.
- Avoid half measures with iterables that are not `Parent`.
Here the situation is a bit delicate since we are in between the
shores: the iterator needs some non trivial parsing and internal
data. Which calls for an intermediate class handling the parsing and
the data storage; is this class meant to model the enumerated set
itself or not?
All that being said, just make your call. I am fine with additional
complexity when there is a proven and worthwhile need for it. And when
someone is willing to pay for the maintenance overhead ...
Cheers,
Nicolas
--
Ticket URL: <http://trac.sagemath.org/ticket/18109#comment:52>
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/d/optout.
