[sage-devel] trying to speed up construction of sets in setpartition

['Martin R' via sage-devel]

In https://trac.sagemath.org/ticket/23873 I was innocently trying to be 
mathematically correct and let the method to_noncrossing_partition of 
DyckWords return a set partition, instead of a nested list.

Christian warned me that there might be a performance penalty.  He was 
right, with the patch 90% of the time is spent in constructing the set 
partition from the list of lists.

With https://trac.sagemath.org/ticket/23877 I modify SetPartition to 
actually use the parameter check=False, which then skips the containment 
check.  This saves some of the time, but not all that much.

The problem is actually, that creating a "Set" is awfully slow.  I am 
afraid (and I really hope that I am wrong) that this is because creating a 
parent is very time consuming.

Can someone enlighten me?

Martin

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] trying to speed up construction of sets in setpartition

[Maarten Derickx]

Hi Martin,

Creating a parent might be time consuming the first time. But it should be 
cashed so if you recreate the same parent over and over only the first one 
should be slow. To test whether caching is working for your parent create it 
twice with the same parameters and test whether 'parent1 is parent2' evaluates 
to true.

If you are creating a lot of distinct parents then it is a more difficult 
problem

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: trying to speed up construction of sets in setpartition

['Martin R' via sage-devel]

I must admit that I don't really know what parents are created.  A profile 
is at https://trac.sagemath.org/ticket/23877 


How could I find out?

Am Montag, 18. September 2017 10:17:09 UTC+2 schrieb Maarten Derickx:
>
> Hi Martin,
>
> Creating a parent might be time consuming the first time. But it should be 
> cashed so if you recreate the same parent over and over only the first one 
> should be slow. To test whether caching is working for your parent create 
> it twice with the same parameters and test whether 'parent1 is parent2' 
> evaluates to true.
>
> If you are creating a lot of distinct parents then it is a more difficult 
> problem
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Faster way to load python code

[Dima Pasechnik]

On Sunday, September 17, 2017 at 10:57:18 AM UTC+1, Simon King wrote:
>
> Hi Dima, 
>
> On 2017-09-17, Dima Pasechnik > wrote: 
> > Isn't it what pickle/cPickle is for? 
>
> I don't want to store data, I want to read them. And I am not the 
> one who stored them. So, I have to take the textfiles as I get 
> them. 
>

loading Python/Sage code is slow. Surely it should be possible to load 
libGAP data, 
and use it to create the necessary Python data in memory.
In particular I suppose you want to bypass Sage generic matrices, and
directly build the matrices you need in Cython...


 

>
> Cheers, 
> Simon 
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: yet another sage-python performance puzzle

[Jeroen Demeyer]

On 2017-09-16 03:31, Nils Bruin wrote:

So if you're finding you can't put a "from A import a" at the top-level
and using it locally has noticeable cost (which can easily happen:
imports have a significant cost, even for modules that are already
present), then you could try to do a straight import and access the
appropriate namespace.


But accessing the namespace is also slower than doing the "from ... 
import ..." import:


sage: x = 42
sage: timeit("sage.structure.element.parent(x)", number=20, repeat=10^6)
20 loops, best of 100: 143 ns per loop
sage: timeit("parent(x)", number=20, repeat=10^6)
20 loops, best of 100: 47.7 ns per loop


--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: yet another sage-python performance puzzle

[Jeroen Demeyer]

On 2017-09-15 21:48, Travis Scrimshaw wrote:



On Friday, September 15, 2017 at 2:31:05 PM UTC-5, Maarten Derickx wrote:

Is it assymptotically 10% or is it 10% for the case in which you are
testing it? In the first case I would be surprised in the second
case it is not that weird.

See the late_import function in src/sage/rings/complex_field.py for
how you can speed up the import statement for the cyclic import case.

Probably most of that should be reduced to necessary lazy_import's or
local imports...


lazy_import doesn't work with Cython. I tried to fix that in 
https://trac.sagemath.org/ticket/22752 but it got rejected. I am still a 
bit disappointed with this: I tried to fix an actual problem. Now the 
actual problem still remains.


--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Faster way to load python code

[Simon King]

Hi all!

On 2017-09-18, Dima Pasechnik  wrote:
> loading Python/Sage code is slow. Surely it should be possible to load 
> libGAP data, 
> and use it to create the necessary Python data in memory.
> In particular I suppose you want to bypass Sage generic matrices, and
> directly build the matrices you need in Cython...

OK, the replies people gave strongly indicate that it would be a bad idea
to try to read the text file directly into Sage. So, I should keep using
libgap to read the file, followed by a translation (of course using Cython)
into Sage and re-saving the data in a binary format.

