Please help me on a design decision on immutability

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

Caesar
Posts: 61
Joined: Fri Oct 24, 2008 12:34 am UTC
Location: Germany

Please help me on a design decision on immutability

Postby Caesar » Thu Sep 10, 2015 1:25 pm UTC

I'd like to have some advice on a software design decision.
I have been writing a geometry library, without knowing much about programming and without supervision of any kind. It has been a good learning experience but I am unsure about the best way to do things.
It's written in C#.

Currently, in my geometry library shapes are objects that can never change after they were created. This is for two reasons.
First. If you want to scale a circle the result will be, in general, an ellipse. It would be a nightmare if it would return a new object only some of the times, depending on whether the result is a new type of shape or not. So I just return a new object every time.
Second. Imagine a collection of shapes that requires them to not overlap. If outside code can change the actual shapes and not copies of them, then I can never know if the collection is still valid.
There is a disadvantage, though. In many cases it would be completely fine to mutate a shape, and this way just generates a lot of garbage. I did implement some functions to deal with bulk operations. For example, if you want the union of a list of shapes, the function that accepts the list will possibly generate less garbage than adding the shapes one by one. But still. Maybe you need a polygon that changes a little bit thousands of times and is never assumed to be static anywhere in the code. It would be fine to mutate it and my way is just extremely wasteful.
Maybe I could implement two different kinds of operations. One that returns a new object (e.g. "Getscaled()") and one that either returns the old one or null if the operation can't be done without changing the type (e.g. "Scale()"). And then the shapes can be set to immutable somehow which disables the ability to change the object directly. Or maybe there are two different classes of each kind of shape, one is mutable and one isn't. A shape that consists of other shapes would only accept immutable ones.

At this point I would like some guidance, please. Before I invest time into something that turns out to be dumb. Or maybe the design is already dumb in which case I want to become aware of that sooner rather than later.

Derek
Posts: 2181
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Please help me on a design decision on immutability

Postby Derek » Thu Sep 10, 2015 7:49 pm UTC

Have you actually measured the performance difference? For many applications it's perfectly acceptable to have immutable objects and just create new copies when changes are required. The allocation and freeing overhead is not necessarily that bad, and there are other benefits that can be gained from using immutable objects (only if they're marked as const/final/immutable though, so the compiler knows it can make optimizations).

If you decide that you do need mutability in some instances, I would create separate mutable and immutable types (with constructors that can easily convert between them). Then for an operation that is more efficient with a mutable type, you can take an immutable input, produce a new mutable copy, perform all your operations, then copy the result to an immutable object.

Caesar
Posts: 61
Joined: Fri Oct 24, 2008 12:34 am UTC
Location: Germany

Re: Please help me on a design decision on immutability

Postby Caesar » Thu Sep 10, 2015 9:17 pm UTC

No, I haven't measured anything. It's just armchair philosophy.

I don't know how to tag the classes as immutable for the compiler. As far as I know that's not possible in C#. I can make the fields read-only, but that's not quite the same.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Please help me on a design decision on immutability

Postby korona » Thu Sep 10, 2015 9:33 pm UTC

There is not much a compiler can do if it knows a memory location is const. CSE usually already applies to all non-volatile variables. EDIT: Although in languages with strong "const" guarantees this information might allow the compiler to CSE or move additional loads when they are interleaved with calls to functions with unknown side effects.

Caesar
Posts: 61
Joined: Fri Oct 24, 2008 12:34 am UTC
Location: Germany

Re: Please help me on a design decision on immutability

Postby Caesar » Thu Sep 10, 2015 10:12 pm UTC

So there is not much performance benefit if I make them explicitly immutable.
But I think it would be a good tool for the programmer anyway. Right now, I try to make them immutable but I could have made mistakes. It would be nice if I would get a compile time error if I ever screw something up. For example, an immutable class should only be able to refer to other immutable types.

