Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (498)
Games in Android Showcase (115)
games submitted by our members
Games in WIP (563)
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  
  Fantastic Map specializations and GC reduction  (Read 13400 times)
0 Members and 1 Guest are viewing this topic.
Offline Grom

Junior Member




Rats...


« Posted 2002-11-18 02:02:22 »

Hello,

I've just come across the package:

http://gongolo.usr.dsi.unimi.it/~vigna/fastUtil/

It provides specializations for Maps. F.E. instead of using a HashMap
with key=Integer, value=Integer you would use an Int2IntHashMap where key=int, value=int.

In a microbenchmark I have found that the Int2IntHashMap can be up
to 30 times faster than java.util.HashMap.
fwiw, 30 = 7272727/236966 where:
1. 7272727 = 2nd iteration of Int2IntHashMap!
2. 236966 = 15th iteration of HashMap (Hot spot had 12 more iterations to optimize)

On top of this, (and the reason for the number 30 above) is that using HashMaps can cause a lot of GC work.

The code and the results follow:

//
// $Id: TestFastUtil.java,v 1.4 2002/11/18 01:09:19 mswanson Exp $
//

package com.wss.utils.test;

import java.util.*;
import it.unimi.dsi.fastUtil.*;

/**
*
*/
public class TestFastUtil {

   public static void main(String[] args) throws Exception {
       int count = 400000;
       int timerCount = 20;
       long start, end;
       Integer tmp;

       // Normal HashMap
       HashMap hashMap = new HashMap(count);
       for (int timer=0; timer < timerCount; ++timer) {
           start = System.currentTimeMillis();
           for (int i=0; i < count; ++i) {
               hashMap.put(new Integer(i), new Integer(i));
           }
           end = System.currentTimeMillis();
           System.out.println("HashMap put(Integer, Integer) count:" + count +
               ", put/s:" + (count / ((float)(end-start) / (float)1000)));

           start = System.currentTimeMillis();
           for (int i=0; i < count; ++i) {
               Integer in = new Integer(i);
               tmp = (Integer)hashMap.get(in);
               if (!tmp.equals(in))
                   throw new Exception("failed equals()");
           }
           end = System.currentTimeMillis();
           System.out.println("HashMap get(Integer) count:" + count +
               ", get/s:" + (count / ((float)(end-start) / (float)1000)));
       }

       // FastUtil HashMap Int2Int
       timerCount = 100;
       Int2IntHashMap int2IntHM = new Int2IntHashMap(count);
       int j;
       for (int timer=0; timer < timerCount; ++timer) {
           start = System.currentTimeMillis();
           for (int i=0; i < count; ++i) {
               int2IntHM.put(i, i);
           }
           end = System.currentTimeMillis();
           System.out.println("Int2Int put(Integer, Integer) count:" + count +
               ", put/s:" + (count / ((float)(end-start) / (float)1000)));

           start = System.currentTimeMillis();
           for (int i=0; i < count; ++i) {
               j = int2IntHM.get(i);
               if (i != j)
                   throw new Exception("Int2Int failed equals()");
           }
           end = System.currentTimeMillis();
           System.out.println("Int2Int get(Integer) count:" + count +
               ", get/s:" + (count / ((float)(end-start) / (float)1000)));
       }

   }

}

HashMap put(Integer, Integer) count:400000, put/s:137174.22
HashMap get(Integer) count:400000, get/s:603318.25
HashMap put(Integer, Integer) count:400000, put/s:508905.84
HashMap get(Integer) count:400000, get/s:966183.56
HashMap put(Integer, Integer) count:400000, put/s:203252.03
HashMap get(Integer) count:400000, get/s:1052631.6
HashMap put(Integer, Integer) count:400000, put/s:586510.25
HashMap get(Integer) count:400000, get/s:997506.25
HashMap put(Integer, Integer) count:400000, put/s:571428.56
HashMap get(Integer) count:400000, get/s:928074.25
HashMap put(Integer, Integer) count:400000, put/s:243013.36
HashMap get(Integer) count:400000, get/s:952381.0
HashMap put(Integer, Integer) count:400000, put/s:635930.06
HashMap get(Integer) count:400000, get/s:816326.5
HashMap put(Integer, Integer) count:400000, put/s:707964.6
HashMap get(Integer) count:400000, get/s:757575.75
HashMap put(Integer, Integer) count:400000, put/s:234879.62
HashMap get(Integer) count:400000, get/s:1111111.1
HashMap put(Integer, Integer) count:400000, put/s:492610.84
HashMap get(Integer) count:400000, get/s:975609.75
HashMap put(Integer, Integer) count:400000, put/s:583941.6
HashMap get(Integer) count:400000, get/s:915331.8
HashMap put(Integer, Integer) count:400000, put/s:626959.25
HashMap get(Integer) count:400000, get/s:275482.1
HashMap put(Integer, Integer) count:400000, put/s:686106.3
HashMap get(Integer) count:400000, get/s:781249.94
HashMap put(Integer, Integer) count:400000, put/s:571428.56
HashMap get(Integer) count:400000, get/s:1049868.8
HashMap put(Integer, Integer) count:400000, put/s:236966.83
HashMap get(Integer) count:400000, get/s:1044386.44
HashMap put(Integer, Integer) count:400000, put/s:589970.5
HashMap get(Integer) count:400000, get/s:943396.25
HashMap put(Integer, Integer) count:400000, put/s:597907.3
HashMap get(Integer) count:400000, get/s:843881.9
HashMap put(Integer, Integer) count:400000, put/s:689655.2
HashMap get(Integer) count:400000, get/s:273597.8
HashMap put(Integer, Integer) count:400000, put/s:698080.25
HashMap get(Integer) count:400000, get/s:767754.25
HashMap put(Integer, Integer) count:400000, put/s:583941.6
HashMap get(Integer) count:400000, get/s:1017811.7
Int2Int put(Integer, Integer) count:400000, put/s:3448276.0
Int2Int get(Integer) count:400000, get/s:3305785.2
Int2Int put(Integer, Integer) count:400000, put/s:7272727.5
Int2Int get(Integer) count:400000, get/s:7547170.0
Int2Int put(Integer, Integer) count:400000, put/s:7142857.0
Int2Int get(Integer) count:400000, get/s:7547170.0
Int2Int put(Integer, Integer) count:400000, put/s:7272727.5
Int2Int get(Integer) count:400000, get/s:7547170.0
Int2Int put(Integer, Integer) count:400000, put/s:7272727.5
Int2Int get(Integer) count:400000, get/s:7142857.0
Int2Int put(Integer, Integer) count:400000, put/s:7272727.5
Int2Int get(Integer) count:400000, get/s:7547170.0
Int2Int put(Integer, Integer) count:400000, put/s:7272727.5
...