Thanks!
Simon

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: trying to speed up construction of sets in setpartition

[Maarten Derickx]

The parents being created are the same in your case:

sage: S = SetPartition([[2,3],[1]], check=False)
sage: S
{{1}, {2, 3}}
sage: S.parent()
Set partitions
sage: S2 = SetPartition([[2,3],[1,4]], check=False)
sage: S.parent() is S2.parent()

but I see on trac that you now have Simon King also looking at it. He 
should know everything you need to know about the category framework and 
more.

On Monday, 18 September 2017 10:20:50 UTC+2, Martin R wrote:
>
> I must admit that I don't really know what parents are created.  A profile 
> is at https://trac.sagemath.org/ticket/23877 
> 
>
> How could I find out?
>
> Am Montag, 18. September 2017 10:17:09 UTC+2 schrieb Maarten Derickx:
>>
>> Hi Martin,
>>
>> Creating a parent might be time consuming the first time. But it should 
>> be cashed so if you recreate the same parent over and over only the first 
>> one should be slow. To test whether caching is working for your parent 
>> create it twice with the same parameters and test whether 'parent1 is 
>> parent2' evaluates to true.
>>
>> If you are creating a lot of distinct parents then it is a more difficult 
>> problem
>>
>>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: yet another sage-python performance puzzle

[Nils Bruin]

On Monday, September 18, 2017 at 3:08:11 AM UTC-7, Jeroen Demeyer wrote:
>
> On 2017-09-16 03:31, Nils Bruin wrote: 
> > So if you're finding you can't put a "from A import a" at the top-level 
> > and using it locally has noticeable cost (which can easily happen: 
> > imports have a significant cost, even for modules that are already 
> > present), then you could try to do a straight import and access the 
> > appropriate namespace. 
>
> But accessing the namespace is also slower than doing the "from ... 
> import ..." import: 
>
> sage: x = 42 
> sage: timeit("sage.structure.element.parent(x)", number=20, repeat=10^6) 
> 20 loops, best of 100: 143 ns per loop 
> sage: timeit("parent(x)", number=20, repeat=10^6) 
> 20 loops, best of 100: 47.7 ns per loop 
>
> Yes, that is where the name-space-tree-flattening tool

sage: import sage.structure.element as elm

comes in handy. With that I get:

sage: timeit("sage.structure.element.parent(x)", number=20, repeat=10^6) 
20 loops, best of 100: 143 ns per loop
sage: timeit("elm.parent(x)", number=20, repeat=10^6) 
20 loops, best of 100: 47.7 ns per loop
sage: timeit("parent(x)", number=20, repeat=10^6) 
20 loops, best of 100: 47.7 ns per loop

I'm very surprised we're getting exactly the same timings. I'm also a 
little suspicious there's no difference measured between the 2nd and 3rd 
test. I think it indicates it helps quite a bit.

Of course, if you *really* care about this overhead, you should make sure 
that a significant part of the loop lies in one function and that the 
function lookup is from a local variable (not a global). I'm hopeful that 
the above indicates that in most cases we can get acceptable performance 
with a renamed global import of the module, without having to rebind 
particular objects from it to global/local variables in a different module 
via a "from ... import ..." construction, and that in many cases this is 
enough to avoid the circular import problems we encounter otherwise.

 

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Security in sage (was How much do we support optional packages)

[Nils Bruin]

On Friday, September 15, 2017 at 8:22:09 AM UTC-7, William wrote:
>
>
> On Fri, Sep 15, 2017 at 8:00 AM Maarten Derickx  > wrote:
>
>> Hi Everybody who wants to discuss security in sage:
>>
>> Please do so in this thread and not in "How much do we support optional 
>> packages".  So that these two discussions can both be held and without 
>> cluttering each other.
>>
>
> Good idea.  And if anybody does write in here, please precisely define 
> your security/threat model before writing anything else...  since otherwise 
> the discussion is worthless.
>

I think a real concern with software distributions with non-centralized 
repository maintenance is the mismatch between the curation expected by the 
user and the curation of code that actually happens by the project.

Users may expect that if they download software from sagemath.org, then 
they are getting files that are from there, and are checked by the people 
there: the user will decide to trust those people and assume that if a 
breach happens there, he/she will be notified then he/she can decide to 
stop trusting that source.

