Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (538)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (600)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  JADE: Another HashMap and more  (Read 3600 times)
0 Members and 1 Guest are viewing this topic.
Offline Preston

Senior Devvie


Medals: 4



« Posted 2003-11-12 06:09:36 »

http://www.javalobby.org/thread.jsp?forum=61&thread=9377
and
http://jade.dautelle.com/

Some articles in the Javalobby thread show however that it depends on your task if it's good to use it or if the standard HashMap will be OK.

Maybe anybody has got some experiences with JADE ?
Offline Jeff

JGO Coder




Got any cats?


« Reply #1 - Posted 2003-11-12 20:24:46 »

No experience with this.

But the "Hey I wrote a faster hashmap!" thread is a perrenial on performance conferences.  Everytime I've looked at such a thread one of thee things develops:
(1)  {most common}  The implementation turns out to be buggy.  By the time they fix the bugs its no longer faster.
(2) {less common} The implementation is great for small numerb fo entries but doesnt scale as well as HashMapand thus fall beyond for larger numbers of entires-- usually pretty awfully.
(3) {least common} It really is faster, but has some serious inherent other limitation.

The guys who wrote the collections code in the JDK are some of the best general computer scientists I know, actually, and HashMap alogirthyms is a highly researched and understood area.  Based  on that, they chose an algorthym that was reasonably fast and scaled well as the eventual uses of such a general data structure are unknown.


Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline swpalmer

JGO Coder


Exp: 12 years


Where's the Kaboom?


« Reply #2 - Posted 2003-11-12 20:40:10 »

Quote
...they chose an algorthym that was reasonably fast and scaled well as the eventual uses of such a general data structure are unknown.

And that is basically the key to your optimization strategy.  The  JRE collection classes are general purpose.  If you can narrow the scope of usage then there are likely alternatives that may work better.  A recent thread here about Radix sort is one example...

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Jeff

JGO Coder




Got any cats?


« Reply #3 - Posted 2003-11-12 21:32:24 »

Quote

And that is basically the key to your optimization strategy.  The  JRE collection classes are general purpose.  If you can narrow the scope of usage then there are likely alternatives that may work better.  A recent thread here about Radix sort is one example...


Yep.. Thats what we call "Algorythmic Tuning" in the book and can be by far your biggest wins.

But make sure what you are tuning really is a bottleneck before you waste your time on it Wink

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline swpalmer

JGO Coder


Exp: 12 years


Where's the Kaboom?


« Reply #4 - Posted 2003-11-12 23:03:35 »

Quote
Yep.. Thats what we call "Algorythmic Tuning" in the book and can be by far your biggest wins.

Where do you think I get this stuff?  I bought your book before it was made available online for free...  Tongue

Offline Jeff

JGO Coder




Got any cats?


« Reply #5 - Posted 2003-11-13 01:31:25 »

ROFLOL.

Thanks but I'm sure you knew the basics of tuning before reading our book.

Adn blame Steve, it was HIS idea to put it all up as HTML after the first year.  I'm a money grubbing bastard and would still be trying to get every nickel Wink

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline Herkules

Senior Devvie




Friendly fire isn't friendly!


« Reply #6 - Posted 2003-11-13 05:03:32 »

Quote
I'm a money grubbing bastard and would still be trying to get every nickel Wink


You've got mine. Not satisfactory enough?

HARDCODE    --     DRTS/FlyingGuns/JPilot/JXInput  --    skype me: joerg.plewe
Offline Preston

Senior Devvie


Medals: 4



« Reply #7 - Posted 2003-11-13 05:18:44 »

Quote
(..)
The guys who wrote the collections code in the JDK are some of the best general computer scientists I know, actually, and HashMap alogirthyms is a highly researched and understood area.  Based  on that, they chose an algorthym that was reasonably fast and scaled well as the eventual uses of such a general data structure are unknown.

Probably there are historical reasons why many programmers and Java newcomers in particular think some Java classes could be faster than they are. I remember the very first Java versions years ago: Java has been slow in these times. I'm not blaming SUN for this: a desktop JVM has been a relatively new thing, so naturally its first incarnations have been more basic than they are today. (I think only one similar thing has been there, before: the british experiment named TAOS - pretty smart, too.)

I'm happy to see that modern JVMs and Java's large library classes are amazingly fast - so you people at SUN do a very good job.

