Opened 7 years ago
Closed 7 years ago
#19299 closed enhancement (fixed)
product of elements of a cartesian products is very slow
Reported by:  Vincent Delecroix  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  algebra  Keywords:  
Cc:  Nathann Cohen  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  954c0d0 (Commits, GitHub, GitLab)  Commit:  954c0d03b85680cb45534ddb7a920aa4ab451357 
Dependencies:  Stopgaps: 
Description (last modified by )
As reported in this sagedevel thread the product of elements of a cartesian product are very slow
sage: X = cartesian_product([IntegerModRing(2)] * 8) sage: A = X.addition_table() # very very long
One problem is the default implementation of cartesian_factors
for element of such product provided by sage.categories.sets_cat
def cartesian_factors(self): # TODO: optimize return tuple(self.cartesian_projection(i) for i in self.parent()._sets_keys())
An other one is that OperationTable
is using a lookup in a tuple with .index()
rather than using a hash table (e.g. with a dict
). We fix those two issues and obtain a dramatic speedup:
Before
sage: X = cartesian_product([IntegerModRing(2)] * 8) sage: %time A = X.addition_table() CPU times: user 12.4 s, sys: 32 ms, total: 12.5 s Wall time: 12.4 s
After
sage: X = cartesian_product([IntegerModRing(2)] * 8) sage: %time A = X.addition_table() CPU times: user 644 ms, sys: 48 ms, total: 692 ms Wall time: 604 ms
Change History (17)
comment:1 Changed 7 years ago by
Branch:  → public/19299 

Commit:  → 617df137291c1fd10fcc7de21435867d316870ff 
comment:2 Changed 7 years ago by
I am still annoyed that %prun
returns that most time is taken by the index
method of tuple... which has no reason to be used.
comment:3 Changed 7 years ago by
Commit:  617df137291c1fd10fcc7de21435867d316870ff → 1b271285ac389d31d9603e227e40da6fe3f45d3e 

Branch pushed to git repo; I updated commit sha1. New commits:
1b27128  Trac 19299: improve speed of OperationTable

comment:4 Changed 7 years ago by
Status:  new → needs_review 

Nathann,
Could you see if this is enough speedup for your purpose?
Vincent
comment:5 Changed 7 years ago by
Description:  modified (diff) 

comment:6 Changed 7 years ago by
Description:  modified (diff) 

comment:7 Changed 7 years ago by
Hello !
The speedup is cool indeed, thanks! My constructions are still very slow but while I was trying to figure out why exactly I noticed that Graph.complement
was rather slow too. I'll finish that and get back to the constructions, to this patch and to my slow code.
Nathann
comment:8 Changed 7 years ago by
Description:  modified (diff) 

comment:9 Changed 7 years ago by
Yo !
My graph generation is still slow, but 10 seconds for a 1024nodes graph is, well, not as bad as some gapbased construction.
I could save a couple of seconds on the graph side, however, but that would require some rewrite of the dense graph backend. I'll get to that.
Is there any reason why you stored the dictionary as a parameter of self
? I added a small commit on top of yours at u/ncohen/19299 which avoid lambda functions. It also removes the caching of the dictionary, but if you really think it can be useful, well, that can be reverted.
Thanks,
Nathann
comment:10 Changed 7 years ago by
Branch:  public/19299 → u/ncohen/19299 

Commit:  1b271285ac389d31d9603e227e40da6fe3f45d3e → a0b8757523c91c8d8c7cea296930743a3b263585 
I do prefer your version!
An index attribute might be useful for the method OperationTable.__getitem__
. But as it is not used intensively for building the table I did not touched it.
Vincent
New commits:
a0b8757  trac #19299: Code rephrase

comment:11 Changed 7 years ago by
Reviewers:  → Nathann Cohen 

Okayyy. Well, then if it's good for you, let it go!
Nathann
comment:12 Changed 7 years ago by
Status:  needs_review → positive_review 

comment:13 Changed 7 years ago by
There's a duplicated line sage: A((1, 1.23)).cartesian_factors()
in the EXAMPLE
of cartesian_factors
, it seems.
comment:15 Changed 7 years ago by
Branch:  u/ncohen/19299 → public/19299 

Commit:  a0b8757523c91c8d8c7cea296930743a3b263585 → 954c0d03b85680cb45534ddb7a920aa4ab451357 
Status:  needs_work → needs_review 
New commits:
954c0d0  Trac 19299: remove a duplicated line

comment:16 Changed 7 years ago by
Status:  needs_review → positive_review 

The patchbot says that everything is cool, so positive_review
again. Sorry 'bout the previous one.
Nathann
comment:17 Changed 7 years ago by
Branch:  public/19299 → 954c0d03b85680cb45534ddb7a920aa4ab451357 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
Trac 19299: implement cartesian_factors