Offline cknoll

Junior Member




Flame On!


« Reply #1 - Posted 2002-11-18 13:21:17 »

Yep, no surprise here, seems a universal law of computer science is that the more generic something is (such as HashMaps ability to store any type) the slower it will perform.  However, I think this problem will be addressed with the introduction of Generics such that you can indicate to the compiler the specific (aka. non-generic) type of Map you want, and should remove the class-casting and other overhead involved in the standard collection classes.

-Chris
Offline Grom

Junior Member




Rats...


« Reply #2 - Posted 2002-11-18 16:26:32 »

wrt Generics I think a good comparison would be valuable. F.E.

1. With Generics, is it possible to _not_ use objects like fastUtil?
2. what are the ways in which Generics are not as efficient as fastUtil?
3. benchmarks would be nice but I do not believe there is an implementation of Generics available yet.

It would be most beneficial if fastUtil could find its way in the hands of all Generics developers. Just knowing something can work this fast could affect the Generics release/design.

I'm sure everyone would be interested in some comments by someone who knows exactly how Generics works.

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

Junior Member




Flame On!


« Reply #3 - Posted 2002-11-18 23:11:43 »

Well, I don't think the fastutil folks are doing anything special, except making collections tailored to the type that it's holding.

As far as your questions:

1)  From what I understand, No.  If I declare an ArrayList for collecting Integers, I can say new ArrayList<Integer> but not new ArrayList<int>.

2)  Initially, the Generics implementation will not be as fast as fastutil because the inital implementation of Generics will merely 'hide' the casting under the covers because of JVM compatabilities, but when they go with a native implementation, it should be as fast as the fastutil lib.

3)  There is an implementation of Generics that you can check out at http://www.javaworld.com/javaworld/jw-06-2001/j1-01-sintes3_p.html.  I could be wrong, but I thought they had an implementation in the JDK 1.4 that you could turn on.

-Chris
Offline Grom

Junior Member




Rats...


« Reply #4 - Posted 2002-11-18 23:42:19 »

Depends on your definition of special. 30x speed improvement is
pretty special to me.

If Generics are using ArrayList<Integer> and not ArrayList<int> then one can say:
1. Generics will always impose a GC overhead - potentially much greater depending on use.
2. Generics will always use more memory. Even with the latest HotSpot an Object is what, 8 or 12 bytes? Plus you have the 4 bytes for the int. This will matter in certain applications.
3. It takes time to create an Object so Generics will always be slower.

Given these 3 conditions, bolstered by my cyberspace anonymity <Dilbert grin>, I will boldly state that:
1. Generics will always be at least 3x slower than fastUtil.
2. Generics will always impose a GC overhead and all that entails
3. Generics are not really what developers want or need - they want and need fastUtils.

<dons flame-suit/>
:-)

Offline Herkules

Senior Member




Friendly fire isn't friendly!


« Reply #5 - Posted 2002-11-19 06:14:37 »

Quote
wrt Generics I think a good comparison would be valuable. F.E.

1. With Generics, is it possible to _not_ use objects like fastUtil?


Not sure, but AFAIK upcoming generics will not support primitives. So they are no replacement for fastUtil.


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

Junior Member




There is nothing Nu under the sun


« Reply #6 - Posted 2002-11-19 13:49:44 »

Quote
Yep, no surprise here, seems a universal law of computer science is that the more generic something is (such as HashMaps ability to store any type) the slower it will perform.  However, I think this problem will be addressed with the introduction of Generics such that you can indicate to the compiler the specific (aka. non-generic) type of Map you want, and should remove the class-casting and other overhead involved in the standard collection classes.

-Chris


A couple of comments.

1) Good genericity doesn't trade off speed. Take a look at how C++ supports extremely well performing generics with template specializations and policies. Modern C++  Design, www.moderncppdesign.com, is an excellent book written by Andrei Alexandrescu who is an expert on generics and performance.

2) Type erasure is a simple change to the compiler that achieves nothing more than creating hidden type-casts. That class casting that you thought was gone is still there. In comparison, with C++ templates you have the choice of implementing the templates in terms of a base type and casting or simply using the template parameter types. If you need the speed, you can get it.

Basically, it boils down to this: Java generics are a weak auto-casting mechanism that can actually hurt performance as they elide the amount of casting going on. C++ templates are a powerful Turing complete language that give you the flexibility to implement very fast algorithms. If only Sun wouldn't bend bass-ackwards in their efforts to keep the VM spec from changing, we might have something more like C++ templates. <sigh>

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 Herkules

Senior Member




Friendly fire isn't friendly!


