as3 final keyword on linked list nodes

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

as3 final keyword on linked list nodes

Michael Baczynski-2
hi,

Ralph Hauwert gave a nice speech today at the FFK in cologne showing
some of his experiments.
in one slide he showed that adding the 'final' keyword to a linked list
node makes iteration much faster.
however, I wasn't able to reproduce this in as3 - there is absolutely no
difference at all in runtime performance (win/release).
maybe someone can confirm this?

e.g. for a 2d vertex:

public final class Node
{
     public var x:Number;
     public var y:Number;
     public var next:Node;

     public function Node() {}
}

the same applies to the 'const' keyword in as3..

best,
michael

--
http://www.polygonal.de


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

Re: as3 final keyword on linked list nodes

Cauê W.
have you tried to run the test with the release (not debug) version??

2010/4/14 Michael Baczynski <[hidden email]>
hi,

Ralph Hauwert gave a nice speech today at the FFK in cologne showing some of his experiments.
in one slide he showed that adding the 'final' keyword to a linked list node makes iteration much faster.
however, I wasn't able to reproduce this in as3 - there is absolutely no difference at all in runtime performance (win/release).
maybe someone can confirm this?

e.g. for a 2d vertex:

public final class Node
{
   public var x:Number;
   public var y:Number;
   public var next:Node;

   public function Node() {}
}

the same applies to the 'const' keyword in as3..

best,
michael

--
http://www.polygonal.de


--
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: as3 final keyword on linked list nodes

Michael Baczynski-2
On 15.04.2010 00:55, Cauê Waneck wrote:
> have you tried to run the test with the release (not debug) version??
of course. when tested in the debug player both versions run slower, but
exactly at the same rate.
likewise, both version run a lot faster in the release player, but again
no difference.
my simple test case:

//Test
package
{
     import flash.display.Sprite;
     import flash.text.TextField;
     import flash.utils.getTimer;

     public class Test extends Sprite
     {
         public function Test()
         {
             init();
             walk();
         }

         private var _node:Node;

         private function init():void
         {
             _node = new Node();

             var n:Node = _node;
             for (var i:int = 0; i < 1000000; i++)
             {
                 n = n.next = new Node();
             }
         }

         private function walk():void
         {
             var ttotal:int = 0;
             for (var i:int = 0; i < 10; i++) //mean over 10 iterations
             {
                 var time:int = getTimer();

                 var n:Node = _node;
                 var x:Number;
                 var y:Number;
                 while (n)
                 {
                     x = n.x;
                     y = n.y;
                     n = n.next;
                 }

                 ttotal += (getTimer() - time);
             }

             var tf:TextField = new TextField();
             tf.text = ''  + (ttotal / 10);
             addChild(tf);
         }
     }
}

//Node.as

package
{
     public final class Node
     {
         public var next:Node;

         public var x:Number;
         public var y:Number;

         public function Node() {}
     }
}


>
> 2010/4/14 Michael Baczynski <[hidden email]
> <mailto:[hidden email]>>
>
>     hi,
>
>     Ralph Hauwert gave a nice speech today at the FFK in cologne
>     showing some of his experiments.
>     in one slide he showed that adding the 'final' keyword to a linked
>     list node makes iteration much faster.
>     however, I wasn't able to reproduce this in as3 - there is
>     absolutely no difference at all in runtime performance (win/release).
>     maybe someone can confirm this?
>
>     e.g. for a 2d vertex:
>
>     public final class Node
>     {
>        public var x:Number;
>        public var y:Number;
>        public var next:Node;
>
>        public function Node() {}
>     }
>
>     the same applies to the 'const' keyword in as3..
>
>     best,
>     michael
>
>     --
>     http://www.polygonal.de
>
>
>     --
>     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: as3 final keyword on linked list nodes

Cauê W.
Could be because the constructor call is orders of magnitude slower than a field access, so here  n = n.next = new Node(); , the n.next access speed isn't really very significant? I mean, it could be 0, it still wouldn't make much a difference.

2010/4/14 Michael Baczynski <[hidden email]>
On 15.04.2010 00:55, Cauę Waneck wrote:
have you tried to run the test with the release (not debug) version??
of course. when tested in the debug player both versions run slower, but exactly at the same rate.
likewise, both version run a lot faster in the release player, but again no difference.
my simple test case:

//Test
package
{
   import flash.display.Sprite;
   import flash.text.TextField;
   import flash.utils.getTimer;

   public class Test extends Sprite
   {
       public function Test()
       {
           init();
           walk();
       }

       private var _node:Node;

       private function init():void
       {
           _node = new Node();

           var n:Node = _node;
           for (var i:int = 0; i < 1000000; i++)
           {
               n = n.next = new Node();
           }
       }

       private function walk():void
       {
           var ttotal:int = 0;
           for (var i:int = 0; i < 10; i++) //mean over 10 iterations
           {
               var time:int = getTimer();

               var n:Node = _node;
               var x:Number;
               var y:Number;
               while (n)
               {
                   x = n.x;
                   y = n.y;
                   n = n.next;
               }

               ttotal += (getTimer() - time);
           }

           var tf:TextField = new TextField();
           tf.text = ''  + (ttotal / 10);
           addChild(tf);
       }
   }
}

//Node.as

package
{
   public final class Node
   {
       public var next:Node;


       public var x:Number;
       public var y:Number;

       public function Node() {}
   }
}



2010/4/14 Michael Baczynski <[hidden email] <mailto:[hidden email]>>


   hi,

   Ralph Hauwert gave a nice speech today at the FFK in cologne
   showing some of his experiments.
   in one slide he showed that adding the 'final' keyword to a linked
   list node makes iteration much faster.
   however, I wasn't able to reproduce this in as3 - there is
   absolutely no difference at all in runtime performance (win/release).
   maybe someone can confirm this?

   e.g. for a 2d vertex:

   public final class Node
   {
      public var x:Number;
      public var y:Number;
      public var next:Node;

      public function Node() {}
   }

   the same applies to the 'const' keyword in as3..

   best,
   michael

   --     http://www.polygonal.de


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




--
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: as3 final keyword on linked list nodes

Nicolas Cannasse
In reply to this post by Michael Baczynski-2
Michael Baczynski a écrit :
> hi,
>
> Ralph Hauwert gave a nice speech today at the FFK in cologne showing
> some of his experiments.
> in one slide he showed that adding the 'final' keyword to a linked list
> node makes iteration much faster.
> however, I wasn't able to reproduce this in as3 - there is absolutely no
> difference at all in runtime performance (win/release).
> maybe someone can confirm this?

In *theory* final *could* run faster. But in practice, it doesn't.

Best,
Nicolas

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

Re: as3 final keyword on linked list nodes

Chris Hecker

> In *theory* final *could* run faster. But in practice, it doesn't.

A common situation when optimizing code!  :)

Chris



Nicolas Cannasse wrote:

> Michael Baczynski a écrit :
>> hi,
>>
>> Ralph Hauwert gave a nice speech today at the FFK in cologne showing
>> some of his experiments.
>> in one slide he showed that adding the 'final' keyword to a linked
>> list node makes iteration much faster.
>> however, I wasn't able to reproduce this in as3 - there is absolutely
>> no difference at all in runtime performance (win/release).
>> maybe someone can confirm this?
>
> In *theory* final *could* run faster. But in practice, it doesn't.
>
> Best,
> Nicolas
>

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

Re: as3 final keyword on linked list nodes

Armén
In reply to this post by Cauê W.
Yes, if you (Michael) are serious about REALLY optimizing your Node applications, "final" regardless, reuse Node objects in a factory.

2010/4/15 Cauê Waneck <[hidden email]>
Could be because the constructor call is orders of magnitude slower than a field access, so here  n = n.next = new Node(); , the n.next access speed isn't really very significant? I mean, it could be 0, it still wouldn't make much a difference.


2010/4/14 Michael Baczynski <[hidden email]>
On 15.04.2010 00:55, Cauę Waneck wrote:
have you tried to run the test with the release (not debug) version??
of course. when tested in the debug player both versions run slower, but exactly at the same rate.
likewise, both version run a lot faster in the release player, but again no difference.
my simple test case:

//Test
package
{
   import flash.display.Sprite;
   import flash.text.TextField;
   import flash.utils.getTimer;

   public class Test extends Sprite
   {
       public function Test()
       {
           init();
           walk();
       }

       private var _node:Node;

       private function init():void
       {
           _node = new Node();

           var n:Node = _node;
           for (var i:int = 0; i < 1000000; i++)
           {
               n = n.next = new Node();
           }
       }

       private function walk():void
       {
           var ttotal:int = 0;
           for (var i:int = 0; i < 10; i++) //mean over 10 iterations
           {
               var time:int = getTimer();

               var n:Node = _node;
               var x:Number;
               var y:Number;
               while (n)
               {
                   x = n.x;
                   y = n.y;
                   n = n.next;
               }

               ttotal += (getTimer() - time);
           }

           var tf:TextField = new TextField();
           tf.text = ''  + (ttotal / 10);
           addChild(tf);
       }
   }
}

//Node.as

package
{
   public final class Node
   {
       public var next:Node;


       public var x:Number;
       public var y:Number;

       public function Node() {}
   }
}



2010/4/14 Michael Baczynski <[hidden email] <mailto:[hidden email]>>


   hi,

   Ralph Hauwert gave a nice speech today at the FFK in cologne
   showing some of his experiments.
   in one slide he showed that adding the 'final' keyword to a linked
   list node makes iteration much faster.
   however, I wasn't able to reproduce this in as3 - there is
   absolutely no difference at all in runtime performance (win/release).
   maybe someone can confirm this?

   e.g. for a 2d vertex:

   public final class Node
   {
      public var x:Number;
      public var y:Number;
      public var next:Node;

      public function Node() {}
   }

   the same applies to the 'const' keyword in as3..

   best,
   michael

   --     http://www.polygonal.de


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




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


--
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: as3 final keyword on linked list nodes

Mark de Bruijn | Dykam
Armencho,what would be the base datastructure be of the factory?
--
Mark


On Mon, Apr 19, 2010 at 11:39 AM, [hidden email] <[hidden email]> wrote:
Yes, if you (Michael) are serious about REALLY optimizing your Node applications, "final" regardless, reuse Node objects in a factory.

2010/4/15 Cauê Waneck <[hidden email]>
Could be because the constructor call is orders of magnitude slower than a field access, so here  n = n.next = new Node(); , the n.next access speed isn't really very significant? I mean, it could be 0, it still wouldn't make much a difference.


2010/4/14 Michael Baczynski <[hidden email]>
On 15.04.2010 00:55, Cauę Waneck wrote:
have you tried to run the test with the release (not debug) version??
of course. when tested in the debug player both versions run slower, but exactly at the same rate.
likewise, both version run a lot faster in the release player, but again no difference.
my simple test case:

//Test
package
{
   import flash.display.Sprite;
   import flash.text.TextField;
   import flash.utils.getTimer;

   public class Test extends Sprite
   {
       public function Test()
       {
           init();
           walk();
       }

       private var _node:Node;

       private function init():void
       {
           _node = new Node();

           var n:Node = _node;
           for (var i:int = 0; i < 1000000; i++)
           {
               n = n.next = new Node();
           }
       }

       private function walk():void
       {
           var ttotal:int = 0;
           for (var i:int = 0; i < 10; i++) //mean over 10 iterations
           {
               var time:int = getTimer();

               var n:Node = _node;
               var x:Number;
               var y:Number;
               while (n)
               {
                   x = n.x;
                   y = n.y;
                   n = n.next;
               }

               ttotal += (getTimer() - time);
           }

           var tf:TextField = new TextField();
           tf.text = ''  + (ttotal / 10);
           addChild(tf);
       }
   }
}

//Node.as

package
{
   public final class Node
   {
       public var next:Node;


       public var x:Number;
       public var y:Number;

       public function Node() {}
   }
}



2010/4/14 Michael Baczynski <[hidden email] <mailto:[hidden email]>>


   hi,

   Ralph Hauwert gave a nice speech today at the FFK in cologne
   showing some of his experiments.
   in one slide he showed that adding the 'final' keyword to a linked
   list node makes iteration much faster.
   however, I wasn't able to reproduce this in as3 - there is
   absolutely no difference at all in runtime performance (win/release).
   maybe someone can confirm this?

   e.g. for a 2d vertex:

   public final class Node
   {
      public var x:Number;
      public var y:Number;
      public var next:Node;

      public function Node() {}
   }

   the same applies to the 'const' keyword in as3..

   best,
   michael

   --     http://www.polygonal.de


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




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


--

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


--
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: as3 final keyword on linked list nodes

Armén
What do you mean by "base datastructure"? Just because it's called a Factory, does not mean it's a building :-) I imagine it would be creating and reusing Node objects. It also goes by the name of "object pool". But a factory is usually more than just an object pool, as the latter is more primitive.

On Mon, Apr 19, 2010 at 14:27, Mark de Bruijn | Dykam <[hidden email]> wrote:
Armencho,what would be the base datastructure be of the factory?
--
Mark


On Mon, Apr 19, 2010 at 11:39 AM, [hidden email] <[hidden email]> wrote:
Yes, if you (Michael) are serious about REALLY optimizing your Node applications, "final" regardless, reuse Node objects in a factory.

2010/4/15 Cauê Waneck <[hidden email]>
Could be because the constructor call is orders of magnitude slower than a field access, so here  n = n.next = new Node(); , the n.next access speed isn't really very significant? I mean, it could be 0, it still wouldn't make much a difference.


2010/4/14 Michael Baczynski <[hidden email]>
On 15.04.2010 00:55, Cauę Waneck wrote:
have you tried to run the test with the release (not debug) version??
of course. when tested in the debug player both versions run slower, but exactly at the same rate.
likewise, both version run a lot faster in the release player, but again no difference.
my simple test case:

//Test
package
{
   import flash.display.Sprite;
   import flash.text.TextField;
   import flash.utils.getTimer;

   public class Test extends Sprite
   {
       public function Test()
       {
           init();
           walk();
       }

       private var _node:Node;

       private function init():void
       {
           _node = new Node();

           var n:Node = _node;
           for (var i:int = 0; i < 1000000; i++)
           {
               n = n.next = new Node();
           }
       }

       private function walk():void
       {
           var ttotal:int = 0;
           for (var i:int = 0; i < 10; i++) //mean over 10 iterations
           {
               var time:int = getTimer();

               var n:Node = _node;
               var x:Number;
               var y:Number;
               while (n)
               {
                   x = n.x;
                   y = n.y;
                   n = n.next;
               }

               ttotal += (getTimer() - time);
           }

           var tf:TextField = new TextField();
           tf.text = ''  + (ttotal / 10);
           addChild(tf);
       }
   }
}

//Node.as

package
{
   public final class Node
   {
       public var next:Node;


       public var x:Number;
       public var y:Number;

       public function Node() {}
   }
}



2010/4/14 Michael Baczynski <[hidden email] <mailto:[hidden email]>>


   hi,

   Ralph Hauwert gave a nice speech today at the FFK in cologne
   showing some of his experiments.
   in one slide he showed that adding the 'final' keyword to a linked
   list node makes iteration much faster.
   however, I wasn't able to reproduce this in as3 - there is
   absolutely no difference at all in runtime performance (win/release).
   maybe someone can confirm this?

   e.g. for a 2d vertex:

   public final class Node
   {
      public var x:Number;
      public var y:Number;
      public var next:Node;

      public function Node() {}
   }

   the same applies to the 'const' keyword in as3..

   best,
   michael

   --     http://www.polygonal.de


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




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


--

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


--

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


--
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: as3 final keyword on linked list nodes

Mark de Bruijn | Dykam
Yes, but I mean, what are you using for pooling the data? An array, or a list? Afaik, for a linkedlist, the overhead will generally be bigger than the time a simple alloc takes.
--
Mark


On Mon, Apr 19, 2010 at 3:25 PM, [hidden email] <[hidden email]> wrote:
What do you mean by "base datastructure"? Just because it's called a Factory, does not mean it's a building :-) I imagine it would be creating and reusing Node objects. It also goes by the name of "object pool". But a factory is usually more than just an object pool, as the latter is more primitive.

On Mon, Apr 19, 2010 at 14:27, Mark de Bruijn | Dykam <[hidden email]> wrote:
Armencho,what would be the base datastructure be of the factory?
--
Mark


On Mon, Apr 19, 2010 at 11:39 AM, [hidden email] <[hidden email]> wrote:
Yes, if you (Michael) are serious about REALLY optimizing your Node applications, "final" regardless, reuse Node objects in a factory.

2010/4/15 Cauê Waneck <[hidden email]>
Could be because the constructor call is orders of magnitude slower than a field access, so here  n = n.next = new Node(); , the n.next access speed isn't really very significant? I mean, it could be 0, it still wouldn't make much a difference.


2010/4/14 Michael Baczynski <[hidden email]>
On 15.04.2010 00:55, Cauę Waneck wrote:
have you tried to run the test with the release (not debug) version??
of course. when tested in the debug player both versions run slower, but exactly at the same rate.
likewise, both version run a lot faster in the release player, but again no difference.
my simple test case:

//Test
package
{
   import flash.display.Sprite;
   import flash.text.TextField;
   import flash.utils.getTimer;

   public class Test extends Sprite
   {
       public function Test()
       {
           init();
           walk();
       }

       private var _node:Node;

       private function init():void
       {
           _node = new Node();

           var n:Node = _node;
           for (var i:int = 0; i < 1000000; i++)
           {
               n = n.next = new Node();
           }
       }

       private function walk():void
       {
           var ttotal:int = 0;
           for (var i:int = 0; i < 10; i++) //mean over 10 iterations
           {
               var time:int = getTimer();

               var n:Node = _node;
               var x:Number;
               var y:Number;
               while (n)
               {
                   x = n.x;
                   y = n.y;
                   n = n.next;
               }

               ttotal += (getTimer() - time);
           }

           var tf:TextField = new TextField();
           tf.text = ''  + (ttotal / 10);
           addChild(tf);
       }
   }
}

//Node.as

package
{
   public final class Node
   {
       public var next:Node;


       public var x:Number;
       public var y:Number;

       public function Node() {}
   }
}



2010/4/14 Michael Baczynski <[hidden email] <mailto:[hidden email]>>


   hi,

   Ralph Hauwert gave a nice speech today at the FFK in cologne
   showing some of his experiments.
   in one slide he showed that adding the 'final' keyword to a linked
   list node makes iteration much faster.
   however, I wasn't able to reproduce this in as3 - there is
   absolutely no difference at all in runtime performance (win/release).
   maybe someone can confirm this?

   e.g. for a 2d vertex:

   public final class Node
   {
      public var x:Number;
      public var y:Number;
      public var next:Node;

      public function Node() {}
   }

   the same applies to the 'const' keyword in as3..

   best,
   michael

   --     http://www.polygonal.de


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




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


--

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


--

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


--

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


--
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: as3 final keyword on linked list nodes

Armén
Yes you are right about linked list(s). Pushing and popping objects to and from a pool using a Vector is faster than my own linked list implementation (which is marginally faster than haXes own FastList generally because I do fewer runtime checks).

Also, for simple objects and/or objects which have cheap constructors, with Flash Player 10 at least, the runtime  outperforms object pools with its own allocator (i.e. 'new'), which I suspect may be using a pool itself on a much finer granular level.

For more complex classes and subclasses, e.g. Sprite and other runtime API classes, a pool allocator is worth using however, and using a Vector as the object pool itself proves to be the fastest currently.

On Mon, Apr 19, 2010 at 17:51, Mark de Bruijn | Dykam <[hidden email]> wrote:
Yes, but I mean, what are you using for pooling the data? An array, or a list? Afaik, for a linkedlist, the overhead will generally be bigger than the time a simple alloc takes.
--
Mark


On Mon, Apr 19, 2010 at 3:25 PM, [hidden email] <[hidden email]> wrote:
What do you mean by "base datastructure"? Just because it's called a Factory, does not mean it's a building :-) I imagine it would be creating and reusing Node objects. It also goes by the name of "object pool". But a factory is usually more than just an object pool, as the latter is more primitive.

On Mon, Apr 19, 2010 at 14:27, Mark de Bruijn | Dykam <[hidden email]> wrote:
Armencho,what would be the base datastructure be of the factory?
--
Mark


On Mon, Apr 19, 2010 at 11:39 AM, [hidden email] <[hidden email]> wrote:
Yes, if you (Michael) are serious about REALLY optimizing your Node applications, "final" regardless, reuse Node objects in a factory.

2010/4/15 Cauê Waneck <[hidden email]>
Could be because the constructor call is orders of magnitude slower than a field access, so here  n = n.next = new Node(); , the n.next access speed isn't really very significant? I mean, it could be 0, it still wouldn't make much a difference.