In reality this is increasingly not the case anymore: sage pulls in 
packages from "Pypi" when installing. Contrary to sagemath.org, there is 
not a well-defined group of people deciding whether to accept/reject code 
changes to Pypi projects.
sagemath isn't just pulling everything from Pypi, so we're perhaps not 
exposed to arbitrary code uploaded to Pypi (see, e.g. 
http://incolumitas.com/2016/06/08/typosquatting-package-managers/), but to 
what extent we are subject to the whims of other project maintainers isn't 
clear to me.

In short: I think the main concern isn't "security" in the sense of 
privilege escalation, but "malware prevention" -- what measures are being 
taken to ensure that sagemath isn't a vector for code that is maliciously 
doing something else than what it is advertising.
If the answer is "absolutely nothing" it may be hard to convince sysadmins 
to install it, and would mean that personal users should also run it in 
well-contained jail, with strict limits on the resources it has access to 
(i.e., everybody should run the VMs that were previously necessary on 
Windows!). This kind of thing needs a balance between paranoia and 
carelessness.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] 12 month Research Software Engineer position at the Laboratoire de Recherche en Informatique, Paris Sud: parallelisation, optimization and packaging

[Nicolas M. Thiery]

Dear Sage developers,

Our lab, the Laboratoire de Recherche en Informatique) of Université
Paris Sud, is recruiting a research software engineer for one year to
support researchers from two of its teams, ParSys (Parallel systems)
and GALaC (Graphs, Algorithms and Combinatorics), in their development
of parallel libraries for numerical linear algebra and combinatorics
respectively. Specifically, the mission will be to help

- port and optimize those libraries on recent parallel architectures
  (shared or distributed memory, possibly using GPU-type accelerators)

- package and integrate them in open source community developed
  libraries like LAPACK/MAGMA and SageMath.

A full description of the position is available from:
https://www.lri.fr/files/vacantPosition/31.pdf (in French)

For more information or to apply, please contact Anne-Catherine
Letournel .

Cheers,
Nicolas

This position is funded by CNRS, with the intention of evaluating the
benefits of hiring a new research software engineers in our lab.
Pending promising results, there is some chance that the CNRS will
later create a permanent research software engineer position.

--
Nicolas M. Thiéry "Isil" 
http://Nicolas.Thiery.name/

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Signs and graded algebras

[John H Palmieri]

I have a graded algebra A over a field k, and I would like the following 
behavior: when I multiply homogeneous elements of the tensor square (A 
tensor A), I want signs to appear, as in:

  (a tensor b) (c tensor d) = (-1)^(deg b deg c) (ac tensor bd)

You could ask for the same when multiplying elements of (A tensor B) for 
two graded algebras A and B. This may not be desirable for all graded 
algebras in Sage, but it might be useful in more than one case. How should 
this be implemented?

I'm guessing and/or hoping that modifying something in the category code 
would help, and that one could appropriately initialize the categories of A 
and B to turn this feature on, but I'm confused enough by the category code 
that I don't know where to start. Any suggestions? (Or is the category 
approach not viable, so something else (and what?) should be done?)

To illustrate my confusion, if A is the mod 3 Steenrod algebra and if y is 
an element in (A tensor A), I don't even know how the multiplication y*y is 
defined. Is this category code, coercion, something else? Note that this 
example leads to a bug:

sage: A = SteenrodAlgebra(3)
sage: x = A.Q(0)
sage: x**2
0

sage: y = x.coproduct()
sage: y**2
2*Q_0 # Q_0

The coproduct is an algebra map, so if x**2=0, then (x.coproduct())**2 
should also be zero, but it's not. If the signs were dealt with 
appropriately, this would be okay, but as it is, we have a bug.

-- 
John

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Faster way to load python code

[Nils Bruin]

On Monday, September 18, 2017 at 6:15:09 AM UTC-7, Simon King wrote:
>
>
> OK, the replies people gave strongly indicate that it would be a bad idea 
> to try to read the text file directly into Sage. So, I should keep using 
> libgap to read the file, followed by a translation (of course using 
> Cython) 
> into Sage and re-saving the data in a binary format. 
>
> This is rather embarrassing:

 sage: open("L.gap","w").write("S:="+str([i for i in range(200)]))
sage: open("L.sage","w").write("S="+str([i for i in range(200)]))
sage: %time exec(open("L.sage").read())
CPU times: user 3.5 s, sys: 507 ms, total: 4 s
Wall time: 4 s
sage: %time libgap.Read("L.gap")
CPU times: user 895 ms, sys: 8.69 ms, total: 903 ms
Wall time: 904 ms
sage: %time V=libgap.eval("S").sage()
CPU times: user 1.62 s, sys: 27.8 ms, total: 1.65 s
Wall time: 1.65 s

Compare with pickle:

sage: %time pckl=dumps(S)
CPU times: user 1.15 s, sys: 5.92 ms, total: 1.16 s
Wall time: 1.16 s
sage: %time S_obj=loads(pckl)
CPU times: user 149 ms, sys: 10.1 ms, total: 159 ms
Wall time: 157 ms