« Reply #7 - Posted 2002-11-19 14:37:48 »

Wow - he really KNOWS!

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

Junior Member




There is nothing Nu under the sun


« Reply #8 - Posted 2002-11-19 15:40:44 »

Quote

<dons flame-suit/>
Grom has got most of that correct. In and of itself, Java's type-erasure form of Generics will never have any positive performance impact upon programs.

Different solutions include adding support to the virtual machine for generics, enhancing generics to work with primitives (without auto-boxing), smart object->primitive replacement, and Smalltalk style primitives. Who knows what Sun will see fit to do.

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 cknoll

Junior Member




Flame On!


« Reply #9 - Posted 2002-11-19 19:59:35 »

Well, obviously your experience is differnt than mine, but the fact that fastutils is so much faster (although only supports specific types of collections) supports my claims.

I think that what generics gives you that fastutils doesn't is that if i need a new type of collection, I'd have to wait for fastutil developers to give it to me (Such as a CustomerHashMap or something) or I need to roll my own.   Generics allows me to define HashMap<Customer> or HashMap<Player> or HashMap<Mob> without having to re-write a container over and over.

C++ templates is nothing more than a code generator:  It actually produces new source code based on the type you specify as the parameter.  This is a sort of 'copy-and-paste' code reuse that I hardly find attractive, but it does have a benefit to the code bloat: it's very fast.

I think that high performance code (that games require) will not find much use for 'generic' classes, the developers will need to take existing code and shape it to do a particular task extremely quickly.  This makes it non-generic.

Anyways, there's nothing that says that a VM can 'collapse' generic code into specific code so that it runs faster, but this would be at a cost of memory (each collapsed version of a super-class-subclass would have it's own distinct instance).  Most likely, this is something that HotSpot does.

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

Junior Member




There is nothing Nu under the sun


« Reply #10 - Posted 2002-11-19 20:43:21 »

Well, obviously your experience is differnt than mine, but the fact that fastutils is so much faster (although only supports specific types of collections) supports my claims.

Huh? Exactly what claims of yours does it support?

I think that what generics gives you that fastutils doesn't

Obviously, fastutils is a response to the crappy performance of Java containers and primitives, generic and otherwise.

C++ templates is nothing more than a code generator:

Lol. Try telling that to the C++ compiler implementers. You can bet they only wish it were that simple.

This is a sort of 'copy-and-paste' code reuse that I hardly find attractive, but it does have a benefit to the code bloat: it's very fast.

I challenge you to define a negative attribute of "copy and paste" that is shared with C++ templates. Any "code bloat" associated with C++ templates is purely the fault of a naive programmer using them. Statements like yours belie any experience you might claim to have with them.

I think that high performance code (that games require) will not find much use for 'generic' classes

To put it about as politely as I can: Only because Java generics suck. If you think people want to have to create an entire new container for each possible combination of types under the sun, you've not been programming for very long.

Anyways, there's nothing that says that a VM can 'collapse' generic code into specific code so that it runs faster, but this would be at a cost of memory (each collapsed version of a super-class-subclass would have it's own distinct instance).  Most likely, this is something that HotSpot does.

Can I have some of what you've been smoking? HotSpot doesn't know anything about generics.  There is no java bytecode anywhere that could possibly indicate any information about generics to Hotspot - All because Sun doesn't want to introduce changes to the VM spec.

I don't want this to turn into any sort of flamefest, I'm just critical - and Java generics push my buttons. I'd been waiting for something good for so long and then they released that crap. I'm not saying I want Java generics to be C++ templates, but for the love of coffee, couldn't we have at least done something 1/10th as powerful? <sigh>

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 Grom

Junior Member




Rats...


« Reply #11 - Posted 2002-11-19 23:24:39 »

Another interesting thing about fastUtil:

It uses a shell script and a C PreProcessor to generate the Java sources. (fyi: the author has mentioned that he should be done a rewrite of the tree maps soon). Off the top of my head I find the following possibilities interesting:

After using C++ templates and the STL heavily for many years, I have noticed that I personally used a core set of features about 80% of the time. A good number of these features are already implemented in fastUtils. fastUtils is "fast" becoming that 1/10th as powerful solution because:

1. fastUtils supports Int2ObjectHashMap <int, Object> and other combinations of native/Object data types that I believe would be optimal enough.

2. fastUtils comes with a large number of specializations pre-built. No longer do I have to suffer long compile times waiting for templates and their partial specializations to compile. Bonus. And, when are enough specializations enough? If you look through the API and see what is covered perhaps you will think all the specializations are covered and all that needs maturing is the selection of algorithms.

3. (Well done, kudos) the fastUtils developer had the forsight to structure the package in such a way where code generation is automated to support more than one specialization. It looks easy enough. If it proves not to be easy, at _least_ it is possible.

To me, fastUtils is potentially the perfect equivalent to C++ templates and the STL, and what Generics should have been. The reason I say this is because fastUtils provides (or will soon provide) me with enough capability to satisfy most if not all of my needs. I can easily fill in the missing pieces or adjust my coding strategies to compensate.

ymmv, of course.

Offline cknoll

Junior Member




Flame On!


« Reply #12 - Posted 2002-11-20 00:45:50 »

rreyelts,
 Try as you might, you are defintely tossing a lot of flaim-bait out there, but I'll try to politely address your points:

1) The claim was that "good" genericity does not trade off speed.  I said that in my experience, the more generalized soemthing becomes, the less performant it becomes (2 examples:  Java Collections API, and the JVM.  In the former case, you need to resort to casts and object overhead in the standard collections, and in the latter case, the JVM is designed to run on multiple platforms and there fore isn't designed to be optimized to one particular platform).  I hope this clears things up.

2) <quote> Obviously...</quote> I don't know what your statement here has to do with my saying one benefit of generics.

