C-like contiguous arrays

[reza_rob2]

Hi everyone,

I need C-like, RAM/Cache-contiguous, arrays, as in:

malloc(sizeof(struct s)  *  <very_big_number>);

Is it correct that for this, I must go to JNI?  Is there any other way, that is relatively clean?  I suppose using a StringBuffer might be hackish and slow?

Thanks so much for any insight.

[tom]

Hava a look at nio buffers. You can allocate and manipulate native memory.

http://java.sun.com/j2se/1.4.2/docs/api/java/nio/ByteBuffer.html

[reza_rob2]

Thanks Tom.  This is very useful.

Is there any way to do:

1	arbitrary_object.set_to(nio_buffer, index);

In C we can just say

1	s = malloc(sizeof(s) * 10);

and that way, it is very easy to give structure to the buffer, and work with it.

What is the best solution for this in Java?

Really appreciate your help.

Games published by our own members! Check 'em out!

[tom]

There is no such thing in java. You have to write functions that encode and decode the state of the object to and from the buffer. And you have to keep track of offsets yourself.

[Orangy Tang]

I need C-like, RAM/Cache-contiguous, arrays, as in:

Out of interest, why? It almost sounds like you're trying to directly port a C memory pool, when a proper OO object pool would work just as well (if not better). Unless you really are doing something freaky that is.

[reza_rob2]

Arrrrgg!  I don't know what happened, but for some reason I've stopped being notified for activity on this thread.

I'm really glad I checked manually.

Out of interest, why? It almost sounds like
you're trying to directly port a C memory pool, when a proper OO
object pool would work just as well (if not better). Unless you really
are doing something freaky that is.

Dear Orangy Tang,

The issue is RAM blowup (and cache discontinuity??)

My algorithms may certainly be improvable.  However, I don't think
that what I'm doing, would be unreasonable in C(resource-wise.)

Our last discussion(another thread,) surely helps a lot.

(I'm not trying to port a C program, quite the contrary: I'm
considering porting existing (and so-so working) Java code into
JNI/C.)

If you like to know, it's a terrain rendering algorithm.  I got the idea from:

http://www.flipcode.com/tutorials/geomipmaps.pdf

(Just glanced at it;  no patience to read the details fully.)


The quad tree, is probably a major cause of the RAM blowup.
-----------------------------------------------


The general question about Java (in the long run, and my specific
problem aside) is this:

Suppose you have many nested objects:

class Quad {
     short [] x_range = new short[2]; // small array; overhead
     short [] y_range = new short[2]; // small array; overhead
     QuadNode [][] children;          // small array(s); overhead

     // more small stuff; overhead
};

Moreover, you must new() everything. In C, I use large array;
malloc overhead =~ 0.

So, what is the right way to do this in Java?

If I'm being freaky, let me know please.

Regards, Reza.


PS:  

I _will_ look at the canyon demo's source code.  Ken pointed that out,
on the JOGL thread, and the demo runs fast :-)

Looking forward to it.

[tom]

The obvious solution to this kind of memory bloat is to use less objects. A smal optimization would be to replace x_range with minx, maxx.

But usually you have to look at the big picture. Try changing the design so you don't need many smal objects. Instead store the data in big arrays. In your example, you could possible have a Grid class with all the ranges of all the Quads in the grid stored in one short[] array.

[Nipsu]

When your arrays have fixed sizes, why not combine them in single, continuos array and use constant offset values to access needed portion of the data? Each reference to array is 4 bytes (in 32bit environments) so in the case of three fixed arrays with same type this approach saves 8 bytes / object. That's nearly a megabyte when you have 100k objects of this type.

class NotSmart
{
 short[] x = new short[2];
 short[] y = new short[2];
 short[] z = new short[2];  
}

class Smart
{
 private short[] xyz = new short[6];
 public short getX(int index)  
 {
   return xyz[index];
 }
 // the server vm will optimize method calls away.
 // it will also optimize the +2 too since that's a constant.
 // basically this is the same as direct array access.
 // (not in client vm though).
 public short getY(int index)  
 {
   return xyz[index + 2];
 }
 .
 .
 . etc
}

I suggest that if u need to store and handle primitive types efficiently take a look at Stephanio Vigna's Fastutil project: http://freshmeat.net/projects/fastutil/

[swpalmer]

Sounds like someone should cast a vote for the structs RFE.  Anyone have the URL handy?

Also, 'Cas did a terrain rendering demo ages ago that was very fast and as far as I know only used very basic OpenGL bindings, no native code or the algorithm.

[princec]

Structs RFE: http://developer.java.sun.com/developer/bugParade/bugs/4820062.html
We need all 3 of your votes!!!! Remove your generics votes, we've got that now

Terrain demo - nvidia only (sorry): http://www.puppygames.net/downloads/shaven_puppy_demo.zip

Cas

Games published by our own members! Check 'em out!

[reza_rob2]

Structs RFE: http://developer.java.sun.com/developer/bugParade/bugs/4820062.html

I read almost all comments regarding this RFE.  I'm not sure where there is more discussion.

I'd appreciate clarification of this point:

1.  Do "child" structures point to the Buffer Object; or only the top parent structure (instances) point back to the BufferObject?

2.  Are all of these structures garbage collected?

3.  Are all structures "passed by reference?"

It seems that the answers are yes.  If so, then is this still compact enough in memory, when we consider the overhead of really small structures?  Or, is the point of the RFE, just to avoid (per structure) new() overhead?  (I can see the RFE achieving this point.)

If auto-garbage-collected, then what happens to the empty memory slot?

I'm a bit rusty on the details.

Thank you.

[princec]

The precise semantics haven't really been thrashed out but the general idea is:

A Struct is an abstract class that has a byte buffer offset in it and a reference to a byte buffer. All its fields, which cannot be Object fields, only primitive types, are laid out in a well-defined fashion in memory and instead of being kept on the heap they actually are mapped to offsets into said byte buffer. You can have as many Struct instances as you want but generally you only need one or two, and you can just slide them around the byte buffer by changing the offset. The JVM ensures that the Struct cannot wander off the ends of the buffer.

Cas

[reza_rob2]

Could we just say, "we want C# like structs?"

That way, understanding the RFE may be easier for the Sun engineers.

I mean, probably, I would _never_ trust a M$ product for my cross-platform needs.  However, if Sun does it for Java, I think it would be very useful.

[princec]

I don't know how C# structs work but if they work like we want them to work - purely as sliding mapped objects inside byte buffers - great. But we don't want to go making serious VM changes. I'm perfectly happy with using new() where it's necessary and letting the VM do escape analysis in the future etc. - don't want any of this by value stuff getting into Java to complicate things.

Cas