2010/4/14 Michael Baczynski <[hidden email]>
On 15.04.2010 00:55, Cauę Waneck wrote:
have you tried to run the test with the release (not debug) version??
of course. when tested in the debug player both versions run slower, but exactly at the same rate.
likewise, both version run a lot faster in the release player, but again no difference.
my simple test case:

//Test
package
{
   import flash.display.Sprite;
   import flash.text.TextField;
   import flash.utils.getTimer;

   public class Test extends Sprite
   {
       public function Test()
       {
           init();
           walk();
       }

       private var _node:Node;

       private function init():void
       {
           _node = new Node();

           var n:Node = _node;
           for (var i:int = 0; i < 1000000; i++)
           {
               n = n.next = new Node();
           }
       }

       private function walk():void
       {
           var ttotal:int = 0;
           for (var i:int = 0; i < 10; i++) //mean over 10 iterations
           {
               var time:int = getTimer();

               var n:Node = _node;
               var x:Number;
               var y:Number;
               while (n)
               {
                   x = n.x;
                   y = n.y;
                   n = n.next;
               }

               ttotal += (getTimer() - time);
           }

           var tf:TextField = new TextField();
           tf.text = ''  + (ttotal / 10);
           addChild(tf);
       }
   }
}

//Node.as

package
{
   public final class Node
   {
       public var next:Node;


       public var x:Number;
       public var y:Number;

       public function Node() {}
   }
}



2010/4/14 Michael Baczynski <[hidden email] <mailto:[hidden email]>>


   hi,

   Ralph Hauwert gave a nice speech today at the FFK in cologne
   showing some of his experiments.
   in one slide he showed that adding the 'final' keyword to a linked
   list node makes iteration much faster.
   however, I wasn't able to reproduce this in as3 - there is
   absolutely no difference at all in runtime performance (win/release).
   maybe someone can confirm this?

   e.g. for a 2d vertex:

   public final class Node
   {
      public var x:Number;
      public var y:Number;
      public var next:Node;

      public function Node() {}
   }

   the same applies to the 'const' keyword in as3..

   best,
   michael

   --     http://www.polygonal.de


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




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


--

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


--

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


--

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


--

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


--
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: as3 final keyword on linked list nodes

Yanis Benson
In reply to this post by Mark de Bruijn | Dykam
class PointFactory{
  public var free:Array<Point>;
 
  public function new(){
    free = [];
    }

  public function create(x:Int, y:Int){
    var point;
    if(free.length > 0)
      point = free.splice(free.length - 1, 1)[0];
    else
      point = new Point();
    point.x = x;
    point.y = y;
    return point;
    }

  public function delete(point:Point){
    free.push(point);
    }

  public function clear(){
    free = [];
    }
  }
This code is still very slow, I just stripped all optimizations. Obvious ones are: don't splice, just get and assign to null and store length by yourself, replace Array with Vector.

On 04/19/2010 07:51 PM, Mark de Bruijn | Dykam wrote:
Yes, but I mean, what are you using for pooling the data? An array, or a list? Afaik, for a linkedlist, the overhead will generally be bigger than the time a simple alloc takes.
--
Mark


On Mon, Apr 19, 2010 at 3:25 PM, [hidden email] <[hidden email]> wrote:
What do you mean by "base datastructure"? Just because it's called a Factory, does not mean it's a building :-) I imagine it would be creating and reusing Node objects. It also goes by the name of "object pool". But a factory is usually more than just an object pool, as the latter is more primitive.

On Mon, Apr 19, 2010 at 14:27, Mark de Bruijn | Dykam <[hidden email]> wrote:
Armencho,what would be the base datastructure be of the factory?
--
Mark


On Mon, Apr 19, 2010 at 11:39 AM, [hidden email] <[hidden email]> wrote:
Yes, if you (Michael) are serious about REALLY optimizing your Node applications, "final" regardless, reuse Node objects in a factory.

2010/4/15 Cauê Waneck <[hidden email]>
Could be because the constructor call is orders of magnitude slower than a field access, so here  n = n.next = new Node(); , the n.next access speed isn't really very significant? I mean, it could be 0, it still wouldn't make much a difference.


2010/4/14 Michael Baczynski <[hidden email]>
On 15.04.2010 00:55, Cauę Waneck wrote:
have you tried to run the test with the release (not debug) version??
of course. when tested in the debug player both versions run slower, but exactly at the same rate.
likewise, both version run a lot faster in the release player, but again no difference.
my simple test case:

//Test
package
{
   import flash.display.Sprite;
   import flash.text.TextField;
   import flash.utils.getTimer;

   public class Test extends Sprite
   {
       public function Test()
       {
           init();
           walk();
       }

       private var _node:Node;

       private function init():void
       {
           _node = new Node();

           var n:Node = _node;
           for (var i:int = 0; i < 1000000; i++)
           {
               n = n.next = new Node();
           }
       }

       private function walk():void
       {
           var ttotal:int = 0;
           for (var i:int = 0; i < 10; i++) //mean over 10 iterations
           {
               var time:int = getTimer();

               var n:Node = _node;
               var x:Number;
               var y:Number;
               while (n)
               {
                   x = n.x;
                   y = n.y;
                   n = n.next;
               }

               ttotal += (getTimer() - time);
           }

           var tf:TextField = new TextField();
           tf.text = ''  + (ttotal / 10);
           addChild(tf);
       }
   }
}

//Node.as

package
{
   public final class Node
   {
       public var next:Node;


       public var x:Number;
       public var y:Number;

       public function Node() {}
   }
}



2010/4/14 Michael Baczynski <[hidden email] <mailto:[hidden email]>>


   hi,

   Ralph Hauwert gave a nice speech today at the FFK in cologne
   showing some of his experiments.
   in one slide he showed that adding the 'final' keyword to a linked
   list node makes iteration much faster.
   however, I wasn't able to reproduce this in as3 - there is
   absolutely no difference at all in runtime performance (win/release).
   maybe someone can confirm this?

   e.g. for a 2d vertex:

   public final class Node
   {
      public var x:Number;
      public var y:Number;
      public var next:Node;

      public function Node() {}
   }

   the same applies to the 'const' keyword in as3..

   best,
   michael

   --     http://www.polygonal.de


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




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


--

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


--

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


--

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


--
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: as3 final keyword on linked list nodes

Yanis Benson
In reply to this post by Armén
Even with flash.geom.Point it's faster to have a pool form my tests. (Of course when you actively delete old points and not just generate and store massive amounts of them.)

On 04/19/2010 10:22 PM, [hidden email] wrote:
Yes you are right about linked list(s). Pushing and popping objects to and from a pool using a Vector is faster than my own linked list implementation (which is marginally faster than haXes own FastList generally because I do fewer runtime checks).

Also, for simple objects and/or objects which have cheap constructors, with Flash Player 10 at least, the runtime  outperforms object pools with its own allocator (i.e. 'new'), which I suspect may be using a pool itself on a much finer granular level.

For more complex classes and subclasses, e.g. Sprite and other runtime API classes, a pool allocator is worth using however, and using a Vector as the object pool itself proves to be the fastest currently.

