#6208: [with patch, needs review] Improving gap interface by pre-compiling
certain
regular expressions
-------------------------+--------------------------------------------------
Reporter: SimonKing | Owner: SimonKing
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.0.2
Component: interfaces | Keywords: gap interface expect regular expression
-------------------------+--------------------------------------------------
At http://groups.google.com/group/sage-
support/browse_thread/thread/657ef562de60fc6a
Jerome pointed out that the built in comparison of permutation groups
sometimes is rather sluggish compared with comparison of their lists of
elements.
While trying to find a reason, I found that the method ``_execute_line``
of the gap interface makes a non-optimal use of regular expressions: One
and the same pattern is compiled over and over again.
I did not succeed to solve the poster's original concern. But at least I
could speed up the gap interface.
Without the patch, I had
{{{
----------------------------------------------------------------------
| Sage Version 4.0, Release Date: 2009-05-29 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: G=SymmetricGroup(7)
sage: time L=[X for X in G if X.order()==2]
CPU times: user 10.19 s, sys: 2.12 s, total: 12.31 s
Wall time: 15.48 s
}}}
With the patch, I have
{{{
----------------------------------------------------------------------
| Sage Version 4.0, Release Date: 2009-05-29 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
Loading Sage library. Current Mercurial branch is: expect-devel
sage: G=SymmetricGroup(7)
sage: time L=[X for X in G if X.order()==2]
CPU times: user 4.02 s, sys: 0.17 s, total: 4.19 s
Wall time: 6.13 s
}}}
__How does the patch work?__
The method ``_execute_line`` contains a ``while`` loop. In the loop, the
expect interface is called, searching for one long and one short pattern.
Without my patch, ``expect`` would compile the two patterns over and over
again. With my patch, the patterns will be compiled ''once'' (I think the
``_start`` method is an appropriate place), stored as attributes, and then
``expect_list`` is called without the need to re-compile the patterns.
Here is another evidence that it works. Without the patch:
{{{
sage: gap._start()
sage: prun gap._execute_line('b:=1;')
3258 function calls (3243 primitive calls) in 0.015 CPU seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
26 0.001 0.000 0.010 0.000 sre_compile.py:501(compile)
26 0.001 0.000 0.002 0.000
sre_compile.py:367(_compile_info)
26 0.001 0.000 0.003 0.000 sre_parse.py:385(_parse)
7 0.001 0.000 0.001 0.000
sre_compile.py:213(_optimize_charset)
15 0.001 0.000 0.001 0.000 {select.select}
1 0.001 0.001 0.001 0.001 {method 'clear' of 'dict'
objects}
8 0.001 0.000 0.003 0.000 pexpect.py:914(expect_list)
186 0.001 0.000 0.001 0.000 sre_parse.py:188(__next)
83 0.001 0.000 0.011 0.000 re.py:227(_compile)
36/31 0.001 0.000 0.001 0.000 sre_parse.py:146(getwidth)
31/26 0.000 0.000 0.002 0.000 sre_compile.py:38(_compile)
657 0.000 0.000 0.000 0.000 {method 'append' of 'list'
objects}
8 0.000 0.000 0.012 0.001
pexpect.py:815(compile_pattern_list)
26 0.000 0.000 0.004 0.000 sre_parse.py:669(parse)
156 0.000 0.000 0.001 0.000 sre_parse.py:207(get)
656/651 0.000 0.000 0.000 0.000 {len}
...
}}}
With the patch:
{{{
sage: gap._start()
sage: prun gap._execute_line('b:=1;')
478 function calls in 0.006 CPU seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
15 0.004 0.000 0.004 0.000 {select.select}
8 0.001 0.000 0.005 0.001 pexpect.py:914(expect_list)
15 0.000 0.000 0.004 0.000
pexpect.py:498(read_nonblocking)
188 0.000 0.000 0.000 0.000 {built-in method search}
15 0.000 0.000 0.000 0.000 {posix.read}
1 0.000 0.000 0.006 0.006 gap.py:573(_execute_line)
15 0.000 0.000 0.000 0.000 pexpect.py:739(isalive)
30 0.000 0.000 0.000 0.000 {posix.waitpid}
1 0.000 0.000 0.000 0.000
sre_compile.py:367(_compile_info)
1 0.000 0.000 0.000 0.000 sre_compile.py:501(compile)
2 0.000 0.000 0.000 0.000 {posix.write}
2 0.000 0.000 0.000 0.000 re.py:227(_compile)
2 0.000 0.000 0.000 0.000 pexpect.py:656(send)
1 0.000 0.000 0.000 0.000 sre_parse.py:385(_parse)
32 0.000 0.000 0.000 0.000 {built-in method start}
1 0.000 0.000 0.006 0.006 <string>:1(<module>)
25 0.000 0.000 0.000 0.000 {method 'append' of 'list'
objects}
2 0.000 0.000 0.000 0.000
pexpect.py:815(compile_pattern_list)
1 0.000 0.000 0.000 0.000 sre_parse.py:146(getwidth)
15 0.000 0.000 0.000 0.000 {method 'find' of 'str'
objects}
2 0.000 0.000 0.004 0.002 pexpect.py:855(expect)
8 0.000 0.000 0.000 0.000 {method 'index' of 'list'
objects}
5 0.000 0.000 0.000 0.000 sre_parse.py:188(__next)
15 0.000 0.000 0.000 0.000 {method 'lower' of 'str'
objects}
1 0.000 0.000 0.000 0.000 sre_parse.py:669(parse)
2 0.000 0.000 0.000 0.000 {time.sleep}
1 0.000 0.000 0.000 0.000 sre_compile.py:486(_code)
20 0.000 0.000 0.000 0.000 {len}
...
}}}
Now I am curious what ``select.select`` refers to. But I think the
improvement is clear.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6208>
Sage <http://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 post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
