Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (499)
Games in Android Showcase (118)
games submitted by our members
Games in WIP (568)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2
  ignore  |  Print  
  Structs  (Read 6095 times)
0 Members and 1 Guest are viewing this topic.
Offline Mark Thornton

Senior Member





« Posted 2003-06-08 08:28:41 »

I gather that some here would to see structs added to Java to improve the efficiency of communications with other systems (notably hardware). Rather than add a new language feature I propose a class (below) which the JIT could optimise to achieve the same efficiency as a C struct.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
public abstract class Struct {
   private ByteBuffer buffer;
   private int position;
   
   protected Struct(ByteBuffer b, ByteOrder order) {
      buffer = b.slice();
      buffer.order(order);
   }

   public abstract int size();
   public int alignment() {return 1;}
   public final int position() {return position;}
   public final void position(int p) {
      if (p < 0 || p+size() > buffer.limit()) throw new IndexOutOfBoundsException();
      if ((p&(alignment()-1)) != 0) throw new IllegalArgumentException("Bad alignment");
      position = p;
   }
   public final void setIndex(int i) {
      position(i*size());
   }

   protected int getInt(int offset) {return buffer.getInt(position+offset);}
   protected void setInt(int offset, int value) {buffer.putInt(position+offset, value);}
}

class MyStruct extends Struct {
   public MyStruct(ByteBuffer buf) {super(buf, ByteOrder.nativeOrder());}
   public int size() {return 8;}
   public int getX() {return getInt(0);}
   public void setX(int x) {setInt(0, x);}
   public int getY() {return getInt(4);}
   public void setY(int y) {setInt(4, y);}
}


Now the JIT should be able to optimise this provided that
  • the size() method returns a constant
  • The supplied ByteOrder is suitable. Note that the byte order can't be changed after construction of the Struct.
  • The calls to the get and set methods have constant values for the offset. Or where the value can be deduced to always lie in the range 0 .. size()-sizeof(type).
  • The alignment is constant and suitable for the processor


This mechanism also allows structs to contain 'union's and you can put padding where appropriate.

Thus the performance objective can be achieved by adding just one 'special' class and modifying JITs to make use of the properties of that class.  Even better the code will work with existing JVMs without change (just slower).

OK, so you have to do a bit more typing (or use a wizard), but it ought to be far easier to get this change through the JCP than one which requires a change to the language itself.
Online princec

JGO Kernel


Medals: 392
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #1 - Posted 2003-06-08 10:26:22 »

The mechanism I've proposed before doesn't need a language change, it needs a JVM change to work efficiently. Anything descended from javax.nio.Struct, or Mapped, or whatever, has its fields laid out in memory in a well-defined manner and overlaps a ByteBuffer.

Cas Smiley

Offline Mark Thornton

Senior Member





« Reply #2 - Posted 2003-06-08 11:44:50 »

Quote
fields laid out in memory in a well-defined manner and overlaps a ByteBuffer.

I don't think you can do that without losing some of the characteristics of an object. specifically the hidden words that provide for synchronization and class information can't be in the ByteBuffer. So they must either be removed in which case the Struct is no longer an Object, or the field references become indirect (effectively the same as my Struct class).
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online princec

JGO Kernel


Medals: 392
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #3 - Posted 2003-06-08 12:06:06 »

That's because you misunderstand my implementation Smiley

The base class Struct is thus:
1  
2  
3  
4  
class Struct {
private int position;
private final StructBuffer buf;
}

and it lives within the context of a StructBuffer:
1  
2  
3  
4  
class StructBuffer {
private final ByteBuffer buf;
private final int stride;
}

So you see - there are two classes; one defines the container for a structure, and the other defines merely a position within the container from where data can be read.

Instances of Struct themselves are normal Java objects but all fields in derived classes are defined to live within their parent StructBuffer's ByteBuffer. Synchronisation and other object overhead tags are all present and correct, just as for any normal Object.

You do not keep millions of Struct instances hanging about everywhere, for that would defeat the purpose of Structs. You only need one Struct, really, which is repeatedly positioned within its parent StructBuffer according to its stride.

