Opened 8 years ago
Closed 7 years ago
#14535 closed enhancement (duplicate)
Mutability of Graphs
Reported by: | SimonKing | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | graph theory | Keywords: | mutability graph |
Cc: | jernej | Merged in: | |
Authors: | Simon King, Volker Braun | Reviewers: | Simon King, Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #14524 #14732 | Stopgaps: |
Description (last modified by )
This patch allows to create immutable graphs, so that they can be used as keys in dictionaries.
Previously, calling hash on a graph did work after assigning the attribute _immutable
to the graph. That's a hack, and it would in fact not prevent the graph from being mutated.
With this patch, the attempt to change an immutable graph be means of methods such as add_vertex or add_edge or delete_vertex, will result in an error. If one really wants to play nasty, one could make an immutable graph mutable and change it, or use the backend of the graph for changing the underlying data.
Attachments (2)
Change History (48)
Changed 8 years ago by
comment:1 Changed 8 years ago by
- Status changed from new to needs_review
comment:2 follow-up: ↓ 4 Changed 8 years ago by
- Cc jernej added
comment:3 Changed 8 years ago by
- Status changed from needs_review to needs_info
comment:4 in reply to: ↑ 2 ; follow-up: ↓ 8 Changed 8 years ago by
Hi!
Replying to ncohen:
Hello !
- Could you show that there is no slowdown in the graph functions because of that please ?
There certainly is a slowdown in all methods that are protected in this way. And I do not use the decorator in cdef classes, in an attempt to prevent a regression.
Does it make sense to time methods like add_vertex separately? In my applications, one would build a graph, and then it will never again be changed. But I am sure you have better use cases than I. Do you have examples in which add/delete_vertex/edge will typically be called zillions of times?
- Besides, why do you need decorators in the Python classes if you forbid modifications directly in the backend ?
I do not forbid to change the graphs in the backend. Or at least, I did not intend to modify the backends. If I did, then it was by mistake. If G is an immutable graph, then G._backend.add_vertex(...)
should not complain.
The reason is, again, that I don't want a slow-down in the "private" methods. If one has an immutable graph used as key in a dictionary, and then decides to work around the "protected" methods add_vertex
, add_edge
etc by changing the graph G via G._backend, then this is a conscious decision for which the user takes full responsibility.
So, protection of the user will be restricted to the "official" methods G.add_vertex etc.
- You create 4 functions in a class that already has a LOT of them. We have several functions that work like that already :
sage: g.mutable() Tells you if it is mutable sage: g.mutable(True) Sets it to be mutable
I did not find any support for mutability in graphs, except for the hack that makes hash
work.
- There is a lot of things that graphs store and which are not vertices, nor edges. For example the vertices' layout, or its name... You can see the list of these awful things in
GenericGraph.__eq__
. If you just want to take edges and vertices in consideration could you say it explicitely in the documentation of the*_mutable
methods ?
Not good. Yes, I should have looked up GenericGraph.__eq__
and take into account all data used there.
And.. Well.. Could you add me in Cc when you write things like that ?
Actually, when I created the ticket, I first looked at a preview, and saw that you are among the (default) owners of this ticket. Hence, I concluded that there is no need in adding you in Cc, because you already were on the list of recipients. Sorry if I misinterpreted the meaning of the list of "owners".
comment:5 Changed 8 years ago by
Here is a little timing.
Without patch:
sage: K12 = graphs.CompleteGraph(12) sage: K4 = graphs.CompleteGraph(4) sage: def test(g,h): ....: g.delete_edges(h.edge_iterator()) ....: g.add_edges(h.edge_iterator()) ....: sage: %timeit test(K12,K4) 10000 loops, best of 3: 118 us per loop
With patch:
sage: K12 = graphs.CompleteGraph(12) sage: K4 = graphs.CompleteGraph(4) sage: def test(g,h): ....: g.delete_edges(h.edge_iterator()) ....: g.add_edges(h.edge_iterator()) ....: sage: %timeit test(K12,K4) 10000 loops, best of 3: 131 us per loop sage: (131-118)/118.*100 11.0169491525424
So, there is a slow-down of 11% in this example. I don't know if in "real" examples, the backend would be used (without slow-down) internally.
comment:6 Changed 8 years ago by
Here are two more timings, this time using DenseGraph
(hence, not using the decorator) and hash:
Without patch:
sage: from sage.graphs.base.dense_graph import DenseGraph sage: D = DenseGraph(nverts=10, extra_vertices=10) sage: def test(g): ....: for i in xrange(100): ....: g.add_vertex(i) ....: for i in xrange(100): ....: for j in xrange(100): ....: g.add_arc(i,j) ....: for i in xrange(100): ....: g.del_vertex(i) ....: sage: %timeit test(D) 100 loops, best of 3: 2.59 ms per loop sage: K12 = graphs.CompleteGraph(12) sage: K12._immutable = True sage: hash(K12) -1604610596753853799 sage: %timeit hash(K12) 1000 loops, best of 3: 212 us per loop
With the patch:
... sage: %timeit test(D) 100 loops, best of 3: 2.72 ms per loop sage: (2.72-2.59)/2.59*100 # 5% slowdown 5.01930501930503 sage: K12 = graphs.CompleteGraph(12) sage: K12.set_immutable() sage: %timeit hash(K12) 1000 loops, best of 3: 216 us per loop
Anyway, I presume that in real use cases, faster unsafe methods would/could/should be used internally.
comment:7 Changed 8 years ago by
- Status changed from needs_info to needs_review
I think I gave the info, so, back to "needs review"...
comment:8 in reply to: ↑ 4 ; follow-ups: ↓ 9 ↓ 16 Changed 8 years ago by
Hellooooooooooooooo !!!
There certainly is a slowdown in all methods that are protected in this way. And I do not use the decorator in cdef classes, in an attempt to prevent a regression.
Hmmmm. And why should we accept a 10% slowdown in order to have immutable graphs ? :-P
Does it make sense to time methods like add_vertex separately? In my applications, one would build a graph, and then it will never again be changed. But I am sure you have better use cases than I. Do you have examples in which add/delete_vertex/edge will typically be called zillions of times?
Not really. Like you, in my examples I spend most of my time reading graphs. And wasting my time translating labels into integers :-P
- Besides, why do you need decorators in the Python classes if you forbid modifications directly in the backend ?
I do not forbid to change the graphs in the backend. Or at least, I did not intend to modify the backends. If I did, then it was by mistake. If G is an immutable graph, then
G._backend.add_vertex(...)
should not complain.
? But you make changes to CGraph
, SparseGraph
and DenseGraph
, don't you ? O_o
And why wouldn't it be better to only deal with immutability directly in the backends ? No need for decorators if it is done there, and if it is only a "if" with a niiice C variable which never changes. Would reduce the slowdown, wouldn't it ?
The reason is, again, that I don't want a slow-down in the "private" methods. If one has an immutable graph used as key in a dictionary, and then decides to work around the "protected" methods
add_vertex
,add_edge
etc by changing the graph G via G._backend, then this is a conscious decision for which the user takes full responsibility.
Hmmmm... But the developpers could have to do that to make some methods more efficient, and then we would have to deal with immutability by hand. But really I am interested in your answer : why don't you prefer to deal with immutability in the backends directly ? In the graphs/base/
files ?
- You create 4 functions in a class that already has a LOT of them. We have several functions that work like that already :
sage: g.mutable() Tells you if it is mutable sage: g.mutable(True) Sets it to be mutableI did not find any support for mutability in graphs, except for the hack that makes
hash
work.
Nonono, we don't have such a method at all ! But we have two methods to allow loops and test if they are allowed :
sage: g = graphs.PetersenGraph() sage: g.allows_loops() False sage: g.allow_loops(True) sage: g.allows_multiple_edges() False sage: g.allow_multiple_edges(True)
So it's already half of what you take, and we could even merge two functions like allows_loops
and allow_loops
into one, as in my previous example. That's one of the joys of coding in Python.
Actually, when I created the ticket, I first looked at a preview, and saw that you are among the (default) owners of this ticket. Hence, I concluded that there is no need in adding you in Cc, because you already were on the list of recipients. Sorry if I misinterpreted the meaning of the list of "owners".
Oh. I see. Then it's the Trac developper's fault. The owners of a section are expected to receive an email indeed, except when there are ... several owners.
In that case, no mails are sent :-P
http://trac.edgewall.org/ticket/7793
Nathann
comment:9 in reply to: ↑ 8 ; follow-up: ↓ 10 Changed 8 years ago by
Replying to ncohen:
There certainly is a slowdown in all methods that are protected in this way. And I do not use the decorator in cdef classes, in an attempt to prevent a regression.
Hmmmm. And why should we accept a 10% slowdown in order to have immutable graphs ?
:-P
It would be nice to have a better solution, but, as for matrices, I do think it would be good to be able to use graphs as keys in dictionaries without a hack.
I do not forbid to change the graphs in the backend. Or at least, I did not intend to modify the backends. If I did, then it was by mistake. If G is an immutable graph, then
G._backend.add_vertex(...)
should not complain.? But you make changes to
CGraph
,SparseGraph
andDenseGraph
, don't you ?O_o
Then we may have different notions of "backend". By "backend", I understood the stuff that is assigned to G._backend
and is defined in sage.graphs.base.graph_backends`.
You think it might be better to move all mutability checks into the backend? I thought so as well, initially. But then I found that a couple of add_* methods first change some data outside of the backend, and call the backend method only later. So, I thought it is safer to check mutability not in the backend, but in the graph.
Hmmmm... But the developpers could have to do that to make some methods more efficient, and then we would have to deal with immutability by hand. But really I am interested in your answer : why don't you prefer to deal with immutability in the backends directly ? In the
graphs/base/
files ?
I would prefer to deal with it in the backends.
comment:10 in reply to: ↑ 9 ; follow-up: ↓ 11 Changed 8 years ago by
It would be nice to have a better solution, but, as for matrices, I do think it would be good to be able to use graphs as keys in dictionaries without a hack.
And you would trade 10%
of speed for that ? O_o
Really, the only way I see to do this properly is to write an immutable backend...
Then we may have different notions of "backend". By "backend", I understood the stuff that is assigned to
G._backend
and is defined in sage.graphs.base.graph_backends`.
Oh. Sorry, then. I call backend whatever is in the base/
folder, but perhaps that isn't right. In any case :
sage: type(Graph()._backend) <class 'sage.graphs.base.sparse_graph.SparseGraphBackend'>
You think it might be better to move all mutability checks into the backend? I thought so as well, initially.
Yep. Looks much cleaner !
But then I found that a couple of add_* methods first change some data outside of the backend, and call the backend method only later.
Oh ? Like which ones ? O_o
So, I thought it is safer to check mutability not in the backend, but in the graph.
I would prefer to deal with it in the backends.
+1.
Nathann
comment:11 in reply to: ↑ 10 ; follow-up: ↓ 12 Changed 8 years ago by
Replying to ncohen:
Oh. Sorry, then. I call backend whatever is in the
base/
folder, but perhaps that isn't right. In any case :sage: type(Graph()._backend) <class 'sage.graphs.base.sparse_graph.SparseGraphBackend'>
OK, then we have the same notions...
But then I found that a couple of add_* methods first change some data outside of the backend, and call the backend method only later.
Oh ? Like which ones ?
O_o
sage.graphs.generic_graph.GenericGraph.delete_vertex
, which is
for attr in attributes_to_update: if hasattr(self, attr) and getattr(self, attr) is not None: getattr(self, attr).pop(vertex, None) self._boundary = [v for v in self._boundary if v != vertex]
and only afterwards calls the backend. If the order of dealing with attributes and dealing with the backend could be reversed, then making the backend immutable would be enough. But in this order, calling the method on an immutable graph backend would destroy some data before raising the error.
Perhaps I should have tried first whether it can be reversed...
Cheers,
Simon
comment:12 in reply to: ↑ 11 ; follow-up: ↓ 13 Changed 8 years ago by
sage.graphs.generic_graph.GenericGraph.delete_vertex
, which isfor attr in attributes_to_update: if hasattr(self, attr) and getattr(self, attr) is not None: getattr(self, attr).pop(vertex, None) self._boundary = [v for v in self._boundary if v != vertex]and only afterwards calls the backend.
Oh, yeah.. The boundary is stored by graphs, too >_<
If the order of dealing with attributes and dealing with the backend could be reversed, then making the backend immutable would be enough. But in this order, calling the method on an immutable graph backend would destroy some data before raising the error.
Perhaps I should have tried first whether it can be reversed...
Hmmmmmm. First I would like to know something : do you really want everything in the graph to be immutable ? Or only edges and vertices ?
Nathann
comment:13 in reply to: ↑ 12 ; follow-up: ↓ 14 Changed 8 years ago by
Replying to ncohen:
Oh, yeah.. The boundary is stored by graphs, too
>_<
Right. Actually I can't recall if my patch protects changing the boundary.
Hmmmmmm. First I would like to know something : do you really want everything in the graph to be immutable ? Or only edges and vertices ?
I want that they are immutable in this sense: "It is impossible to change the hash or to change the ==
-equivalence class of an immutable object by calling methods that do not start with an underscore.
comment:14 in reply to: ↑ 13 Changed 8 years ago by
I want that they are immutable in this sense: "It is impossible to change the hash or to change the
==
-equivalence class of an immutable object by calling methods that do not start with an underscore.
Then there's a nightmare ahead of you :-P
Nathann
comment:15 follow-up: ↓ 21 Changed 8 years ago by
I haven't looked at the patch yet, but I want to keep an eye on it, and I want to advocate uniformity: try to make the mutability behavior and interface the same as that of Sage's matrices.
I'd be happy if we got immutable graphs. I'd be very happy if we could add/delete/contract and get a copy of the graph without explicitly saying "inplace=False" all the time, but one can dream...
And what about the following?
sage: G = graphs.PetersenGraph?() sage: G Petersen graph: Graph on 10 vertices sage: G.add_vertex(11) sage: G Petersen graph: Graph on 11 vertices
Should named graphs be immutable?
comment:16 in reply to: ↑ 8 ; follow-up: ↓ 17 Changed 8 years ago by
sage: g.mutable() Tells you if it is mutable sage: g.mutable(True) Sets it to be mutable
I hope that last line remains fantasy: Changing the mutability of an object is a mutation, so should be forbidden on an immutable object (the only case where g.mutable(True)
should succeed is when g
is already mutable).
comment:17 in reply to: ↑ 16 ; follow-up: ↓ 20 Changed 8 years ago by
Replying to nbruin:
I hope that last line remains fantasy: Changing the mutability of an object is a mutation, so should be forbidden on an immutable object (the only case where
g.mutable(True)
should succeed is wheng
is already mutable).
Sure it is a mutation. However, I was told a couple of times that the "pythonic way" is to pretend that programmers are adult people who know what they do and who are prepared to take responsibility for their actions. Hence, while there should be some protection against accidental changes to an immutable object, it should still be possible to work around the protection.
I conclude that it would be the anti-pythonic way to
- allow to make a mutable object immutable, but not the other way (this is by making
_is_immutable
a cdef attribute, and restrict the interface to three methodsis_immutable
,is_mutable
andset_immutable
) - make it virtually impossible that a sub-class overrides a mutation-protected method by a method that does not check for mutation (this is possible with metaclasses)
- turn an object into an immutable object as soon as its hash is computed, so that its hash bucket will henceforth never change.
We need to find a reasonable middle way between the overly permissive approach ("all graphs are mutable and hashable, the programmer really has to be careful") and the overly protective approach (as described in the bulleted list).
comment:18 follow-up: ↓ 19 Changed 8 years ago by
Again, Matrices have (in my opinion) a decent balance:
sage: A = matrix([[1,2],[3,4]]) sage: A.set_immutable() sage: A[1,1] = 4 Traceback (most recent call last): ... ValueError: matrix is immutable; please change a copy instead (i.e., use copy(M) to change a copy of M). sage: B = copy(A) sage: B[1,1] = 1
Follow that lead, and be consistent with other parts of Sage.
comment:19 in reply to: ↑ 18 Changed 8 years ago by
Replying to Stefan:
Again, Matrices have (in my opinion) a decent balance:
sage: A = matrix([[1,2],[3,4]]) sage: A.set_immutable() sage: A[1,1] = 4 Traceback (most recent call last): ... ValueError: matrix is immutable; please change a copy instead (i.e., use copy(M) to change a copy of M). sage: B = copy(A) sage: B[1,1] = 1
Actually I have not been aware that there is no A.set_mutable
. So, thank you for the pointer!
comment:20 in reply to: ↑ 17 Changed 8 years ago by
Replying to SimonKing:
Sure it is a mutation. However, I was told a couple of times that the "pythonic way" is to pretend that programmers are adult people who know what they do and who are prepared to take responsibility for their actions. Hence, while there should be some protection against accidental changes to an immutable object, it should still be possible to work around the protection.
This goes a step further, though: Once an object is immutable, people can use it as a key in a dictionary (and as you know, caching methods such as UniqueRepresentation
constructors) can do so in quite unobvious ways.
If you then later allow the object to become mutable again, you have now made the graph illegal as dictionary key again! (in fact, if you now mutate it and set it back to mutable, you've made your key unfindable in the dictionaries. That would create VERY hard to debug bugs (as we've recently seen on an object that was just inadvertently changing its hash).
There's already precedent: marking a matrix immutable is a one-way street. Of course, if you really try (and reach in) you can still mutate the matrix. That's where the "consenting adults" comes in. But changing an object from immutable to mutable should never be "official" API.
I don't think you'll lose anything. Making an immutable structure mutable is always a bug. Changing an immutable structure in a way that doesn't "essentially" change it might not be, but in that case it's reasonable to expect you can make that change even without the structure being mutable (e.g., by reaching into the backend to make the change)
comment:21 in reply to: ↑ 15 Changed 8 years ago by
Should named graphs be immutable?
Hmmmmmm :-/
I see the points (we could cache nice information inside of them which is hard to compute), but I don't like it much :-/
We already had some problems with the class BipartiteGraph
which constrained some operations (you were not able to add an edge between two vertices of the same class, for instance). The CompleteBipartiteGraph
and RandomBipartiteGraph
were automatically BipartiteGraph
instances, and it really was a mess. Because you could not expect a function thought for regular graphs to work well on such instances, and the only way out was to make copies of these input again and again into normal graphs, then work on them... :-/
Then again, perhaps you are right and I just complain because I am used to the old way... :-/
Nathann
comment:22 Changed 8 years ago by
Patch needs to be rebased. Also:
set_mutable
should be removed. If you know what you are doing, you can change the_is_immutable
attribute. But we shouldn't write and document a method where you are likely to shoot yourself in the foot.- Override
__copy__
and make the copy an immutable object mutable. Its a common pattern tocopy(const_obj)
to get a mutable copy. - Please no
g.mutable(x=None)
. Method names should be crystal-clear about whether they mutate or not. But this is intentionally straddling the boundary between const and mutable, making code intentional hard to read. And there are lots of fun things that can go wrong now, for startersx=None
will make it look like you are changing it while actually getting the value.
This is also in accord with what matrices are doing.
comment:23 Changed 8 years ago by
I'm still totally against a performance loss in exchange for a feature.
To me the only way out is an immutable backend.
Nathann
comment:24 follow-up: ↓ 25 Changed 8 years ago by
You mean performance loss because we are checking one cdef boolean? This is not really a measurable amount of time, I think. It might even be free if the compiler correctly identifies the unlikely branch and speculative execution works its way. On the plus side, you can then use graphs as hash keys which allows you to implement more efficient algorithms. From that point of view, we are talking about a net performance gain.
comment:25 in reply to: ↑ 24 Changed 8 years ago by
Replying to vbraun:
You mean performance loss because we are checking one cdef boolean?
If I recall correctly, the current decorator is indeed not very quick.
By the way, what changes did you do?
comment:26 Changed 8 years ago by
- Description modified (diff)
I've updated the patch.
I also removed the mutability checks from some of the backends. The central user-facing point to implement them is in GenericGraph
/ GenericGraph_pyx
. This is similar to the matrix code where we, for example, don't patch linbox to support (im)mutability.
It seems there is quite a bit of overhead in graph construction since the GenericGraph._backend
is a Python class. This means various dictionary lookups to locate add_vertex
and friends. You could shave off a lot of overhead by
- Move the construction methods (
add_vertex
etc) fromGenericGraph
toGenericGraph_pyx
- Switch
GenericGraphBackend
and its subclasses to Cython and make its methods cdef - Equip
GenericGraph_pyx
with a Cython attributecdef GenericGraphBackend _backend
See also http://docs.cython.org/src/userguide/early_binding_for_speed.html But thats material for another ticket.
Once all the constructions methods are in GenericGraph_pyx
it'll also be easy to switch the mutability check to a very fast inline function.
comment:27 Changed 8 years ago by
Why don't you implement these immutable graph with a boolean value in the sage/graphs/base/ files ? I have nothing against a cdef boolean value that would be checked when add_edge/vertex methods are called (even though I think that the only good way to implement this is to write another backend for immutable graphs. But I can do that later, I don't mind), but I do have something against any unnecessary loss of performances in these classes, and especially in these functions.
I exchange many emails these days about how these base classes should be reimplemented efficiently, and if on the other hand you just come and add 10% there or there, we're just wasting our time.
Nathann
comment:28 follow-up: ↓ 29 Changed 8 years ago by
Another backend for immutable NetworkX graphs, another backend for immutable dense graphs, another backend for immutable sparse graphs? Thats crazy.
We could move the mutability stuff to the base GenericGraphBackend
but then we still have to push the actual check into each backend. Its a possibility, but it does include quite a bit of copy&pasting. And you then can't use the backend in some other code without the mutability check. I think it would be cleaner to just encapsulate the backend (whatever it may be), and push our implementation of mutability into GenericGraph_pyx
.
I can produce a patch that switches the backends to Cython but we should first be onboard that this is the way to go.
comment:29 in reply to: ↑ 28 Changed 8 years ago by
Another backend for immutable NetworkX graphs, another backend for immutable dense graphs, another backend for immutable sparse graphs? Thats crazy.
?
Welll..... That makes one backend per data structure. How crazy is that ? O_o
We could move the mutability stuff to the base
GenericGraphBackend
but then we still have to push the actual check into each backend. Its a possibility, but it does include quite a bit of copy&pasting.
Yep. That's precisely why I don't like it. To me the only way to implement this cleanly and efficiently is to write a backend for that.
Because you can store data much better, and write much more efficient methods for edge queries and neighbor listings when you know that your data will never change. Just write all of it in a big sorted C array.
This way you have no need to copy/paste anything, you surely don't slow anything down, and and you actually gain performance on immutable graphs by using the fact that your data will never change.
Nathann
comment:30 follow-up: ↓ 31 Changed 8 years ago by
If you think you can implement a better immutable-only backend then thats great. But chances are it won't be the best implementation in all cases (e.g. dense vs. sparse). If the user-facing part of the immutability is in GenericGraph_pyx
then its easy to add an imutable backend next to mutable ones, the only difference is that the constructor will already set the immutability flag for the immutable backend(s). Whereas duplicating the backends means twice as many bugs and nothing to base Quivers on until you get around to implementing all of them...
comment:31 in reply to: ↑ 30 Changed 8 years ago by
If you think you can implement a better immutable-only backend then thats great.
Well, it's on the way : #14589 for dense graphs or for sparse graphes http://www.sagemath.org/doc/reference/graphs/sage/graphs/base/static_sparse_graph.html
But these have been written for C implementations of time-consuming algorithms. And thus they do not support labels at all (I personally hate labels more than anything). But I intend to write general-purpose immutable backends for these kinds of graphs in not so long, sooo...
But chances are it won't be the best implementation in all cases (e.g. dense vs. sparse).
Of course not. That's precisely why we have several backends.
If the user-facing part of the immutability is in
GenericGraph_pyx
then its easy to add an imutable backend next to mutable ones, the only difference is that the constructor will already set the immutability flag for the immutable backend(s).
Well, what I had in mind was something like that
immutable_g = Graph(g, immutable = True)
Rather simple.
Whereas duplicating the backends means twice as many bugs
Come on Volker. A backend has very few and very short functions. And immutable data structure are the simplest of all. Are you scared of bugs ? :-P
and nothing to base Quivers on until you get around to implementing all of them...
O_o
Having nothing to base Quivers on is probably the last of my worries. Besides, it does not make much sense to have an immutable dense backend that supports multiple edges and edge labels (they just contradict what 'dense' means), so only a sparse one will exist. No choice, no worry :-P
Nathann
comment:32 Changed 8 years ago by
So your proposal is to copy&paste the (im)mutability check from GenericGraph_pyx
into each mutable backend, and then write immutable backends that eventually will reach feature parity with the mutable backends. And all that so that you don't have to check the mutability flag for the backends that are already immutable? Which is one clock cycle, and possibly for free?
comment:33 Changed 8 years ago by
I don't get what you say. The system of decorators that this patch uses seems to induce a 10% slowdown in a couple of fundamental functions, doesn't it ? If you want to implement immutable graphs with just an additional test of a cdef boolean variable in the necessary functions I don't have anything against it a priori, as the slowdown would be much smaller O_o
And I don't like copied/pasted code. But if you end up writing a patch that does that, I cannot really complain about anything as there are no immutable backends available to replace it. I can't set such a patch to "needs work" saying that you have to implement a real backend, can I ? :-P
So if you end up writing a patch with a lot of copy and paste, and because I will not like it at all, I will later write another patch with a real immutable backend and remove all those copied/pasted code.
And the world will be at peace.
Nathann
comment:34 follow-up: ↓ 35 Changed 8 years ago by
whether or not there is an immutable backend doesn't change the fact that we want to mark mutable graphs as immutable. Unless you always want to copy the graph data in that step, it will always require you to check a mutability flag.
comment:35 in reply to: ↑ 34 Changed 8 years ago by
whether or not there is an immutable backend doesn't change the fact that we want to mark mutable graphs as immutable.
If you just want to mark the Graph
object as immutable, then that does not prevent you from changing the backend while you are at it. Doing so may mean that you get better performances for the adjacency tests later on if a real immutable backend is implemented somewhere.
Unless you always want to copy the graph data in that step, it will always require you to check a mutability flag.
Once more : checking that the graph is immutable is fine with me if you must do it this way, and I will try to save this by writing an immutable graph backend later on. What I want to avoid is a slowdown in current graphs methods.
I expect that, as you say, check a cdef boolean value would not produce a significant slowdown, while the current patch based on decorators does produce a slowdown.
Nathann
comment:36 Changed 8 years ago by
Could we also get this so that we can construct immutable graphs using something like Graph(4, immutable=True)
?
comment:37 Changed 8 years ago by
- Dependencies changed from #14524 to #14524 #14732
comment:38 Changed 8 years ago by
Hello guys !
I just updated #14806, which now contains a (rather large, sorry :-/
) patch which implements a static graph backend. The graphs themselves are not immutable, for they contain many mutable stuff that isn't located in the backends (positions, boundary, fancy other stuff), but at least with this patch you will not have to add decorators to the basic graph methods. And as a result, you will even get better performances with these graphs. It may even improve your own computation if you switch to those backends, as I am told that you do not modify your graphs often. Well, now this information is put to good use :-)
I tried to add documentation/comments to the code, but this patch is so long that there will obviously be things that need fixing. Now I need the "second pair of eyes" which our review process says to be the key to perfection :-P
Nathann
comment:39 Changed 8 years ago by
Would you have anything against my setting this ticket to needs_work
, as there is now an immutable backend on which this feature could definitely use ?
Nathann
comment:40 Changed 8 years ago by
- Status changed from needs_review to needs_work
So whats the roadmap? add set_immutable
as a flag or force the user to make an immutable copy if he wants to hash a graph?
comment:41 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:42 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:43 Changed 7 years ago by
- Status changed from needs_work to needs_info
I notice that this is still "needs work". Is it not the case that we meanwhile have fully-fledged immutable graphs? So, is it a duplicate?
comment:44 Changed 7 years ago by
O_o
Well yes, I guess we have immutable graphs right now. I mean, I fixed many many many bugs because of them, and I would hate to think I fixed all these bugs even though we have no immutable graphs.
I wouldn't stand it.
Nathann
comment:45 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-duplicate/invalid/wontfix
- Reviewers set to Simon King, Nathann Cohen
- Status changed from needs_info to positive_review
Great! So, it is "positive review" with the suggested resolution "duplicate".
comment:46 Changed 7 years ago by
- Resolution set to duplicate
- Status changed from positive_review to closed
Hello !
GenericGraph.__eq__
. If you just want to take edges and vertices in consideration could you say it explicitely in the documentation of the*_mutable
methods ?And.. Well.. Could you add me in Cc when you write things like that ?
Nathann