Opened 11 years ago

Closed 8 years ago

#9887 closed defect (worksforme)

slow coercion from integer ring to integer mod ring

Reported by: dmharvey Owned by: tbd
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: performance Keywords: sd51
Cc: Merged in:
Authors: Reviewers: ​Alex Ghitza
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Sage 4.5.3, 2.6GHz Opteron, Linux

sage: R = Integers(3^20)
sage: u = Integer(2)
sage: timeit("z = R(u)")
625 loops, best of 3: 6.84 µs per loop

Why does it take 18000 cycles to convert a tiny integer to an element of R?

Attachments (3)

9887.patch (46.8 KB) - added by roed 10 years ago.
9887_vs_47.patch (46.8 KB) - added by roed 10 years ago.
Apply against 4.7
9887_vs_48a2.patch (46.1 KB) - added by roed 9 years ago.
Apply against 4.8.alpha2

Download all attachments as: .zip

Change History (18)

comment:1 Changed 11 years ago by roed

  • Status changed from new to needs_review

This depends on #7883, #8333, #8334 and #9814. In particular, you first need to apply

333_finite_fields_to_new_coercion.patch
7883_ideals.patch
7883_fixes.patch
7585_9_1_frac_and_coerce_updates.patch
8334_residue_fields-rebased_for_8446.patch
7585_12_1_fixes.patch
9814-2.patch

from those tickets.

On the other hand, it also addresses the speed issues in #9885, #9884, #9883 and #9882. It should also fix #9886: the timings indicate that ZZ.convert_map_from(R) is getting called each time, rather than the morphism being found in the convert_from_hash, and I don't know why this would be the case.

comment:2 Changed 11 years ago by roed

Oops, the top of the dependencies got cut off, and there are newer versions of some of these patches. It should read:

8333_parent_init.patch
8333_finite_fields_to_new_coercion.2.patch
7883_ideals.patch
7883_fixes.patch
7585_9_1_frac_and_coerce_updates.patch
8334_residue_fields-rebased_for_8446.patch
7585_12_1_fixes.patch.2
9814-2.patch

Note that you can find 7585_12_1_fixes.patch and 7585_9_1_frac_and_coerce_updates.patch at #8334.

comment:3 Changed 11 years ago by davidloeffler

  • Milestone set to sage-4.6

I tried the test cases from tickets #9882-#9887 under 4.5.3, under 4.6.alpha2 without this patch, and with this patch. Apologies for the crappy ASCII-art table.

      -------------------------------
      |   4.5.3 |  4.6.a2 | + patch |
-------------------------------------
#9882 | 19.8 µs | 15.9 µs | 3.87 µs |
#9883 | 4.25 ms |  133 µs | 21.5 µs |
#9884 | 1.04 ms |  385 µs |   18 µs |
#9885 | 1.23 µs | 1.24 µs | 1.34 µs |
#9886 | 33.7 µs | 32.5 µs | 32.9 µs |
#9887 | 6.54 µs |  966 ns |  992 ns |
-------------------------------------

So it looks like David's other finite rings patches have already made a dramatic speed improvement to several of these, and the patch on this ticket further improves some of them. The fact that #9885 actually slowed down marginally as a result of the patch is slightly worrying; it might just be random noise, but I did several more runs and the slight slowdowns in #9885 and (to a lesser extent) #9887 seemed quite consistent. It might be a price worth paying for the dramatic speedups elsewhere, but it would be nice if we could avoid it.

I'd be interested to see corresponding timings on other systems.

comment:4 Changed 11 years ago by roed

I'm not sure why there are slight slowdowns for #9885 and #9887. But I did figure out why #9886 was unexpectedly slow: see #10130.