It's brilliant, even if I do say so myself Smiley

Cas Smiley

Offline Mark Thornton

Senior Member





« Reply #4 - Posted 2003-06-08 13:02:26 »

I think your original proposal included a struct keyword which is certainly a language change. My proposal and yours have the same effect but differ in the following respects
  • You change the semantics of fields in subclasses of Struct. This also counts as a language change. I presume that attempts to include reference fields would be rejected (compile time error).
  • I allow the struct to positioned anywhere in the buffer subject to the alignment constraint. This allows it to be used for nonhomogenous data. Access to data beyond the declared size would also be permitted but not optimised. This would be useful with variable size structures which have a fixed 'header' section.
  • In my proposal the code would run on both existing and new JVMs with the same results. Only the performance is affected.

All that my Struct does is provide the compiler with some guarantees:
  • There are at least size() bytes after the position
  • The position is always a multiple of alignment(). Some machines will require alignment to achieve best optimisation.
  • The byte order doesn't change

You add some syntactic convenience and leave the layout of the struct to the compiler (presumably to be in the order specified without gaps). Whereas currently the order of fields makes no difference to a Java program.

In my case the derived class methods could include loops accessing the buffer and provided that the JIT could deduce (from the loop range) that the resulting accesses were always within the size() constraint then they too could be optimised (i.e. bounds checks eliminated).
Offline Captain-Goatse

Junior Member




I suck at teh 2D. XBOX IS BIG LOL!111


« Reply #5 - Posted 2003-06-08 16:40:08 »

Isn't the point of structs that they are public by nature.

This would prevent other usage that would belong to a class and also emphasis the use of structures.
-unsafe
-fast
-no fancypants functions
-no overhead and easy to optimize/"inline"



Online princec

JGO Kernel


Medals: 392
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #6 - Posted 2003-06-08 18:17:06 »

No, that's not the point of "Structs" - the point of structs is combining efficient memory access with full-blown Java OO capabilities.

I'm having a think about the idea of non-homogenous buffers. I don't like them really - if the data stream is just that, a stream, then you want a stream based protocol to read the data out in the first place, which we've got in NIO already. You can synthesise non-homogenous buffers anyway by wrapping the same bytebuffer in different structbuffers with different offsets and strides but that sounds like a burden of complexity on the programmer. Hm.

Cas Smiley

Offline Mark Thornton

Senior Member





« Reply #7 - Posted 2003-06-08 18:35:49 »

As the purpose of structs would be to improve efficiency of communication with hardware or other processes, we will often not get the luxury of designing the protocol. It was for this reason that I included non homgenous buffers.

You mentioned elsewhere that the facility might also be used for other purposes purely within Java such as holding computation information. While this is possible, I think there are better ways of addressing those shortcomings. My preference would be for a immutable classes with value semantics (much like that proposed by Gosling).
Offline Captain-Goatse

Junior Member




I suck at teh 2D. XBOX IS BIG LOL!111


« Reply #8 - Posted 2003-06-09 06:25:49 »

Quote
No, that's not the point of "Structs" - the point of structs is combining efficient memory access with full-blown Java OO capabilities.

I'm having a think about the idea of non-homogenous buffers. I don't like them really - if the data stream is just that, a stream, then you want a stream based protocol to read the data out in the first place, which we've got in NIO already. You can synthesise non-homogenous buffers anyway by wrapping the same bytebuffer in different structbuffers with different offsets and strides but that sounds like a burden of complexity on the programmer. Hm.

Cas Smiley



Well, why access the memory through buffers then at all?

Why not propose a "struct" that tells the compiler to allocate x amount of memory for x object which's duration is in the hands of the programmer?

It doesn't help at all if you add another non direct route.

But I guess in its essence your idea is like that?
Offline Mark Thornton

Senior Member





« Reply #9 - Posted 2003-06-09 06:36:13 »

Quote

Well, why access the memory through buffers then at all?

Why not propose a "struct" that tells the compiler to allocate x amount of memory for x object which's duration is in the hands of the programmer?

