[math] Mutable "Vector3D"

classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

[math] Mutable "Vector3D"

Gilles Sadowski
Hello.

Would you consider implementing a _mutable_ 3D-vector class?
A crude benchmark which I just did shows that re-using the same object is
always (if sometimes only slightly) more efficient than re-creating it.

[I can help with the editing work.]

Best,
Gilles

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [math] Mutable "Vector3D"

Luc Maisonobe

----- "Gilles Sadowski" <[hidden email]> a écrit :

> Hello.

Hi Gilles,

>
> Would you consider implementing a _mutable_ 3D-vector class?
> A crude benchmark which I just did shows that re-using the same object
> is
> always (if sometimes only slightly) more efficient than re-creating
> it.

3D vectors have been changed from mutable to immutable for both robustness and efficiency reasons ...

When small benchmarks are set up, the overall context is completely under control and instances are created/used/reused in a specific use case, corresponding to a simplified view. In these cases, instances modification appear faster and manageable.

Real life situations with complex systems are not that simple.

Here is a summary of a real case problem, encountered on an operational library using commons-math and Vector3D before it was turned to immutable. In a complex application with lots of data sharing and time-dependent data, we wrote something like:

  Vector3D computeMotion(Trajectory trajectory) {
    Vector3D initialPosition = trajectory.getCurrentPosition();
    complexAlgorithm.processTrajectory(trajectory, targetDate);
    Vector3D finalPosition   = trajectory.getCurrentPosition();
    return finalPosition.subtract(initialPosition);
  }

The team developing computeMotion and the team developing Trajectory worked apart from one another.

With mutable vector, you must be sure the two teams are aware that at each interface they must really know who is responsible for the data, the caller or the callee. They may decide that getCurrentPosition should build and return a new vector, which belongs to the caller which can do what it wants with it, including modifying it. In this case, two vectors are built since getPosition is called twice and processTrajectory has no implementation constraint. They may decide that the getCurrentPosition should return a reference to an internal vector, then computeMotion should be rewritten to clone initialPosition before finalPosition is retrieved. They should also know if the clone must be created before or after the processTrajectory call because the internal reference may be modified internally. Failing to have a very precise interface definition which includes the responsibilities at each level leads to difficult to find bugs.

In order to avoid these bugs, you often resort in using defensive programming and adding a copy yourself, just in case the other team did not do its job properly. In some case, when what you develop is by itself an intermediate library and you don't know how the instances you create will be used, you *must* do this copy.

This leads to a strange result: you have a potentially buggy code if one of the team forgot to do defensive programming properly and you have a code that is really inefficient just because everybody copies everything even when in fact it is not needed.

With immutable object, on the other hand, you really don't have to worry at all. People cannot change the object whatever they do, so you just keep references around and create new instances when you want to change one coordinates. You cannot do otherwise and don't rely on programming rules or developers being smart. There are much fewer bugs and since new instances are created only when needed, at the end you have not that much allocations.Here is a good article about immutable objects: <http://www.ibm.com/developerworks/java/library/j-jtp02183.html>

At the end, it appears that for complex applications with several layers, there are more copies and allocations with mutable objects than with immutable objects!

Another point to note is that the generational garbage collectors work better with really short lived objects. So small immutable instances are handled quickly and allocation should not be feared. It is efficient now, see <http://www.ibm.com/developerworks/java/library/j-jtp09275.html>.

The points above are not theoretical one. Vector3D was mutable and it cost us weeks of works at that time to track difficult bugs in a complex application. This was not a simple problem of communication: I was involved in all teams from commons-math to high level application, the rest of the team was just around me and we exchanged lots of information. After we changed to immutable, all problems were gone and we didn't notice any performance drawback. In fact, another team in another project facing huge performances problems looked at what we have done and changed also their objects to immutable: they got significant performance improvements after that change because their code was copying everything beforehand and it was not needed anymore afterward.

Luc

>
> [I can help with the editing work.]
>
> Best,
> Gilles
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [math] Mutable "Vector3D"

Eric Bowman
[hidden email] wrote:

