#19620: fast (lazy) infinite words
-------------------------------------+-------------------------------------
Reporter: vdelecroix | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.11
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Vincent Delecroix | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/vdelecroix/19620 | 064ec7b1f46e8b531539eab1d57fe548a80fea59
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Description changed by vdelecroix:
Old description:
> In order to have fast infinite words, we implement a new class
> `WordDatatype_char_infinite` that uses an `unsigned char *` as data. It
> lazily updates this cache on demand. The previous `WordDatatype_char` is
> renamed `WordDatatype_char_finite`. With this branch we have several
> predefined classes
>
> - `WordDatatype_iter_char`
> - `WordDatatype_callable_char`
> - `WordDatatype_substitutive_char`
>
> And it is very simple to create a new class for a word by inheritance
> (either in Python or Cython) from `WordDatatype_char_infinite`.
>
> As a prerequisite, we need to add one indirection level for finite words
> (i.e. use an `unsigned char **` instead of an `unsigned char *`) as the
> data pointed by an infinite word might be reallocated.
>
> Some timings with the develop branch
> {{{
> sage: w = WordMorphism({0: [0,1], 1:[0]}).fixed_point(0)
> sage: %time w[2**20]
> > 2 min (still waiting)
> sage: %timeit w[:2**15]
> 100 loops, best of 3: 1.99 ms per loop
> sage: %timeit w[:2**16]
> 1 loops, best of 3: 5.56 ms per loop
> sage: %timeit w[:2**17]
> 1 loops, best of 3: 7.84 ms per loop
> sage: %timeit w[:2**18]
> 1 loops, best of 3: 19.6 ms per loop
> }}}
> while with the uplodaded one
> {{{
> sage: w = WordMorphism({0:[0,1], 1:[0]}).fixed_point(0)
> sage: %time w[2**20]
> CPU times: user 16 ms, sys: 0 ns, total: 16 ms
> Wall time: 18.3 ms
> 1
> sage: %timeit w[:2**15]
> 1000000 loops, best of 3: 905 ns per loop
> sage: %timeit w[:2**16]
> 1000000 loops, best of 3: 907 ns per loop
> sage: %timeit w[:2**17]
> 1000000 loops, best of 3: 910 ns per loop
> sage: %timeit w[:2**18]
> 1000000 loops, best of 3: 909 ns per loop
> }}}
New description:
In order to have fast infinite words, we implement a new class
`WordDatatype_char_infinite` that uses an `unsigned char *` as data. It
lazily updates this cache on demand. The previous `WordDatatype_char` is
renamed `WordDatatype_char_finite`. With this branch we have several
predefined classes
- `WordDatatype_iter_char`
- `WordDatatype_callable_char`
- `WordDatatype_substitutive_char`
And it is very simple to create a new class for a word by inheritance
(either in Python or Cython) from `WordDatatype_char_infinite`.
As a prerequisite, we need to add one indirection level for finite words
(i.e. use an `unsigned char **` instead of an `unsigned char *`) as the
data pointed by an infinite word might be reallocated.
Some timings with the develop branch
{{{
sage: w = WordMorphism({0: [0,1], 1:[0]}).fixed_point(0)
sage: %time w[2**15]
CPU times: user 1.26 s, sys: 16 ms, total: 1.27 s
Wall time: 1.23 s
sage: w = WordMorphism({0: [0,1], 1:[0]}).fixed_point(0)
sage: %time w[2**16]
CPU times: user 4.58 s, sys: 24 ms, total: 4.6 s
Wall time: 4.48 s
sage: w = WordMorphism({0: [0,1], 1:[0]}).fixed_point(0)
sage: %time w[2**17]
CPU times: user 21.7 s, sys: 28 ms, total: 21.8 s
Wall time: 21.7 s
}}}
while on `u/vdelecroix/19620` we have
{{{
sage: w = WordMorphism({0:[0,1], 1:[0]}).fixed_point(0)
sage: %time w[2**20]
CPU times: user 16 ms, sys: 0 ns, total: 16 ms
Wall time: 18.3 ms
}}}
Moreover, since the finite slices now shares with the infinite words it is
very fast to get the prefixes. On develop we had
{{{
sage: W = InfiniteWords([0,1])
sage: w = W(lambda n: Integer(n).popcount()%2)
sage: %time w[2**16]
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 169 µs
sage: %timeit w[:2**16]
10 loops, best of 3: 50.3 ms per loop
}}}
while on `u/vdelecroix/19620`
{{{
sage: W = InfiniteWords([0,1])
sage: w = W(lambda n: Integer(n).popcount()%2)
sage: %time w[2**16]
CPU times: user 60 ms, sys: 12 ms, total: 72 ms
Wall time: 61.2 ms
sage: %timeit w[:2**16]
1000000 loops, best of 3: 913 ns per loop
}}}
Note that however the call to `w[2**16]` is slower in the new version. The
reason is that this computation actually caches '''all''' letters up to
`w[2**16]`.
--
--
Ticket URL: <http://trac.sagemath.org/ticket/19620#comment:2>
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 https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