So long as a reference to the object exists we want the behaviour when attempting to use it to be well defined. Unlike C++.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline cfmdobbie

Senior Member


Medals: 1


Who, me?


« Reply #10 - Posted 2003-08-13 10:16:53 »

Incidentally, this RFE appears to have stalled most spectacularly:

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

Is anyone still interested in it, or do priorities lie elsewhere these days?  If still wanted, maybe it should be written up with current understanding and resubmitted?

Hellomynameis Charlie Dobbie.
Online princec

JGO Kernel


Medals: 392
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #11 - Posted 2003-08-13 10:55:27 »

Maybe. I heard that dougtwilleager was interested in the proposal. Or I might have imagined it.

Cas Smiley

Offline gregorypierce

Senior Member




I come upon thee like the blue screen of death....


« Reply #12 - Posted 2003-08-16 01:00:32 »

Wait til the C# advocates make enough noise and then it will rise in priority. While C# is not a cross platform language and .Net pretty much sucks rocks, the Java devs could learn a lot from the language semantics of C# (yeah it has structs too.... and they get allocated on the stack instead of the heap).

http://www.gregorypierce.com

She builds, she builds oh man
When she links, she links I go crazy
Cause she looks like good code but she's really a hack
I think I'll run upstairs and grab a snack!
Offline shawnkendall

Senior Member





« Reply #13 - Posted 2004-02-13 19:32:39 »

I couldn't find the original thread on this but this seems as good as any place to post...
Now that 1.5 beta is out, the RFE list is getting cleaned up a bit.

Currently, there are still several RFEs in the top 20 that are in 1.5 and will get pulled but even without that being done yet, right now the "structs" RFE is at #15.

BUT STILL NO "Evaluation"!

Anyway, here's the link again so vote 'em if ya got 'em

Provide "struct" syntax in the Java language
http://developer.java.sun.com/developer/bugParade/bugs/4820062.html

and the top RFE link
http://developer.java.sun.com/developer/bugParade/top25rfes.html

Shawn Kendall
Cosmic Interactive, LLC
http://www.facebook.com/BermudaDash
Offline Mark Thornton

Senior Member





« Reply #14 - Posted 2004-02-14 08:57:13 »

I notice that JSR-203 is now targetted at J2SE 1.6, having previously fallen of the end of JSR-51 (part of which made 1.4). This relates to the find free disk space  RFE.
There are several other RFEs above Struct which clearly aren't going to make Tiger. In fact as the feature cut off is long gone, if it isn't in 1.5 already it won't make it.
Offline shawnkendall

Senior Member





« Reply #15 - Posted 2004-02-14 16:53:19 »

I certainly don't expect it to make it to 1.5
What I was saying is that, now 1.5. is out a bunch of the higher RFEs will be cleared, and structs wil rise into the top 10 soon, yet stil there has been no eval.

Also, I woudl like to make a call to votes again on this topic.
Whether or not you like the way this struct proposal is being made, more votes for the struct RFE will still help get the issue addressed officially by Sun.

Shawn Kendall
Cosmic Interactive, LLC
http://www.facebook.com/BermudaDash
Offline swpalmer

JGO Coder


Exp: 12 years


Where's the Kaboom?


« Reply #16 - Posted 2004-02-14 23:27:23 »

I don't know that it must be implemented exactly as described in the RFE.  But I agree with the general idea of a mechanism to efficently map the contents of ByteBuffers to a particular arrangement of primative types.  If there is some fancy way of tagging fields in a class so that they can be backed by a particular offset into a byte buffer that may do the trick.. and only be slightly different from how structs is currently proposed.

Mind you I also think there are a lot of other critical enhancements, like that mentioned of better access to the filesystems - free disk space,  file attributes like read,write, executable bits, owner, created time vs. modified time, etc.  Those things are more obviously lacking and it is depressing to see it take so long for such basic things to get addressed.  It's all related to more efficient integration with the external systems though - something critical for Java to work well on the client.

Offline shawnkendall

Senior Member





« Reply #17 - Posted 2004-03-10 15:13:46 »