Some time ago I've been involved in a C++ project where we used the unfortunate STL which comes with the unfortunate MS Visual C++ v6.x. I think MS' STL even missed a HashMap. Anyway we replaced the MS STL with the platform neutral STLport and for (normal) Maps and Sets this boosted performance by the factor of 2+ in any case we used it. I could well imagine a lot of people are suspicious about "built in library collections" because of similar experiences. Even if this is inequitable in a case like Java today.
Offline Jeff

JGO Coder




Got any cats?


« Reply #8 - Posted 2003-11-13 05:54:12 »

Quote

Probably there are historical reasons why many programmers and Java newcomers in particular think some Java classes could be faster than they are. I remember the very first Java versions years ago: Java has been slow in these times. I'm not blaming SUN for this: a JVM has been a new thing to the computing world


Actually VMs themselves are quite old, going back as far as the UCSD P-Machine and IBM's VM operating system.  But if you mean run-time compilers then yes they are fairly recent.  They were used in high performance small talk systems before Java. (In fact Sun's original Hotspot team was a small but brilliant Smalltalk maker that Sun bought and re-purposed.)

What people really need to realize is that performance can be bad for many reasons.  In the beginning, interpretation and simple JITs were an issue. Once we started getting a handle  on that then other things, like architectural problems in Swing surfaced.  Heck,  Swing's firs release was slow because it just happened to be ontop of the brand new 2D library and THAT was slow because we had relied on microbenchmarks and fooled ourselves about its speed.  (The primary thing thst made 1.3 so much better was that we put together a much better benchmark suite to guide us.)

But things like Java2D and Swing are very complex and there are many ways to go wrong.  Something as pure and simple as a HashMap is pretty hard to screw up if you know the datastructures and issues thereof.

Quote

the british experiment named TAOS - pretty smart, too.)

I know a fair bit about TAOS actually. I'm not as a big a fan as apparently you are.  I guess I should leave it at that.

Quote

I'm happy to see that modern JVMs and Java's large library classes are amazingly fast - so you people at SUN do a very good job.


Thank you.  The IBM JVM developers are very fine too, as is the Mac team (though the Mac one is partly based on our code).
I take pride though that we can reasonably compete with IBM witha  much smaller VM team then they have :)

Quote

Some time ago I've been involved in a C++ project where we used the unfortunate STL which comes with the unfortunate MS Visual C++ v6.x.


Been there.  Part of the problem is that MSFT created a non-ANSI C++ that is missing some of whats needed to support normal STL. As a result they had to hack it up.

Quote

I think MS' STL even missed a HashMap. Anyway we replaced the MS STL with the platform neutral STLport


Really? How?  When we tried we found that MSFT's C++ didn't support some unusual "new" syntax that STL used.  (As I recall, and its been awhile, it was a way to use new that let you supply the memory....)


Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline William

Junior Devvie




No Exit


« Reply #9 - Posted 2003-11-13 13:35:42 »

I don't doubt that the collections folks at Sun know their algorithms, but isn't the problem with the collections the internal allocations of objects that are necessary because the collections are so general?

Shawn Kendall posted a thread about that his team had finally found ArrayList to perform well enough to be used in real-time games, and I guess it is no accident that ArrayList doesn't do any per-object allocations/deallocations like HashMap or LinkedList. Internal object creation also keeps the generics proposal from being truly useful to us, as we won't be able to use the auto-boxed primitive collections (even ArrayLists) in performance sensitive applications.

The Jade HashMap seems to solve the problem for HashMap by using an object pool (conceptually quite similar to how ArrayList is able to avoid lots of garbage), but I'm thinking that the best solution would be to avoid the extra object allocation altogether. I've done this in some applications for LinkedLists by creating an interface that specifies the ListEntry functionality, allowing me to implement the interface in the base class of the objects that I want to store in the list. The downside of this is that I have to implement the whole list class myself too.

This is a very application-specific solution and it is bad from a robustness POV to have to implement the ListEntry funcationlity in all the objects to be stored in the list (too easy to forget something somewhere). I guess this is an area where C++'s multiple implementation-inheritance could result in a better solution as it would allow the collection library author to create one class with the ListEntry functionality and have the user of the collection make all the objects he wants to store in a list subclass that class. However, that still wouldn't work for primitive types.

Are there any other optimizations, either in the libraries or the VM/GC, on the horizon that could allow collections as general as Sun's to avoid, or at at least diminish the negative consequences of, the internal allocations?  
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline shawnkendall

