FastList<T> is not performing as expected ?

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

FastList<T> is not performing as expected ?

Achmad Aulia Noorhakim
Hi list,

I've been doing some benchmarking between Array in AS3 (Flex) & Array in haXe, both outputing to Flash9. The result was satisfying since the haXe test was 2x faster than the AS3 version, and with inline it is even faster. Since what I need is something that will spend most time being iterated (every frame) I though to give FastList<T> a try against the haXe Array<T>, which most people say (including haXe blog) is faster than Array when iterating. But to my surprise my implementation was way slower even against AS3 Array. Is there something wrong with how I use the FastList<T> ?

Here is the code btw, I commented out the Array code, to test the Array code just comment the FastList<T> code and uncomment the Array part.

class Main
{
   
    static function main()
    {
        var foo:Foo = new Foo();
        //var arrFoo:Array<Foo> = new Array<Foo>();
        var avgFill:Float = 0;
        var avgIter:Float = 0;
       
        var lstFoo:haxe.FastList<Foo> = new haxe.FastList<Foo>();
       
        var testCount:Int = 10;
        var fooCount:Int = 1000000;
       
        for (test in 0...testCount)
        {
            var fillBeg:Int = Lib.getTimer();
            for (idx in 0...fooCount)
            {
                //arrFoo.push(foo);
                lstFoo.add(foo);
            }
            var fillEnd:Int = Lib.getTimer();
           
            var iterBeg:Int = Lib.getTimer();
            /*
            for (idx in 0...fooCount)
            {
                arrFoo[idx].doSomething();
            }
            */
            var node:FastCell<Foo> = lstFoo.head;
            while (node != null)
            {
                node.elt.doSomething();
                node = node.next;
            }
            var iterEnd:Int = Lib.getTimer();
           
            avgFill += (fillEnd - fillBeg);
            avgIter += (iterEnd - iterBeg);

        }
       
        avgFill /= testCount;
        avgIter /= testCount;
       
       
        var tf:TextField         = new TextField();
        tf.defaultTextFormat     = new TextFormat("Lucida Console", 10, 0xFFFFFFFF);
        tf.width                 = Lib.current.stage.stageWidth;
        tf.height                 = Lib.current.stage.stageHeight;
        tf.text                 = "";
        Lib.current.stage.addChild(tf);
       
        tf.text = "Fill Time : " + Std.string( avgFill ) + "\nIterate Time : " + Std.string( avgIter );
       
       
    }
   
}


Info:
Foo is just a simple class with 1 function doSomething() that do some simple calculation (eg. var a:Float = 10*20*0.5; :3).

Thx.

PS: Yes I know I probably won't need 1000000 object being iterated everytime (that would mean I'm doing something wrong infact :3). But I still wan't to know :D


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: FastList<T> is not performing as expected ?

Nicolas Cannasse
Achmad Aulia a écrit :

> Hi list,
>
> I've been doing some benchmarking between Array in AS3 (Flex) & Array in
> haXe, both outputing to Flash9. The result was satisfying since the haXe
> test was 2x faster than the AS3 version, and with inline it is even
> faster. Since what I need is something that will spend most time being
> iterated (every frame) I though to give FastList<T> a try against the
> haXe Array<T>, which most people say (including haXe blog) is faster
> than Array when iterating. But to my surprise my implementation was way
> slower even against AS3 Array. Is there something wrong with how I use
> the FastList<T> ?

FastList should be slower than Array for insertion, since you need to
create a new FastCell everytime and this is a very slow operation. But
it should be a lot faster for iteration.

Nicolas

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: FastList<T> is not performing as expected ?

Robin Palotai
I am interested in why is Array slow? If indexed serially and not
random, its content should be in the memory cache, and lookup should
be fast. Why is the flash implementation so slow? Just curious, if you
know any technical detail.

Thanks,
Robin

On Wed, Apr 15, 2009 at 2:11 PM, Nicolas Cannasse
<[hidden email]> wrote:

> Achmad Aulia a écrit :
>>
>> Hi list,
>>
>> I've been doing some benchmarking between Array in AS3 (Flex) & Array in
>> haXe, both outputing to Flash9. The result was satisfying since the haXe
>> test was 2x faster than the AS3 version, and with inline it is even faster.
>> Since what I need is something that will spend most time being iterated
>> (every frame) I though to give FastList<T> a try against the haXe Array<T>,
>> which most people say (including haXe blog) is faster than Array when
>> iterating. But to my surprise my implementation was way slower even against
>> AS3 Array. Is there something wrong with how I use the FastList<T> ?
>
> FastList should be slower than Array for insertion, since you need to create
> a new FastCell everytime and this is a very slow operation. But it should be
> a lot faster for iteration.
>
> Nicolas
>
> --
> haXe - an open source web programming language
> http://haxe.org
>

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: FastList<T> is not performing as expected ?

Achmad Aulia Noorhakim
In reply to this post by Nicolas Cannasse
Hi Nicolas, thank you for your reply,

Yes I know that allocation/insertion in FastList is slow, but as you can see in the code, I also calculate the iteration time. I don't really complain about the insertion time of FastList, since I expect it to be slower than Array. It's the iteration time that is bugging me, since it seems that everyone get better result with FastList, why does in my result, FastList is slower ?

Oh and there is some bug in my code, I forgot to reset the Array/List every loop, it's fixed now (in my code), but the list is still slightly slower.

BTW here is the result in my computer (Core2Duo E6550, 4 GB RAM, FX8800 GTS), with Flash Player 9 (standalone)

Array AS3 : Fill time : 95.9. ms | Iter time : 188.7 ms
Array Haxe (with inline in function doSomething()) : Fill time : 96.7 ms | iter time : 7.7 ms
FastList Haxe (with inline) : Fill time : 705.5 ms | iter time : 11 ms

As you can see, the iteration time is still below Array haxe.

Oh and here is the new code:

class Main
{
   
    static function main()
    {
        var foo:Foo = new Foo();
        var arrFoo:Array<Foo> = new Array<Foo>();
        var avgFill:Float = 0;
        var avgIter:Float = 0;
       
        //var lstFoo:haxe.FastList<Foo> = new haxe.FastList<Foo>();
       
        var testCount:Int = 10;
        var fooCount:Int = 1000000;
       
        for (test in 0...testCount)
        {
            //lstFoo.head = null;
            arrFoo.splice(0, arrFoo.length);
           
            var fillBeg:Int = Lib.getTimer();
            for (idx in 0...fooCount)
            {
                arrFoo.push(foo);
                //lstFoo.add(foo);
            }
            var fillEnd:Int = Lib.getTimer();
           
            var iterBeg:Int = Lib.getTimer();

            for (idx in 0...fooCount)
            {
                arrFoo[idx].doSomething();
            }

            /*
            var node:FastCell<Foo> = lstFoo.head;
            while (node != null)
            {
                node.elt.doSomething();
                node = node.next;
            }
            */

            var iterEnd:Int = Lib.getTimer();
           
            avgFill += (fillEnd - fillBeg);
            avgIter += (iterEnd - iterBeg);

        }
       
        avgFill /= testCount;
        avgIter /= testCount;
       
       
        var tf:TextField         = new TextField();
        tf.defaultTextFormat     = new TextFormat("Lucida Console", 10, 0xFFFFFFFF);
        tf.width                 = Lib.current.stage.stageWidth;
        tf.height                 = Lib.current.stage.stageHeight;
        tf.text                 = "";
        Lib.current.stage.addChild(tf);
       
        tf.text = "Fill Time : " + Std.string( avgFill ) + "\nIterate Time : " + Std.string( avgIter );
       
       
    }
   
}

On Wed, Apr 15, 2009 at 7:11 PM, Nicolas Cannasse <[hidden email]> wrote:
Achmad Aulia a écrit :

Hi list,

I've been doing some benchmarking between Array in AS3 (Flex) & Array in haXe, both outputing to Flash9. The result was satisfying since the haXe test was 2x faster than the AS3 version, and with inline it is even faster. Since what I need is something that will spend most time being iterated (every frame) I though to give FastList<T> a try against the haXe Array<T>, which most people say (including haXe blog) is faster than Array when iterating. But to my surprise my implementation was way slower even against AS3 Array. Is there something wrong with how I use the FastList<T> ?