Latest progress update -
Structs moved up 1 from 15 to 14, due to removal of a complete RFE above in the list.
4 more to go to top ten and well, then maybe there will be an official Sun response.

Keep on voting!

Shawn Kendall
Cosmic Interactive, LLC
http://www.facebook.com/BermudaDash
Offline shawnkendall

Senior Member





« Reply #18 - Posted 2004-08-12 15:18:29 »

Latest progress update -
Structs RFE has moved up to number 12 in the RFE list.
I am on a push in my communities to get another round of votes to get it over the hill to make the top 10.
Only need about 20 more people to give all 3 of their votes.

Remember, even if you don't like the particular proposal, at least it can get a RESPONSE from Sun if we get it up there.

Keep on voting!

Top 25 RFE's (Request for Enhancements)
http://bugs.sun.com/bugdatabase/top25_rfes.do

Actual RFE
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4820062

Shawn Kendall
Cosmic Interactive, LLC
http://www.facebook.com/BermudaDash
Offline Giddy

Senior Newbie




Java games rock!


« Reply #19 - Posted 2004-08-12 17:47:32 »

I am not a C++ shark. But I seem to recall that the only difference between a struct and a class is that all members of a struct are public.

But the difference between a C++ class and a Java class, is that you can cast an arbitrary memory pointer to a pointer of a given class (or struct) and then you can scroll your 'class view' through memory with pointer arithmetics.

I would hate to see such a thing in Java, because pointer arithmetics is awful.

But luckily, the code samples that you have posted, look more like the good old Flyweight Pattern from GOF.

I am not sure I totally follow, how the JVM should be able to optimize this code in a particular way.

Where is the significant performance gain?
Offline swpalmer

JGO Coder


Exp: 12 years


Where's the Kaboom?


« Reply #20 - Posted 2004-08-13 00:23:12 »

There is a memory savings because there is no memory overhead per object.  Since structs would exist in the byte buffer.  Bounds checks would be a little more efficient because they would only be need for the struct boundary, not individual members.

I'm not sure that there will be big savings in the actual machine code produced, but it will be a significant programming convenience and memory savings.

Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #21 - Posted 2004-08-13 05:02:56 »

Quote

I would hate to see such a thing in Java, because pointer arithmetics is awful.


NB: I am a strong advocate of preventing java from ever having full C++ style pointers, for reasons e.g. simlar to those that I don't program in assembler any more - it's unmaintainable and unnecessary. However...

Your reaction is reactionary - it sounds like a knee-jerk "oh, this involves pointers! Pointers are bad! This must be bad!" without thinking about hte details. I feel tempted to say that before making such comments, you should go and learn more of Java. Pointer arithmetic is here, now, and it's not going anywhere (it's a fundamental concept provided by NIO - and I've seen several people use it as such); structs would promote a subset of pointer arithmetic into object management. IMHO, this is a good thing - java has had no syntax-level pointers for 10 years, and now we are in a position to know very well where and how it is necessary for a systems language to gradually introduce some uses of poitners in a controlled way - and are able to do so without suddenly opening a can of worms.

Structs can be (and, as far as I can see, probably already are being) implemented by individuals right now, but you have to do all the setup and management yourself and lose much help you could have had from the compiler and from the JVM if they were "supported" more by the language.

Quote

Where is the significant performance gain?


Please tell me how to manage my 100 million objects, all of which I'll be accessing during the next few milliseconds? No, really. I would like to know! How many decades will it be before Sun's heuristic-based object management has a hope of catching up with the tricks I could do when I - as the app developer - actually know for totally unpredictable (at the execution level) but totally predictable (at the app design level) reasons which objects I want when and in what order?

100 million is NOT an exaggeration...I have game apps that generate that many (not vanilla stuff, but nevertheless (to do with background AI)). I'm not using any big BSP trees myself at the moment, but it's clear that they are going to have rather a lot too on modern game levels with many polygons, no?

malloc will be first against the wall when the revolution comes...
Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #22 - Posted 2004-08-13 05:16:08 »

Quote
There is a memory savings because there is no memory overhead per object.


