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

Priority:  major  Milestone:  sage6.9 
Component:  algebra  Keywords:  
Cc:  ncohen  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  954c0d0 (Commits)  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 4 years ago by
 Branch set to public/19299
 Commit set to 617df137291c1fd10fcc7de21435867d316870ff
comment:2 Changed 4 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 4 years ago by
 Commit changed from 617df137291c1fd10fcc7de21435867d316870ff to 1b271285ac389d31d9603e227e40da6fe3f45d3e
Branch pushed to git repo; I updated commit sha1. New commits:
1b27128  Trac 19299: improve speed of OperationTable

comment:4 Changed 4 years ago by
 Status changed from new to needs_review
Nathann,
Could you see if this is enough speedup for your purpose?
Vincent
comment:5 Changed 4 years ago by
 Description modified (diff)
comment:6 Changed 4 years ago by
 Description modified (diff)
comment:7 Changed 4 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 4 years ago by
 Description modified (diff)
comment:9 Changed 4 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 4 years ago by
 Branch changed from public/19299 to u/ncohen/19299
 Commit changed from 1b271285ac389d31d9603e227e40da6fe3f45d3e to 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 4 years ago by
 Reviewers set to Nathann Cohen
Okayyy. Well, then if it's good for you, let it go!
Nathann
comment:12 Changed 4 years ago by
 Status changed from needs_review to positive_review
comment:13 Changed 4 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 4 years ago by
 Branch changed from u/ncohen/19299 to public/19299
 Commit changed from a0b8757523c91c8d8c7cea296930743a3b263585 to 954c0d03b85680cb45534ddb7a920aa4ab451357
 Status changed from needs_work to needs_review
New commits:
954c0d0  Trac 19299: remove a duplicated line

comment:16 Changed 4 years ago by
 Status changed from needs_review to positive_review
The patchbot says that everything is cool, so positive_review
again. Sorry 'bout the previous one.
Nathann
comment:17 Changed 4 years ago by
 Branch changed from public/19299 to 954c0d03b85680cb45534ddb7a920aa4ab451357
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Trac 19299: implement cartesian_factors