3) What: a "preprocessor that creates source" doesn't sound like a code generator?

4) Negative impact of copy-paste:  If you find a problem with your 'boilerplate' template, you need to go back and recompile (or re-generate) all the code that was built off that template.  With generics it will work almost like inheritance in the sense that you only need to recompile your generic class for all instances of your generics to get updated.

5)  I was only making another point about the tradeoffs to get performance:  Hotspot needs to keep a lot more around in memory to make it's optimizations.  This is overhead.  C++ templates generate lots of source code that will need to be kept track of if the base tempate changes.  This is overhead.   I think most of my points in this thread have gone over-your-head.  (sorry, that was rude of me)

-Chris
Offline rreyelts

Junior Member




There is nothing Nu under the sun


« Reply #13 - Posted 2002-11-20 01:42:24 »

1) The claim was that "good" genericity does not trade off speed... I hope this clears things up.
Nope, you're pretty much making no sense whatsoever. Java's generic collections are poorly designed and thus suffer a performance penalty, and Java doesn't give up platform optimizations - they're just deferred to the JVM until runtime.

2) <quote> Obviously...</quote> I don't know what your statement here has to do with my saying one benefit of generics.
My point was that fastutil isn't really a response to generics and so you're comparing apples and oranges. Fastutil is a response to crappy container performance and crappy Java generics won't change that.

3) What: a "preprocessor that creates source" doesn't sound like a code generator?

Lol. There isn't a single C++ compiler in existance that implements templates using a preprocessor. I'm beginning to doubt that you've ever worked with C++.

4) Negative impact of copy-paste:  If you find a problem with your 'boilerplate' template, you need to go back and recompile (or re-generate) all the code that was built off that template.  With generics it will work almost like inheritance in the sense that you only need to recompile your generic class for all instances of your generics to get updated.

Lol. That's the best you can come up with? That same "problem" is what allows you to perform optimizations like compile-time loop unrolling.

5)  I was only making another point about the tradeoffs to get performance:  Hotspot needs to keep a lot more around in memory to make it's optimizations.  This is overhead.  C++ templates generate lots of source code that will need to be kept track of if the base tempate changes.  This is overhead.

No Chris, you're just talking nonsense. Let me repeat some of it: Anyways, there's nothing that says that a VM can 'collapse' generic code into specific code so that it runs faster, but this would be at a cost of memory (each collapsed version of a super-class-subclass would have it's own distinct instance).  Most likely, this is something that HotSpot does.

I think most of my points in this thread have gone over-your-head.  (sorry, that was rude of me)

Oh I see, the logic hurts, so you resort to fallacious ad hominem attacks. Fine, if you think you're talking over my head, then why don't you Google around some and take a look at the work I've done? I eat java bytecode for breakfast. You on the other hand, chris.knoll@immedient.com, seem to spend all of your time chewing on .NET, http://www.immedient.com/aboutus.asp?Nav=2&Tab=2

I'm not surprised it's warped your brain.  Wink

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 swpalmer

JGO Coder


Exp: 12 years


Where's the Kaboom?


« Reply #14 - Posted 2002-11-20 03:12:51 »

Hey guys.. people are just trying to understand stuff here..  If someone doesn't know how things work but they think they do, it can be a simple honest misunderstanding.  It isn't because they are trying to be a smart*ss or something.  Let's try to correct these misunderstandings in a friendlier manner.

Just how are C++ templates realized then?  I had always thought of the trivial implementation that amounts to automatic copy-paste as well.. (it seems like the easiest thing to do... so I would guess that at least early implementations worked that way.)

What am I missing?

Offline vigna

Innocent Bystander




Java games rock!


« Reply #15 - Posted 2002-11-20 08:30:29 »

Hi guys, I'm the author of fastUtil.

There are a lot of issues in this thread, so I'll just try to give my perspective.

1) I wrote this stuff because I needed hash-based sets and maps with high performance and small memory footprint for a web crawler I'm developing with other people. We already use several type-specific classes in the COLT distribution, but it did not contain everything we needed.

2) Genericity in Java *as currently specified* is useful syntactic sugar, but no more; certainly it does not apply to primitive types, certainly does not solve the wrap/unwrap problem, and possibly (but I wouldn't bet on it) could even reduce performance.

3) fastUtil is clearly "inspired" by C++ templates. There is however a major difference: because of the way Java handles classes, you can precompile everything (you will end up loading only the class you use anyway). This has a number of advantages.

4) The speed gain with fastUtil is certainly also due to less garbage collection but for the most to better algorithms. Sincerely, I haven't seen in the last years anyone implementing closed addressing (as Sun did). Its only advantage is that it handles slightly better deletions. Probably they also thought that since they had to wrap primitive types, there would have been no real disadvantage in wrapping *again* the wrapper in an Entry object. I don't know--I just know that those classes are completely useless for my needs. The algorithms used in fastUtil are simple but effective. They use all the known theory about hash tables to squeeze every bit of performance (e.g., using twin primes). Moreover, the important functions are willingly coded as tight loops contained in a single method, so that they end up being optimised very soon.

5) fastUtil uses theory, but tries to be pragmatic. Yes, you can use an additional pointer per entry to keep a list of entries, so that iteration is linear in the number of entries. However, in the real world a 75% filled table scanned with a tight loop will always give faster iteration, even if you have a slight overhead due to empty/deleted buckets. This can hinder performance if the table contains mostly deleted entries, but again, fastUtil is optimised for the *general* case.

I have almost finished developing a replacement for sorted sets and maps. It consumes only one integer and two references per stored element (against three references and one boolean for java.util). Of course, it doesn't need wrappers.