Tub
Posts: 475
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Please help me on a design decision on immutability

Postby Tub » Fri Sep 11, 2015 3:47 pm UTC

Caesar wrote:But I think it would be a good tool for the programmer anyway. Right now, I try to make them immutable but I could have made mistakes. It would be nice if I would get a compile time error if I ever screw something up. For example, an immutable class should only be able to refer to other immutable types.

C++, Rust (and probably others) have this concept. You can have a normal reference or a const reference to an object. The former can be used to do anything with the object, while the latter can only call methods that don't modify the object.

It's pretty cool (if you need it), but you need pretty good discipline to mark everything that can be const as const.


So, should you make your objects mutable or immutable?

Immutable objects make for simple programming models, since you can just pass objects around without worrying that they'll be modified. Functional languages (like Haskell) work entirely on immutable objects, and they allow for very simple and concise solutions for common problems. Immutable objects are also great for concurrent programming, since you don't need to acquire a lock every time you wish to access an object.

Of course the drawback is that you'll need to copy the whole object every time you make a change. Depending on the size of the object, that can be expensive.
The overhead of memory allocations (including memory fragmentation) depends on the language. In garbage collected languages, memory allocations are cheap and memory is defragmented during collection. (Which is why strings are immutable in Java and C#, but mutable in C++)


So, if you only support very small objects, like Points, Circles, Rectangles and Triangles, the additional copies shouldn't matter much. If you have objects like 10.000-vertex Polygons, that's an entirely different matter.

You should also consider whether collections of Geometries are Geometries themselves. If so, they should implement the same interfaces (like scale() and translate(), which are applied recursively), and with an immutable design, that'd result in a deep copy of everything.

If you only manage a few simple objects, an immutable design is very clean, easy to use and free of pitfalls (like accidentally scaling a geometry inside a non-overlapping container, thus violating the invariant).

If you have either large objects or lots of objects and tight performance deadlines (e.g. in games or visualizations meant to run at 60 fps), your current approach will likely run into its limitations. There are geometry libraries optimized for performance, and their design looks very different from yours (or from any design recommended by a book about object oriented programming).

douglasm
Posts: 630
Joined: Mon Apr 21, 2008 4:53 am UTC

Re: Please help me on a design decision on immutability

Postby douglasm » Tue Sep 15, 2015 2:53 am UTC

In general, immutable objects are much less likely to introduce bugs due to carelessness. Bugs can be costly, in the bug's actual effect, programmer time to fix, and customer perception of your product, and that cost is inherently unpredictable and all too likely to be high.

The primary benefit of mutable objects is potential performance gains from fewer copy actions. This is strictly an optimization and, to quote Knuth, premature optimization is the root of all evil. The performance gain from mutability will likely be small in most cases, and may even be negative - mutable objects have to be copied any time you provide one to another section of code and want to be certain the other code doesn't change your local data, but immutable objects can be passed around by reference without concern.

I would recommend making your objects immutable, excepting only objects where mutability is an essential part of the object's purpose, at least until your program is far enough along to perform a meaningful part of its designed features. Once you reach that point, then start testing performance. If its performance is acceptable, leave it as is. If not, use a performance profiling tool to find where the program is spending most of its time. If profiling results indicate that object copy actions are a major part of the program's operation, then and only then should you go back and make your objects mutable - and even then you should restrict the change to the largest offenders.

User avatar
Xanthir
My HERO!!!
Posts: 5423
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Please help me on a design decision on immutability

Postby Xanthir » Tue Sep 15, 2015 8:07 pm UTC

Well put. I'd add to the last paragraph: and also scope the mutability as much as possible, by only creating and using a mutable variant where necessary, and otherwise converting back to immutable as it leaves to the wider system. A la StringBuilder vs strings.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Caesar
Posts: 61
Joined: Fri Oct 24, 2008 12:34 am UTC
Location: Germany

Re: Please help me on a design decision on immutability

Postby Caesar » Wed Sep 30, 2015 10:59 am UTC

Thanks for all your replies.

I'm gonna abuse the thread to ask a different question about my geometry library.
Mathematically, my shapes are defined as sets of points in the 2D-plane. For example, a circle which center lies on (0,0) and which radius 1 is simply the set of points whose euclidean distance to (0,0) doesn't exceed 1.
But sometimes, I'm not 100% complying to this definition. Circles with negative radius or clockwise polygons, basically "holes", are too practical to explicitly forbid.
They're not well behaved, though. The negative circle has a negative circumference but a positive area (since the radius is squared). The negative polygon on the other hand has a positive "circumference" (what's the word for the generalized circumference anyway?) but a negative area (because cross-product). It's madness!
Similarly, the circumference of a polygon is the sum of the length of its line-segments. But a degenerate polygon which is essentially just a line, according to my definition of what a set is, gives the wrong answer then. The degenerate polygon is well-behaved in some regards and not well-behaved on others and I'm split whether to count it. I COULD check if a polygon traces back parts of itself, or whether it forms a figure-8 and the likes. But it would be comparatively expensive and a bitch to write.
You could say, I'm going back and forth between treating the classes as "objects" and "data structures", if that makes sense.
Right now, many shapes can be used wrong. The user has to make sure himself that the data is valid and if not, the library guarantees for nothing.

