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: sage-6.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:

Status badges

Description (last modified by Vincent Delecroix)

As reported in this sage-devel 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 Vincent Delecroix

Branch: public/19299
Commit: 617df137291c1fd10fcc7de21435867d316870ff

New commits:

617df13Trac 19299: implement cartesian_factors

comment:2 Changed 7 years ago by Vincent Delecroix

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 git

Commit: 617df137291c1fd10fcc7de21435867d316870ff1b271285ac389d31d9603e227e40da6fe3f45d3e

Branch pushed to git repo; I updated commit sha1. New commits:

1b27128Trac 19299: improve speed of OperationTable

comment:4 Changed 7 years ago by Vincent Delecroix

Status: newneeds_review

Nathann,

Could you see if this is enough speedup for your purpose?

Vincent

comment:5 Changed 7 years ago by Vincent Delecroix

Description: modified (diff)

comment:6 Changed 7 years ago by Vincent Delecroix

Description: modified (diff)

comment:7 Changed 7 years ago by Nathann Cohen

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 Vincent Delecroix

Description: modified (diff)

comment:9 Changed 7 years ago by Nathann Cohen

Yo !

My graph generation is still slow, but 10 seconds for a 1024-nodes graph is, well, not as bad as some gap-based 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 Vincent Delecroix

Branch: public/19299u/ncohen/19299
Commit: 1b271285ac389d31d9603e227e40da6fe3f45d3ea0b8757523c91c8d8c7cea296930743a3b263585

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:

a0b8757trac #19299: Code rephrase

comment:11 Changed 7 years ago by Nathann Cohen

Reviewers: Nathann Cohen

Okayyy. Well, then if it's good for you, let it go!

Nathann

comment:12 Changed 7 years ago by Vincent Delecroix

Status: needs_reviewpositive_review

comment:13 Changed 7 years ago by Johan Rosenkilde

There's a duplicated line sage: A((1, 1.23)).cartesian_factors() in the EXAMPLE of cartesian_factors, it seems.

comment:14 Changed 7 years ago by Vincent Delecroix

Status: positive_reviewneeds_work

Indeed...

comment:15 Changed 7 years ago by Vincent Delecroix

Branch: u/ncohen/19299public/19299
Commit: a0b8757523c91c8d8c7cea296930743a3b263585954c0d03b85680cb45534ddb7a920aa4ab451357
Status: needs_workneeds_review

New commits:

954c0d0Trac 19299: remove a duplicated line

comment:16 Changed 7 years ago by Nathann Cohen

Status: needs_reviewpositive_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 Volker Braun

Branch: public/19299954c0d03b85680cb45534ddb7a920aa4ab451357
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.