If anyone is interested in beta testing, please let me know.

Ciao,

                                                                 seba
Offline Grom

Junior Member




Rats...


« Reply #16 - Posted 2002-11-20 10:16:38 »

Thanks for posting Vigna!
Your fastUtil package is having a profound effect on a particular module I'm using. fastUtil will probably wind up in most projects I work on from now on.

Cheers.
Offline rreyelts

Junior Member




There is nothing Nu under the sun


« Reply #17 - Posted 2002-11-20 12:27:36 »

Let's try to correct these misunderstandings in a friendlier manner.

Well, I tried to warn people that Java generics push my buttons. If you try to defend them to me, you're liable to get mown down. Tongue

Just how are C++ templates realized then?  I had always thought of the trivial implementation that amounts to automatic copy-paste as well

First, let's get this notion of using a preprocessor to implement templates out of the way. A preprocessor implements a language of its own. For example, both cpp and m4 implement their own languages. They operate outside of the bounds of the meaning of the text they transform. Therefore, preprocessors have no respect for your programming language's features - such as type, scope, namespaces, overloading, etc... (anything which has semantic meaning above grammar / syntax). Obviously C++ templates can't be implemented by a preprocessor because they respect and interact with all of these language features (sometimes in quite complicated ways) - whereas, macros, for example, don't respect a single one.

Now, to address "copy and paste". C++ templates are _generative_ (which is part of what makes them generic - read a good book on generic programming), but they aren't copy and paste.

First, you aren't manually generating any code which you have to maintain. For example, java.lang.reflect.Proxy is also generative - it generates new classes at runtime. However, we don't think of Proxy as a copy and paste mechanism, because it doesn't suffer any of the classic pitfalls of copy and paste. It's simply a generative, generic class.

Second, templates follow special rules that have nothing to do with copy and paste, for example, template specialization, both partial and full. Another example of special template rules are those that govern the interaction of templates and the C++ type system. They don't match a copy and paste mechanism.

Third, the C++ template mechanism implements a Turing complete language, with features like compile time control-flow and iteration / recursion. For example, it's possible to write a function that computes the factorial of a parameter N at compile time. This use of templates is known as template meta-programming and is commonly used to perform optimizations like compile-time loop unrolling. Try doing that with Ctrl+C and Ctrl+V.

I can only guess that some programmers may be tricked into believing that templates are "copy and paste", because they operate on structural conformance. (Another point of flexibility I wish Java generics had - or at least replaced with something better).

Again, to reiterate my point, Java generics don't have to equal C++ templates, but they should have learned something from them. Instead, they're a dumb auto-casting mechanism, with no power and no flexibility. They are not generics - They're a hack to make Java containers slightly easier to work with. Don't get me wrong, I love Java: the lack of broken type semantics, cross-platform, built-in multithreading, monitor info, stack trace info, security, reflection, dynamic class loading, easy to understand bytecode (and hence easy generative programming) - but Java generics just plain suck.

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 Member




There is nothing Nu under the sun


« Reply #18 - Posted 2002-11-20 12:37:46 »

2) Genericity in Java *as currently specified* is useful syntactic sugar, but no more; certainly it does not apply to primitive types, certainly does not solve the wrap/unwrap problem, and possibly (but I wouldn't bet on it) could even reduce performance.

If you double-check you can see that my comment on reducing performance was in respect to the hiding of casts. Apparently some programmers believe that Java generics will be removing the casts. Given that, they might opt for using Object-based containers when they otherwise would have not.

3) fastUtil is clearly "inspired" by C++ templates. There is however a major difference: because of the way Java handles classes, you can precompile everything (you will end up loading only the class you use anyway). This has a number of advantages.

Can you explain what you mean by this? You can also "pre-compile" C++ templates. For example, I could explicitly instantiate ("pre-compile") vector<int>, vector<string>, vector<float>, etc... In the same respect, even the most naive C++ linkers would be smart enough to remove the dead code, if say, the vector<float> instantiation went unused in the final program.

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 cknoll

Junior Member




Flame On!


« Reply #19 - Posted 2002-11-20 15:55:53 »

Ah well, I can only respond to the same idiocy two times before I give up, so, I suggest if you really want to understand what I'm saying, re-read my posts again.  You obviously can't accept information from anyplace except your own misconceptions, and you are completely blinded by where you _think_ the information is comming from (Yep, I work for a MS Solution provider, but I strictly do Java work, and I like to think of myself as someone keeping the balance of technologies in my corporation.  You should not be to quick to judge.).  I'm sure that you can go on and on reading one passage from me and understanding something completely different, but while you might find it fun playing the fool, I find it pretty boring to talk to one.

I'm getting flashbacks about talking to someone about the applet security model and webstart, and he was as thick as you seem to be.   Enough is enough.

-Chris
Offline rreyelts

Junior Member




There is nothing Nu under the sun


« Reply #20 - Posted 2002-11-20 16:40:53 »

Ah well, I can only respond to the same idiocy two times before I give up

Lol, Beautiful, just beautiful. It's plain to see you're not interested in discussing this rationally at all. When backed into a corner by facts you can only respond with cries of "idiocy" and other such third-grade antics.

You obviously can't accept information from anyplace except your own misconceptions,

Chris, this sentence might make sense if you could point out even a single misconception.

you are completely blinded by where you _think_ the information is comming from...  You should not be to quick to judge.

That's hilarious. You started the ad hominem attacks (as you continue to do), at which point I tried to Google you down and suggested that people check out both of our histories. I couldn't find any identifying information about you on the Internet at all, except the company you work for. I won't even go into how that compares to my background, but anyone here can do the leg work in about 60 seconds.

