toton

Hi everyone,
I need to have alarge array of small class'es (in c# sense struct).
For premitive types, as the ArrayList stores value types, hence it
is possible to use apache common primitives library to save memory &
cache overflow.
However, for array of classes, which are small enough, I want to
store them as value, so that they occupy contiguous memory space,
rether than heving them referenced from list.
This is just to decrease cache overflow error & speedup things. Is
there a possible way to do it?.
In general, is there a possible way to locate the class in local stack,
rather than heap or free store? Some common base class or weak
reference type?


abir

peter d

As toton put it so eloquently,


i think you mean objects.

basically, no. and you're probably not going to get as much speed-up
or space savings as you might think. even if not allocated
contiguously, the copying garbage collector is likely to organize them
to be contiguous after the first GC. the extra indirect from the
array of pointers is pretty cheap.

if you *really* want to do something like this, you can allocate an
int[] and logically partition it in the code yourself, but this is
VERY nasty, breaks the OO philosophy, etc.

same deal. the best to could do is create a couple variables with the
"fields" and manually inline the code in the method.

at least from the language perspective, all Java objects are
heap-allocated and accessed through a direct reference (pointer).
i presume a virtual machine would be allowed to break these rules in
cases it can prove equivalence, but i doubt this is used much if at
all. i believe VM implementers instead focus on making the memory
manager fast, fast, and fast.

--
Peter Dillinger
http://www.peterd.org

andrew reilly

That depends a *lot* on the type of object, IMO. Consider things like
complex numbers, or (dunno, I have less experience with these (x,y,z)
coordinate tuples. Compared to cache-prefetch-assisted in-order access
that you get from an embedded array, pointer dereferences are way expensive.


Sometimes you just have to break it. I'm pretty sure that a good matrix
arithmetic class would manage complex numbers the way Matlab does: not as
objects of type "complex", but as a complex-vector class that contains a
vector of floats (or doubles), and another possibly-null vector for the
imaginary part. You still get your OO paradigm, but only at scales larger
than vector. Scalars have to be done differently.

Eiffel (which pre-dates Java) has a nice way of handling this. It has
explicit syntax/key words for managing unboxed objects, in arrays, or as
class members. I imagine that it makes the compiler more complicated, but
it does let you keep your paradigm "all the way down" with good efficiency.

(Hmm: there are Java-bytecode back-ends for at least two Eiffel compilers
that I know about, but I've not used them. I wonder how they manage to
support this Eiffel language feature *and* be JVM-compatible?)

Cheers,

--
Andrew

toton

The problem is, the objects are small, but plenty in number. u can
think them as 2D points ... and I have a fixed size array for them...
Now I access them sequentially, but may not create them sequentally.
Thus if I dont have all the points in nearby place in memory it not
only causes one extra indirection, but also cache overflow. The cost
comes high for computational geomery....
I event dont want the objects to be garbage collected. When I create a
new point, I want to put it it the array at the appropriate place (The
array behaves like a circular buffer here). Thus, no memory management
is at all needed for these large number of objects in practical sense.
(Want to do something like C++ placement new, which is used inside STl
vector class). Thus garbage collector will also get a relief rather
than managing large no of objects to e garbage collected....
Well, when a new Point comes, I really create a new point to put it
into a circular buffer,
rether than reintializing the field of the old point, which was already
there to a new value.
This is done, to keep in mind, I do computation on them in seperate
thread. Once I create a point, it is immutable, fields can't be
changed. Thus thread synchronization problems are not there (which is
another costly thing to do).
Now the points come, the circular buffer stores them, discards the
old, and process in different thread.
Thus, it is better to have them in neaarby memory place, and not t get
garbage collected.
To me, it looks very much like C++ by value array, or C# struct.
The general method do work, but time goes high, ( I think java do
outperform C++ even when it comes for looped processing... or hot
spots, and it has reason to do so). But this is a particular case
where I feel, stack allocation is better, and garbage collector should
not perform...
I have heard that mustang ( Java1.6) performs escape analysis to
allocate small objects in stack rether than heap, to speed up this kind
of feature... Do anyone know how it performs? abir

chris uppal

I think that, if the performance you are seeing is /actually/ inadequate (which
I find quite plausible, but you haven't posted anything quantative so I can't
tell), then you'll be forced to give up on OO style programming for this.

If you want to represent a circular buffer of 2D points, then you could use a
single double[] array with the x and y co-ordinates at even and odd indexes.
Alternatively (and perhaps more feasibly if the data is more complicated than
just a pair of numbers), you could use a bunch of arrays: one for each "field".

You can give that a more OO flavour by creating objects which simply contain an
index into the array(s), and which implement their "fields" by accessing the
arrays. Needless to say, the more performance-critical parts of the code would
not use those objects, but other parts of the code (presumably the bulk of it,
even if it is boring) could use them.

Other that that (which basically amounts to writting C in Java), I don't think
you have any option but to switch to a different language.

-- chris

peter d

As Chris Uppal put it so eloquently,

as in JNI

--
Peter Dillinger
http://www.peterd.org