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

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 4 years ago by vdelecroix

  • Branch set to public/19299
  • Commit set to 617df137291c1fd10fcc7de21435867d316870ff

New commits:

617df13Trac 19299: implement cartesian_factors

comment:2 Changed 4 years ago by vdelecroix

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 git

  • Commit changed from 617df137291c1fd10fcc7de21435867d316870ff to 1b271285ac389d31d9603e227e40da6fe3f45d3e

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

1b27128Trac 19299: improve speed of OperationTable

comment:4 Changed 4 years ago by vdelecroix

  • 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 vdelecroix

  • Description modified (diff)

comment:6 Changed 4 years ago by vdelecroix

  • Description modified (diff)

comment:7 Changed 4 years ago by ncohen

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 vdelecroix

  • Description modified (diff)

comment:9 Changed 4 years ago by ncohen

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 4 years ago by vdelecroix

  • 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:

a0b8757trac #19299: Code rephrase

comment:11 Changed 4 years ago by ncohen

  • 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 vdelecroix

  • Status changed from needs_review to positive_review

comment:13 Changed 4 years ago by jsrn

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

comment:14 Changed 4 years ago by vdelecroix

  • Status changed from positive_review to needs_work

Indeed...

comment:15 Changed 4 years ago by vdelecroix

  • 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:

954c0d0Trac 19299: remove a duplicated line

comment:16 Changed 4 years ago by ncohen

  • 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 vbraun

  • Branch changed from public/19299 to 954c0d03b85680cb45534ddb7a920aa4ab451357
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.