#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:
-------------------------------------+-------------------------------------
Changes (by vdelecroix):
* status: new => needs_review
* component: PLEASE CHANGE => combinatorics
* dependencies: #19619 =>
* branch: => u/vdelecroix/19620
* milestone: sage-6.10 => sage-6.11
* commit: => 064ec7b1f46e8b531539eab1d57fe548a80fea59
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`.
>
> 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.
>
> In order to have fast slices (i.e. with shared memory), we first need a
> cleanup in `words.py` (see #19619).
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**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
}}}
--
Comment:
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=ca3edb813980105900c9eb737f5b42f8bb224785
ca3edb8]||{{{Trac 19620: one more indirection level}}}||
||[http://git.sagemath.org/sage.git/commit/?id=90eedbe0151edf5deee7f282258edbc849e23b2f
90eedbe]||{{{Trac 19620: datatypes and classes for infinite words}}}||
||[http://git.sagemath.org/sage.git/commit/?id=064ec7b1f46e8b531539eab1d57fe548a80fea59
064ec7b]||{{{Trac 19620: fix cdef -> cpdef and add an example}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/19620#comment:1>
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.