> The points above are not theoretical one. Vector3D was mutable and it
> cost us weeks of works at that time to track difficult bugs in a
> complex application. This was not a simple problem of communication: I
> was involved in all teams from commons-math to high level application,
> the rest of the team was just around me and we exchanged lots of
> information. After we changed to immutable, all problems were gone and
> we didn't notice any performance drawback. In fact, another team in
> another project facing huge performances problems looked at what we
> have done and changed also their objects to immutable: they got
> significant performance improvements after that change because their
> code was copying everything beforehand and it was not needed anymore
> afterward.

+1

The cognitive overhead of dealing with the possibility of side effects
is a serious brain drain, particularly on such a fundamental atom.
Embrace immutability, and rejoice.

--
Eric Bowman
Boboco Ltd
[hidden email]
http://www.boboco.ie/ebowman/pubkey.pgp
+35318394189/+353872801532


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [math] Mutable "Vector3D"

Ted Dunning
With small objects like this, it is generally a very clear win to have
immutable objects.

With larger matrix and vector objects, the advantage is not so clear.  It is
often very nice to mutate large matrices in place via views.  This usually
happens in the context of a single class such as a decomposition method so a
fruitful approach often is to allow a programmer to make a mutable copy that
is manipulated for a while destructively and then marked as immutable when
it is exposed to the outside world.

On Fri, Apr 24, 2009 at 8:09 AM, Eric Bowman <[hidden email]> wrote:

> [hidden email] wrote:
> > The points above are not theoretical one. Vector3D was mutable and it
> > cost us weeks of works at that time to track difficult bugs in a
> > complex application. ...
>
> +1
>
> The cognitive overhead of dealing with the possibility of side effects
> is a serious brain drain, particularly on such a fundamental atom.
> Embrace immutability, and rejoice.
>
>
Reply | Threaded
Open this post in threaded view
|

Re: [math] Mutable "Vector3D"

sebb-2-2
On 24/04/2009, Ted Dunning <[hidden email]> wrote:
> With small objects like this, it is generally a very clear win to have
>  immutable objects.
>
>  With larger matrix and vector objects, the advantage is not so clear.  It is
>  often very nice to mutate large matrices in place via views.  This usually
>  happens in the context of a single class such as a decomposition method so a
>  fruitful approach often is to allow a programmer to make a mutable copy that
>  is manipulated for a while destructively and then marked as immutable when
>  it is exposed to the outside world.

How does that work?
Do threads have to get a shared read-lock or exclusive write-lock on the object?

>
>  On Fri, Apr 24, 2009 at 8:09 AM, Eric Bowman <[hidden email]> wrote:
>
>  > [hidden email] wrote:
>  > > The points above are not theoretical one. Vector3D was mutable and it
>  > > cost us weeks of works at that time to track difficult bugs in a
>
> > > complex application. ...
>
> >
>  > +1
>  >
>  > The cognitive overhead of dealing with the possibility of side effects
>  > is a serious brain drain, particularly on such a fundamental atom.
>  > Embrace immutability, and rejoice.
>  >
>  >
>

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [math] Mutable "Vector3D"

Ted Dunning
My view is that once it is immutable it is immutable.  Restoring mutability
is done by making a new copy and in the context of the applications I was
describing is essentially never done.

On Fri, Apr 24, 2009 at 10:39 AM, sebb <[hidden email]> wrote:

> allow a programmer to make a mutable copy that
> >  is manipulated for a while destructively and then marked as immutable
> when
> >  it is exposed to the outside world.
>
> How does that work?
> Do threads have to get a shared read-lock or exclusive write-lock on the
> object?




--
Ted Dunning, CTO
DeepDyve
Reply | Threaded
Open this post in threaded view
|

Re: [math] Mutable "Vector3D"

sebb-2-2
OK, that makes sense.

However, only objects that are immutable from construction are
thread-safe without needing some kind of synchronisation.

Passing it to a newly created thread would be OK (Thread.start() is
synch.), but if it is passed to an existing thread some other means of
synch. would be needed.

On 24/04/2009, Ted Dunning <[hidden email]> wrote:

> My view is that once it is immutable it is immutable.  Restoring mutability
>  is done by making a new copy and in the context of the applications I was
>  describing is essentially never done.
>
>
>  On Fri, Apr 24, 2009 at 10:39 AM, sebb <[hidden email]> wrote:
>
>  > allow a programmer to make a mutable copy that
>  > >  is manipulated for a while destructively and then marked as immutable
>  > when
>  > >  it is exposed to the outside world.
>  >
>  > How does that work?
>  > Do threads have to get a shared read-lock or exclusive write-lock on the
>  > object?
>
>
>
>
>
> --
>  Ted Dunning, CTO
>  DeepDyve
>

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [math] Mutable "Vector3D"

Ted Dunning
That is a good and subtle point.

On Fri, Apr 24, 2009 at 11:34 AM, sebb <[hidden email]> wrote:

> OK, that makes sense.
>
> However, only objects that are immutable from construction are
> thread-safe without needing some kind of synchronisation.
>
> Passing it to a newly created thread would be OK (Thread.start() is
> synch.), but if it is passed to an existing thread some other means of
> synch. would be needed.
>
> On 24/04/2009, Ted Dunning <[hidden email]> wrote:
> > My view is that once it is immutable it is immutable.  Restoring
> mutability
> >  is done by making a new copy and in the context of the applications I
> was
> >  describing is essentially never done.
> >
> >
> >  On Fri, Apr 24, 2009 at 10:39 AM, sebb <[hidden email]> wrote:
> >
> >  > allow a programmer to make a mutable copy that
> >  > >  is manipulated for a while destructively and then marked as
> immutable
> >  > when
> >  > >  it is exposed to the outside world.
> >  >
> >  > How does that work?
> >  > Do threads have to get a shared read-lock or exclusive write-lock on
> the
> >  > object?
> >
> >
> >
> >
> >
> > --
> >  Ted Dunning, CTO
> >  DeepDyve
> >
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>


--
Ted Dunning, CTO
DeepDyve

111 West Evelyn Ave. Ste. 202
Sunnyvale, CA 94086
www.deepdyve.com
858-414-0013 (m)
408-773-0220 (fax)
Reply | Threaded
Open this post in threaded view
|

Re: [math] Mutable "Vector3D"

John Bollinger
In reply to this post by Ted Dunning
Ted Dunning wrote:
> My view is that once it is immutable it is immutable.  Restoring mutability
> is done by making a new copy [...].

That position is stronger than you make it sound.  Changing a supposedly
immutable object so that it is mutable would itself be a mutation.  If it were
possible then the object in question was never genuinely immutable in the
first place.


John


     
Reply | Threaded
Open this post in threaded view
|

Re: [math] Mutable "Vector3D"

Ted Dunning
On Fri, Apr 24, 2009 at 11:50 AM, John Bollinger <[hidden email]>wrote:

> Ted Dunning wrote:
> > My view is that once it is immutable it is immutable.  Restoring
> mutability
> > is done by making a new copy [...].
>
> That position is stronger than you make it sound.  Changing a supposedly
> immutable object so that it is mutable would itself be a mutation.  If it
> were
> possible then the object in question was never genuinely immutable in the
> first place.
>

I agree, but that is a bit more of a philosophical answer.  I wanted to give
an operational answer.
Reply | Threaded
Open this post in threaded view
|

Re: [math] Mutable "Vector3D"

John Bollinger
Ted Dunning wrote:

> On Fri, Apr 24, 2009 at 11:50 AM, John Bollinger <[hidden email]>wrote:
>
> > Ted Dunning wrote:
> > > My view is that once it is immutable it is immutable.  Restoring
> > mutability
> > > is done by making a new copy [...].
> >
> > That position is stronger than you make it sound.  Changing a supposedly
> > immutable object so that it is mutable would itself be a mutation.  If it
> > were
> > possible then the object in question was never genuinely immutable in the
> > first place.
> >
> I agree, but that is a bit more of a philosophical answer.  I wanted to give
> an operational answer.

Yes and no.  I'm not trying to be nit picky, and I didn't explicitly say this in my
previous comment, but part of what I was thinking was that the sequence

foo.setMutable(true);
foo.setX(3.14159);

just as surely mutates "immutable" foo as it does mutable foo.


John



     
Reply | Threaded
Open this post in threaded view
|

Re: [math] Mutable "Vector3D"