On Mon, Apr 19, 2010 at 17:51, Mark de Bruijn | Dykam <[hidden email]> wrote:
Yes, but I mean, what are you using for pooling the data? An array, or a list? Afaik, for a linkedlist, the overhead will generally be bigger than the time a simple alloc takes.
--
Mark


On Mon, Apr 19, 2010 at 3:25 PM, [hidden email] <[hidden email]> wrote:
What do you mean by "base datastructure"? Just because it's called a Factory, does not mean it's a building :-) I imagine it would be creating and reusing Node objects. It also goes by the name of "object pool". But a factory is usually more than just an object pool, as the latter is more primitive.

On Mon, Apr 19, 2010 at 14:27, Mark de Bruijn | Dykam <[hidden email]> wrote:
Armencho,what would be the base datastructure be of the factory?
--
Mark


On Mon, Apr 19, 2010 at 11:39 AM, [hidden email] <[hidden email]> wrote:
Yes, if you (Michael) are serious about REALLY optimizing your Node applications, "final" regardless, reuse Node objects in a factory.

2010/4/15 Cauê Waneck <[hidden email]>
Could be because the constructor call is orders of magnitude slower than a field access, so here  n = n.next = new Node(); , the n.next access speed isn't really very significant? I mean, it could be 0, it still wouldn't make much a difference.


2010/4/14 Michael Baczynski <[hidden email]>
On 15.04.2010 00:55, Cauę Waneck wrote:
have you tried to run the test with the release (not debug) version??
of course. when tested in the debug player both versions run slower, but exactly at the same rate.
likewise, both version run a lot faster in the release player, but again no difference.
my simple test case:

//Test
package
{
   import flash.display.Sprite;
   import flash.text.TextField;
   import flash.utils.getTimer;

   public class Test extends Sprite
   {
       public function Test()
       {
           init();
           walk();
       }

       private var _node:Node;

       private function init():void
       {
           _node = new Node();

           var n:Node = _node;
           for (var i:int = 0; i < 1000000; i++)
           {
               n = n.next = new Node();
           }
       }

       private function walk():void
       {
           var ttotal:int = 0;
           for (var i:int = 0; i < 10; i++) //mean over 10 iterations
           {
               var time:int = getTimer();

               var n:Node = _node;
               var x:Number;
               var y:Number;
               while (n)
               {
                   x = n.x;
                   y = n.y;
                   n = n.next;
               }

               ttotal += (getTimer() - time);
           }

           var tf:TextField = new TextField();
           tf.text = ''  + (ttotal / 10);
           addChild(tf);
       }
   }
}

//Node.as

package
{
   public final class Node
   {
       public var next:Node;


       public var x:Number;
       public var y:Number;

       public function Node() {}
   }
}



2010/4/14 Michael Baczynski <[hidden email] <mailto:[hidden email]>>


   hi,

   Ralph Hauwert gave a nice speech today at the FFK in cologne
   showing some of his experiments.
   in one slide he showed that adding the 'final' keyword to a linked
   list node makes iteration much faster.
   however, I wasn't able to reproduce this in as3 - there is
   absolutely no difference at all in runtime performance (win/release).
   maybe someone can confirm this?

   e.g. for a 2d vertex:

   public final class Node
   {
      public var x:Number;
      public var y:Number;
      public var next:Node;

      public function Node() {}
   }

   the same applies to the 'const' keyword in as3..

   best,
   michael

   --     http://www.polygonal.de


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




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


--

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


--

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


--

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


--

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


--
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: as3 final keyword on linked list nodes

Armén
Here is my version, change it at will (to accept construction parameters, since my version is for objects without constructors). It is faster than yours, because I use 'pop' instead of 'splice' (it looks like you wanted a pop anyway?) and don't use 'length' which is an O(n) operation for arrays, vectors included. Also, don't forget inline signatures. The 'Stack' typedef is simply to define a netural interface for the pool, so that one can swap the type without changing a lot of code.

typedef Stack<T> = flash.Vector<T>;

class Factory<T>
{
    var objects: Stack<T>;
    var cl: Class<T>;

    public function new(cl: Class<T>)
    {
        this.cl = cl;
        objects = new Stack<T>();
    }

    public inline function create()
    {
        var obj = objects.pop();
        if(obj == null) return untyped __new__(cl);
        else return obj;
    }

    public inline function reclaim(obj: T)
    {
        objects.push(obj);
    }
}

This is of course a very rudimentary object factory.

On Mon, Apr 19, 2010 at 20:28, Yanis Benson <[hidden email]> wrote:
Even with flash.geom.Point it's faster to have a pool form my tests. (Of course when you actively delete old points and not just generate and store massive amounts of them.)


On 04/19/2010 10:22 PM, [hidden email] wrote:
Yes you are right about linked list(s). Pushing and popping objects to and from a pool using a Vector is faster than my own linked list implementation (which is marginally faster than haXes own FastList generally because I do fewer runtime checks).

Also, for simple objects and/or objects which have cheap constructors, with Flash Player 10 at least, the runtime  outperforms object pools with its own allocator (i.e. 'new'), which I suspect may be using a pool itself on a much finer granular level.

For more complex classes and subclasses, e.g. Sprite and other runtime API classes, a pool allocator is worth using however, and using a Vector as the object pool itself proves to be the fastest currently.

On Mon, Apr 19, 2010 at 17:51, Mark de Bruijn | Dykam <[hidden email]> wrote:
Yes, but I mean, what are you using for pooling the data? An array, or a list? Afaik, for a linkedlist, the overhead will generally be bigger than the time a simple alloc takes.
--
Mark


On Mon, Apr 19, 2010 at 3:25 PM, [hidden email] <[hidden email]> wrote:
What do you mean by "base datastructure"? Just because it's called a Factory, does not mean it's a building :-) I imagine it would be creating and reusing Node objects. It also goes by the name of "object pool". But a factory is usually more than just an object pool, as the latter is more primitive.

On Mon, Apr 19, 2010 at 14:27, Mark de Bruijn | Dykam <[hidden email]> wrote:
Armencho,what would be the base datastructure be of the factory?
--
Mark


On Mon, Apr 19, 2010 at 11:39 AM, [hidden email] <[hidden email]> wrote:
Yes, if you (Michael) are serious about REALLY optimizing your Node applications, "final" regardless, reuse Node objects in a factory.

2010/4/15 Cauê Waneck <[hidden email]>
Could be because the constructor call is orders of magnitude slower than a field access, so here  n = n.next = new Node(); , the n.next access speed isn't really very significant? I mean, it could be 0, it still wouldn't make much a difference.


2010/4/14 Michael Baczynski <[hidden email]>
On 15.04.2010 00:55, Cauę Waneck wrote:
have you tried to run the test with the release (not debug) version??
of course. when tested in the debug player both versions run slower, but exactly at the same rate.
likewise, both version run a lot faster in the release player, but again no difference.
my simple test case:

//Test
package
{
   import flash.display.Sprite;
   import flash.text.TextField;
   import flash.utils.getTimer;

   public class Test extends Sprite
   {
       public function Test()
       {
           init();
           walk();
       }

       private var _node:Node;

       private function init():void
       {
           _node = new Node();

           var n:Node = _node;
           for (var i:int = 0; i < 1000000; i++)
           {
               n = n.next = new Node();
           }
       }

       private function walk():void
       {
           var ttotal:int = 0;
           for (var i:int = 0; i < 10; i++) //mean over 10 iterations
           {
               var time:int = getTimer();

               var n:Node = _node;
               var x:Number;
               var y:Number;
               while (n)
               {
                   x = n.x;
                   y = n.y;
                   n = n.next;
               }

               ttotal += (getTimer() - time);
           }

           var tf:TextField = new TextField();
           tf.text = ''  + (ttotal / 10);
           addChild(tf);
       }
   }
}

//Node.as

package
{
   public final class Node
   {
       public var next:Node;


       public var x:Number;
       public var y:Number;

       public function Node() {}
   }
}



2010/4/14 Michael Baczynski <[hidden email] <mailto:[hidden email]>>


   hi,

   Ralph Hauwert gave a nice speech today at the FFK in cologne
   showing some of his experiments.
   in one slide he showed that adding the 'final' keyword to a linked
   list node makes iteration much faster.
   however, I wasn't able to reproduce this in as3 - there is
   absolutely no difference at all in runtime performance (win/release).
   maybe someone can confirm this?

   e.g. for a 2d vertex:

   public final class Node
   {
      public var x:Number;
      public var y:Number;
      public var next:Node;

      public function Node() {}
   }

   the same applies to the 'const' keyword in as3..

   best,
   michael

   --     http://www.polygonal.de


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




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


--

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


--

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


--

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


--

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


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



--
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: as3 final keyword on linked list nodes

Mark de Bruijn | Dykam
In reply to this post by Yanis Benson
You might... want to use Array.pop() instead of Array.splice(,)[0].
--
Mark


On Mon, Apr 19, 2010 at 8:28 PM, Yanis Benson <[hidden email]> wrote:
Even with flash.geom.Point it's faster to have a pool form my tests. (Of course when you actively delete old points and not just generate and store massive amounts of them.)


On 04/19/2010 10:22 PM, [hidden email] wrote:
Yes you are right about linked list(s). Pushing and popping objects to and from a pool using a Vector is faster than my own linked list implementation (which is marginally faster than haXes own FastList generally because I do fewer runtime checks).

Also, for simple objects and/or objects which have cheap constructors, with Flash Player 10 at least, the runtime  outperforms object pools with its own allocator (i.e. 'new'), which I suspect may be using a pool itself on a much finer granular level.

For more complex classes and subclasses, e.g. Sprite and other runtime API classes, a pool allocator is worth using however, and using a Vector as the object pool itself proves to be the fastest currently.

On Mon, Apr 19, 2010 at 17:51, Mark de Bruijn | Dykam <[hidden email]> wrote:
Yes, but I mean, what are you using for pooling the data? An array, or a list? Afaik, for a linkedlist, the overhead will generally be bigger than the time a simple alloc takes.
--
Mark


On Mon, Apr 19, 2010 at 3:25 PM, [hidden email] <[hidden email]> wrote:
What do you mean by "base datastructure"? Just because it's called a Factory, does not mean it's a building :-) I imagine it would be creating and reusing Node objects. It also goes by the name of "object pool". But a factory is usually more than just an object pool, as the latter is more primitive.

On Mon, Apr 19, 2010 at 14:27, Mark de Bruijn | Dykam <[hidden email]> wrote:
Armencho,what would be the base datastructure be of the factory?
--
Mark


On Mon, Apr 19, 2010 at 11:39 AM, [hidden email] <[hidden email]> wrote:
Yes, if you (Michael) are serious about REALLY optimizing your Node applications, "final" regardless, reuse Node objects in a factory.

2010/4/15 Cauê Waneck <[hidden email]>
Could be because the constructor call is orders of magnitude slower than a field access, so here  n = n.next = new Node(); , the n.next access speed isn't really very significant? I mean, it could be 0, it still wouldn't make much a difference.


2010/4/14 Michael Baczynski <[hidden email]>
On 15.04.2010 00:55, Cauę Waneck wrote:
have you tried to run the test with the release (not debug) version??
of course. when tested in the debug player both versions run slower, but exactly at the same rate.
likewise, both version run a lot faster in the release player, but again no difference.
my simple test case:

//Test
package
{
   import flash.display.Sprite;
   import flash.text.TextField;
   import flash.utils.getTimer;

   public class Test extends Sprite
   {
       public function Test()
       {
           init();
           walk();
       }

       private var _node:Node;

       private function init():void
       {
           _node = new Node();

           var n:Node = _node;
           for (var i:int = 0; i < 1000000; i++)
           {
               n = n.next = new Node();
           }
       }

       private function walk():void
       {
           var ttotal:int = 0;
           for (var i:int = 0; i < 10; i++) //mean over 10 iterations
           {
               var time:int = getTimer();

               var n:Node = _node;
               var x:Number;
               var y:Number;
               while (n)
               {
                   x = n.x;
                   y = n.y;
                   n = n.next;
               }

               ttotal += (getTimer() - time);
           }

           var tf:TextField = new TextField();
           tf.text = ''  + (ttotal / 10);
           addChild(tf);
       }
   }
}

//Node.as

package
{
   public final class Node
   {
       public var next:Node;


       public var x:Number;
       public var y:Number;

       public function Node() {}
   }
}



2010/4/14 Michael Baczynski <[hidden email] <mailto:[hidden email]>>


   hi,

   Ralph Hauwert gave a nice speech today at the FFK in cologne
   showing some of his experiments.
   in one slide he showed that adding the 'final' keyword to a linked
   list node makes iteration much faster.
   however, I wasn't able to reproduce this in as3 - there is
   absolutely no difference at all in runtime performance (win/release).
   maybe someone can confirm this?

   e.g. for a 2d vertex:

   public final class Node
   {
      public var x:Number;
      public var y:Number;
      public var next:Node;

      public function Node() {}
   }

   the same applies to the 'const' keyword in as3..

   best,
   michael

   --     http://www.polygonal.de


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




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


--

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


--

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


--

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


--

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


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



--
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: as3 final keyword on linked list nodes

Mark de Bruijn | Dykam
In reply to this post by Armén
I think you want to mark that typedef private.
--
Mark


On Mon, Apr 19, 2010 at 9:24 PM, [hidden email] <[hidden email]> wrote:
Here is my version, change it at will (to accept construction parameters, since my version is for objects without constructors). It is faster than yours, because I use 'pop' instead of 'splice' (it looks like you wanted a pop anyway?) and don't use 'length' which is an O(n) operation for arrays, vectors included. Also, don't forget inline signatures. The 'Stack' typedef is simply to define a netural interface for the pool, so that one can swap the type without changing a lot of code.

typedef Stack<T> = flash.Vector<T>;

class Factory<T>
{
    var objects: Stack<T>;
    var cl: Class<T>;

    public function new(cl: Class<T>)
    {
        this.cl = cl;
        objects = new Stack<T>();
    }

    public inline function create()
    {
        var obj = objects.pop();
        if(obj == null) return untyped __new__(cl);
        else return obj;
    }

