kiwi
kiwi copied to clipboard
Objective cell memory leak?
It seems as though the cells for the objective
will grow, but not shrink when edit variables are added/suggested/removed. More specifically, adding edit variables for equality will lead to the objective
picking up 2 cells. These cells are then reduced down to 1. But that cell is not removed from the objective
when the edit variable is removed. Instead, the added cell's value is decremented. This means the objective
cells size will grow with repeated add/remove calls. Is there something I'm missing?
You are not missing anything. That was a deliberate design choice. Trying to track down and remove those cells requires a linear scan over the entire system. It was simpler and faster to simply zero out the cell and make it have no effect on the system.
The reasoning behind this is that the intended use of the solver is to build the system once with a single set of edit variables, and then solve that system multiple times for different values of the same edit variables. I didnt consider adding and removing edit variables frequently/constantly to be a common use case. At that point, its easier to just discard the entire solver and build a new one. All memory from the old solver will be reclaimed.
However, if you are seeing leaks when only using “solver.suggestValue(..)”, that would be a bug.
On Fri, Aug 19, 2022 at 10:08 Nicholas Eddy @.***> wrote:
It seems as though the cells for the objective will grow, but not shrink when edit variables are added/suggested/removed. This means the cells size is unbounded and leads to memory issues for large cycles of edit suggestions. Is there something I'm missing?
— Reply to this email directly, view it on GitHub https://github.com/nucleic/kiwi/issues/154, or unsubscribe https://github.com/notifications/unsubscribe-auth/AABBQSI2ETYRJUMOQUE33SDVZ6PPBANCNFSM57BB5VZQ . You are receiving this because you are subscribed to this thread.Message ID: @.***>
Thanks for the quick reply! 🙏
In my case, I need to update the edit variables whenever an object "tries" to adjust. I could discard the solver each time, but I'm hoping to gain a bit of speed by keeping it around and not rebuilding the constraints each time something adjusts. I also see the same growth for any equals
constraint actually. So this is independent of edit variables. I just happened to notice it there b/c mine contained equality constraints.
Do you have recommendations for how to do the cleanup correctly? I am actually working with a port of this lib that I have full code control over.
The case for a single equals
constraint is that 2 Error
entries are added to the objective, but only 1 is removed when that constraint is remove.
Removing constraints is the same problem. It’s easier to zero out their effect on the system, than to try to remove their objects from the system.
The issue is that when you add a constraint or edit var to the system, it becomes a series of separate cells in a sparse matrix. Solving the system involves moving those cells around (pivoting) the matrix. This means that the parts of a constraint end up scattered all over the matrix. Removing them properly is essentially just as complex as adding them, since the matrix has to be pivoted to do so (IIRC, it’s been a while). So from a complexity standpoint, removing them has the same complexity as creating a new system.
You dont have to re-create the constraints each time, just the solver. The solver doesnt take ownership of the constraints, and is smart enough to only free memory that it created.
It might just be a case of formulating your problem differently.
In the case of a (simplified) UI, the window width and height are the only two edit variables. When the user resizes the window, the new width/height becomes input to ‘solver.suggestValue’. The output of the solver is then the geometry of all the widgets in the window.
If you can describe a bit your use case, I might be able to give a suggestion on how to structure the problem.
On Fri, Aug 19, 2022 at 10:52 Nicholas Eddy @.***> wrote:
Thanks for the quick reply! 🙏
In my case, I need to update the edit variables whenever an object "tries" to adjust. I could discard the solver each time, but I'm hoping to gain a bit of speed by keeping it around and not rebuilding the constraints each time something adjusts. I also see the same growth for any equals constraint actually. So this is independent of edit variables. I just happened to notice it there b/c mine contained equality constraints.
Do you have recommendations for how to do the cleanup correctly? I am actually working with a port of this lib that I have full code control over.
— Reply to this email directly, view it on GitHub https://github.com/nucleic/kiwi/issues/154#issuecomment-1220829656, or unsubscribe https://github.com/notifications/unsubscribe-auth/AABBQSNN3SPOQEM2ARIQBKLVZ6USLANCNFSM57BB5VZQ . You are receiving this because you commented.Message ID: @.***>
A common misconception is using = constraints when you should be using ‘suggestValue’ for an edit var with a ‘strong’ or ‘required’ strength
On Fri, Aug 19, 2022 at 10:54 Nicholas Eddy @.***> wrote:
The case for a single equals constraint is that 2 Error entries are added to the objective, but only 1 is removed when that constraint is remove.
— Reply to this email directly, view it on GitHub https://github.com/nucleic/kiwi/issues/154#issuecomment-1220831971, or unsubscribe https://github.com/notifications/unsubscribe-auth/AABBQSPSH6XVKAWJNKEOIZLVZ6U3RANCNFSM57BB5VZQ . You are receiving this because you commented.Message ID: @.***>
Interesting. Thanks for clarifying. As you suggested, I'll follow up with more context on my use case to get more guidance.
So the leak was actually a bug in the port. But I'll provide more details of my use case still since I'm trying to improve performance while doing more dynamic updates to the constrains/edits.
Ok, I know it's been a while. But I made a lot of good progress on optimizing my solution in the general cases. Now I'm thinking about a slightly different problem. The implementation is very efficient when updating variables, which makes sense. But I have cases where it would be great to express the idea of a "read-only" variable. This would work great in UI layout cases, where you'd like to have a relationship with a parent element that is dynamic, as in it can change over time, yet the solver never tries to update it unless you explicitly suggest a value for it. So essentially, "read-only" edit variables.
And example of this would be: child.left + child.width == parent.width / 2
where you want to avoid the solver ever changing parent.width
, but you want the ability to set/suggest it over time.
Right now I solve this by removing constraints and re-adding them as follows, but this is inefficient.
+ `child.left + child.width == 100
- `child.left + child.width == 100
+ `child.left + child.width == 200
Any suggestions for how you might address this or evolve the solver to handle it?
As suggested @sccolbert in one of his earlier comment you could use an edit variable with a required strength. As a consequence the solver won't change it but you will be able to.
Edit variables can't actually have a strength of required: https://github.com/nucleic/kiwi/blob/78134f725da6b93858da1330bc6fd42dc87d34e2/kiwi/solverimpl.h#L211
Maybe we can experiment with removing that restriction.
On Mon, Oct 24, 2022 at 20:17 Nicholas Eddy @.***> wrote:
Edit variables can't actually have a strength of required: https://github.com/nucleic/kiwi/blob/78134f725da6b93858da1330bc6fd42dc87d34e2/kiwi/solverimpl.h#L211
— Reply to this email directly, view it on GitHub https://github.com/nucleic/kiwi/issues/154#issuecomment-1289850521, or unsubscribe https://github.com/notifications/unsubscribe-auth/AABBQSJMSB7BIX5MUYECCXLWE4YLXANCNFSM57BB5VZQ . You are receiving this because you were mentioned.Message ID: @.***>
I wondered about that, and would be interested in using that ability if possible. Separately, I am exploring a method like suggestValue that updates the constant for a constraint. So far this seems to work.
Maybe we can experiment with removing that restriction.
That would be incredible.
I think this was forbidden because if abused it can easily lead to poor performance. @sccolbert any memory of why you forbid it.
Lifting the restriction in itself would be easy but would call for some extra documentation on when it should be used. Would anybody be interested in making a PR ?
I cant remember, to be honest. Since “required” is just a numerical strength like anything else, I’m thinking that maybe it was just a style decision. Like “you shouldnt need to do this, because there is a better way to solve your problem”. If I recall correctly, there are no special cases for “required” in the math part of the code (but I may be wrong).
On Wed, Oct 26, 2022 at 16:05 Matthieu Dartiailh @.***> wrote:
I think this was forbidden because if abused it can easily lead to poor performance. @sccolbert https://github.com/sccolbert any memory of why you forbid it.
Lifting the restriction in itself would be easy but would call for some extra documentation on when it should be used. Would anybody be interested in making a PR ?
— Reply to this email directly, view it on GitHub https://github.com/nucleic/kiwi/issues/154#issuecomment-1292651808, or unsubscribe https://github.com/notifications/unsubscribe-auth/AABBQSL76G6V7YD6UFPZNZDWFGMKLANCNFSM57BB5VZQ . You are receiving this because you were mentioned.Message ID: @.***>