FastList should be slower than Array for insertion, since you need to create a new FastCell everytime and this is a very slow operation. But it should be a lot faster for iteration.

Nicolas

--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: FastList<T> is not performing as expected ?

Nicolas Cannasse
Achmad Aulia a écrit :

> Hi Nicolas, thank you for your reply,
>
> Yes I know that allocation/insertion in FastList is slow, but as you can
> see in the code, I also calculate the iteration time. I don't really
> complain about the insertion time of FastList, since I expect it to be
> slower than Array. It's the iteration time that is bugging me, since it
> seems that everyone get better result with FastList, why does in my
> result, FastList is slower ?
>
> Oh and there is some bug in my code, I forgot to reset the Array/List
> every loop, it's fixed now (in my code), but the list is still slightly
> slower.
>
> BTW here is the result in my computer (Core2Duo E6550, 4 GB RAM, FX8800
> GTS), with Flash Player 9 (standalone)

Did you try with release player (not debug version) ?

Nicolas

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: FastList<T> is not performing as expected ?

Achmad Aulia Noorhakim
Hmm my standalone player seems to be the debug player, does any have the release standalone player ?
Ok I'll try with the browser flash player. Thanks

On Wed, Apr 15, 2009 at 7:47 PM, Nicolas Cannasse <[hidden email]> wrote:
Achmad Aulia a écrit :
Hi Nicolas, thank you for your reply,


Yes I know that allocation/insertion in FastList is slow, but as you can see in the code, I also calculate the iteration time. I don't really complain about the insertion time of FastList, since I expect it to be slower than Array. It's the iteration time that is bugging me, since it seems that everyone get better result with FastList, why does in my result, FastList is slower ?

Oh and there is some bug in my code, I forgot to reset the Array/List every loop, it's fixed now (in my code), but the list is still slightly slower.

BTW here is the result in my computer (Core2Duo E6550, 4 GB RAM, FX8800 GTS), with Flash Player 9 (standalone)

Did you try with release player (not debug version) ?


Nicolas

--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: FastList<T> is not performing as expected ?

Achmad Aulia Noorhakim
Ok i've tried using the release flash player that come with the browser (using FD Play in Popup, I believe it's using browser flash player ? Since I don't see any Show redraw region in the context menu I assume it's release player).

Without inline, 1.000.000 obj, haXe
Array = 96.x ms
FastList = 86.x ms
* without inlining FastList win by 10 ms

With Inline, 1.000.000 obj, haXe
Array = 10 ms
FastList = 10.5 ms
* I gues when inline involved and the situation is right, both Array and FastList will produce roughly the same result ?

Thanks to Nicolas, I think I just have my prove, and inlining is damn nice ! :D


On Wed, Apr 15, 2009 at 8:05 PM, Achmad Aulia <[hidden email]> wrote:
Hmm my standalone player seems to be the debug player, does any have the release standalone player ?
Ok I'll try with the browser flash player. Thanks


On Wed, Apr 15, 2009 at 7:47 PM, Nicolas Cannasse <[hidden email]> wrote:
Achmad Aulia a écrit :
Hi Nicolas, thank you for your reply,


Yes I know that allocation/insertion in FastList is slow, but as you can see in the code, I also calculate the iteration time. I don't really complain about the insertion time of FastList, since I expect it to be slower than Array. It's the iteration time that is bugging me, since it seems that everyone get better result with FastList, why does in my result, FastList is slower ?

Oh and there is some bug in my code, I forgot to reset the Array/List every loop, it's fixed now (in my code), but the list is still slightly slower.

BTW here is the result in my computer (Core2Duo E6550, 4 GB RAM, FX8800 GTS), with Flash Player 9 (standalone)

Did you try with release player (not debug version) ?


Nicolas

--
haXe - an open source web programming language
http://haxe.org



--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: FastList<T> is not performing as expected ?

Chris Hecker
In reply to this post by Nicolas Cannasse

 > FastList should be slower than Array for insertion, since you need to
 > create a new FastCell everytime and this is a very slow operation. But
 > it should be a lot faster for iteration.