    public inline function reclaim(obj: T)
    {
        objects.push(obj);
    }
}

This is of course a very rudimentary object factory.

On Mon, Apr 19, 2010 at 20:28, Yanis Benson <[hidden email]> wrote:
Even with flash.geom.Point it's faster to have a pool form my tests. (Of course when you actively delete old points and not just generate and store massive amounts of them.)


On 04/19/2010 10:22 PM, [hidden email] wrote:
Yes you are right about linked list(s). Pushing and popping objects to and from a pool using a Vector is faster than my own linked list implementation (which is marginally faster than haXes own FastList generally because I do fewer runtime checks).

Also, for simple objects and/or objects which have cheap constructors, with Flash Player 10 at least, the runtime  outperforms object pools with its own allocator (i.e. 'new'), which I suspect may be using a pool itself on a much finer granular level.

For more complex classes and subclasses, e.g. Sprite and other runtime API classes, a pool allocator is worth using however, and using a Vector as the object pool itself proves to be the fastest currently.

On Mon, Apr 19, 2010 at 17:51, Mark de Bruijn | Dykam <[hidden email]> wrote:
Yes, but I mean, what are you using for pooling the data? An array, or a list? Afaik, for a linkedlist, the overhead will generally be bigger than the time a simple alloc takes.
--
Mark


On Mon, Apr 19, 2010 at 3:25 PM, [hidden email] <[hidden email]> wrote:
What do you mean by "base datastructure"? Just because it's called a Factory, does not mean it's a building :-) I imagine it would be creating and reusing Node objects. It also goes by the name of "object pool". But a factory is usually more than just an object pool, as the latter is more primitive.

On Mon, Apr 19, 2010 at 14:27, Mark de Bruijn | Dykam <[hidden email]> wrote:
Armencho,what would be the base datastructure be of the factory?
--
Mark


On Mon, Apr 19, 2010 at 11:39 AM, [hidden email] <[hidden email]> wrote:
Yes, if you (Michael) are serious about REALLY optimizing your Node applications, "final" regardless, reuse Node objects in a factory.

2010/4/15 Cauê Waneck <[hidden email]>
Could be because the constructor call is orders of magnitude slower than a field access, so here  n = n.next = new Node(); , the n.next access speed isn't really very significant? I mean, it could be 0, it still wouldn't make much a difference.


2010/4/14 Michael Baczynski <[hidden email]>
On 15.04.2010 00:55, Cauę Waneck wrote:
have you tried to run the test with the release (not debug) version??
of course. when tested in the debug player both versions run slower, but exactly at the same rate.
likewise, both version run a lot faster in the release player, but again no difference.
my simple test case:

//Test
package
{
   import flash.display.Sprite;
   import flash.text.TextField;
   import flash.utils.getTimer;

   public class Test extends Sprite
   {
       public function Test()
       {
           init();
           walk();
       }

       private var _node:Node;

       private function init():void
       {
           _node = new Node();

           var n:Node = _node;
           for (var i:int = 0; i < 1000000; i++)
           {
               n = n.next = new Node();
           }
       }

       private function walk():void
       {
           var ttotal:int = 0;
           for (var i:int = 0; i < 10; i++) //mean over 10 iterations
           {
               var time:int = getTimer();

               var n:Node = _node;
               var x:Number;
               var y:Number;
               while (n)
               {
                   x = n.x;
                   y = n.y;
                   n = n.next;
               }

               ttotal += (getTimer() - time);
           }

           var tf:TextField = new TextField();
           tf.text = ''  + (ttotal / 10);
           addChild(tf);
       }
   }
}

//Node.as

package
{
   public final class Node
   {
       public var next:Node;


       public var x:Number;
       public var y:Number;

       public function Node() {}
   }
}



2010/4/14 Michael Baczynski <[hidden email] <mailto:[hidden email]>>


   hi,

   Ralph Hauwert gave a nice speech today at the FFK in cologne
   showing some of his experiments.
   in one slide he showed that adding the 'final' keyword to a linked
   list node makes iteration much faster.
   however, I wasn't able to reproduce this in as3 - there is
   absolutely no difference at all in runtime performance (win/release).
   maybe someone can confirm this?

   e.g. for a 2d vertex:

   public final class Node
   {
      public var x:Number;
      public var y:Number;
      public var next:Node;

      public function Node() {}
   }

   the same applies to the 'const' keyword in as3..

   best,
   michael

   --     http://www.polygonal.de


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




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


--

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


--

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


--

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


--

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


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



--

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


--
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: as3 final keyword on linked list nodes

Gustavs
In reply to this post by Mark de Bruijn | Dykam

On 19 April 2010 15:27, Mark de Bruijn | Dykam <[hidden email]> wrote:
Armencho,what would be the base datastructure be of the factory?

>.>
A list.

class Test
{
    static function main ()
    {
        var n = 1000000, t = flash.Lib.getTimer;
       
        var pool = null;
        for (x in 0 ... n) pool = new Node (x,pool);
       
        var t1 = t ();
       
        var list = null;
        for (x in 0 ... n)
        {
            var n = pool;
            pool = n.next;
            n.next = list;
            list = n;
        }
       
        var t2 = t ();
       
        trace (t1);
        trace (t2-t1);
    }
}

class Node
{
    public var val  : Int;
    public var next : Node;
   
    public function new (v,n) { val = v; next = n; }
}



I'd certainly like an example where the performance of Flash constructors could be called anything but miserable.



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

Re: as3 final keyword on linked list nodes

Yanis Benson
In reply to this post by Armén
class Pool1<T>{
  var pool:Stack<T>;
  var cl:Class<T>;

  public function new(cl:Class<T>){
    pool = new Stack<T>();
    this.cl = cl;
    }

  public function create(){
    var obj = pool.pop();

    if(obj == null) obj = untyped __new__(cl);
    return obj;
    }

  public function reclaim(obj:T){
    pool.push(obj);
    }
  }

class Pool2<T>{
  var pool:Stack<T>;
  var poollength:Int;
  var cl:Class<T>;

  public function new(cl:Class<T>){
    pool = new Stack<T>();
    this.cl = cl;
    poollength = 0;
    }

  public function create(){
    var obj;
    if(poollength > 0){
      poollength--;
      obj = pool[poollength];
      pool[poollength] = null;
      }
    else{
      obj = untyped __new__(cl);
      }
    return obj;
    }

  public function reclaim(obj:T){
    pool[poollength] = obj;
    poollength++;
    }
  }
For testing functions:

    var pool = new Pool[12](flash.geom.Point);
    var i = it;
    while(i --> 0){
      a = pool.create();
      pool.reclaim(a);
      a = pool.create();
      }

Gives me:
     - typedef Stack<T> = flash.Vector<T> : stable approx 2400 for Pool1 and 1800-2000(always jumping, some strange inner stuff, i think) for Pool2.
     - typedef Stack<T> = Array<T>: stable approx 2200 for Pool1 and stable 1700 for Pool2.
Not so big speedup, but since it's just few more lines of code, it can be helpful.

