#15820: Implement sequences of bounded integers
-------------------------------------+-------------------------------------
Reporter: SimonKing | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.3
Component: algebra | Resolution:
Keywords: sequence bounded | Merged in:
integer | Reviewers:
Authors: Simon King | Work issues: Use mpn_* for speedup
Report Upstream: N/A | of iteration and item access
Branch: | Commit:
u/SimonKing/ticket/15820 | 735939e593c9c302ff42c4973cbfe2e48eb22644
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by SimonKing):
* status: needs_work => needs_review
Comment:
Using the `mpn_*` function was a very good idea. Some basic operations are
a lot faster now. Here I am repeating (and slightly extending) my earlier
benchmarks for those operations that have changed in the recent commits:
__The test bed__
{{{
sage: from sage.misc.bounded_integer_sequences import
BoundedIntegerSequence
sage: L0 = [randint(0,7) for i in range(5)]
sage: L1 = [randint(0,15) for i in range(15)]
sage: L2 = [randint(0,31) for i in range(50)]
sage: L3 = [randint(0,31) for i in range(5000)]
sage: T0 = tuple(L0); T1 = tuple(L1); T2 = tuple(L2); T3 = tuple(L3)
sage: S0 = BoundedIntegerSequence(8, L0)
sage: S1 = BoundedIntegerSequence(16, L1)
sage: S2 = BoundedIntegerSequence(32, L2)
sage: S3 = BoundedIntegerSequence(32, L3)
}}}
__Conversion list -> tuple/sequence__
{{{
sage: %timeit x = tuple(L0)
1000000 loops, best of 3: 307 ns per loop
sage: %timeit x = tuple(L1)
1000000 loops, best of 3: 369 ns per loop
sage: %timeit x = tuple(L2)
1000000 loops, best of 3: 534 ns per loop
sage: %timeit x = tuple(L3)
10000 loops, best of 3: 19.6 µs per loop
sage: %timeit x = BoundedIntegerSequence(8, L0)
1000000 loops, best of 3: 1.34 µs per loop
sage: %timeit x = BoundedIntegerSequence(16, L1)
1000000 loops, best of 3: 1.57 µs per loop
sage: %timeit x = BoundedIntegerSequence(32, L2)
100000 loops, best of 3: 2.06 µs per loop
sage: %timeit x = BoundedIntegerSequence(32, L3)
10000 loops, best of 3: 76.7 µs per loop
}}}
Conversion to a tuple seems to be roughly 4 times faster. But I don't
think this will be critical (at least not in my own applications...)
__Conversion tuple/sequence -> list__
{{{
sage: %timeit x = list(T0)
1000000 loops, best of 3: 537 ns per loop
sage: %timeit x = list(T1)
1000000 loops, best of 3: 624 ns per loop
sage: %timeit x = list(T2)
1000000 loops, best of 3: 752 ns per loop
sage: %timeit x = list(T3)
100000 loops, best of 3: 22.6 µs per loop
sage: %timeit x = list(S0)
1000000 loops, best of 3: 1.58 µs per loop
sage: %timeit x = list(S1)
100000 loops, best of 3: 2.06 µs per loop
sage: %timeit x = list(S2)
100000 loops, best of 3: 4.19 µs per loop
sage: %timeit x = list(S3)
1000 loops, best of 3: 253 µs per loop
sage: %timeit x = S0.list()
1000000 loops, best of 3: 1.05 µs per loop
sage: %timeit x = S1.list()
1000000 loops, best of 3: 1.87 µs per loop
sage: %timeit x = S2.list()
100000 loops, best of 3: 4.95 µs per loop
sage: %timeit x = S3.list()
1000 loops, best of 3: 306 µs per loop
}}}
The gap between lists and sequences strongly depends on the bound of the
sequence, which is not much of a surprise. Anyway, it is faster than
before.
__Slicing__
For step 1, short tuples are faster than short sequences, but long
sequences are faster than long tuples:
{{{
sage: timeit("x=T0[:-1]", number=100000)
100000 loops, best of 3: 479 ns per loop
sage: timeit("x=T1[:-1]", number=100000)
100000 loops, best of 3: 548 ns per loop
sage: timeit("x=T2[:-1]", number=100000)
100000 loops, best of 3: 773 ns per loop
sage: timeit("x=T3[:-1]", number=100000)
100000 loops, best of 3: 19.6 µs per loop
sage: timeit("x=S0[:-1]", number=100000)
100000 loops, best of 3: 1.75 µs per loop
sage: timeit("x=S1[:-1]", number=100000)
100000 loops, best of 3: 1.8 µs per loop
sage: timeit("x=S2[:-1]", number=100000)
100000 loops, best of 3: 1.77 µs per loop
sage: timeit("x=S3[:-1]", number=100000)
100000 loops, best of 3: 2.4 µs per loop
}}}
As before, a step different from 1 is bad for sequences. However, there is
an improvement compared with the previous timings:
{{{
sage: timeit("x=T2[:-1:2]", number=100000)
100000 loops, best of 3: 944 ns per loop
sage: timeit("x=T3[:-1:2]", number=100000)
100000 loops, best of 3: 11.8 µs per loop
sage: timeit("x=S2[:-1:2]", number=10000)
10000 loops, best of 3: 2.7 µs per loop
sage: timeit("x=S3[:-1:2]", number=10000)
10000 loops, best of 3: 52.2 µs per loop
}}}
__Accessing single items__
Bounded integer sequences can now compete with tuples, both short and
long!
{{{
sage: timeit("x=T0[1]", number=1000000)
1000000 loops, best of 3: 349 ns per loop
sage: timeit("x=T0[4]", number=1000000)
1000000 loops, best of 3: 351 ns per loop
sage: timeit("x=S0[1]", number=1000000)
1000000 loops, best of 3: 354 ns per loop
sage: timeit("x=S0[4]", number=1000000)
1000000 loops, best of 3: 355 ns per loop
sage: timeit("x=T3[1]", number=1000000)
1000000 loops, best of 3: 346 ns per loop
sage: timeit("x=T3[4500]", number=1000000)
1000000 loops, best of 3: 347 ns per loop
sage: timeit("x=S3[1]", number=1000000)
1000000 loops, best of 3: 350 ns per loop
sage: timeit("x=S3[4500]", number=1000000)
1000000 loops, best of 3: 370 ns per loop
}}}
__Containment tests__
Here we talk about operations that do not exist in this form for tuples
(e.g., subsequence tests). They have been improved by the latest commits:
{{{
sage: L0x = [randint(0,7) for i in range(5)]
sage: L1x = [randint(0,15) for i in range(15)]
sage: L2x = [randint(0,31) for i in range(50)]
sage: L3x = [randint(0,31) for i in range(5000)] # verified that they
differ from L0,L1,L2,L3
sage: S0x = BoundedIntegerSequence(8, L0x)
sage: S1x = BoundedIntegerSequence(16, L1x)
sage: S2x = BoundedIntegerSequence(32, L2x)
sage: S3x = BoundedIntegerSequence(32, L3x)
sage: S1y = BoundedIntegerSequence(16, L1)
sage: S2y = BoundedIntegerSequence(32, L2)
sage: S3y = BoundedIntegerSequence(32, L3)
sage: S1y==S1!=S1x, S1y is not S1
(True, True)
sage: S0z1 = S0+S0
sage: S0z2 = S0+S0x
sage: S1z1 = S1+S1
sage: S1z2 = S1+S1x
sage: S2z1 = S2+S2
sage: S2z2 = S2+S2x
sage: S3z1 = S3+S3
sage: S3z2 = S3+S3x
sage: timeit("S0z2.startswith(S0)", number=1000000)
1000000 loops, best of 3: 230 ns per loop
sage: timeit("S0z2.startswith(S0x)", number=1000000)
1000000 loops, best of 3: 236 ns per loop
sage: timeit("S0x in S0z2", number=1000000)
1000000 loops, best of 3: 511 ns per loop
sage: timeit("S1z2.startswith(S1)", number=1000000)
1000000 loops, best of 3: 215 ns per loop
sage: timeit("S1z2.startswith(S1x)", number=1000000)
1000000 loops, best of 3: 219 ns per loop
sage: timeit("S1x in S1z2", number=1000000)
1000000 loops, best of 3: 692 ns per loop
sage: timeit("S2z2.startswith(S2)", number=1000000)
1000000 loops, best of 3: 238 ns per loop
sage: timeit("S2z2.startswith(S2x)", number=1000000)
1000000 loops, best of 3: 228 ns per loop
sage: timeit("S2x in S2z2", number=1000000)
1000000 loops, best of 3: 1.92 µs per loop
sage: timeit("S3z2.startswith(S3)", number=1000000)
1000000 loops, best of 3: 981 ns per loop
sage: timeit("S3z2.startswith(S3x)", number=1000000)
1000000 loops, best of 3: 213 ns per loop
sage: timeit("S3x in S3z2", number=1000)
1000 loops, best of 3: 2.41 ms per loop
}}}
__Conclusion__
- Slicing and iteration are still a weak point of bounded integer
sequences. However, there is an improvement by the latest commits.
- Access to single items is now competitive. Some other operations have
been competitive or superior before.
- Probably iteration and slicing could be improved with more complicated
code: Currently, I take a single item, do a bitshift (which is faster than
before!) and then proceed with the next item. But since several items
usually fit into one "limb" (this is how GMP stores the data), it would be
possible to accumulate a group of items into one limb, then do a
''single'' bitshift for this group of items, and then proceed to the next
group of items. I would consider to implement it if my own applications
show the need for it...
Needs review, I think! Please check if I produced a memory leak (by not
freeing allocated temporary data), a memory corruption (by messing up in
the case of items that are stored exactly on the seam between two limbs),
or functions in which a memory error or keyboard interrupt would not be
propagated. I plan to do such tests, too, but I suppose 4 or 6 eyes see
more than 2.
--
Ticket URL: <http://trac.sagemath.org/ticket/15820#comment:71>
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.