Senior Devvie





« Reply #10 - Posted 2003-11-13 16:30:42 »

Linked list interface enbedded in your storable objects is definitely the best solution performance-wise in any language.

It just makes application level programming a pain since you have to implement the damn thing right when you don't want to :-)

In a "complete" system/engine, this is done for the containable objects and then system is used as a whole, so that is one of the things that defines a "layer" - IMHO

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

Senior Devvie




Giving Java a second chance after ludumdare fiasco


« Reply #11 - Posted 2003-11-13 22:29:29 »

n/m
Offline rreyelts

Junior Devvie




There is nothing Nu under the sun


« Reply #12 - Posted 2003-11-14 00:19:39 »

Quote
The guys who wrote the collections code in the JDK are some of the best general computer scientists I know, actually, and HashMap alogirthyms is a highly researched and understood area.  Based  on that, they chose an algorthym that was reasonably fast and scaled well as the eventual uses of such a general data structure are unknown.


We've been working on routing algorithms lately, and it's caused us to take a closer look at some of the java.util data structures. We hold about 100 millions links and nodes in memory. It was interesting to see that Josh Bloch used the same algorithms book that I have from school (Introduction To Algorithms) to create the red-black tree implementation for TreeMap. So, yes, the authors of the Collections classes are using well-proven theory.

On the other hand, if you take a look at the source for HashMap, you can see how things could be more efficient. For example, they re-calculate a hash every single time you perform a get or a put, and the justification used is that the user may have picked a poor hashcode. That's probably smart to guard against the unwashed masses, but it sucks when you're trying to squeeze out every last microsecond of performance.

What's worse is how Sun can't be bothered to support data structures that work efficiently with primitive types. JSR14 is just a sad disappointment in that respect.

God bless,
-Toby Reyelts

About me: http://jroller.com/page/rreyelts
Jace - Easier JNI: http://jace.reyelts.com/jace
Retroweaver - Compile on JDK1.5, and deploy on 1.4: http://retroweaver.sf.net.
Offline rreyelts

Junior Devvie




There is nothing Nu under the sun


« Reply #13 - Posted 2003-11-14 00:23:27 »

Quote
Really? How?  When we tried we found that MSFT's C++ didn't support some unusual "new" syntax that STL used.  (As I recall, and its been awhile, it was a way to use new that let you supply the memory....)


It's called "placement new", and, yes, you supply the address to which the object is "placed". You must have been using a very old version of VC++, because, AFAIK, VC++ 6.0 has always supported placement new, even if it sucked so, so much in so, so many different ways.

God bless,
-Toby Reyelts

About me: http://jroller.com/page/rreyelts
Jace - Easier JNI: http://jace.reyelts.com/jace
Retroweaver - Compile on JDK1.5, and deploy on 1.4: http://retroweaver.sf.net.
Offline Jeff

JGO Coder




Got any cats?


« Reply #14 - Posted 2003-11-14 01:45:33 »

Quote
I don't doubt that the collections folks at Sun know their algorithms, but isn't the problem with the collections the internal allocations of objects that are necessary because the collections are so general?


More to the point, they allocate and deallocate because they were written with your average Java application in mind.

Game clients can have unusually stringent requirements in this area.  