So, Array is ~10% faster than Vector in this case. Also, assign/null assign way instead of push/pop makes it all ~20% faster.

On 04/19/2010 11:24 PM, [hidden email] wrote:
Here is my version, change it at will (to accept construction parameters, since my version is for objects without constructors). It is faster than yours, because I use 'pop' instead of 'splice' (it looks like you wanted a pop anyway?) and don't use 'length' which is an O(n) operation for arrays, vectors included. Also, don't forget inline signatures. The 'Stack' typedef is simply to define a netural interface for the pool, so that one can swap the type without changing a lot of code.

typedef Stack<T> = flash.Vector<T>;

class Factory<T>
{
    var objects: Stack<T>;
    var cl: Class<T>;

    public function new(cl: Class<T>)
    {
        this.cl = cl;
        objects = new Stack<T>();
    }

    public inline function create()
    {
        var obj = objects.pop();
        if(obj == null) return untyped __new__(cl);
        else return obj;
    }

    public inline function reclaim(obj: T)
    {
        objects.push(obj);
    }
}

This is of course a very rudimentary object factory.


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

Re: as3 final keyword on linked list nodes

Yanis Benson
In reply to this post by Mark de Bruijn | Dykam
It was just stripped example, I normally use assigns.

On 04/19/2010 11:28 PM, Mark de Bruijn | Dykam wrote:
You might... want to use Array.pop() instead of Array.splice(,)[0].
--
Mark


On Mon, Apr 19, 2010 at 8:28 PM, Yanis Benson <[hidden email]> wrote:
Even with flash.geom.Point it's faster to have a pool form my tests. (Of course when you actively delete old points and not just generate and store massive amounts of them.)


On 04/19/2010 10:22 PM, [hidden email] wrote:
Yes you are right about linked list(s). Pushing and popping objects to and from a pool using a Vector is faster than my own linked list implementation (which is marginally faster than haXes own FastList generally because I do fewer runtime checks).

Also, for simple objects and/or objects which have cheap constructors, with Flash Player 10 at least, the runtime  outperforms object pools with its own allocator (i.e. 'new'), which I suspect may be using a pool itself on a much finer granular level.

For more complex classes and subclasses, e.g. Sprite and other runtime API classes, a pool allocator is worth using however, and using a Vector as the object pool itself proves to be the fastest currently.

On Mon, Apr 19, 2010 at 17:51, Mark de Bruijn | Dykam <[hidden email]> wrote:
Yes, but I mean, what are you using for pooling the data? An array, or a list? Afaik, for a linkedlist, the overhead will generally be bigger than the time a simple alloc takes.
--
Mark


On Mon, Apr 19, 2010 at 3:25 PM, [hidden email] <[hidden email]> wrote:
What do you mean by "base datastructure"? Just because it's called a Factory, does not mean it's a building :-) I imagine it would be creating and reusing Node objects. It also goes by the name of "object pool". But a factory is usually more than just an object pool, as the latter is more primitive.

On Mon, Apr 19, 2010 at 14:27, Mark de Bruijn | Dykam <[hidden email]> wrote:
Armencho,what would be the base datastructure be of the factory?
--
Mark


On Mon, Apr 19, 2010 at 11:39 AM, [hidden email] <[hidden email]> wrote:
Yes, if you (Michael) are serious about REALLY optimizing your Node applications, "final" regardless, reuse Node objects in a factory.

2010/4/15 Cauê Waneck <[hidden email]>
Could be because the constructor call is orders of magnitude slower than a field access, so here  n = n.next = new Node(); , the n.next access speed isn't really very significant? I mean, it could be 0, it still wouldn't make much a difference.


2010/4/14 Michael Baczynski <[hidden email]>
On 15.04.2010 00:55, Cauę Waneck wrote:
have you tried to run the test with the release (not debug) version??
of course. when tested in the debug player both versions run slower, but exactly at the same rate.
likewise, both version run a lot faster in the release player, but again no difference.
my simple test case:

//Test
package
{
   import flash.display.Sprite;
   import flash.text.TextField;
   import flash.utils.getTimer;

   public class Test extends Sprite
   {
       public function Test()
       {
           init();
           walk();
       }

       private var _node:Node;

       private function init():void
       {
           _node = new Node();

           var n:Node = _node;
           for (var i:int = 0; i < 1000000; i++)
           {
               n = n.next = new Node();
           }
       }

       private function walk():void
       {
           var ttotal:int = 0;
           for (var i:int = 0; i < 10; i++) //mean over 10 iterations
           {
               var time:int = getTimer();

               var n:Node = _node;
               var x:Number;
               var y:Number;
               while (n)
               {
                   x = n.x;
                   y = n.y;
                   n = n.next;
               }

               ttotal += (getTimer() - time);
           }

           var tf:TextField = new TextField();
           tf.text = ''  + (ttotal / 10);
           addChild(tf);
       }
   }
}

//Node.as

package
{
   public final class Node
   {
       public var next:Node;


       public var x:Number;
       public var y:Number;

       public function Node() {}
   }
}



2010/4/14 Michael Baczynski <[hidden email] <mailto:[hidden email]>>


   hi,

   Ralph Hauwert gave a nice speech today at the FFK in cologne
   showing some of his experiments.
   in one slide he showed that adding the 'final' keyword to a linked
   list node makes iteration much faster.
   however, I wasn't able to reproduce this in as3 - there is
   absolutely no difference at all in runtime performance (win/release).
   maybe someone can confirm this?

   e.g. for a 2d vertex:

   public final class Node
   {
      public var x:Number;
      public var y:Number;
      public var next:Node;

      public function Node() {}
   }

   the same applies to the 'const' keyword in as3..

   best,
   michael

   --     http://www.polygonal.de


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




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


--

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


--

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


--

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


--

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


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



--
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: as3 final keyword on linked list nodes

Yanis Benson
In reply to this post by Armén
Also, according to some more tests, inlining makes push/pop 14% faster, assign/assign null 10% faster.
Making personal factory without generic makes assign/assign null with array and inlining 5% percents faster. Not much gain, but taking into attention the fact you usually want to pass something to created instance(/instance you've got out of pool) and thus will be rewriting code anyway, it makes some sense.

On 04/19/2010 11:24 PM, [hidden email] wrote:
Here is my version, change it at will (to accept construction parameters, since my version is for objects without constructors). It is faster than yours, because I use 'pop' instead of 'splice' (it looks like you wanted a pop anyway?) and don't use 'length' which is an O(n) operation for arrays, vectors included. Also, don't forget inline signatures. The 'Stack' typedef is simply to define a netural interface for the pool, so that one can swap the type without changing a lot of code.

typedef Stack<T> = flash.Vector<T>;

class Factory<T>
{
    var objects: Stack<T>;
    var cl: Class<T>;

    public function new(cl: Class<T>)
    {
        this.cl = cl;
        objects = new Stack<T>();
    }

    public inline function create()
    {
        var obj = objects.pop();
        if(obj == null) return untyped __new__(cl);
        else return obj;
    }

    public inline function reclaim(obj: T)
    {
        objects.push(obj);
    }
}

This is of course a very rudimentary object factory.



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