Re: [sage-devel] overhead in creating p-adic elements
So, I have a patch up at #9814 which improves the situation. One thing to note is that addition actually puts off the mpz_remove until later: the x you obtain from x = y + z has x._normalized = False, so that repeated additions don't require multiple mpz_removes. You can argue with this design decision, but it's the way things work at the moment, and contributed to the difference in speed David observed. But I've eliminated most of the other overhead by implementing explicit morphisms from ZZ and QQ to base p-adic rings and fields. On my machine the timings now look like: sage: K = Qp(13, 5) sage: y = K(10) sage: z = K(20) sage: timeit(x = y * z) 625 loops, best of 3: 368 ns per loop sage: timeit(x = y + z) 625 loops, best of 3: 354 ns per loop Note that for me, the cost of an empty cpdef'd function call the returns its input is 190 ns, adding a PY_NEW to that adds 90 ns, and adding an mpz_init adds another 65 ns. I'm actually not quite sure why these arithmetic operations are as fast as they are, given these timings... sage: timeit(x = K(4)) 625 loops, best of 3: 1.91 µs per loop sage: a = 4 sage: timeit(x = K(a)) 625 loops, best of 3: 1.62 µs per loop sage: f = K.coerce_map_from(ZZ) sage: timeit(x = f(a)) 625 loops, best of 3: 938 ns per loop sage: timeit(x = f._call_(a)) 625 loops, best of 3: 870 ns per loop Most of this time is now going to an mpz_remove, which we can't get rid of. Anyway, patch ready for review. David On Fri, Aug 13, 2010 at 3:31 PM, David Harvey dmhar...@cims.nyu.edu wrote: Hi, sage: K = Qp(13, 5) sage: 13^5 371293 sage: y = K(10) sage: z = K(20) sage: timeit(x = y * z) 625 loops, best of 3: 961 ns per loop # varies a bit but this is typical sage: timeit(x = y + z) 625 loops, best of 3: 942 ns per loop # ditto That's the cost of arithmetic. Pretty slow in my opinion, but anyway. Here is the real problem: sage: timeit(x = K(4)) 625 loops, best of 3: 22.6 µs per loop sage: y = int(4) sage: timeit(x = K(y)) 625 loops, best of 3: 23.2 µs per loop sage: from sage.rings.padics.padic_capped_relative_element import pAdicCappedRelativeElement sage: timeit(x = pAdicCappedRelativeElement(K, 4)) 625 loops, best of 3: 17.6 µs per loop So there seems to be serious overhead in several places. Note that the cost cannot be in determining the valuation, since the simple x = y + z would have to do that too. I ran into this while trying to multiply a p-adic by an integer: sage: y = K(10) sage: z = 20 sage: timeit(x = y * z) 625 loops, best of 3: 23.9 µs per loop Is there an easy way to fix this? david -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.comsage-devel%2bunsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] overhead in creating p-adic elements
So, I haven't looked at profiling for p-adics for quite a while. But one way to speed up this kind of item creation is to implement a morphism from ZZ to Qp and then write a super-fast _call_ method. I can't do it right now, but I can provide advice if someone else wants to. David On Fri, Aug 13, 2010 at 1:31 PM, David Harvey dmhar...@cims.nyu.edu wrote: Hi, sage: K = Qp(13, 5) sage: 13^5 371293 sage: y = K(10) sage: z = K(20) sage: timeit(x = y * z) 625 loops, best of 3: 961 ns per loop # varies a bit but this is typical sage: timeit(x = y + z) 625 loops, best of 3: 942 ns per loop # ditto That's the cost of arithmetic. Pretty slow in my opinion, but anyway. Here is the real problem: sage: timeit(x = K(4)) 625 loops, best of 3: 22.6 µs per loop sage: y = int(4) sage: timeit(x = K(y)) 625 loops, best of 3: 23.2 µs per loop sage: from sage.rings.padics.padic_capped_relative_element import pAdicCappedRelativeElement sage: timeit(x = pAdicCappedRelativeElement(K, 4)) 625 loops, best of 3: 17.6 µs per loop So there seems to be serious overhead in several places. Note that the cost cannot be in determining the valuation, since the simple x = y + z would have to do that too. I ran into this while trying to multiply a p-adic by an integer: sage: y = K(10) sage: z = 20 sage: timeit(x = y * z) 625 loops, best of 3: 23.9 µs per loop Is there an easy way to fix this? david -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.comsage-devel%2bunsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] overhead in creating p-adic elements
Hi, sage: K = Qp(13, 5) sage: 13^5 371293 sage: y = K(10) sage: z = K(20) sage: timeit(x = y * z) 625 loops, best of 3: 961 ns per loop # varies a bit but this is typical sage: timeit(x = y + z) 625 loops, best of 3: 942 ns per loop # ditto That's the cost of arithmetic. Pretty slow in my opinion, but anyway. Here is the real problem: sage: timeit(x = K(4)) 625 loops, best of 3: 22.6 µs per loop sage: y = int(4) sage: timeit(x = K(y)) 625 loops, best of 3: 23.2 µs per loop sage: from sage.rings.padics.padic_capped_relative_element import pAdicCappedRelativeElement sage: timeit(x = pAdicCappedRelativeElement(K, 4)) 625 loops, best of 3: 17.6 µs per loop So there seems to be serious overhead in several places. Note that the cost cannot be in determining the valuation, since the simple x = y + z would have to do that too. I ran into this while trying to multiply a p-adic by an integer: sage: y = K(10) sage: z = 20 sage: timeit(x = y * z) 625 loops, best of 3: 23.9 µs per loop Is there an easy way to fix this? david -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org