Here are timings on my Macbook Pro (+ patch includes the patch at #10130):

      -------------------------------
      | 4.3.rc0 |  4.6.a2 | + patch |
-------------------------------------
#9882 | 19.9 µs |   15 µs | 3.71 µs |
#9883 | 4.34 ms |  117 µs | 20.2 µs |
#9884 | 3.79 ms |  314 µs | 30.7 µs |
#9885 | 1.22 µs |  850 ns |  938 ns |
#9886 | 9.99 µs | 33.4 µs |  264 ns |
#9887 |    ? µs |  787 ns |  814 ns |
-------------------------------------

I got a range of values for #9885 in the middle column, from 835ns to 1.07µs.

I wanted to check 9.99µs in the first column in a different branch, so rebuilt only to discover that that copy of sage was built when I had an earlier version of OS X and was thus running 32 bit...

comment:5 Changed 10 years ago by kedlaya

  • Status changed from needs_review to needs_work

This patch fails to apply against 4.7:

cd "/home/kedlaya/Downloads/sage-4.7/devel/sage" && hg import   "/home/kedlaya/Downloads/9887.patch"
applying /home/kedlaya/Downloads/9887.patch
patching file sage/rings/finite_rings/integer_mod.pxd
Hunk #1 succeeded at 12 with fuzz 1 (offset 0 lines).
patching file sage/rings/polynomial/polynomial_ring.py
Hunk #7 FAILED at 1246
1 out of 13 hunks FAILED -- saving rejects to file sage/rings/polynomial/polynomial_ring.py.rej
abort: patch failed to apply

Changed 10 years ago by roed

comment:6 Changed 10 years ago by roed

  • Status changed from needs_work to needs_review

It should apply against 4.7.1.alpha4.

comment:7 Changed 10 years ago by roed

For patchbot (and others working against 4.7), apply 9887_vs_47.patch only.

Changed 10 years ago by roed

Apply against 4.7

comment:8 Changed 9 years ago by jason

What is the status of this patch now? It looks like it could easily bit-rot (if it hasn't already).

Changed 9 years ago by roed

Apply against 4.8.alpha2

comment:9 Changed 9 years ago by roed

Apply only 9887_vs_48a2.patch

comment:10 Changed 9 years ago by davidloeffler

  • Dependencies set to 11900
  • Reviewers set to PatchBot
  • Status changed from needs_review to needs_work
  • Work issues set to needs rebase

This does not apply to the current beta, as it conflicts with #9138 and #11900, so I'm afraid it will need yet another rebase.

comment:11 Changed 9 years ago by davidloeffler

  • Dependencies changed from 11900 to #11900

comment:12 Changed 8 years ago by tscrim

  • Status changed from needs_work to needs_info

There is at least some partial work on this done in 5.7.beta3:

sage: R = Integers(3^20)
sage: u = Integer(2)
sage: %timeit z = R(u)
100000 loops, best of 3: 1.48 us per loop
sage: %timeit z = R(u)
1000000 loops, best of 3: 1.74 us per loop

So should we close this ticket?

Edit - I'm running this test on my Ubuntu VM while video chatting on Skype in my Host OS.

Last edited 8 years ago by tscrim (previous) (diff)

comment:13 Changed 8 years ago by AlexGhitza

  • Dependencies #11900 deleted
  • Keywords sd51 added
  • Reviewers PatchBot deleted
  • Status changed from needs_info to positive_review
  • Work issues needs rebase deleted

I second the request to close the ticket. On sage-5.10:

sage: R = Integers(3^20)
sage: u = Integer(2)
sage: %timeit("z = R(u)")
10000000 loops, best of 3: 24.6 ns per loop
sage: %timeit("z = ZZ(u)")
10000000 loops, best of 3: 24.5 ns per loop

In other words, putting u into R takes the same time as putting u into ZZ (where it is already). It shouldn't be possible to do any better.

I'll tag this as "positive review" to bring it to the release manager's attention.

comment:14 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-duplicate/invalid/wontfix
  • Reviewers set to ​Alex Ghitza

comment:15 Changed 8 years ago by jdemeyer

  • Resolution set to worksforme
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.