I did some measurements and it really depended on size and length for my
tests.  They should be in the archive.  This was a few versions ago, though.

Chris



Nicolas Cannasse wrote:

> Achmad Aulia a écrit :
>> Hi list,
>>
>> I've been doing some benchmarking between Array in AS3 (Flex) & Array
>> in haXe, both outputing to Flash9. The result was satisfying since the
>> haXe test was 2x faster than the AS3 version, and with inline it is
>> even faster. Since what I need is something that will spend most time
>> being iterated (every frame) I though to give FastList<T> a try
>> against the haXe Array<T>, which most people say (including haXe blog)
>> is faster than Array when iterating. But to my surprise my
>> implementation was way slower even against AS3 Array. Is there
>> something wrong with how I use the FastList<T> ?
>
> FastList should be slower than Array for insertion, since you need to
> create a new FastCell everytime and this is a very slow operation. But
> it should be a lot faster for iteration.
>
> Nicolas
>

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: FastList<T> is not performing as expected ?

Tony Polinelli
Hi-  out of curiosity, would you be able to benchmark the standard List object aswell?  - would be interesting


Tony Polinelli
http://www.touchmypixel.com


On Thu, Apr 16, 2009 at 2:54 AM, Chris Hecker <[hidden email]> wrote:

> FastList should be slower than Array for insertion, since you need to
> create a new FastCell everytime and this is a very slow operation. But
> it should be a lot faster for iteration.

I did some measurements and it really depended on size and length for my tests.  They should be in the archive.  This was a few versions ago, though.

Chris




Nicolas Cannasse wrote:
Achmad Aulia a écrit :
Hi list,

I've been doing some benchmarking between Array in AS3 (Flex) & Array in haXe, both outputing to Flash9. The result was satisfying since the haXe test was 2x faster than the AS3 version, and with inline it is even faster. Since what I need is something that will spend most time being iterated (every frame) I though to give FastList<T> a try against the haXe Array<T>, which most people say (including haXe blog) is faster than Array when iterating. But to my surprise my implementation was way slower even against AS3 Array. Is there something wrong with how I use the FastList<T> ?

FastList should be slower than Array for insertion, since you need to create a new FastCell everytime and this is a very slow operation. But it should be a lot faster for iteration.

Nicolas


--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: FastList<T> is not performing as expected ?

Chris Hecker

Can't remember.  Search the archives!  I even posted a test app.  :)

Chris


Tony Polinelli wrote:

> Hi-  out of curiosity, would you be able to benchmark the standard List
> object aswell?  - would be interesting
>
>
> Tony Polinelli
> http://www.touchmypixel.com
>
>
> On Thu, Apr 16, 2009 at 2:54 AM, Chris Hecker <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>
>      > FastList should be slower than Array for insertion, since you need to
>      > create a new FastCell everytime and this is a very slow
>     operation. But
>      > it should be a lot faster for iteration.
>
>     I did some measurements and it really depended on size and length
>     for my tests.  They should be in the archive.  This was a few
>     versions ago, though.
>
>     Chris
>
>
>
>
>     Nicolas Cannasse wrote:
>
>         Achmad Aulia a écrit :
>
>             Hi list,
>
>             I've been doing some benchmarking between Array in AS3
>             (Flex) & Array in haXe, both outputing to Flash9. The result
>             was satisfying since the haXe test was 2x faster than the
>             AS3 version, and with inline it is even faster. Since what I
>             need is something that will spend most time being iterated
>             (every frame) I though to give FastList<T> a try against the
>             haXe Array<T>, which most people say (including haXe blog)
>             is faster than Array when iterating. But to my surprise my
>             implementation was way slower even against AS3 Array. Is
>             there something wrong with how I use the FastList<T> ?
>
>
>         FastList should be slower than Array for insertion, since you
>         need to create a new FastCell everytime and this is a very slow
>         operation. But it should be a lot faster for iteration.
>
>         Nicolas
>
>
>     --
>     haXe - an open source web programming language
>     http://haxe.org
>
>

--
haXe - an open source web programming language
http://haxe.org