efficient vector math...

Discussion in 'Java' started by BGB, Nov 29, 2010.

  1. BGB

    BGB Guest

    sorry if I am missing something obvious here, but I am hoping for
    suggestions on a relatively efficient general-purpose way to handle
    vector math and similar (in the sense of geometric vectors...).

    I will likely be writing any code myself, so the request is for ideas
    for a general design.

    this is for a personal project (most of the rest of the project uses C,
    but this will be for the Java part of the project). Java isn't really my
    main language FWIW...



    purposes and requirements:
    performance should be good, and interface should also be nice (if possible);
    the app will be soft real-time on a custom JVM (JavaME style), and the
    GC is slow and so avoiding GC (by minimizing garbage) is preferable (so
    user will not experience stalls);
    it doesn't need to deal with arbitrary N-sized vectors, only 2, 3, and 4
    element vectors (XYZW), and also Quaternions;
    likely vector size and usage will be considered as part of the type (a
    Vec2 is not a Vec3 which is not a Vec4 which is not a Quat);
    the vectors will potentially be recalculated frequently and in large
    numbers;
    ....


    so, a few possibilities:

    A, immutable vectors:
    pros: clean interface, supports merging and sharing vectors, ...
    cons: many vectors may be created, likely creating lots of garbage.

    B, mutable vectors:
    pros: likely to reduce garbage (most recalculation can reuse existing
    vectors);
    cons: vectors can't be shared (since they may change without warning),
    and the interface is more awkward (vector values are copied, meaning
    vectors need to be provided to use for storing temporary values, ...).

    C, supporting both (as different types):
    pros: can mix and match as needed;
    cons: 2x or 3x as many types (mutable and immutable versions of each
    size, 3x if both versions are subclasses of a common abstract type),
    more awkward class names to distinguish them, more methods, ...

    D, supporting both (as different operations on the same type):
    pros: allows mixing and matching use-patterns (general);
    cons: use-case ambiguity (need to infer intended use from context).


    arrays and indices ("float[] vecs=new float[nvecs*4];" or similar):
    pros: errm... likely compact memory...
    cons: likely overly ugly/awkward.

    I have been considering this matter over the past several days.
    leaning at the moment is for option D.


    example classes:
    basic: Vec2, Vec3, Vec4, Quat
    multi-typed (option C):
    Vec2a, Vec3a, Vec4a, Quata //abstract
    Vec2c, Vec3c, Vec4c, Quadc //constant/immutable
    Vec2n, Vec3n, Vec4n, Quatn //mutable

    Vec#c and Vec#n would be subtypes of Vec#a, so methods accepting the
    abstract forms would accept both, with the mutable and immutable forms
    differing in terms of their external behavior.

    options B and D would likely use a "pool" for freed vectors of a given
    type (garbage reduced by manually "freeing" spare vectors, whereas A
    would likely try to do a lookup and on failure create a new vector).

    matrix math may also be considered.


    suggestions, opinions, or other options?...
     
    BGB, Nov 29, 2010
    #1
    1. Advertising

  2. BGB

    markspace Guest

    On 11/28/2010 11:43 PM, BGB wrote:
    > sorry if I am missing something obvious here, but I am hoping for
    > suggestions on a relatively efficient general-purpose way to handle
    > vector math and similar (in the sense of geometric vectors...).



    1. Sorry but tl;dr.

    2. Don't reinvent the wheel.

    <http://kenai.com/projects/jogl/>

    <https://java3d.dev.java.net/>

    <http://www.jmonkeyengine.com/>
     
    markspace, Nov 29, 2010
    #2
    1. Advertising

  3. BGB

    Tom Anderson Guest

    On Mon, 29 Nov 2010, rossum wrote:

    > On Mon, 29 Nov 2010 00:43:09 -0700, BGB <> wrote:
    >
    >> A, immutable vectors:
    >> pros: clean interface, supports merging and sharing vectors, ...
    >> cons: many vectors may be created, likely creating lots of garbage.

    > Use immutable vectors.
    >
    > Whatever method you go for, there will be garbage, reusage or both.
    > Anything you write yourself will be less efficient than the GC written
    > by the Java library programmers.


    He's talking about running this on his own VM, so the GC written by the
    Java VM (not library) programmers is immaterial.

    Although perhaps he might be better off writing something which makes
    garbage, and spending his spare brain power on improving his GC.

    tom

    --
    NO REAL THAN YOU ARE -- Ego Leonard, The Zandvoort Man
     
    Tom Anderson, Nov 29, 2010
    #3
  4. BGB

    BGB Guest

    On 11/29/2010 9:11 AM, Tom Anderson wrote:
    > On Mon, 29 Nov 2010, rossum wrote:
    >
    >> On Mon, 29 Nov 2010 00:43:09 -0700, BGB <> wrote:
    >>
    >>> A, immutable vectors:
    >>> pros: clean interface, supports merging and sharing vectors, ...
    >>> cons: many vectors may be created, likely creating lots of garbage.

    >> Use immutable vectors.
    >>
    >> Whatever method you go for, there will be garbage, reusage or both.
    >> Anything you write yourself will be less efficient than the GC written
    >> by the Java library programmers.

    >
    > He's talking about running this on his own VM, so the GC written by the
    > Java VM (not library) programmers is immaterial.
    >
    > Although perhaps he might be better off writing something which makes
    > garbage, and spending his spare brain power on improving his GC.
    >


    yeah...

    it is custom written, and I have determined roughly aligns with the Java
    ME CLDC profile in terms of the supported language subset.


    I am using a concurrent conservative mark/sweep collector.

    being a conservative GC, the stalls are a bit steep, and the thing
    doesn't do reference counting, meaning that any garbage produced will
    pollute the heap until the GC runs (garbage minimization is then a major
    concern...).

    note that it is concurrent, but does use a SW write barrier, and any
    thread hitting this write barrier during a GC pass will sleep until the
    GC completes (effectively stalling any threads which try to write to the
    heap during a GC, which in Java's case, is pretty much any of them).


    note, I don't use a precise GC mainly for the fact that the GC is mostly
    also used for a large amount of C code, and is not specific to my
    mimi-JVM. precise GC's are notably more of a hassle to work with from C
    (since one has to track GC roots and similar, and be very careful with
    assignments, ...), so I am not so inclined to use them.


    or such...
     
    BGB, Nov 29, 2010
    #4
  5. BGB

    BGB Guest

    On 11/29/2010 8:19 AM, rossum wrote:
    > On Mon, 29 Nov 2010 00:43:09 -0700, BGB<> wrote:
    >
    >> A, immutable vectors:
    >> pros: clean interface, supports merging and sharing vectors, ...
    >> cons: many vectors may be created, likely creating lots of garbage.

    > Use immutable vectors.
    >
    > Whatever method you go for, there will be garbage, reusage or both.
    > Anything you write yourself will be less efficient than the GC written
    > by the Java library programmers.
    >


    note: this would apply if I were using a standard JVM.
    I am not for sake of the project.


    > You do not specify which calculations need to be done with the
    > vectors. When you write your immutable vectors you can 'cheat' and
    > write some special methods that do some of the very common
    > calculations in a non-immutable way internally while exposing an
    > immutable interface. IIRC BigInteger does this, there is a mutable
    > internal class that BI uses for intermediate values that is never
    > exposed in the class interface.
    >


    3D engine scripting stuff...

    this will not be for anything rendering related (luckily), but will have
    to deal with things such as (potentially) entity AI's and moving objects
    around in the scene graph (projectiles, ...).

    typical calculations are likely to be vector addition, subtraction,
    cross product, ...


    > If you are worried about speed then you may well find more problems
    > with the C / Java interface than with GC.
    >


    I have considered the above...

    however, my JNI implementation is not likely to be a big issue, since
    the JNI interface is basically just a thin wrapper over the machinery
    used internally, and also the thing is currently using an interpreter
    anyways (I have not yet gotten around to writing a JIT for JBC yet).


    but, the main performance worry at the moment is the GC, since this
    thing causes obvious pauses when it runs...
     
    BGB, Nov 29, 2010
    #5
  6. BGB

    BGB Guest

    On 11/29/2010 8:49 AM, markspace wrote:
    > On 11/28/2010 11:43 PM, BGB wrote:
    >> sorry if I am missing something obvious here, but I am hoping for
    >> suggestions on a relatively efficient general-purpose way to handle
    >> vector math and similar (in the sense of geometric vectors...).

    >
    >
    > 1. Sorry but tl;dr.
    >
    > 2. Don't reinvent the wheel.
    >
    > <http://kenai.com/projects/jogl/>
    >
    > <https://java3d.dev.java.net/>
    >
    > <http://www.jmonkeyengine.com/>
    >


    Note:
    non-standard/custom-written JVM running inside a modified Quake2 engine
    (as an intended extension/replacement of the standard "gamex86.dll"
    mechanism...).

    so, these libs will do me little good absent going through the pain of
    porting them or implementing them myself (which would likely require
    more of the JavaSE featureset, vs the currently planned JavaME CLDC only
    support), unless there is some specific design note worth considering...


    note: the VM also interacts with another custom VM/language (BGBScript,
    which is based partly on JavaScript and ActionScript, and mostly
    implements ECMA-262-5th Ed...).

    actually, both VM's share the same underlying implementation and
    MM/GC/OO facilities (the same machinery does Class/Instance and
    Prototype OO).


    or such...
     
    BGB, Nov 29, 2010
    #6
  7. BGB

    Arne Vajhøj Guest

    On 29-11-2010 02:43, BGB wrote:
    > sorry if I am missing something obvious here, but I am hoping for
    > suggestions on a relatively efficient general-purpose way to handle
    > vector math and similar (in the sense of geometric vectors...).
    >
    > I will likely be writing any code myself, so the request is for ideas
    > for a general design.
    >
    > this is for a personal project (most of the rest of the project uses C,
    > but this will be for the Java part of the project). Java isn't really my
    > main language FWIW...
    >
    >
    >
    > purposes and requirements:
    > performance should be good, and interface should also be nice (if
    > possible);
    > the app will be soft real-time on a custom JVM (JavaME style), and the
    > GC is slow and so avoiding GC (by minimizing garbage) is preferable (so
    > user will not experience stalls);
    > it doesn't need to deal with arbitrary N-sized vectors, only 2, 3, and 4
    > element vectors (XYZW), and also Quaternions;
    > likely vector size and usage will be considered as part of the type (a
    > Vec2 is not a Vec3 which is not a Vec4 which is not a Quat);
    > the vectors will potentially be recalculated frequently and in large
    > numbers;
    > ...
    >
    >
    > so, a few possibilities:
    >
    > A, immutable vectors:
    > pros: clean interface, supports merging and sharing vectors, ...
    > cons: many vectors may be created, likely creating lots of garbage.
    >
    > B, mutable vectors:
    > pros: likely to reduce garbage (most recalculation can reuse existing
    > vectors);
    > cons: vectors can't be shared (since they may change without warning),
    > and the interface is more awkward (vector values are copied, meaning
    > vectors need to be provided to use for storing temporary values, ...).
    >
    > C, supporting both (as different types):
    > pros: can mix and match as needed;
    > cons: 2x or 3x as many types (mutable and immutable versions of each
    > size, 3x if both versions are subclasses of a common abstract type),
    > more awkward class names to distinguish them, more methods, ...
    >
    > D, supporting both (as different operations on the same type):
    > pros: allows mixing and matching use-patterns (general);
    > cons: use-case ambiguity (need to infer intended use from context).


    In general: A

    With your special restrictions: B

    Never C and D - they seem to combine the worst of A and B.

    Arne
     
    Arne Vajhøj, Nov 30, 2010
    #7
  8. BGB

    Arne Vajhøj Guest

    On 29-11-2010 10:19, rossum wrote:
    > On Mon, 29 Nov 2010 00:43:09 -0700, BGB<> wrote:
    >
    >> A, immutable vectors:
    >> pros: clean interface, supports merging and sharing vectors, ...
    >> cons: many vectors may be created, likely creating lots of garbage.

    > Use immutable vectors.
    >
    > Whatever method you go for, there will be garbage, reusage or both.
    > Anything you write yourself will be less efficient than the GC written
    > by the Java library programmers.


    Hm.

    It is not unusual that specialized solutions are more efficient
    than general solutions.

    > If you are worried about speed then you may well find more problems
    > with the C / Java interface than with GC.


    He said that he would be using a custom JVM with a very slow GC, so ...

    Arne
     
    Arne Vajhøj, Nov 30, 2010
    #8
  9. BGB

    BGB Guest

    On 11/29/2010 5:39 PM, Arne Vajhøj wrote:
    > On 29-11-2010 10:19, rossum wrote:
    >> On Mon, 29 Nov 2010 00:43:09 -0700, BGB<> wrote:
    >>
    >>> A, immutable vectors:
    >>> pros: clean interface, supports merging and sharing vectors, ...
    >>> cons: many vectors may be created, likely creating lots of garbage.

    >> Use immutable vectors.
    >>
    >> Whatever method you go for, there will be garbage, reusage or both.
    >> Anything you write yourself will be less efficient than the GC written
    >> by the Java library programmers.

    >
    > Hm.
    >
    > It is not unusual that specialized solutions are more efficient
    > than general solutions.
    >


    yeah, dropping back in an array of spares may be faster than waiting for
    the GC to reclaim the memory (via good old mark/sweep), and if anything
    may shave off the amount of garbage some.

    but, yes, this is mostly an artifact of a GC, which is decidedly not
    very good (performance wise), but in general it works well provided one
    can avoid a GC (usually this is done via semi-manual MM, IOW, actually
    freeing stuff...).


    whether or not this would be faster in a JVM with an actually decent GC
    is an open question. I have my reasons here though (for both a GC and a
    custom-written VM).


    >> If you are worried about speed then you may well find more problems
    >> with the C / Java interface than with GC.

    >
    > He said that he would be using a custom JVM with a very slow GC, so ...
    >


    yeah...

    500ms or 1s or more is typical, ... which is very obvious in an
    interactive 3D engine...
     
    BGB, Nov 30, 2010
    #9
  10. BGB

    BGB Guest

    On 11/29/2010 5:37 PM, Arne Vajhøj wrote:
    > On 29-11-2010 02:43, BGB wrote:
    >> sorry if I am missing something obvious here, but I am hoping for
    >> suggestions on a relatively efficient general-purpose way to handle
    >> vector math and similar (in the sense of geometric vectors...).
    >>
    >> I will likely be writing any code myself, so the request is for ideas
    >> for a general design.
    >>
    >> this is for a personal project (most of the rest of the project uses C,
    >> but this will be for the Java part of the project). Java isn't really my
    >> main language FWIW...
    >>
    >>
    >>
    >> purposes and requirements:
    >> performance should be good, and interface should also be nice (if
    >> possible);
    >> the app will be soft real-time on a custom JVM (JavaME style), and the
    >> GC is slow and so avoiding GC (by minimizing garbage) is preferable (so
    >> user will not experience stalls);
    >> it doesn't need to deal with arbitrary N-sized vectors, only 2, 3, and 4
    >> element vectors (XYZW), and also Quaternions;
    >> likely vector size and usage will be considered as part of the type (a
    >> Vec2 is not a Vec3 which is not a Vec4 which is not a Quat);
    >> the vectors will potentially be recalculated frequently and in large
    >> numbers;
    >> ...
    >>
    >>
    >> so, a few possibilities:
    >>
    >> A, immutable vectors:
    >> pros: clean interface, supports merging and sharing vectors, ...
    >> cons: many vectors may be created, likely creating lots of garbage.
    >>
    >> B, mutable vectors:
    >> pros: likely to reduce garbage (most recalculation can reuse existing
    >> vectors);
    >> cons: vectors can't be shared (since they may change without warning),
    >> and the interface is more awkward (vector values are copied, meaning
    >> vectors need to be provided to use for storing temporary values, ...).
    >>
    >> C, supporting both (as different types):
    >> pros: can mix and match as needed;
    >> cons: 2x or 3x as many types (mutable and immutable versions of each
    >> size, 3x if both versions are subclasses of a common abstract type),
    >> more awkward class names to distinguish them, more methods, ...
    >>
    >> D, supporting both (as different operations on the same type):
    >> pros: allows mixing and matching use-patterns (general);
    >> cons: use-case ambiguity (need to infer intended use from context).

    >
    > In general: A
    >
    > With your special restrictions: B
    >


    I guess I will have to agree here...
    A is cleaner, and likely a fast GC would clean things up effectively
    without any obvious stalls (like in a real JVM).

    B works because it can minimize garbage, despite being a little less
    elegant.


    > Never C and D - they seem to combine the worst of A and B.
    >


    yeah, I guess I agree...


    C seems like it would add too much complexity to be worthwhile...

    D yeah, I guess is likely to be unreasonably error prone, and violates
    the ideal of a single object that does a single thing in a single way
    (similar object that does similar things in multiple ways).


    so, plain mutable vectors it is probably...


    well, there is a reason I posted this on usenet...
     
    BGB, Nov 30, 2010
    #10
  11. In article <id1ubf$dih$>, BGB <>
    wrote:

    > so, plain mutable vectors it is probably...


    This simulation,

    <http://sites.google.com/site/drjohnbmatthews/kineticmodel>

    uses a mutable 2D org.gcs.kinetic.Vector:

    <http://sites.google.com/site/drjohnbmatthews/kineticmodel/code#Vector>

    Alternatively, JScicence offers a more general, immutable
    org.jscience.mathematics.vector.Vector. It uses Javolution's stack
    allocation feature to reduce garbage collection.

    <http://www.jscience.org/>

    --
    John B. Matthews
    trashgod at gmail dot com
    <http://sites.google.com/site/drjohnbmatthews>
     
    John B. Matthews, Nov 30, 2010
    #11
  12. In article <icvlii$db$>, BGB <>
    wrote:

    > sorry if I am missing something obvious here, but I am hoping for
    > suggestions on a relatively efficient general-purpose way to handle
    > vector math and similar (in the sense of geometric vectors...).
    >
    > I will likely be writing any code myself, so the request is for ideas
    > for a general design.
    >
    > this is for a personal project (most of the rest of the project uses C,
    > but this will be for the Java part of the project). Java isn't really my
    > main language FWIW...
    >
    >
    >
    > purposes and requirements:
    > performance should be good, and interface should also be nice (if possible);
    > the app will be soft real-time on a custom JVM (JavaME style), and the
    > GC is slow and so avoiding GC (by minimizing garbage) is preferable (so
    > user will not experience stalls);
    > it doesn't need to deal with arbitrary N-sized vectors, only 2, 3, and 4
    > element vectors (XYZW), and also Quaternions;
    > likely vector size and usage will be considered as part of the type (a
    > Vec2 is not a Vec3 which is not a Vec4 which is not a Quat);
    > the vectors will potentially be recalculated frequently and in large
    > numbers;
    > ...
    >
    >
    > so, a few possibilities:
    >
    > A, immutable vectors:
    > pros: clean interface, supports merging and sharing vectors, ...
    > cons: many vectors may be created, likely creating lots of garbage.
    >
    > B, mutable vectors:
    > pros: likely to reduce garbage (most recalculation can reuse existing
    > vectors);
    > cons: vectors can't be shared (since they may change without warning),
    > and the interface is more awkward (vector values are copied, meaning
    > vectors need to be provided to use for storing temporary values, ...).
    >
    > C, supporting both (as different types):
    > pros: can mix and match as needed;
    > cons: 2x or 3x as many types (mutable and immutable versions of each
    > size, 3x if both versions are subclasses of a common abstract type),
    > more awkward class names to distinguish them, more methods, ...
    >
    > D, supporting both (as different operations on the same type):
    > pros: allows mixing and matching use-patterns (general);
    > cons: use-case ambiguity (need to infer intended use from context).
    >
    >
    > arrays and indices ("float[] vecs=new float[nvecs*4];" or similar):
    > pros: errm... likely compact memory...
    > cons: likely overly ugly/awkward.
    >
    > I have been considering this matter over the past several days.
    > leaning at the moment is for option D.
    >
    >
    > example classes:
    > basic: Vec2, Vec3, Vec4, Quat
    > multi-typed (option C):
    > Vec2a, Vec3a, Vec4a, Quata //abstract
    > Vec2c, Vec3c, Vec4c, Quadc //constant/immutable
    > Vec2n, Vec3n, Vec4n, Quatn //mutable
    >
    > Vec#c and Vec#n would be subtypes of Vec#a, so methods accepting the
    > abstract forms would accept both, with the mutable and immutable forms
    > differing in terms of their external behavior.
    >
    > options B and D would likely use a "pool" for freed vectors of a given
    > type (garbage reduced by manually "freeing" spare vectors, whereas A
    > would likely try to do a lookup and on failure create a new vector).
    >
    > matrix math may also be considered.
    >
    >
    > suggestions, opinions, or other options?...



    Option A is the clean way but GC costs will completely dominate the CPU.
    GC is indeed fast, but it's nowhere near as fast as small vector
    operations.

    Option B works but it brittle when caching and sharing is involved.
    Mutable keys destroy many types of caches.

    Option C: I've done mixed class types for bitmap rendering where
    intermediate stages needed caching. Immutable was the special case
    because caching and sharing were few compared to the many calculations.
    The abstract base class for both supported all read operations and
    defined methods getMutable() and getImmutable(). The
    getMutable/getImmutable implementations returned the 'this' reference or
    a new object as needed. No casting or 'instanceof' was needed.


    D sounds messy.
    --
    I will not see posts or email from Google because I must filter them as spam
     
    Kevin McMurtrie, Dec 2, 2010
    #12
  13. BGB

    BGB Guest

    On 12/1/2010 8:09 PM, Kevin McMurtrie wrote:
    > In article<icvlii$db$>, BGB<>
    > wrote:
    >
    >> sorry if I am missing something obvious here, but I am hoping for
    >> suggestions on a relatively efficient general-purpose way to handle
    >> vector math and similar (in the sense of geometric vectors...).
    >>
    >> I will likely be writing any code myself, so the request is for ideas
    >> for a general design.
    >>
    >> this is for a personal project (most of the rest of the project uses C,
    >> but this will be for the Java part of the project). Java isn't really my
    >> main language FWIW...
    >>
    >>
    >>
    >> purposes and requirements:
    >> performance should be good, and interface should also be nice (if possible);
    >> the app will be soft real-time on a custom JVM (JavaME style), and the
    >> GC is slow and so avoiding GC (by minimizing garbage) is preferable (so
    >> user will not experience stalls);
    >> it doesn't need to deal with arbitrary N-sized vectors, only 2, 3, and 4
    >> element vectors (XYZW), and also Quaternions;
    >> likely vector size and usage will be considered as part of the type (a
    >> Vec2 is not a Vec3 which is not a Vec4 which is not a Quat);
    >> the vectors will potentially be recalculated frequently and in large
    >> numbers;
    >> ...
    >>
    >>
    >> so, a few possibilities:
    >>
    >> A, immutable vectors:
    >> pros: clean interface, supports merging and sharing vectors, ...
    >> cons: many vectors may be created, likely creating lots of garbage.
    >>
    >> B, mutable vectors:
    >> pros: likely to reduce garbage (most recalculation can reuse existing
    >> vectors);
    >> cons: vectors can't be shared (since they may change without warning),
    >> and the interface is more awkward (vector values are copied, meaning
    >> vectors need to be provided to use for storing temporary values, ...).
    >>
    >> C, supporting both (as different types):
    >> pros: can mix and match as needed;
    >> cons: 2x or 3x as many types (mutable and immutable versions of each
    >> size, 3x if both versions are subclasses of a common abstract type),
    >> more awkward class names to distinguish them, more methods, ...
    >>
    >> D, supporting both (as different operations on the same type):
    >> pros: allows mixing and matching use-patterns (general);
    >> cons: use-case ambiguity (need to infer intended use from context).
    >>
    >>
    >> arrays and indices ("float[] vecs=new float[nvecs*4];" or similar):
    >> pros: errm... likely compact memory...
    >> cons: likely overly ugly/awkward.
    >>
    >> I have been considering this matter over the past several days.
    >> leaning at the moment is for option D.
    >>
    >>
    >> example classes:
    >> basic: Vec2, Vec3, Vec4, Quat
    >> multi-typed (option C):
    >> Vec2a, Vec3a, Vec4a, Quata //abstract
    >> Vec2c, Vec3c, Vec4c, Quadc //constant/immutable
    >> Vec2n, Vec3n, Vec4n, Quatn //mutable
    >>
    >> Vec#c and Vec#n would be subtypes of Vec#a, so methods accepting the
    >> abstract forms would accept both, with the mutable and immutable forms
    >> differing in terms of their external behavior.
    >>
    >> options B and D would likely use a "pool" for freed vectors of a given
    >> type (garbage reduced by manually "freeing" spare vectors, whereas A
    >> would likely try to do a lookup and on failure create a new vector).
    >>
    >> matrix math may also be considered.
    >>
    >>
    >> suggestions, opinions, or other options?...

    >
    >
    > Option A is the clean way but GC costs will completely dominate the CPU.
    > GC is indeed fast, but it's nowhere near as fast as small vector
    > operations.
    >
    > Option B works but it brittle when caching and sharing is involved.
    > Mutable keys destroy many types of caches.
    >
    > Option C: I've done mixed class types for bitmap rendering where
    > intermediate stages needed caching. Immutable was the special case
    > because caching and sharing were few compared to the many calculations.
    > The abstract base class for both supported all read operations and
    > defined methods getMutable() and getImmutable(). The
    > getMutable/getImmutable implementations returned the 'this' reference or
    > a new object as needed. No casting or 'instanceof' was needed.
    >
    >
    > D sounds messy.


    yeah.


    in my implementation (a custom-written mini-JVM with a slow GC and no
    JIT), option B is probably the best overall...

    although sadly I am busy enough recently that I haven't gotten around to
    implementing it as of yet...


    the revised 'Option C' is an interesting idea, I may consider it...

    I will guess it does not support direct access: 'vec.x' (since one needs
    to either make it final or not final, or rely on good graces that one
    does not assign it in the immutable case...).

    I guess, "vec.getX()" or "vec.x()" should also work.


    (below is untested, just assuming that javac will not barf...).


    idly thinking here:
    public class Vec3
    {
    private static final int MAX=1024;
    private static Vec3[] cache;
    private static int nCache;

    private double x, y, z;

    static {
    cache=new Vec3[MAX];
    nCache=0;
    }

    public Vec3()
    { this(0, 0, 0); }
    public Vec3(double x, double y, double z)
    { this.x=x; this.y=y; this.z=z; }

    public float x() { return x; }
    public float y() { return y; }
    public float z() { return z; }

    public void x(double v) { x=v; }
    public void y(double v) { y=v; }
    public void z(double v) { z=v; }

    public void set(double x, double y, double z)
    { this.x=x; this.y=y; this.z=z; }
    public void set(Vec3 v)
    { x=v.x; y=v.y; z=v.z; }

    public void addn(Vec3 v)
    { x+=v.x; y+=v.y; z+=v.z; }
    public void subn(Vec3 v)
    { x-=v.x; y-=v.y; z-=v.z; }

    public Vec3 add(Vec3 v)
    { return Vec3.at(x+v.x, y+v.y, z+v.z); }
    public Vec3 sub(Vec3 v)
    { return Vec3.at(x-v.x, y-v.y, z-v.z); }

    public double dot(Vec3 v)
    { return x*v.x + y*v.y + z*v.z; }

    ....

    public Vec3 at(double x, double y, double z)
    {
    Vec3 tmp;
    if(nCache>0)
    {
    tmp=cache[--nCache];
    tmp.set(x, y, z);
    return tmp;
    }
    return new Vec3(x, y, z);
    }

    public void free()
    {
    if(nCache<MAX)
    cache[nCache++]=this;
    }

    }


    an immutable case (implicit subclass?) could possibly disallow the
    destructive methods (they are no-op or throw an exception), and probably
    an 'Vec3.at(x, y, z)' method could be used to cache immutable vectors
    (likely merged by epsilon and hashed).

    something like:

    public int hash()
    {
    long ix, iy, iz, i; //long is overkill?...
    ix=(long)(x/EPSILON);
    iy=(long)(y/EPSILON);
    iz=(long)(z/EPSILON);

    i=((ix*4294967291L+iy)*4294967291L+iz)*4294967291L;
    return (int)(i>>>32);
    }

    public Vec3 at(double x, double y, double z)
    {
    Vec3 tmp;
    int h;

    h=hash()&1023;

    tmp=cache[h];
    if(tmp && tmp.isAt(x, y, z))
    return tmp;
    tmp=new ImmutableVec3(x, y, z);
    cache[h]=tmp;
    return tmp;
    }


    or such...
     
    BGB, Dec 2, 2010
    #13
  14. BGB

    BGB Guest

    On 12/1/2010 11:58 PM, BGB wrote:

    >
    > (below is untested, just assuming that javac will not barf...).
    >


    grr...

    more than a few obvious problems in this one...

    oh well, fixed a few of them after copy/paste/edit/compile...
    well, alas, these sorts of errors are typical and expected...


    >
    > idly thinking here:
    > public class Vec3

    public class Vec3 extends Object

    > {


    protected static final double EPSILON=0.000001;
    (epsilon is arbitrary but should work...)

    > private static final int MAX=1024;
    > private static Vec3[] cache;
    > private static int nCache;
    >

    (still private: subclass has its own cache)

    > private double x, y, z;

    protected double x, y, z;
    (because subclass needs to see it...).

    >
    > static {
    > cache=new Vec3[MAX];
    > nCache=0;
    > }
    >
    > public Vec3()
    > { this(0, 0, 0); }
    > public Vec3(double x, double y, double z)
    > { this.x=x; this.y=y; this.z=z; }
    >
    > public float x() { return x; }
    > public float y() { return y; }
    > public float z() { return z; }


    public double x() { return x; }
    public double y() { return y; }
    public double z() { return z; }

    (note: getX()/... would be a bit much added typing...).

    >
    > public void x(double v) { x=v; }
    > public void y(double v) { y=v; }
    > public void z(double v) { z=v; }
    >
    > public void set(double x, double y, double z)
    > { this.x=x; this.y=y; this.z=z; }
    > public void set(Vec3 v)
    > { x=v.x; y=v.y; z=v.z; }
    >
    > public void addn(Vec3 v)
    > { x+=v.x; y+=v.y; z+=v.z; }
    > public void subn(Vec3 v)
    > { x-=v.x; y-=v.y; z-=v.z; }
    >
    > public Vec3 add(Vec3 v)
    > { return Vec3.at(x+v.x, y+v.y, z+v.z); }
    > public Vec3 sub(Vec3 v)
    > { return Vec3.at(x-v.x, y-v.y, z-v.z); }
    >


    (I don't figure having both destructive and non-destructive ops hurts
    too much here...).

    > public double dot(Vec3 v)
    > { return x*v.x + y*v.y + z*v.z; }
    >
    > ...
    >
    > public Vec3 at(double x, double y, double z)

    public static Vec3 at(double x, double y, double z)
    > {
    > Vec3 tmp;
    > if(nCache>0)
    > {
    > tmp=cache[--nCache];
    > tmp.set(x, y, z);
    > return tmp;
    > }
    > return new Vec3(x, y, z);
    > }
    >
    > public void free()
    > {
    > if(nCache<MAX)
    > cache[nCache++]=this;
    > }
    >


    'free()' is decidedly "dangerous", but anyways if cache gets full extras
    fall to GC... this is mostly for cases where one knows the vector is
    garbage. this operation is no-op for ImmutableVec3.

    > }
    >
    >
    > an immutable case (implicit subclass?) could possibly disallow the
    > destructive methods (they are no-op or throw an exception), and probably
    > an 'Vec3.at(x, y, z)' method could be used to cache immutable vectors
    > (likely merged by epsilon and hashed).
    >
    > something like:
    >
    > public int hash()

    public static int hash(double x, double y, double z)

    > {
    > long ix, iy, iz, i; //long is overkill?...


    (still dunno, long is slow and possibly overkill, but dividing by
    EPSILON will give large numbers, and it is preferable to be able to hash
    as many bits as reasonable, even despite a lot of these bits being
    discarded anyways...).

    > ix=(long)(x/EPSILON);
    > iy=(long)(y/EPSILON);
    > iz=(long)(z/EPSILON);
    >
    > i=((ix*4294967291L+iy)*4294967291L+iz)*4294967291L;
    > return (int)(i>>>32);
    > }
    >


    public int hash()
    { return hash(x, y, z); }

    both above merged into Vec3.

    for clarity:
    public boolean isAt(double x, double y, double z)
    {
    if(Math.abs(this.x-x)>EPSILON)return false;
    if(Math.abs(this.y-y)>EPSILON)return false;
    if(Math.abs(this.z-z)>EPSILON)return false;
    return true;
    }


    below is for ImmutableVec3:

    > public Vec3 at(double x, double y, double z)

    public static Vec3 at(double x, double y, double z)
    > {
    > Vec3 tmp;
    > int h;
    >
    > h=hash()&1023;


    h=hash(x, y, z)&1023;
    (errm... yeah...)

    >
    > tmp=cache[h];

    tmp=immCache[h];
    (renamed for clarity...).

    > if(tmp && tmp.isAt(x, y, z))

    if(tmp!=null && tmp.isAt(x, y, z))
    > return tmp;
    > tmp=new ImmutableVec3(x, y, z);
    > cache[h]=tmp;

    immCache[h]=tmp;

    > return tmp;
    > }
    >


    ImmutableVec3 currently makes destructive operations no-op, but
    preferable would be to throw something (since if one tries to modify an
    immutable vector something is obviously wrong...).

    would likely have to make a new exception though as there don't appear
    to be any obvious choices.


    yes, conceptually awkward, but likely most workable...


    >
    > or such...
     
    BGB, Dec 2, 2010
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. pmatos
    Replies:
    6
    Views:
    24,125
  2. Replies:
    8
    Views:
    1,999
    Csaba
    Feb 18, 2006
  3. Javier
    Replies:
    2
    Views:
    622
    James Kanze
    Sep 4, 2007
  4. Rushikesh Joshi
    Replies:
    0
    Views:
    397
    Rushikesh Joshi
    Jul 10, 2004
  5. VK
    Replies:
    15
    Views:
    1,324
    Dr J R Stockton
    May 2, 2010
Loading...

Share This Page