John Bollinger
In reply to this post by sebb-2-2
sebb wrote:
> OK, that makes sense.
>
> However, only objects that are immutable from construction are
> thread-safe without needing some kind of synchronisation.
>
> Passing it to a newly created thread would be OK (Thread.start() is
> synch.), but if it is passed to an existing thread some other means of
> synch. would be needed.

That's one reason why immutability is best designed as a property of a
class, rather than a property of instances.  A good immutable class does
not provide any mutation methods in the first place, so there is never any
question about whether instances can or should be mutated, and there is
never* a synchronization issue.

Where there is use in having both mutable and immutable representations
of the same thing, it is better to use separate classes.  In some cases, it
might be useful for one or both classes to provide a mechanism to create
copies in the form of the other class (example1: hypothetical method
MutableVector3D#createImmutableCopy() : Vector3D) (example2:
hypothetical constructor MutableVector3D#MutableVector3D(Vector3D)).
Instances can still be used (somewhat) interchangeably if their classes
implement a common interface.


*Caveat: if the constructor does something stupid that makes references
accessible to other threads before the constructor returns, then instances
are not automatically safe from construction.


John



     
Reply | Threaded
Open this post in threaded view
|

Re: [math] Mutable "Vector3D"

Gilles Sadowski
In reply to this post by Luc Maisonobe
Hi.

> > Would you consider implementing a _mutable_ 3D-vector class?
>
> 3D vectors have been changed from mutable to immutable for both robustness and efficiency reasons ...

I'm all convinced that immutability makes for cleaner, and safer code.

The question is: Can we be sure that programming with immutable "Vector3D"
ojects will always be as efficient?
Or equivalently, is the constructor as fast as a method call that would
modify an existing object?

As far as I'm currently concerned, I've changed my source to use "Vector3D"
and, for a code that runs for 60 seconds, the difference is indeed
irrelevant (around 1 part in 60). So I'm not going to insist :-)

> At the end, it appears that for complex applications with several layers,
> there are more copies and allocations with mutable objects than with
> immutable objects!

Of course this is a loose-loose situation ;-)

I still wonder whether there are use-cases that could benefit from a
"MutableVector3D" (as was suggested in a previous post).

> Another point to note is that the generational garbage collectors work
> better with really short lived objects. So small immutable instances are
> handled quickly and allocation should not be feared. It is efficient now,
> see <http://www.ibm.com/developerworks/java/library/j-jtp09275.html>.

This shows that allocation in Java is efficient, but does not compare the
constructor with another method call. Although... if the object is
short-lived, then the JVM could possibly create it on the stack, while
re-using an object may mean that it is long-lived (i.e. on the heap) so that
a method call would actually be slower!

> [...]

Thanks for sharing your experience on the benefits of using immutable
objects.

Best regards,
Gilles

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [math] Mutable "Vector3D"

Ted Dunning
No we can't be sure.  But your point about re-use leading to objects that
could be stack allocated being moved to long-lived storage and thus
triggering full GC's is a strong hint.

For small vectors like this, it is also worth pointing out that accessing
one element is barely faster than allocating and copying 3 elements.  Once
you pay the cache miss price of accessing the first element, the rest come
almost for free.

Another factor that comes into play is that with ad-hoc code or with small
vectors (or, indeed, with vectors instead of matrices) it is very likely
that the CPU is completely bus-bound rather than compute bound.  This again
makes the full copy just about as fast as mutation.

All of these effects are even before you consider the problem of excess
copying due to impenetrable usage patterns.

On Tue, Apr 28, 2009 at 6:06 AM, Gilles Sadowski <
[hidden email]> wrote:

> > > Would you consider implementing a _mutable_ 3D-vector class?
> >
> > 3D vectors have been changed from mutable to immutable for both
> robustness and efficiency reasons ...
>
> I'm all convinced that immutability makes for cleaner, and safer code.
>
> The question is: Can we be sure that programming with immutable "Vector3D"
> ojects will always be as efficient?
> Or equivalently, is the constructor as fast as a method call that would
> modify an existing object?
>



--
Ted Dunning, CTO
DeepDyve

111 West Evelyn Ave. Ste. 202
Sunnyvale, CA 94086
www.deepdyve.com
858-414-0013 (m)
408-773-0220 (fax)