It is also worth pointing out that when you have very large datasets a lot of the java data structures become useless; creating and managing custom data structures which contain objects using indexes into a big struct is a safe and easy way of working around this (and if you need that many object you probably are skilled enough at DS to be able to make whatever custom DS you need).

For instance, try using an ArrayList with 50,000 objects in it...things that scaled poorly with N but started fast enough were usable at 1,000 objects but now are useless.

malloc will be first against the wall when the revolution comes...
Offline Giddy

Senior Newbie




Java games rock!


« Reply #23 - Posted 2004-08-13 08:29:19 »

Don't get me wrong. I am not against you, but the descriptions in the RFE and this thread are muddy.

The flyweight pattern "solves" the 100 million object problem.

So please clarify:

What facilities should the new VM and API's provide?

What patterns/attributes/annotations/marker-interface signals that the class should be optimized, and what optimizations can be provided?

What are the constraints for objects of this kind. Can the class be part of an inheritance hierarchy? Can it participate in composite structures? Can it have other members than the primitives.
Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #24 - Posted 2004-08-13 08:47:42 »

Quote

The flyweight pattern "solves" the 100 million object problem.


I am eager to hear how - according to you - my objects, which do not contain any shared information beyond their method bodies, are solved by flyweights. I thought flyweights were only useful where many of the objects were object-equivalent, or where significant numbers had identically-valued variables for some subset of the set of vars in the object?

malloc will be first against the wall when the revolution comes...
Offline Giddy

Senior Newbie




Java games rock!


« Reply #25 - Posted 2004-08-13 09:51:33 »

The flyweight pattern shares object instances by making object state extrinsic.

In this particular case, object state is stored in a ByteBuffer.
The only intrinsic state that is needed per instance is the start offset in the bytebuffer.

As PrinseC pointed out, you can probably get away with having a single instance of your 'struct' flyweight object, and modify the offset on demand.
Offline nonnus29

Senior Member




Giving Java a second chance after ludumdare fiasco


« Reply #26 - Posted 2004-08-13 22:48:41 »

Quote
Giddy said;
In this particular case, object state is stored in a ByteBuffer.
The only intrinsic state that is needed per instance is the start offset in the bytebuffer.  

As PrinseC pointed out, you can probably get away with having a single instance of your 'struct' flyweight object, and modify the offset on demand.


I think thats what blah meant when he said this:

Quote
blah said;
Structs can be (and, as far as I can see, probably already are being) implemented by individuals right now,


Isn't this the array-of-objects vs the object-of-arrays argument all over again?
Online princec

JGO Kernel


Medals: 392
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #27 - Posted 2004-08-14 10:53:54 »

Still no sign of anyone looking at this RFE. Perhaps a Sun VM engineer would care to join in the discussion...?

Cas Smiley

Offline NVaidya

Junior Member




Java games rock!


« Reply #28 - Posted 2004-08-14 17:13:47 »

IMHO, this thread should have been appropriately started in the Performance Tuning section for greater visibility - a thought much in hinsight though I must admit !

Probably could try Azeem Jiva or even Jeff (where is he ?) in the Tuning section to see if someone would pick up the bait.

Surely there must be more than 300 members in this Forum eligible to cast their votes. If not anything more, just go vote to get Sun to come up with counterpoints/counter-proposals.

Gravity Sucks !
Online princec

JGO Kernel


Medals: 392
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #29 - Posted 2004-08-15 08:36:35 »

Yeah, but with the extreme sparsity of mods around here we can't move threads around much...

Cas Smiley

Pages: [1] 2
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Pippogeek (41 views)
2014-09-24 16:13:29

Pippogeek (32 views)
2014-09-24 16:12:22

Pippogeek (22 views)
2014-09-24 16:12:06

Grunnt (47 views)
2014-09-23 14:38:19

radar3301 (30 views)
2014-09-21 23:33:17

BurntPizza (65 views)
2014-09-21 02:42:18

BurntPizza (37 views)
2014-09-21 01:30:30

moogie (44 views)
2014-09-21 00:26:15

UprightPath (53 views)
2014-09-20 20:14:06

BurntPizza (55 views)
2014-09-19 03:14:18
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!