And I find it quite funny that you would think that your personal background is somehow "blinding me". No Chris, my observations come from many years of working with Java and C++. Personally, Chris, I don't care who you work for, I just want to participate in cogent discussion. (Though I have to admit to finding your occupation funny in relation to all of this).

but while you might find it fun playing the fool, I find it pretty boring to talk to one

More personal attacks Chris? If you'd take the time to respond to any of the facts, this could be an interesting and fruitful discussion, but apparently you're either incapable of or unwilling to do so.

Oh well. I encourage others to contribute to this well-scorched thread.

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 Grom

Junior Member




Rats...


« Reply #21 - Posted 2002-11-20 16:41:57 »

cknoll,

It is fair and helpful to disagree with someone. However, if you disagree with someone the mature thing to do is to give some good reasons why. This can lead to discussion and people can learn. In the future, I hope you will participate by giving reasons for your opinions instead of by calling someone an idiot or thick headed. If you think about it, rreyelts posted some very good comments and backed them up with very sound concepts.

Cheers.
Offline swpalmer

JGO Coder


Exp: 12 years


Where's the Kaboom?


« Reply #22 - Posted 2002-11-20 17:19:34 »

Quote

First, let's get this notion of using a preprocessor to implement templates out of the way.


Just remember that ages ago the orginal C++ language was implemented as something like a preprocessor that produced straight C code...  Although I guess in that sense you could call the preprocessor something that compiles to C source.


Quote
First, you aren't manually generating any code which you have to maintain.


- much like a macro


Quote
Third, the C++ template mechanism implements a Turing complete language, with features like compile time control-flow and iteration / recursion. For example, it's possible to write a function that computes the factorial of a parameter N at compile time. This use of templates is known as template meta-programming and is commonly used to perform optimizations like compile-time loop unrolling. Try doing that with Ctrl+C and Ctrl+V.


Well just for the sake of argument.. that 'meta-programming' sounds a lot like an abusive hack.. I would hate to see such code.  And, I unroll loops with Ctrl-C, Ctrl-V all the time, so I seem to have missed the point there.  These things certianly don't sound like the stuff that I see C++ templates used for 99.9% of the time.  So the fact that the Java Generics mechanism can't handle that specific bit doesn't seem like a big deal.
In terms of how I see C++ templates used, they are essentially a glorified macro - a really powerful and useful one, sure.

Quote
Again, to reiterate my point, Java generics don't have to equal C++ templates, but they should have learned something from them. Instead, they're a dumb auto-casting mechanism, with no power and no flexibility.


