Opened 3 years ago
Closed 3 years ago
#23383 closed enhancement (fixed)
Speeding up congruencerelated lattice functions
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage8.1 
Component:  combinatorics  Keywords:  
Cc:  tscrim, chapoton  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  6f8c510 (Commits)  Commit:  6f8c5108ad9d96fa548c61d1efcdd9ee757be3d4 
Dependencies:  Stopgaps: 
Description (last modified by )
This patch adds precomputing intervals in the HasseDiagram
to speed up some congruencerelated lattice functions. If L = Posets.BooleanLattice(7)
, then we have
sage: timeit("list(L._hasse_diagram.congruences_iterator())") 5 loops, best of 3: 4.63 s per loop
and after L._hasse_diagram._precompute_intervals()
sage: timeit("list(L._hasse_diagram.congruences_iterator())") 5 loops, best of 3: 656 ms per loop
OTOH this will eat memory.
Currently this feature is well hidden, only available as a _
function of a _
variable. Later we should think about interface. A global "savecpueatmemory" switch or "aux functions" to lattices (posets?) or something else?
Change History (23)
comment:1 Changed 3 years ago by
 Branch set to u/jmantysalo/precomputeintervals
comment:2 Changed 3 years ago by
 Branch u/jmantysalo/precomputeintervals deleted
 Cc tscrim chapoton added
 Status changed from new to needs_info
comment:3 Changed 3 years ago by
 Branch set to u/jmantysalo/precomputeintervals
comment:4 followup: ↓ 5 Changed 3 years ago by
 Commit set to 4b183a23a044589dff27d7f3193057f9756d7f36
comment:5 in reply to: ↑ 4 ; followup: ↓ 6 Changed 3 years ago by
Replying to tscrim:
Also, it might be faster to have the
dict
indexed by a pair(x,y)
as it only needs to do 1 hash and table lookup instead of 2.
Actually, even faster should be a list of lists, that needs no lookup at all.
There is no need to create the empty object and you save a lot of Python calls by doing the dict comprehension.
True. I was thinking about lists but then somehow ended up to dict in this PoC.
And now the most important:
I consider Hasse diagrams not as part of the true API, but an implementation detail of posets. So I don't see any problem with changing the output type.
OK. I tested by adding precomputing to __init__
of poset. Only errors I got from long test of combinat/posets
where from .open_interval
in posets.py
. But I think currently intervals are given as in the linear extension order, and that is propably a good thing.
comment:6 in reply to: ↑ 5 Changed 3 years ago by
Replying to jmantysalo:
Replying to tscrim:
Also, it might be faster to have the
dict
indexed by a pair(x,y)
as it only needs to do 1 hash and table lookup instead of 2.Actually, even faster should be a list of lists, that needs no lookup at all.
Well, there still is a lookup, but now it is (relatively) very fast. +1 for list of lists.
I consider Hasse diagrams not as part of the true API, but an implementation detail of posets. So I don't see any problem with changing the output type.
OK. I tested by adding precomputing to
__init__
of poset. Only errors I got from long test ofcombinat/posets
where from.open_interval
inposets.py
. But I think currently intervals are given as in the linear extension order, and that is propably a good thing.
I think it would be best if the numbering was done increasing (as that is assumed to be a linear extension IIRC).
comment:7 Changed 3 years ago by
 Commit changed from 4b183a23a044589dff27d7f3193057f9756d7f36 to 0cafe94f3de78f8b39336173e83ff5759afcd72f
Branch pushed to git repo; I updated commit sha1. New commits:
0cafe94  Use list of lists.

comment:8 Changed 3 years ago by
 Milestone changed from sage8.0 to sage8.1
 Status changed from needs_info to needs_review
Here it is. The speedup is quite big:
sage: L = Posets.BooleanLattice(7) sage: timeit("list(L._hasse_diagram.congruences_iterator())") 5 loops, best of 3: 4.63 s per loop sage: timeit("L._hasse_diagram._precompute_intervals()") 25 loops, best of 3: 23.6 ms per loop sage: timeit("list(L._hasse_diagram.congruences_iterator())") 5 loops, best of 3: 656 ms per loop
comment:9 followup: ↓ 11 Changed 3 years ago by
 Status changed from needs_review to needs_work