Stripping out the "read" file operation in the "exec" hardly matters.

The fact that the "loads" is fairly quick shows that the *actual 
construction* of the data structure isn't what has a high cost. It's the 
parsing (for exec) and the conversion (for libgap("S").sage() ) that is 
slow.

I expect that both of these can be made considerably better (perhaps parse 
(simple) python to the pickle VM rather than the CPython VM?), and both of 
these should be very doable for people who are experts with computer 
programming and data structures, but don't have significant mathematical 
training otherwise.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Security in sage (was How much do we support optional packages)

[William Stein]

On Mon, Sep 18, 2017 at 12:38 PM Nils Bruin  wrote:

> On Friday, September 15, 2017 at 8:22:09 AM UTC-7, William wrote:
>
>>
>> On Fri, Sep 15, 2017 at 8:00 AM Maarten Derickx 
>> wrote:
>>
>>> Hi Everybody who wants to discuss security in sage:
>>>
>>> Please do so in this thread and not in "How much do we support optional
>>> packages".  So that these two discussions can both be held and without
>>> cluttering each other.
>>>
>>
>> Good idea.  And if anybody does write in here, please precisely define
>> your security/threat model before writing anything else...  since otherwise
>> the discussion is worthless.
>>
>
> I think a real concern with software distributions with non-centralized
> repository maintenance is the mismatch between the curation expected by the
> user and the curation of code that actually happens by the project.
>
> Users may expect that if they download software from sagemath.org, then
> they are getting files that are from there, and are checked by the people
> there: the user will decide to trust those people and assume that if a
> breach happens there, he/she will be notified then he/she can decide to
> stop trusting that source.
>
> In reality this is increasingly not the case anymore: sage pulls in
> packages from "Pypi" when installing. Contrary to sagemath.org, there is
> not a well-defined group of people deciding whether to accept/reject code
> changes to Pypi projects.
>

>From 3 days ago:

Ten Malicious Libraries Found on PyPI - Python Package Index

https://www.bleepingcomputer.com/news/security/ten-malicious-libraries-found-on-pypi-python-package-index/



> sagemath isn't just pulling everything from Pypi, so we're perhaps not
> exposed to arbitrary code uploaded to Pypi (see, e.g.
> http://incolumitas.com/2016/06/08/typosquatting-package-managers/), but
> to what extent we are subject to the whims of other project maintainers
> isn't clear to me.
>
> In short: I think the main concern isn't "security" in the sense of
> privilege escalation, but "malware prevention" -- what measures are being
> taken to ensure that sagemath isn't a vector for code that is maliciously
> doing something else than what it is advertising.
> If the answer is "absolutely nothing" it may be hard to convince sysadmins
> to install it, and would mean that personal users should also run it in
> well-contained jail, with strict limits on the resources it has access to
> (i.e., everybody should run the VMs that were previously necessary on
> Windows!). This kind of thing needs a balance between paranoia and
> carelessness.
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-devel+unsubscr...@googlegroups.com.
> To post to this group, send email to sage-devel@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.
>
-- 
-- William Stein

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Security in sage (was How much do we support optional packages)

[Volker Braun]

On Monday, September 18, 2017 at 9:38:30 PM UTC+2, Nils Bruin wrote:
>
> In reality this is increasingly not the case anymore: sage pulls in 
> packages from "Pypi" when installing
>

A normal install (i.e. running "make") does not pull packages from pypi. 
Obviously we don't have the resources to security audit every dependency, 
but at least you can be assured that you are installing the same packages 
as when the release was made.

But once sage is built you can of course use pip to install additional 
third-party packages from pypi. 

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Security in sage (was How much do we support optional packages)

[Nils Bruin]

On Monday, September 18, 2017 at 3:40:33 PM UTC-7, Volker Braun wrote:
>
> On Monday, September 18, 2017 at 9:38:30 PM UTC+2, Nils Bruin wrote:
>>
>> In reality this is increasingly not the case anymore: sage pulls in 
>> packages from "Pypi" when installing
>>
>
> A normal install (i.e. running "make") does not pull packages from pypi. 
> Obviously we don't have the resources to security audit every dependency, 
> but at least you can be assured that you are installing the same packages 
> as when the release was made.
>

Thank you for correcting me on this! Clearly I was wrong (the fact that we 
package pip so that people can use it explicitly themselves is of course 
not a "trust" concern here).
Indeed, scanning the build logs suggests that the downloads triggered by 
"make build" are all from sagemath.org mirrors. So a concerned sysadmin 
would "just" have to inspect the files there.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.