search

ebolwidt / cassowary-java

Optimized version of the port of the cassowary linear constraint solver to the Java language.
Other
10 stars 5 forks source link

What changes have you made to cassowary? #1

Open p-b-west opened 11 years ago

p-b-west commented 11 years ago

Hi,

Can you tell me what changes you have hade to the original cassowary?

Thanks.

ebolwidt commented 11 years ago

On 12/4/13 7:04 AM, numinasthmatic wrote:

Hi,

Can you tell me what changes you have hade to the original cassowary?

Thanks.

— Reply to this email directly or view it on GitHub https://github.com/ebolwidt/cassowary-java/issues/1.

Hi,

I only worked on the java version, and I focused (so far) only on performance. I was going to focus on a Layout Manager as it was related to work activities, but my work focus changed so I haven't completed that.

However I did manage to achieve a major performance boost. Primarily by using the more modern collections API instead of old-fashioned Vectors and Hashtables (it makes the code more maintainable, and it offers some performance improvement by not synchronizing - cassowary isn't thread-safe in any case) More specifically by using IdentityHashMap / IdentityHashSet to associate objects with eachother instead of ordinary Maps - this provides a major performance boost. In a few tests I did, this improved performance 2-3 fold if I remember correctly.

Erwin

p-b-west commented 11 years ago

Hi Erwin,

Thanks for getting back to me. I don't have a mathematical background, so I struggle to understand the algorithm, but I'm going to try to dissect it. Do you understand the maths of the simplex and the modifications that were done by Badros and Borning? What I would like to do is separate out the standard simplex from the adjustments they have made for the edits and stays, if that is possible. The purpose would be to gain a better understanding of the algorithm, which might point the way to some improvements.

I started a project back in 2009 to update the JFlex, CUP and Cassowary project to use Java 1.6 Collections, generics and enums. That stalled when I couldn't get my changes accepted by the JFlex project. There was also the problem that the CUP developers were in the process of a complete rewrite of CUP.

Peter West

"Have you believed because you have seen me? Blessed are those who have not seen and yet believe."

On 12/04/2013, at 3:12 PM, Erwin Bolwidt notifications@github.com wrote:

On 12/4/13 7:04 AM, numinasthmatic wrote:

Hi,

Can you tell me what changes you have hade to the original cassowary?

Thanks.

— Reply to this email directly or view it on GitHub https://github.com/ebolwidt/cassowary-java/issues/1.

Hi,

I only worked on the java version, and I focused (so far) only on performance. I was going to focus on a Layout Manager as it was related to work activities, but my work focus changed so I haven't completed that.

However I did manage to achieve a major performance boost. Primarily by using the more modern collections API instead of old-fashioned Vectors and Hashtables (it makes the code more maintainable, and it offers some performance improvement by not synchronizing - cassowary isn't thread-safe in any case) More specifically by using IdentityHashMap / IdentityHashSet to associate objects with eachother instead of ordinary Maps - this provides a major performance boost. In a few tests I did, this improved performance 2-3 fold if I remember correctly.

Erwin — Reply to this email directly or view it on GitHub.

ebolwidt commented 11 years ago

Hi,

I understand the idea behind linear constraint solving, and a little bit about simplex. As I understand it, cassowary is interesting because of the way in which variables are handled and how re-solving after the initial solve is handled: if only variables change, solving is much faster than if constraints were added. And the algorithm prefers small changes to variable values. Both of which are useful when it is used for user-interface layouts.

But cassowary isn't being maintained. The java code was written by C++ programmers, and quite a while ago - so it's not up to the current accepted standards for Java source code, I believe.

Did you find the cassowary paper? http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.36.3894&rep=rep1&type=pdf

This page is a simpler description: http://www.wikihow.com/Carry-out-the-Simplex-Algorithm

Erwin

On 12/4/13 9:00 PM, numinasthmatic wrote:

Hi Erwin,

Thanks for getting back to me. I don't have a mathematical background, so I struggle to understand the algorithm, but I'm going to try to dissect it. Do you understand the maths of the simplex and the modifications that were done by Badros and Borning? What I would like to do is separate out the standard simplex from the adjustments they have made for the edits and stays, if that is possible. The purpose would be to gain a better understanding of the algorithm, which might point the way to some improvements.

I started a project back in 2009 to update the JFlex, CUP and Cassowary project to use Java 1.6 Collections, generics and enums. That stalled when I couldn't get my changes accepted by the JFlex project. There was also the problem that the CUP developers were in the process of a complete rewrite of CUP.

Peter West

"Have you believed because you have seen me? Blessed are those who have not seen and yet believe."

On 12/04/2013, at 3:12 PM, Erwin Bolwidt notifications@github.com wrote:

On 12/4/13 7:04 AM, numinasthmatic wrote:

Hi,

Can you tell me what changes you have hade to the original cassowary?

Thanks.

— Reply to this email directly or view it on GitHub https://github.com/ebolwidt/cassowary-java/issues/1.

Hi,

I only worked on the java version, and I focused (so far) only on performance. I was going to focus on a Layout Manager as it was related to work activities, but my work focus changed so I haven't completed that.

However I did manage to achieve a major performance boost. Primarily by using the more modern collections API instead of old-fashioned Vectors and Hashtables (it makes the code more maintainable, and it offers some performance improvement by not synchronizing - cassowary isn't thread-safe in any case) More specifically by using IdentityHashMap / IdentityHashSet to associate objects with eachother instead of ordinary Maps - this provides a major performance boost. In a few tests I did, this improved performance 2-3 fold if I remember correctly.

Erwin — Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHub https://github.com/ebolwidt/cassowary-java/issues/1#issuecomment-16291396.

p-b-west commented 11 years ago

Thanks Erwin,

I have read the B&B paper, which is available on the Cassowary web site. The other reference was very informative, especially the video.

Trying to build your project under NetBeans, I see the following problems. Scanning for projects...

Some problems were encountered while building the effective model for org.klomp:cassowary:jar:1.0.0-SNAPSHOT 'build.plugins.plugin.version' for org.apache.maven.plugins:maven-compiler-plugin is missing. @ line 51, column 12 'build.plugins.plugin.version' for org.apache.maven.plugins:maven-eclipse-plugin is missing. @ line 61, column 12

It is highly recommended to fix these problems because they threaten the stability of your build.

For this reason, future Maven versions might no longer support building such malformed projects.

and

T E S T S

Running org.klomp.cassowary.AddDelResolversTest starting timing test. nCns = 900, nSolvers = 15, nResolves = 400 done building data structures done adding 900 constraints [1177 attempted, 0 exceptions] done adding 900 constraints [1177 attempted, 0 exceptions] done adding 900 constraints [1177 attempted, 0 exceptions] done adding 900 constraints [1177 attempted, 0 exceptions] done adding 900 constraints [1177 attempted, 0 exceptions] done adding 900 constraints [1177 attempted, 0 exceptions] done adding 900 constraints [1177 attempted, 0 exceptions] done adding 900 constraints [1177 attempted, 0 exceptions] done adding 900 constraints [1177 attempted, 0 exceptions] done adding 900 constraints [1177 attempted, 0 exceptions] done adding 900 constraints [1177 attempted, 0 exceptions] done adding 900 constraints [1177 attempted, 0 exceptions] done adding 900 constraints [1177 attempted, 0 exceptions] done adding 900 constraints [1177 attempted, 0 exceptions] done adding 900 constraints [1177 attempted, 0 exceptions] Editing vars with indices 593, 170 about to start resolves done resolves -- now ending edits Elapsed time for add: 2.42 seconds Elapsed time for resolve: 0.606 seconds 900,15,400,1,2420.0,14.0,606.0,5.0,0.17925925925925923,0.4666666666666667,0.10099999999999999,0.16666666666666666 Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 4.805 sec Running org.klomp.cassowary.CassowaryTest Tests run: 10, Failures: 1, Errors: 0, Skipped: 0, Time elapsed: 0.003 sec <<< FAILURE! Running org.klomp.cassowary.util.IdentityHashDoubleMapTest a b c Tests run: 3, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.001 sec

Results :

Failed tests: requiredEditVar(org.klomp.cassowary.CassowaryTest): _editVarMap.size() > 0

Tests run: 14, Failures: 1, Errors: 0, Skipped: 0

The problem is with the assert in ClSimplexSolver.java

// beginEdit() should be called before sending // resolve() messages, after adding the appropriate edit variables public final ClSimplexSolver beginEdit() throws CLInternalError { assert _editVarMap.size() > 0 : "_editVarMap.size() > 0"; // may later want to do more in here _infeasibleRows.clear(); resetStayConstants(); _stkCedcns.addFirst(new Integer(_editVarMap.size())); return this; }

Peter West

"Have you believed because you have seen me? Blessed are those who have not seen and yet believe."

On 12/04/2013, at 11:26 PM, Erwin Bolwidt notifications@github.com wrote:

Hi,

I understand the idea behind linear constraint solving, and a little bit about simplex. As I understand it, cassowary is interesting because of the way in which variables are handled and how re-solving after the initial solve is handled: if only variables change, solving is much faster than if constraints were added. And the algorithm prefers small changes to variable values. Both of which are useful when it is used for user-interface layouts.

But cassowary isn't being maintained. The java code was written by C++ programmers, and quite a while ago - so it's not up to the current accepted standards for Java source code, I believe.

Did you find the cassowary paper? http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.36.3894&rep=rep1&type=pdf

This page is a simpler description: http://www.wikihow.com/Carry-out-the-Simplex-Algorithm

Erwin

On 12/4/13 9:00 PM, numinasthmatic wrote:

Hi Erwin,

Thanks for getting back to me. I don't have a mathematical background, so I struggle to understand the algorithm, but I'm going to try to dissect it. Do you understand the maths of the simplex and the modifications that were done by Badros and Borning? What I would like to do is separate out the standard simplex from the adjustments they have made for the edits and stays, if that is possible. The purpose would be to gain a better understanding of the algorithm, which might point the way to some improvements.

I started a project back in 2009 to update the JFlex, CUP and Cassowary project to use Java 1.6 Collections, generics and enums. That stalled when I couldn't get my changes accepted by the JFlex project. There was also the problem that the CUP developers were in the process of a complete rewrite of CUP.

Peter West

"Have you believed because you have seen me? Blessed are those who have not seen and yet believe."

On 12/04/2013, at 3:12 PM, Erwin Bolwidt notifications@github.com wrote:

On 12/4/13 7:04 AM, numinasthmatic wrote:

Hi,

Can you tell me what changes you have hade to the original cassowary?

Thanks.

— Reply to this email directly or view it on GitHub https://github.com/ebolwidt/cassowary-java/issues/1.

Hi,

I only worked on the java version, and I focused (so far) only on performance. I was going to focus on a Layout Manager as it was related to work activities, but my work focus changed so I haven't completed that.

However I did manage to achieve a major performance boost. Primarily by using the more modern collections API instead of old-fashioned Vectors and Hashtables (it makes the code more maintainable, and it offers some performance improvement by not synchronizing - cassowary isn't thread-safe in any case) More specifically by using IdentityHashMap / IdentityHashSet to associate objects with eachother instead of ordinary Maps - this provides a major performance boost. In a few tests I did, this improved performance 2-3 fold if I remember correctly.

Erwin — Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHub https://github.com/ebolwidt/cassowary-java/issues/1#issuecomment-16291396.

— Reply to this email directly or view it on GitHub.