Do you have any advice for situations like this?

AndyG314
Posts: 99
Joined: Mon Feb 11, 2008 5:16 pm UTC
Location: Waltham MA
Contact:

Re: Please help me on a design decision on immutability

Postby AndyG314 » Wed Sep 30, 2015 8:54 pm UTC

None of the things you are concerned about really care if the types are immutable or not.

Caesar wrote:First. If you want to scale a circle the result will be, in general, an ellipse. It would be a nightmare if it would return a new object only some of the times, depending on whether the result is a new type of shape or not. So I just return a new object every time.


The operation of scaling a circle should never turn it into an ellipse. Scaling something is a changes is's size without modifying it's aspects.
All circles are ellipses, but not all ellipses are circles. There is no need to implement a special class for circles, an ellipse constructor which generates circles should be sufficient.
If you choose to implement a special circle class, then I don't see why you would allow the ability to morph one into an ellipse, the operation is a change in the essential nature of the circle.


Caesar wrote:Second. Imagine a collection of shapes that requires them to not overlap. If outside code can change the actual shapes and not copies of them, then I can never know if the collection is still valid.

A collection of mutable types can still be const if this is desired.
If it's dead, you killed it.

Caesar
Posts: 61
Joined: Fri Oct 24, 2008 12:34 am UTC
Location: Germany

Re: Please help me on a design decision on immutability

Postby Caesar » Wed Sep 30, 2015 9:56 pm UTC

AndyG314 wrote:The operation of scaling a circle should never turn it into an ellipse. Scaling something is a changes is's size without modifying it's aspects.
All circles are ellipses, but not all ellipses are circles. There is no need to implement a special class for circles, an ellipse constructor which generates circles should be sufficient.
If you choose to implement a special circle class, then I don't see why you would allow the ability to morph one into an ellipse, the operation is a change in the essential nature of the circle.

Yes, circles are a special case of ellipses but it still makes sense to support a circle class because the code is much simpler and I don't expect to deal with ellipses very often anyway. It also has only one radius whereas an ellipse has two, so in a class hierarchy sense, circles are not ellipses.
But of course I still want to be able to scale a circle! I have to be able to scale a circle, it's a fundamental operation of any shape and my base-class requires that I can.
To be clear, I never wanted to MUTATE a circle into an ellipse. That's not possible. That's why the output had to be a new object, because it's of a different type.

Edit:
A collection of mutable types can still be const if this is desired.

I researched this and in C# something can only be const if the value is known at compile time. So that doesn't help me at all here.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 4 guests