Remove Symbol classes?

[alexbirkett]

A conversation I had with Kiwi's author suggests that there is no benefit to having Symbols in the Java implementation of Kiwi:

Hi

Alex,

Glad to see you are using Kiwi! My responses are inline.

On Fri, May 8, 2015 at 5:52 AM, Alex Birkett [email protected] wrote: Hi,

Back in February I started work on a java port of kiwi. My hope is that it will be faster than cassowary. I never made it work and had another look at it yesterday.

https://github.com/alexbirkett/kiwi-java

I wondered if you would be kind enough to answer some questions?

One of the reasons it does not work is that the HashMaps are not sorted. It gets into an infinite loop in the solver.optimize method.

Can explain how the Constraints, Expressions, Rows are compared with each other? I can't find the code where it's done and suspect it's something built into C++. My working assumption is that

bool operator<( const Symbol& other ) const

{

return m_id < other.m_id;

}

is used to order the Symbols in the maps.

Constraint & Varialbe - These are compared using their internal heap-allocated data pointer, which is wrapped in a SharedDataPtr: https://github.com/nucleic/kiwi/blob/master/kiwi/constraint.h#L56, https://github.com/nucleic/kiwi/blob/master/kiwi/variable.h#L78. This allows them to be used with value semantics without incurring the cost of copying the actual internal data. Expression - Expressions are temporary objects used to populate constraints. They are never used as keys in a map and are passed around with value semantics. This does incur a copy, but compared to the number of times a constraint is passed around, it is trivial. RowMap, Row & Symbol - The row map is the workhorse data structure of the solver. This is modified a lot, so it's important to make modification to it as cheap as possible. This means value semantics with small values. You'll see that the keys are symbols (~12bytes) and the values are raw pointers (8bytes). Neither of these types are virtual and they have trivial copy constructors (no ref counts). This makes them extremely efficient to copy around. A Row uses the same principle with its cell map. As mentioned above, Symbols allow modifications to be made to a map in an efficient manner, but these symbols must be associated with something else in order to be useful. This is where the variable map comes into play. After the solver runs, it makes a pass over the variable map to update the variable value using the value associated with its symbol: https://github.com/nucleic/kiwi/blob/master/kiwi/solverimpl.h#L297

The other thing to keep in mind is the choice of data structure for these maps. Kiwi uses a sorted vector as its map container, instead of a node-based container like std::map. This is very important for performance. Vectors with value types have outstanding cache locality, and this causes them to outperform traditional maps (even on random inserts) until they hit ~1 million elements. You can prove this to yourself by swapping out the map implementation and running a profile: https://github.com/nucleic/kiwi/blob/master/kiwi/maptype.h#L31. In my testing, the sorted vector is ~2x-4x faster than std::map, and ~40% more memory efficient.

Do all maps even need to be sorted or just the maps that use Symbols as keys?

Being sorted is an implementation detail. If you use hash maps, you'll need to implement a hash code for your objects.

Another thing that I may have got wrong is memory handling. I've not implemented any of the inner classes that inherit from SharedData. I'm not sure when you are copying data and when you are sharing references.

Since you are using Java, everything is heap allocated anyway, so you wont really get any benefit of the optimizations I mention above. Your implementation would be better served by ignoring SharedData and Symbols entirely, and just passing around your Variable and Constraint objects directly.

Thanks

Kind regards,

Alex

Cheers,

Chris