Well I certainly agree that if Java Generics are nothing more than hiding some casting, then they perhaps aren't as powerful as they should be.  Although if you were going to use things like the generic containers and casting anyway they do make things easier.  So while java Generics aren't what you want them to be, they are still good for something.
Could you implement something that appeared to be the equivalent of STL with java generics for instance?  'cause that to me seems to cover the bulk of what C++ templates are used for.
How much am I really missing? (I know you'll want to tell me Wink, and I seriously want to know. )

Offline cknoll

Junior Member




Flame On!


« Reply #23 - Posted 2002-11-20 18:44:16 »

Grom,
 I did reply with concrete examples, and these were met with the likes of 'LOL. Is that the best you can do?'  You should re-read the _whole_ thread again.  I never disputed fastutil's performance,  and any discussion on my part at all dealt with performance of 'generic' code. (Not generics specifically).  I did say that copy-and-paste reuse was problematic (and I said why, but if you can't magine going back to 20 classes to recompile against a new template, then maybe you haven't been exposed to large projects that would require the use of collections of 20 different types).

In any case, it seems you and rreyelts are big big fastutil fans and Generic haters (Personally, I don't care about either, I was just giving point of view) and anyone who thinks differently sucks and is a target for abuse, so I'll leave you two to your ramblings.

-Chris
Offline rreyelts

Junior Member




There is nothing Nu under the sun


« Reply #24 - Posted 2002-11-20 19:19:08 »

Just remember that ages ago the orginal C++ language was implemented as something like a preprocessor that produced straight C code...

Apples and oranges Scott. There are many languages which use C as their IL (intermediate language). Heck, there are static Java compilers which use C as their IL. Are you suggesting that Java is just a macro? The key here is that the process is actually  compilation - which all of us CS geeks know is just a synonym for _translation_.

much like a macro

Fine. You've taken what my point was (Templates, like java.lang.reflect.Proxy, are a form of generative-generic programming), and turned it on its head. Let me ask you this, then: Do you believe java.lang.reflect.Proxy is basically a macro? If not, then how is it different? Then how does Proxy differ from templates? Hopefully, these questions will be rhetorical for you.

that 'meta-programming' sounds a lot like an abusive hack..

It's definitely not a hack (templates were designed to have those capabilities), but it's not exactly pretty either. It's the preferred way, now, because it is currently the most elegant solution. I would love to see Java implement the same functionality, but in a much more elegant fashion.

And, I unroll loops with Ctrl-C, Ctrl-V all the time, so I seem to have missed the point there.

Yes, you strayed far from the point. You can use templates to create a parameterized algorithm which the compiler manually unrolls for you. For example, you can create a matrix algorithm that will automatically unroll itself perfectly for any size matrix. With manual unrolling, you would have to create a new version of the algorithm for each differently sized matrix. If you needed to change your algorithm, you'd have to do it for each and every unrolled loop for each and every differently sized matrix. Hope your wife won't miss you while your gone.

These things certianly don't sound like the stuff that I see C++ templates used for 99.9% of the time.

It is common. Check out OONumerics and the Loki library for example.

So the fact that the Java Generics mechanism can't handle that specific bit doesn't seem like a big deal.

Humm... what you've done here is falsely trivialized what templates can do, and then said that you don't see why they are good.

As another example of what templates can do, consider specialization. I can take any algorithm and specialize it for any data type, and it's totally transparent to the users of that algorithm. Jace (my open-source C++ JNI library) uses template specialization extensively throughout its library to create seamless access to Java arrays, fields, and methods of any type.

In terms of how I see C++ templates used, they are essentially a glorified macro - a really powerful and useful one, sure.

Actually, if anything is like a macro, it's Java generics. Think about it some. One is a Turing complete language - the other drops in type casts.

Well I certainly agree that if Java Generics are nothing more than hiding some casting, then they perhaps aren't as powerful as they should be.  Although if you were going to use things like the generic containers and casting anyway they do make things easier.  So while java Generics aren't what you want them to be, they are still good for something.

Right - they're mostly useless. Somewhat more powerful than comments.

Could you implement something that appeared to be the equivalent of STL with java generics for instance?

Somebody has already written a poor Java imitation of the standard C++ container library - It's called JGL. It, for example, doesn't support specialization. It also doesn't implement anything akin to traits classes. It also has no concept of policy classes. All of these things come from templates.

'cause that to me seems to cover the bulk of what C++ templates are used for.

So, I've already covered what you missed in the standard C++ library alone. Again, I suggest you take a look at some powerful template libraries. Check out Loki, Blitz++, the C++ Lambda library, even Jace, for real world examples of the many powerful things you can do with templates.

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 Member




There is nothing Nu under the sun


« Reply #25 - Posted 2002-11-20 19:47:08 »

I did reply with concrete examples, and these were met with the likes of 'LOL. Is that the best you can do?'

The responses were equal to the merits of the questions. At least I was considerate enough to refrain from calling you an "idiotic fool who's too stupid to understand the ongoing discussion".

I did say that copy-and-paste reuse was problematic (and I said why, but if you can't magine going back to 20 classes to recompile against a new template, then maybe you haven't been exposed to large projects that would require the use of collections of 20 different types).

You don't have to "go back" to any classes. You change your template class as needed and type "make" at the command prompt. This and your other comments: C++ templates is nothing more than a code generator:  It actually produces new source code based on the type you specify as the parameter. and Negative impact of copy-paste:  If you find a problem with your 'boilerplate' template, you need to go back and recompile (or re-generate) all the code that was built off that template. seem to indicate that you believe that templates end up generating some sort of source code, which is patently false. Templates have the same advantages as Java Generics, in that you only maintain a single source file. Templates vary from Java generics, in that additional object code is produced - either by the compiler or the linker.

Btw, I use templates extensively in Jace. In Jace, at least one template gets instantiated for each Java type you build against. In the case of the Java class library, that's, at a bare minimum, over 5000 different template instantiations. Off the cuff, I would guess it's somewhere around 5 times that much in reality. I've built against the entire Java class library. I think I have a pretty good idea of what's involved in extensive instantiation of templates.

In any case, it seems you and rreyelts are big big fastutil fans and Generic haters

I've never used fastutil and reserve the right to pass any judgement on it until I do. It may be the greatest thing since sliced bread, or it may be crap.

and anyone who thinks differently sucks and is a target for abuse

I don't think you suck and have never said such a thing. At this point, I do think you're confused about Java generics and C++ templates in general.

so I'll leave you two to your ramblings.

As you wish.

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 swpalmer

JGO Coder


Exp: 12 years


Where's the Kaboom?


« Reply #26 - Posted 2002-11-20 20:05:04 »

Quote
Are you suggesting that Java is just a macro? The key here is that the process is actually  compilation...


I just meant that a preprocesor could be something of a compiler.. to rationalize why people would think of templates in that way.  I acknowledge that they are more integrated into the language than a simple macro facility.

Quote
Do you believe java.lang.reflect.Proxy is basically a macro? If not, then how is it different? Then how does Proxy differ from templates?


I've never looked at java.lang.reflect.Proxy .. so I'll have to go away and read a bit before I can appreciate your point...

Quote
Yes, you strayed far from the point. You can use templates to create a parameterized algorithm which the compiler manually unrolls for you.


I wasn't trying to stray, but I see your point now..  templates can be designed to adapt much better than some sort of macro would.. (is that the point?).. I have to admit though taht my knowledge of C++ templates (which may be severely lacking) makes it seem that what you are talking about is akin to a fancy recursive macro.  Something that really does need (as you say) a more elegant implementation.  Not that it would be easy to do..  maybe generics in Java are not all that because the Java language tries to keep simple and elegant .. and a simple elegant way to do this meta-programming was too far off?  I don't know, I'm just hypothesizing.


Quote
So the fact that the Java Generics mechanism can't handle that specific bit doesn't seem like a big deal.

Humm... what you've done here is falsely trivialized what templates can do, and then said that you don't see why they are good.


That wasn't my intention at all.  I can only speak from my personal experience, in which I have never seen serious use of templates to unroll loops and the like.  I had heard it coudl be done.. but it seemed more like the kind of stuff that you would do in an obfuscated C++ contest, than stuff that people did for real.   I don't mean to suggest that it is an unreasonable use of templates.. but it adds a significantly different dimension to the language..  I'm not sure if I'm ready to go there...  it feels like it would be similar to coding half of your routines in prolog and the other half in C Smiley

Quote
As another example of what templates can do, consider specialization. I can take any algorithm and specialize it for any data type, and it's totally transparent to the users of that algorithm.


Can't you get a lot of that with Java Generics?  I mean, there are existing ways to deal with that..  e..g. you can sort any objects that implement comparable.  The generic algorithms and containers of STL are where I see the most use of C+= templates.. and I thought that java generics would allow you to work like that, even if the implementation really just amounted to doing the casting for you.
Which is why this:
Quote
Right - they're mostly useless. Somewhat more powerful than comments.
seems to be a strrange conclusion.. I would have concluded "Right - so there isn't much to them, but they give you a lot."

Quote
So, I've already covered what you missed in the standard C++ library alone. Again, I suggest you take a look at some powerful template libraries. Check out Loki, Blitz++, the C++ Lambda library, even Jace, for real world examples of the many powerful things you can do with templates.[\quote]

I would like to, if I can find some time I probably will..  but to be honest, the fact that I worked with C++ for so many years and only recently hearing of these things is why I suggested that templates generally aren't used that way in most programs, and that what most programs actually use templates for in typical applications may be coverd by java generics.

The whole Lambda-calculus thing for instance.. it seems mostly academic now.. how much programming is really done that way... in the grand scheme of things none (at he moment), regardless of it's power.   So while I accept your point that generics could be vastly more powerful, and that C++ templates ARE more powerful, it still seems that the power is ultimately lost on the chumps like me that haven't caught on to it yet.. but since we chumps make up the bulk of the users (I'm making assumptions, I know) it isn't really worth it...
Just an opinion, it could easily change by the time I read your reply Smiley

Offline Grom

Junior Member




Rats...


« Reply #27 - Posted 2002-11-21 00:08:05 »

Quote

Grom,
 I did reply with concrete examples, and these were met with the likes of 'LOL. Is that the best you can do?'  You should re-read the _whole_ thread again.


Generally rreyelts gave those types of responses when you used immature and offensive language.

Quote

I never disputed fastutil's performance,  and any discussion on my part at all dealt with performance of 'generic' code. (Not generics specifically).  I did say that copy-and-paste reuse was problematic (and I said why, but if you can't magine going back to 20 classes to recompile against a new template, then maybe you haven't been exposed to large projects that would require the use of collections of 20 different types).

It is wrong of you to second-guess what I "magine".

Quote

In any case, it seems you and rreyelts are big big fastutil fans and Generic haters (Personally, I don't care about either, I was just giving point of view) and anyone who thinks differently sucks and is a target for abuse, so I'll leave you two to your ramblings.

-Chris

It _is_ funny that you instantly degrade to offensive 13-year-old "anyone who thinks differently sucks" communications. If you read back, you will see I did not make you a target at all. I only complained about your language.

I am positive about fastUtils because I wrote a microbenchmark and liked the results. I can see it being useful. I call it "fantastic" because of its "potential" and to get people interested and join in discussion so I can learn more about it and related technologies like Generics. In doing so, I received a pretty good idea about Generics. I need to do a lot of reading on Generics, and I need to use fastUtil a lot before I really understand it and trust it enough to recommend.
Offline cknoll

Junior Member




Flame On!


« Reply #28 - Posted 2002-11-21 00:57:12 »

Well, grom, you certainly spent a lot of time sifting through my responses, how about you sift through rreyelts and critique those?

It's funny that you claim i use immature and offensive language, but you don't quote any of my passages on that.  Hmm....

-Chris
Offline cknoll

Junior Member




Flame On!


« Reply #29 - Posted 2002-11-21 01:25:24 »

Well, there's been claims that there's no code-generation wrt STL, here's an interesting quote from an article i found at http://www.yrl.co.uk/~phil/stl/stl.htmlx

Quote

Templates avoid these problems. Because they are built into the language, they are able to provide full type safety checking and deduce the types of their arguments automatically, generating the code for whatever arguments are used.


The next question is: is there a way to view the c++ source that a STL generates?  I didn't find much, but I did find this quote:

Quote

In some cases it is possible to override the template-generated code by providing special definitions for specific types. This is called template specialization. For example:

#include <iostream.h>

//max returns the maximum of the two elements of type T, where T is a

//class or data type for which operator> is defined.

template <class T>

T max(T a, T b)

{

   return a > b ? a : b ;

}

void main()

{    

   cout << "max(10, 15) = " << max(10, 15) << endl ;

   cout << "max('k', 's') = " << max('k', 's') << endl ;

   cout << "max(10.1, 15.2) = " << max(10.1, 15.2) << endl ;

   cout << "max(\"Aladdin\", \"Jasmine\") = " << max("Aladdin", "Jasmine") << endl ;

}

Here is the output:

max(10, 15) = 15

max('k', 's') = s

max(10.1, 15.2) = 15.2

max("Aladdin", "Jasmine") = Aladdin

Not quite the expected results! Why did that happen? The function call max(&#8220;Aladdin&#8221;, &#8220;Jasmine&#8221;) causes the compiler to generate code for max(char*, char*), which compares the addresses of the strings!


So, exactly how is STL not the code generator that I've been describing all this time?  I understand that it's 'smart' and it handles recursion, etc etc, but I think it still amounts to copy-paste coding which can be a nightmare to maintain.  R. claims that you just need to re-run your make and all the code will be re-generated, but that's one thing I like about java: you don't need to do an entire rebuild if you just change a single class.  Generics allow you to define a full-fledged java object that is parameterized (aka "Parameterized Types") that if it changes, you only need to rebuild the PT and re-deploy.  With the copy-paste methodology, you need to redeploy every class that was generated from the template.  I think this is a negative.

-Chris



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.

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

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

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

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

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

BurntPizza (31 views)
2014-09-19 03:14:18

Dwinin (48 views)
2014-09-12 09:08:26

Norakomi (74 views)
2014-09-10 13:57:51

TehJavaDev (102 views)
2014-09-10 06:39:09

Tekkerue (50 views)
2014-09-09 02:24:56
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!