Hi Dan!
On Thu, Feb 10, 2011 at 09:35:08AM -0800, Daniel Bump wrote:
> I am returning to the question of timing issues with #7922.
>
> I recall that for a variety of branching rules, I ran tests
> with and without the test, and obtained the following
> results:
>
> Old Code 48 seconds
> New Code 25 seconds
> Old Code, cache=true 18 seconds
>
> This is copied from the trac ticket.
>
> With the old code, there is an option to cache results of calculations,
> such as multipliciations. The caching is implemented by dictionaries, and
> @cached_method is not used. After #7922, caching is done by default,
>
> A question is therefore whether #8611 improved these results. I can
> investigate this, but I am more concerned about something else,
> unrelated to caching.
>
> Consider the following task:
>
> sage: A2=WeylCharacterRing("A2",style="coroots")
> sage: A7=WeylCharacterRing("A7",style="coroots")
> sage: s = A7.fundamental_weights()[1]
> sage: ad=A2(1,1)
> sage: A7(5*s).branch(A2,rule=branching_rule_from_plethysm(ad,"A7"))
> A2(0,0) + A2(0,3) + 2*A2(1,1) + A2(3,0) + A2(1,4) + 2*A2(2,2) + A2(4,1) +
> A2(2,5) + 2*A2(3,3) + A2(5,2) + A2(4,4) + A2(5,5)
>
> This computes the fifth symmetric power of the 8-dimensional
> adjoint representation of GL(3), decomposing it into irreducibles.
>
> With the old code, caching has no effect on the timing of this:
> on one machine, it takes about 8.8 seconds.
>
> However after applying #7922, the same task takes about 31
> seconds on the same hardware.
>
> This seems unacceptable to me. I think we need to try to understand
> the reason that this is slow before #7922 can be considered.
I just ran your example under the profiler, and looked at the result
with runsnake [1]:
http://sage.math.washington.edu/home/nthiery/runsnake-7922.png
What appears is that about 2/3 of the time is spent computing hash
values of ambient space elements, most likely for cache lookup.
This raises two questions:
- Is it reasonnable that hash is called 4 000 000 times in your
example? Are there huge elements being manipulated?
Btw: looking at _weight_multiplicities, the operation seems to be
something like:
self.linear_combination( (self._irr_weights(k),c) for (k,c) in x )
Right? Beside improving the readability, writing it as such would
make use of Christian's optimizations. This could in particular
possibly reduce a bit the number of hash calls.
- What would be an efficient implementation of hashing for free
module elements? The one you implemented in AmbientSpace is on can
be 10 times faster than the default one provided by SageObject and
using repr. So it would be worth to at least move it up to
CombinatorialFreeModule, if not to optimize it further:
sage: X = CombinatorialFreeModule(ZZ,ZZ)
sage: X.an_element()
3*B[-1] + B[0] + 3*B[1]
sage: x = X.an_element()
sage: %timeit hash(x)
625 loops, best of 3: 46.9 µs per loop
sage: X = RootSystem(["A",7]).ambient_space()
sage: x = X.an_element()
sage: %timeit hash(x)
625 loops, best of 3: 4.82 µs per loop
It could actually make sense to cache it, although just using
cached_method at this point is not worthwhile (but could become so
after further optimization):
sage: %timeit hash(x)
625 loops, best of 3: 15.5 µs per loop
Cheers,
Nicolas
PS: in practice, I did:
sage: import cProfile
sage: tmpfile = "/tmp/sage-runsnake.profile"
sage: cProfile.runctx("... the command to be run ...", globals(), locals(),
filename=tmpfile)
And outside of sage:
> easy_install RunSnakeRun
> runsnakerun /tmp/sage-runsnake.profile
--
Nicolas M. Thiéry "Isil" <nthi...@users.sf.net>
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