If you want even more speed:
 v_up = [None] * n  v_down = [None] * n  for v in range(n):  v_up[v] = frozenset(self.depth_first_search(v))  v_down[v] = frozenset(self.depth_first_search(v, neighbors=self.neighbors_in)) + v_up = [frozenset(self.depth_first_search(v)) for v in range(n)] + v_down = [frozenset(self.depth_first_search(v, neighbors=self.neighbors_in)) + for v in range(n)]  self._intervals = [[None] * n for _ in range(n)]  for u in range(n):  for v in range(n):  self._intervals[u][v] = sorted(v_up[u].intersection(v_down[v])) + self._intervals = [[sorted(up.intersection(down)) for down in v_down] + for up in v_up]
I've seen using list comprehension have a significant effect for things like this because of the extra Python overhead.
I do not like the documentation of _alt_interval
. It should explain what it is doing (well, really it should be similar/same as interval
. Moreover, you should put somewhere in some documentation about this feature and how to use it. It probably is good to make this part of the API for posets somewhere with a warning about the memory usage.
You also should update the ticket description.
comment:10 Changed 3 years ago by
 Commit changed from 0cafe94f3de78f8b39336173e83ff5759afcd72f to 5c3e75c90c8807c9fe9fde44f8ea5b471d76382c
Branch pushed to git repo; I updated commit sha1. New commits:
5c3e75c  Use list comprehension.

comment:11 in reply to: ↑ 9 Changed 3 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
Replying to tscrim:
If you want even more speed:
Done that. And yes, it gives some milliseconds: for Posets.BooleanLattice(10)
it took 1,65 seconds, now it takes 1,41 seconds. (Of course that means nothing when compared to time to compute congruences.) And the code is shorted and more pythonic.
Much more speedup should be possible with better algorithm: an interval from a
with covers a1
and a2
to b
is union of intervals (a1, b)
and (a2, b)
.
I do not like the documentation of
_alt_interval
. It should explain what it is doing (well, really it should be similar/same asinterval
. Moreover, you should put somewhere in some documentation about this feature and how to use it. It probably is good to make this part of the API for posets somewhere with a warning about the memory usage.You also should update the ticket description.
I added a note about this to the description. Needs to think for a while.
comment:12 Changed 3 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to needs_work
However, I still would like to see a bit better of documentation for _alt_interval
describing the algorithm (i.e., by precomputing) and what you need to do to make it work. In some ways, I don't like the implementation because you need to explicitly call another function first instead of it just working. I am see this through the eyes of someone browsing through the code and seeing this who did not read this specific ticket, which will almost certainly happen at some point.
comment:13 followups: ↓ 15 ↓ 16 Changed 3 years ago by
First, a technical question: A Python function can return an internal function, i.e. this will print "Hello":
def f(): def g(): print("Hello") return g f()()
Would it be meaningfull to use this feature, and remove _alt_interval
from the top level of Hasse diagram?
Now to the main question.
The problem is, IMO, UniqueRepresentation
. No created poset will ever be freed from the memory, and so making test with random posets will eventually eat all the memory. And if we compute lequal_matrix()
or _meet
etc, those will be saved too. That's why I am worried about this.
When should this precomputing be called? In interval()
? In congruence()
? In, say, is_isoform()
?
I will formulate longer description for _atl_interval
.
comment:14 Changed 3 years ago by
 Commit changed from 5c3e75c90c8807c9fe9fde44f8ea5b471d76382c to 99412fe92ec3987236d698fa8e2cca11edfa93ae
Branch pushed to git repo; I updated commit sha1. New commits:
99412fe  More documentation.

comment:15 in reply to: ↑ 13 Changed 3 years ago by
 Status changed from needs_work to needs_review
More comments on this? Specially for this:
When should this precomputing be called? In
interval()
? Incongruence()
? In, say,is_isoform()
?
comment:16 in reply to: ↑ 13 ; followup: ↓ 17 Changed 3 years ago by
Replying to jmantysalo:
First, a technical question: A Python function can return an internal function, i.e. this will print "Hello":
def f(): def g(): print("Hello") return g f()()
Yes, that is correct. We return functions in a number of places within Sage too.
Would it be meaningfull to use this feature, and remove
_alt_interval
from the top level of Hasse diagram?
I do not think so by default because of how much memory this would use. Although it could be something we do for small posets (less that 5 vertices?).
The problem is, IMO,
UniqueRepresentation
. No created poset will ever be freed from the memory, and so making test with random posets will eventually eat all the memory. And if we computelequal_matrix()
or_meet
etc, those will be saved too. That's why I am worried about this.
That should not be true. Once you delete all references to a poset, it should be freeable as it is a weak reference (otherwise it is a memory leak bug).
When should this precomputing be called? In
interval()
? Incongruence()
? In, say,is_isoform()
?
Probably in none of these places, but instead we should document it as an alternative method for increasing the speed.
comment:17 in reply to: ↑ 16 Changed 3 years ago by
Replying to tscrim:
That should not be true. Once you delete all references to a poset, it should be freeable as it is a weak reference (otherwise it is a memory leak bug).
If that would be true, then for example this should print the same number again and again:
i = 0 j = 0 for P in Posets(8): j += 1 if j % 1000 == 0: print(sage.misc.getusage.get_memory_usage()) if P.is_connected(): i += 1 print(i)
(Compare this with same except digraphs(8)
instead of Posets(8)
.)
Currently there is no way to for example search for counterexample with random posets to unlimited time.
comment:18 followup: ↓ 19 Changed 3 years ago by
I know UniqueRepresentation
is a weak cache, and I do not see anything that would explicitly nail it in the memory. What is probably happening is with the iterator populating the cache and moving around all of the memory is not giving the garbage collector time to work. If I force a garbage collection, then the memory usage (basically) does not grow:
import gc i = 0 j = 0 for P in Posets(8): j += 1 if j % 100 == 0: gc.collect() print(sage.misc.getusage.get_memory_usage()) if P.is_connected(): i += 1 print(i)
IIRC, Python will force a garbage collection to see if it can free up the memory before giving an outofmemory exception. Although I've never really done anything that would cause that to happen.
comment:19 in reply to: ↑ 18 Changed 3 years ago by
Replying to tscrim:
First, thanks for gc.collect()
! I think I have read it before, and totally forget.
IIRC, Python will force a garbage collection to see if it can free up the memory before giving an outofmemory exception. Although I've never really done anything that would cause that to happen.
The problem is propably memory overcommit or usage of every bit of memory. When almost every byte is used, Linux is extremely slow, and so never goes to the limit where Python would give outofmemory exception.
This should be handled in Python level or in OS level. Sage can only add some temporary workarounds.
comment:20 followup: ↓ 22 Changed 3 years ago by
One last trivial thing: code format ``x``
and ``y``
in _alternate_interval
. Once done, you can set a positive review on my behalf.
comment:21 Changed 3 years ago by
 Commit changed from 99412fe92ec3987236d698fa8e2cca11edfa93ae to 6f8c5108ad9d96fa548c61d1efcdd9ee757be3d4
Branch pushed to git repo; I updated commit sha1. New commits:
6f8c510  Docstring formatting.

comment:22 in reply to: ↑ 20 Changed 3 years ago by
 Status changed from needs_review to positive_review
Replying to tscrim:
One last trivial thing: code format
``x``
and``y``
in_alternate_interval
. Once done, you can set a positive review on my behalf.
Done that.
comment:23 Changed 3 years ago by
 Branch changed from u/jmantysalo/precomputeintervals to 6f8c5108ad9d96fa548c61d1efcdd9ee757be3d4
 Resolution set to fixed
 Status changed from positive_review to closed
I consider Hasse diagrams not as part of the true API, but an implementation detail of posets. So I don't see any problem with changing the output type. Although it is part of the API for
HasseDiagram
, thus, it technically is a backwards incompatible change.Also, it might be faster to have the
dict
indexed by a pair(x,y)
as it only needs to do 1 hash and table lookup instead of 2. Also, a better way to populate_intervals
:There is no need to create the empty object and you save a lot of Python calls by doing the dict comprehension.
New commits:
Precomputing intervals of HasseDiagram.