Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (775)
Games in Android Showcase (230)
games submitted by our members
Games in WIP (856)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
   Home   Help   Search   Login   Register   
  Show Posts
Pages: [1]
1  Game Development / Performance Tuning / Re: Fantastic Map specializations and GC reduction on: 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.


Pages: [1]
EgonOlsen (1866 views)
2018-06-10 19:43:48

EgonOlsen (1889 views)
2018-06-10 19:43:44

EgonOlsen (1256 views)
2018-06-10 19:43:20

DesertCoockie (1700 views)
2018-05-13 18:23:11

nelsongames (1369 views)
2018-04-24 18:15:36

nelsongames (1987 views)
2018-04-24 18:14:32

ivj94 (2743 views)
2018-03-24 14:47:39

ivj94 (1945 views)
2018-03-24 14:46:31

ivj94 (3036 views)
2018-03-24 14:43:53

Solater (1088 views)
2018-03-17 05:04:08
Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08

Deployment and Packaging
by gouessej
2018-08-22 08:03:45

Deployment and Packaging
by philfrei
2018-08-20 02:33:38

Deployment and Packaging
by philfrei
2018-08-20 02:29:55

Deployment and Packaging
by philfrei
2018-08-19 23:56:20

Deployment and Packaging
by philfrei
2018-08-19 23:54:46 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‑
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!