[quote
Shawn Kendall posted a thread about that his team had finally found ArrayList to perform well enough to be used in real-time games, and I guess it is no accident that ArrayList doesn't do any per-object allocations/deallocations like HashMap or LinkedList.
[/quote]

Oh boy, thats a MONSTEROUS leap in logic with no data.
If you really did measurments to see what the impact of these was then it might be supportable, but as a bald faced assertion its nothing more then guesswork and assertion.

In fact, Java allocation and deallocatio nare EXTREMELY fast, much faster then C/C++ as has been shown by numerous benchmarks.  The real issue is not allocation/deallocation at all, its garbage collectiotn.

If you re-read Shawn's post yo uwill see that GC is very specifically what he is talking about.

How your garbage collector responds depends totally on its implementation.  Array list doesnt do a lot of smal lallocations, but it DOES do large allocations as it grows AND does array copies.  Its pretty much a VM specific which is going to cost you more, if either does.

Quote

Internal object creation also keeps the generics proposal from being truly useful to us, as we won't be able to use the auto-boxed primitive collections (even ArrayLists) in performance sensitive applications.


Again, more to the point, blindly relying on autoboxing wilol DEFINITELY hurt you because there IS a translation step at each boxing/unboxing.  There is no code differencve between autoboxing and manually wrapping pirmatives, its juts a bit cleaner syntactically.

Quote

The Jade HashMap seems to solve the problem for HashMap by using an object pool (conceptually quite similar to how ArrayList is able to avoid lots of garbage),


The overhead of pooling is at least as much as the overhead of the Hotspot newspace.  If those objects are short lived, then its probably a net loss.  If they are  long lived, then gc is much less an issue.

Quote

but I'm thinking that the best solution would be to avoid the extra object allocation altogether. I've done this in some applications for LinkedLists by creating an interface that specifies the ListEntry functionality,


Yup building the list header into your data structrues can be a useful tool.  This is one of the few places, actually, where I miss multiple inheritance in Java.

Quote

Are there any other optimizations, either in the libraries or the VM/GC, on the horizon that could allow collections as general as Sun's to avoid, or at at least diminish the negative consequences of, the internal allocations?  


Again your focused  on the wrong place.  Allocation is shit-arse fast in Java.  The issues are GC, and as Shawn pointed out, the GC continues to improve.  We can reasonably hope at some point in the near future it will be a  non-issue.

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #15 - Posted 2003-11-14 08:00:00 »

Quote

Again, more to the point, blindly relying on autoboxing wilol DEFINITELY hurt you because there IS a translation step at each boxing/unboxing.  There is no code differencve between autoboxing and manually wrapping pirmatives, its juts a bit cleaner syntactically.


I know it's only your opinion, but it worries me that this perspective could be common within Sun: if there is no intention to make boxing anything other than syntactic sugar then I'm going to join the "please please please remove this stupid idea from java" camp (I don't think there is one yet, but if people start to realise this is where it's going I'm sure one will form pretty rapidly...)

If I want performance-gobbling syntax changes that do NOTHING other than save my fingers some typing, I'll retrain as a VB programmer. IIRC it's one of the defining features - it takes very little code to do anything, but you typically sacrifice a lot of the performance you would have had if you'd written a few more lines of code in a proper ;P language. You write VB programs when you'll be sorting lists of 10 items on a 1 Ghz PC, so that the huge performance drops don't matter.

I've only stood by boxing (and I suspect this is true for many people?) because I have faith that what Sun introduces as a transparent code-rewrite now will be turned into a low-level trick in a future version which *doesn't* sacrifice performance. This kind of faith mainly rests upon the power of a JVM - I write the code now, you update the JVM + core libs in 2 years time, and my code benefits without me having to be around to re-link or re-compile.

Ditto generics - part of it's value is that the official inclusion by Sun opens the way for clever high-performance versions in future standard Java distributions...although generics obviously also has the much greater value of bringing compile-time checks to the biggest area where they were historically absent (and causing no end of problems Sad)

IMHO

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

Senior Devvie





« Reply #16 - Posted 2003-11-14 08:22:48 »

Quote

I've only stood by boxing (and I suspect this is true for many people?) because I have faith that what Sun introduces as a transparent code-rewrite now will be turned into a low-level trick in a future version which *doesn't* sacrifice performance. This kind of faith mainly rests upon the power of a JVM - I write the code now, you update the JVM + core libs in 2 years time, and my code benefits without me having to be around to re-link or re-compile.


Well, inside bytecode, boxing is actually turned into real new Integer(5) opcodes, so jvm will have to be very smart to guess what you really want. Additionally, I expect boxing to be mostly used for collections - and I do not see a reasonable way to avoid object allocation (Smalltalk small/bigint probably will not ever get into jvm, as it costs speed for every operation).

Boxing/unboxing IS a syntactic sugar. I don't think that anybody ever even considered it to be optimized in any way - at least in no way more than normal object allocation (escape analysis/on-stack alloc etc).

Artur Biesiadowski
Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #17 - Posted 2003-11-14 08:58:17 »

Quote


Well, inside bytecode, boxing is actually turned into real new Integer(5) opcodes, so jvm will have to be very smart to guess what you really want. Additionally, I expect boxing to be mostly used for collections - and I do not see a reasonable way to avoid object allocation (Smalltalk small/bigint probably will not ever get into jvm, as it costs speed for every operation).

Boxing/unboxing IS a syntactic sugar. I don't think that anybody ever even considered it to be optimized in any way - at least in no way more than normal object allocation (escape analysis/on-stack alloc etc).


Well, yes, exactly. I was talking about people hoping that *in the future* it would be better.

Sorry if I was unclear, but my references to the JVM in particular being able to optimize things in future versions were meant to be generic, not specifically for this. I have no idea where optimizations could be made for boxing (altering the compiler, the byte-codes, the JIT, using some metadata, altering the JLS, etc)

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

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #18 - Posted 2003-11-14 09:37:43 »

Quote

I've only stood by boxing (and I suspect this is true for many people?) because I have faith that what Sun introduces as a transparent code-rewrite now will be turned into a low-level trick in a future version which *doesn't* sacrifice performance. This kind of faith mainly rests upon the power of a JVM - I write the code now, you update the JVM + core libs in 2 years time, and my code benefits without me having to be around to re-link or re-compile.

Hmm, I always assumed that auto-boxing was a compile time thing, and so generated the same byte code as without. But to do some sort of internal JVM trick to optimise this then the VM would need to explicitly know about it, and so the boxing must be actually in the byte code and reworked at runtime.

Which one is it? I had assumed the first, but its taken so long to appear that that points to an actual addition to the bytecode language.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline ChrisRijk

Senior Newbie




Optimise or Die


« Reply #19 - Posted 2003-11-14 12:08:18 »

Generally, what you want is a efficient int HashMap, or some other collection. As others have pointed out, auto-boxing won't mean primatives suddenly can be used efficiently with general purpose collections.

What you want is the generics stuff, and a JRE/VM that will optimise for this. Ie you use a HashMap that is compile time constrained to only use int's for the keys and/or values. At runtime the JRE or VM can then substitute in an int optimised HashMap instead of the default one.

However, I don't think primatives can be specified for generics - ie would have to be Integer object not int. Since an Integer object isn't modifiable, could argue that functionally, storing them as ints wouldn't make any difference. I think that'd be the case unless you were doing something that specifically depended on object references...
Offline rreyelts

Junior Devvie




There is nothing Nu under the sun


« Reply #20 - Posted 2003-11-14 12:25:35 »

Quote
Which one is it? I had assumed the first, but its taken so long to appear that that points to an actual addition to the bytecode language.

Autoboxing is purely a compile-time trick. The only new thing that it uses is some valueOf() methods which were added to Integer and the like.

One kind of "optimization" that could be done with autoboxing is removing it entirely. This could be done if primitives were handled in a manner similar to the way Smalltalk handles numbers.

God bless,
-Toby Reyelts

About me: http://jroller.com/page/rreyelts
Jace - Easier JNI: http://jace.reyelts.com/jace
Retroweaver - Compile on JDK1.5, and deploy on 1.4: http://retroweaver.sf.net.
Offline rreyelts

Junior Devvie




There is nothing Nu under the sun


« Reply #21 - Posted 2003-11-14 12:43:47 »

Quote
What you want is the generics stuff, and a JRE/VM that will optimise for this. Ie you use a HashMap that is compile time constrained to only use int's for the keys and/or values. At runtime the JRE or VM can then substitute in an int optimised HashMap instead of the default one.

Yes, we need type-specific instantiations of parameterized classes - just like you'd get in C++ or PolyJ. No, we don't need to be delaying the generation of those classes until runtime. That's just a pure waste of compute power.

Quote
However, I don't think primatives can be specified for generics - ie would have to be Integer object not int.

No, in the current implementation of JSR14 we can't use primitives for type parameters. Yes, in a good implementation of parametric genericity we can. Look at PolyJ. http://pmg.lcs.mit.edu/polyj/

Sun's complaint with Poly was that it wasn't as backwards compatible as GJ was. My suggestion to Sun is that they use a mixed-style strategy then. Continue to use type-erasure for instantiations with reference type parameters, where compatibility is actually an issue. Use heterogeneous or PolyJ-style translation for instantiations with primitive type parameters, where compatibility isn't an issue.

Then, everybody would get what they need.

God bless,
-Toby Reyelts

About me: http://jroller.com/page/rreyelts
Jace - Easier JNI: http://jace.reyelts.com/jace
Retroweaver - Compile on JDK1.5, and deploy on 1.4: http://retroweaver.sf.net.
Offline thughes

Junior Newbie




Java games rock!


« Reply #22 - Posted 2003-11-14 15:09:28 »

If you wanna squeeze some extra performance from your collections without reinventing the wheel you may want to check out primitive collections for java http://pcj.sourceforge.net/ and the jakarta commons package http://jakarta.apache.org/commons/collections.html

Tom
Offline rreyelts

Junior Devvie




There is nothing Nu under the sun


« Reply #23 - Posted 2003-11-14 15:30:32 »

Quote
If you wanna squeeze some extra performance from your collections without reinventing the wheel

There's also another one, which I haven't seen mentioned in this thread yet, though it has been talked about on JavaLobby and on this board many moons ago.

fastutil - http://fastutil.dsi.unimi.it/

The laughable part is that they used the brain-dead C preprocessor to generate the library for them. The proliferation of these kinds of libraries is a strong reflection of the gaping hole in Java generics.

God bless,
-Toby Reyelts

About me: http://jroller.com/page/rreyelts
Jace - Easier JNI: http://jace.reyelts.com/jace
Retroweaver - Compile on JDK1.5, and deploy on 1.4: http://retroweaver.sf.net.
Offline Jeff

JGO Coder




Got any cats?


« Reply #24 - Posted 2003-11-15 02:46:38 »

Quote
Which one is it? I had assumed the first, but its taken so long to appear that that points to an actual addition to the bytecode language.


AIUI autoboxing in 1.5 will just be a compiler trick so its just syntax.

As you and others have pointed out, there really is no way for the VM to recognize it since theres no "box" opcode.

A VM COULD theoretically be designed to treat int AS an object.  (Some smalltalk VMs do this) but it would take some pretty deep-in-the-design things in the VM, and the repercussions of that on the existing syntax are inbovious and would have to be carefully considered.

On the bright side, I don't think this feature in CLR is anything other then syntactic sugar, also Smiley

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline William

Junior Devvie




No Exit


« Reply #25 - Posted 2003-11-15 15:24:36 »

Jeff, I am well aware that Java's heap allocation is faster than that of C/C++, I was only asking about optimizations that could make per-object heap allocated collections perform as well as collections that allocate several objects at a time (ArrayList) or avoid doing much allocation at all (by using object pools or by implementing ListEntry in the storage object).

I know the GC is the main issue and that this is both application and VM specific, that's why I was asking for research on optimizations to the current VMs that could make the general collections as efficient as specific ones (like how escape analysis can eliminate some heap allocations and their need for garbage collection, or how generational GC helped speed up allocation).

For instance, couldn't the compiler perhaps use the new metadata facility to hint to the VM that a collection is being used as a primitive container with boxing, allowing the VM to eliminate the boxing and its associated garbage collection?
Offline Jeff

JGO Coder




Got any cats?


« Reply #26 - Posted 2003-11-16 00:43:06 »

well I am NOT a VM or  compiler expert... but I don't follow what this code would  look like,

How would you write a collection so that it could use unboxed primatives without completely different code from Object collections??  Remember, general pointers don't exist in the VM, only object pointers ("references").


Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline William

Junior Devvie




No Exit


« Reply #27 - Posted 2003-11-16 17:42:58 »

I guess you're right, the gains of replacing or re-generating a collection to natively support primitives wouldn't be very big, except for perhaps for ArrayList, since you'd still need to have the List/Map-entry object.

I can understand now why they didn't add primitive versions of the collections to the package. They would only be able to get rid of per-object allocations/GC for ArrayList, which is the easiest of the collections to implement yourself, and if you can accept one allocation per object to store you can probably also accept the allocation that the auto-boxing brings.

I used to think that they didn't provide primitive collections because they had some smart optimization up their sleeves that would make auto-boxed primitive use of the Object collections real efficient.
Pages: [1]
  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.

rwatson462 (28 views)
2014-12-15 09:26:44

Mr.CodeIt (19 views)
2014-12-14 19:50:38

BurntPizza (35 views)
2014-12-09 22:41:13

BurntPizza (70 views)
2014-12-08 04:46:31

JscottyBieshaar (32 views)
2014-12-05 12:39:02

SHC (44 views)
2014-12-03 16:27:13

CopyableCougar4 (40 views)
2014-11-29 21:32:03

toopeicgaming1999 (108 views)
2014-11-26 15:22:04

toopeicgaming1999 (94 views)
2014-11-26 15:20:36

toopeicgaming1999 (29 views)
2014-11-26 15:20:08
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

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
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!