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 (601)
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  
  Bag and ArrayList Testing... Memory Error?  (Read 2142 times)
0 Members and 1 Guest are viewing this topic.
Offline coltonoscopy

Junior Devvie


Medals: 2



« Posted 2012-08-10 05:53:45 »

Hey, everybody!

I discovered Kappa's Bag code and decided to put it some use against an ArrayList. So far, I'm very happy with the results! The code for his data structure, if you haven't seen it yet, is here:

http://www.java-gaming.org/topics/the-bag-fast-object-collection/24203/view.html

I wrote a little test program to test just simple functionality out of it here (not a realistic example, by any means, but just something for some quick benchmarks, I suppose):

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
package test;

import java.util.ArrayList;
import java.util.Random;
import util.Bag;

public class BagTest
{
    public static void main(String args[])
    {
        Bag stringBag = new Bag();
        ArrayList stringList = new ArrayList();
        Random r = new Random();
       
        long time = System.currentTimeMillis();
       
        for (int i = 0; i < 1000000; i++)
        {
            stringBag.add(r.nextInt(2) == 1 ? "hello" : "goodbye");
        }
       
        System.out.println("Adding to the Bag: " + ((System.currentTimeMillis() - time) / 1000.0) + "s");
       
        time = System.currentTimeMillis();
       
        for (int i = 0; i < 1000000; i++)
        {
            stringList.add(r.nextInt(2) == 1 ? "hello" : "goodbye");
        }
       
        System.out.println("Adding to the ArrayList: " + ((System.currentTimeMillis() - time) / 1000.0) + "s");
       
        time = System.currentTimeMillis();
       
        while (!stringBag.isEmpty())
        {
            int remover = r.nextInt(stringBag.size());
            String s = (String)stringBag.get(remover);
           
            if (s.equals("goodbye"))
            {
                stringBag.remove(remover);
            }
            else
            {
                stringBag.remove(remover);
                stringBag.add("goodbye");
            }
        }
       
        System.out.println("Removing from the Bag: " + ((System.currentTimeMillis() - time) / 1000.0) + "s");
       
        time = System.currentTimeMillis();
       
        while (!stringList.isEmpty())
        {
            int remover = r.nextInt(stringList.size());
            String s = (String)stringList.get(remover);
           
            if (s.equals("goodbye"))
            {
                stringList.remove(remover);
            }
            else
            {
                stringList.remove(remover);
                stringList.add("goodbye");
            }
        }
       
        System.out.println("Removing from the ArrayList: " + ((System.currentTimeMillis() - time) / 1000.0) + "s");
    }
}


It runs fine with test cases up to 100000 entries (during which, by the way, Bag seems to always take the cake with this test), but when I try to add on another factor of 10 by raising the count to 1000000 (I haven't tested it in between yet), the last bit where it counts ArrayList removing entries never appears, as if the app has gone into some sort of infinite loop or something without any error messages. I'm not entirely sure why this is, so I thought I'd ask to see if you guys did!

Btw, I did make sure to set -Xss256m and -Xms256m in case this was the issue, but this didn't help either.

Thanks a bunch!

Best regards,
Colton

Straight flippin.
Offline theagentd

« JGO Bitwise Duke »


Medals: 365
Projects: 2
Exp: 8 years



« Reply #1 - Posted 2012-08-10 12:00:05 »

You're doing random remove()s, and they scale very badly with longer lists. It's probably just really slow.

Myomyomyo.
Offline teletubo
« League of Dukes »

JGO Ninja


Medals: 48
Projects: 4
Exp: 8 years



« Reply #2 - Posted 2012-08-10 12:53:13 »

Well first of all you should debug your stuff before jumping into conclusion that it is an inifinite loop or a memory error (?).

Have you debugged to see if the size of the list is decreasing?

Secondly, you're putting a random factor in your benchmark for adding two types of elements ("hello" and "goodbye") which will directly affect the outcome of the remove phase. In the ArrayList run you might have 2 times more removes than the Bag removes, so you cannot conclude anything with that.

If you want to benchmark something against something else, they should operate on the exact same data, not on completely different sets!
With this random set benchmarking you might (and probably will) get different results even if you declared both lists as a Bag!

And finally, if you're measuring the add and remove, your loop should contain ONLY that, not a call to a random function which probably is more expensive than an add().
Let's assume your whole loop spends 1000ms in the Random function, and 200ms in the add() for ArrayList and 100ms for the add in the Bag.
You'll conclude that ArrayList performs 1100/1200=91% of Bag, when you should be concluding that it performs 100/200=50% comparing to Bag.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online Roquen
« Reply #3 - Posted 2012-08-10 13:43:28 »

Microbenching is hard.  No offense intended, but everything is wrong. Smiley
Offline coltonoscopy

Junior Devvie


Medals: 2



« Reply #4 - Posted 2012-08-10 20:42:41 »

Well first of all you should debug your stuff before jumping into conclusion that it is an inifinite loop or a memory error (?).

Have you debugged to see if the size of the list is decreasing?

Secondly, you're putting a random factor in your benchmark for adding two types of elements ("hello" and "goodbye") which will directly affect the outcome of the remove phase. In the ArrayList run you might have 2 times more removes than the Bag removes, so you cannot conclude anything with that.

If you want to benchmark something against something else, they should operate on the exact same data, not on completely different sets!
With this random set benchmarking you might (and probably will) get different results even if you declared both lists as a Bag!

And finally, if you're measuring the add and remove, your loop should contain ONLY that, not a call to a random function which probably is more expensive than an add().
Let's assume your whole loop spends 1000ms in the Random function, and 200ms in the add() for ArrayList and 100ms for the add in the Bag.
You'll conclude that ArrayList performs 1100/1200=91% of Bag, when you should be concluding that it performs 100/200=50% comparing to Bag.
You're right; I probably should have taken all of those other factors into consideration! However, I wanted to also check randomness as part of their performance, because I would be using them in scenarios involving randomization.

EDIT: Another thing is that both the Bag and the ArrayList are given the same set of instructions, and yet the Bag will always finish all of its removes in less than a tenth of a second. I did some outputs on the ArrayList removes and it takes it an astronomical amount of time for it to do essentially the same thing, consistently; in fact, I haven't had the patience to let it complete a full run yet, but it takes many minutes.

Microbenching is hard.  No offense intended, but everything is wrong. Smiley
No offense taken; I have much to learn! Cheesy

Colton

Straight flippin.
Online Roquen
« Reply #5 - Posted 2012-08-10 21:04:46 »

Awesome.
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 (29 views)
2014-12-15 09:26:44

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

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

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

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

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

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

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

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

toopeicgaming1999 (30 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

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