Tips/help with optimization of some small pieces of code

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

Tips/help with optimization of some small pieces of code

edA-qa mort-ora-y
I have a few places in my code (critical points) which I'd like to know
if there is a faster way to achieve the same effect.  My primary
platform of interest in Flash9, so I'm okay with flash specific
optimizations.

1) Floored division:
  return Math.floor( card / suitSize );
How can I exploit native Integral division to avoid the floor?

2) Sorting by secondary criteria
 someArray.sort( function( a : Int, b : Int ) { return rank( b ) - rank(
a ); } );
Is there a faster way to achieve such sorting?  The lists are usually
only 5-10 items long.

3) maximum value in an array:
        var sc = 0;
        for( c in someArray() )
                if( c > sc )
                        sc = c;
        return sc;


These three things are accounting for about 70% of the time of the code
I'm trying to optimize. I fear I have pushed it nearly to its limit, but
perhaps I'm missing something that would really help.

--
edA-qa mort-ora-y
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

BigTPoker uses haXe and DHLIB
        http://BigTPoker.com/?source=haxe-list

The dis-Emi-A haXe Library
        http://wiki.disemia.com/HaXe
       
A full set of tools, classes, and support facilities aimed at
simplifying and expediting game creation in Flash 9.

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Sign: Please digitally sign your emails.
Encrypt: I'm also happy to receive encrypted mail.


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

signature.asc (260 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Tips/help with optimization of some small pieces of code

Nicolas Cannasse
edA-qa mort-ora-y a écrit :
> I have a few places in my code (critical points) which I'd like to know
> if there is a faster way to achieve the same effect.  My primary
> platform of interest in Flash9, so I'm okay with flash specific
> optimizations.
>
> 1) Floored division:
>   return Math.floor( card / suitSize );
> How can I exploit native Integral division to avoid the floor?

There is no native integral division in flash9.
The fastest is to use Std.int(a/b)

> 2) Sorting by secondary criteria
>  someArray.sort( function( a : Int, b : Int ) { return rank( b ) - rank(
> a ); } );
> Is there a faster way to achieve such sorting?  The lists are usually
> only 5-10 items long.

It should be faster to use a member method (not a static one) instead of
a local method.

> 3) maximum value in an array:
> var sc = 0;
> for( c in someArray() )
> if( c > sc )
> sc = c;
> return sc;

Seems fine.

Nicolas

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

Re: Tips/help with optimization of some small pieces of code

Niel Drummond-3
Nicolas Cannasse wrote:
>> 2) Sorting by secondary criteria
>>  someArray.sort( function( a : Int, b : Int ) { return rank( b ) - rank(
>> a ); } );
>> Is there a faster way to achieve such sorting?  The lists are usually
>> only 5-10 items long.
I've found the native flash sort to be faster than haxe's sort:
#if flash
                untyped someArray.sortOn( "b", Array.NUMERIC |
Array.DESCENDING );
#else

The same goes for point (3).

- Niel

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

Re: Tips/help with optimization of some small pieces of code

gershon
for #1, web says that .5* is faster than /2, and using a suitSize which is a power of 2 bitwise shift might be even faster, card >> suitSize will floor it down
Std.int(5/2) == 5 >> 1 == 0101 >> 1 == 0010 == 2

if 5 were x though, and x be Float, he'd have to be rounded too, haxe does bitwise only on u\ints...

On Thu, Sep 3, 2009 at 10:08 AM, Niel Drummond <[hidden email]> wrote:
Nicolas Cannasse wrote:
2) Sorting by secondary criteria
 someArray.sort( function( a : Int, b : Int ) { return rank( b ) - rank(
a ); } );
Is there a faster way to achieve such sorting?  The lists are usually
only 5-10 items long.
I've found the native flash sort to be faster than haxe's sort:
#if flash
              untyped someArray.sortOn( "b", Array.NUMERIC | Array.DESCENDING );
#else

The same goes for point (3).

- Niel


--
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: Tips/help with optimization of some small pieces of code

Ian Thomas
In reply to this post by edA-qa mort-ora-y
On Thu, Sep 3, 2009 at 7:05 AM, edA-qa mort-ora-y<[hidden email]> wrote:

> 3) maximum value in an array:
>        var sc = 0;
>        for( c in someArray() )
>                if( c > sc )
>                        sc = c;
>        return sc;

I don't know what the array is - but if you only _insert_ into the
array (rather than delete or change), you could make this faster by
updating the maximum value every time you do the insert rather than
when you need to calculate the maximum.

HTH,
   Ian

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

Re: Tips/help with optimization of some small pieces of code

Ian Thomas
Alternatively you could maintain it as a sorted array. That means a
big hit when you insert, but very very fast to pull out the maximum.
Depends where you want the processing to happen!

HTH,
   Ian

On Thu, Sep 3, 2009 at 9:11 AM, Ian Thomas<[hidden email]> wrote:

> On Thu, Sep 3, 2009 at 7:05 AM, edA-qa mort-ora-y<[hidden email]> wrote:
>
>> 3) maximum value in an array:
>>        var sc = 0;
>>        for( c in someArray() )
>>                if( c > sc )
>>                        sc = c;
>>        return sc;
>
> I don't know what the array is - but if you only _insert_ into the
> array (rather than delete or change), you could make this faster by
> updating the maximum value every time you do the insert rather than
> when you need to calculate the maximum.
>
> HTH,
>   Ian
>

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

Re: Tips/help with optimization of some small pieces of code

James W. Hofmann
In reply to this post by edA-qa mort-ora-y
> 2) Sorting by secondary criteria
>  someArray.sort( function( a : Int, b : Int ) { return rank( b ) - rank(
> a ); } );
> Is there a faster way to achieve such sorting?  The lists are usually
> only 5-10 items long.
>
> 3) maximum value in an array:
> var sc = 0;
> for( c in someArray() )
> if( c > sc )
> sc = c;
> return sc;

For 2 and 3, have you considered testing different sequence types for  
different purposes, e.g. List/FastList/ByteArray? Although, to make  
effective use of them, you might have to split up the data structure  
so that it can be accessed in the optimal ways at all times, and with  
those kinds of changes come tradeoffs, so it's no longer a clear  
performance win.

ByteArray would basically be my last resort: writing a custom data  
structure from scratch. This would give you lots of control to write  
an optimal data structure, but it could get painful very fast.


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

Re: Tips/help with optimization of some small pieces of code

Gamehaxe
In reply to this post by edA-qa mort-ora-y
You could try:

   var look_up_table = Vector<int>()

   return look_up_table[card]

   Maybe even fast-mem-access.

Hugh

> 1) Floored division:
>   return Math.floor( card / suitSize );
> How can I exploit native Integral division to avoid the floor?



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

Re: Tips/help with optimization of some small pieces of code

Adrian Veith
In reply to this post by edA-qa mort-ora-y
for 2 and 3:

don't use Arrays but a Binary Search Tree (if the data comes reasonable
random). In the worst case (ascending or descending data) its as quick
as a linear list.



edA-qa mort-ora-y schrieb:

> I have a few places in my code (critical points) which I'd like to know
> if there is a faster way to achieve the same effect.  My primary
> platform of interest in Flash9, so I'm okay with flash specific
> optimizations.
>
> 1) Floored division:
>   return Math.floor( card / suitSize );
> How can I exploit native Integral division to avoid the floor?
>
> 2) Sorting by secondary criteria
>  someArray.sort( function( a : Int, b : Int ) { return rank( b ) - rank(
> a ); } );
> Is there a faster way to achieve such sorting?  The lists are usually
> only 5-10 items long.
>
> 3) maximum value in an array:
> var sc = 0;
> for( c in someArray() )
> if( c > sc )
> sc = c;
> return sc;
>
>
> These three things are accounting for about 70% of the time of the code
> I'm trying to optimize. I fear I have pushed it nearly to its limit, but
> perhaps I'm missing something that would really help.
>
>  

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

Re: Tips/help with optimization of some small pieces of code

Owen Durni-2
This would be highly dependent on what your data is like for (2), but
you could try non-comparison methods of sorting, especially if the
range of possible inputs is indeed only the rank of a card.

Counting sort or bucket sort should work nicely.

For 3, people have suggested a binary tree to find the max, but I
believe that maintaining a max-heap would be faster than maintaining a
BST (less strict ordering requirements). I think the average case
insert for a heap is something like 2.6 percolations (as opposed to
log(n) for a tree).

--Owen

On Thu, Sep 3, 2009 at 6:24 AM, Adrian Veith<[hidden email]> wrote:

> for 2 and 3:
>
> don't use Arrays but a Binary Search Tree (if the data comes reasonable
> random). In the worst case (ascending or descending data) its as quick
> as a linear list.
>
>
>
> edA-qa mort-ora-y schrieb:
>> I have a few places in my code (critical points) which I'd like to know
>> if there is a faster way to achieve the same effect.  My primary
>> platform of interest in Flash9, so I'm okay with flash specific
>> optimizations.
>>
>> 1) Floored division:
>>   return Math.floor( card / suitSize );
>> How can I exploit native Integral division to avoid the floor?
>>
>> 2) Sorting by secondary criteria
>>  someArray.sort( function( a : Int, b : Int ) { return rank( b ) - rank(
>> a ); } );
>> Is there a faster way to achieve such sorting?  The lists are usually
>> only 5-10 items long.
>>
>> 3) maximum value in an array:
>>       var sc = 0;
>>       for( c in someArray() )
>>               if( c > sc )
>>                       sc = c;
>>       return sc;
>>
>>
>> These three things are accounting for about 70% of the time of the code
>> I'm trying to optimize. I fear I have pushed it nearly to its limit, but
>> perhaps I'm missing something that would really help.
>>
>>
>
> --
> 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: Tips/help with optimization of some small pieces of code

Ron Wheeler
I would also suggest that you make sure that your design is very object
oriented.
Optimization get easy to do if you only have to change one place.

I would also suggest adding some counts to see what the ratio of the
different operations is.
As has been hinted earlier, structures that are fast to read are often
slow to update and vice versa.

Ron

Owen Durni wrote:

> This would be highly dependent on what your data is like for (2), but
> you could try non-comparison methods of sorting, especially if the
> range of possible inputs is indeed only the rank of a card.
>
> Counting sort or bucket sort should work nicely.
>
> For 3, people have suggested a binary tree to find the max, but I
> believe that maintaining a max-heap would be faster than maintaining a
> BST (less strict ordering requirements). I think the average case
> insert for a heap is something like 2.6 percolations (as opposed to
> log(n) for a tree).
>
> --Owen
>
> On Thu, Sep 3, 2009 at 6:24 AM, Adrian Veith<[hidden email]> wrote:
>  
>> for 2 and 3:
>>
>> don't use Arrays but a Binary Search Tree (if the data comes reasonable
>> random). In the worst case (ascending or descending data) its as quick
>> as a linear list.
>>
>>
>>
>> edA-qa mort-ora-y schrieb:
>>    
>>> I have a few places in my code (critical points) which I'd like to know
>>> if there is a faster way to achieve the same effect.  My primary
>>> platform of interest in Flash9, so I'm okay with flash specific
>>> optimizations.
>>>
>>> 1) Floored division:
>>>   return Math.floor( card / suitSize );
>>> How can I exploit native Integral division to avoid the floor?
>>>
>>> 2) Sorting by secondary criteria
>>>  someArray.sort( function( a : Int, b : Int ) { return rank( b ) - rank(
>>> a ); } );
>>> Is there a faster way to achieve such sorting?  The lists are usually
>>> only 5-10 items long.
>>>
>>> 3) maximum value in an array:
>>>       var sc = 0;
>>>       for( c in someArray() )
>>>               if( c > sc )
>>>                       sc = c;
>>>       return sc;
>>>
>>>
>>> These three things are accounting for about 70% of the time of the code
>>> I'm trying to optimize. I fear I have pushed it nearly to its limit, but
>>> perhaps I'm missing something that would really help.
>>>
>>>
>>>      
>> --
>> 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: Tips/help with optimization of some small pieces of code

edA-qa mort-ora-y
In reply to this post by Nicolas Cannasse
Nicolas Cannasse wrote:
> The fastest is to use Std.int(a/b)
> It should be faster to use a member method (not a static one) instead of
> a local method.

I recall that at one point such optimizations made a large difference,
but this time I'm actually not seeing much a difference doing such changes.

Perhaps I'm just squeezing dry lemons at this point. I guess most of my
time is now spent in tight for-loops rather than in function or
accessing overhead.

I guess I've hit the limit then, on my system neko/flash can evaluate
about 7,000 2-player games of hold'em in one second -- barring writing
the algorithm specifically for hold'em that is.

Now I have to figure out why if I do this in a timer loop it drops to
about 1000 (flash is weird).

--
edA-qa mort-ora-y
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

BigTPoker uses haXe and DHLIB
        http://BigTPoker.com/?source=haxe-list

The dis-Emi-A haXe Library
        http://wiki.disemia.com/HaXe
       
A full set of tools, classes, and support facilities aimed at
simplifying and expediting game creation in Flash 9.

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Sign: Please digitally sign your emails.
Encrypt: I'm also happy to receive encrypted mail.


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

signature.asc (260 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Tips/help with optimization of some small pieces of code

Hudson Ansley
In reply to this post by edA-qa mort-ora-y
On Thu, Sep 3, 2009 at 2:05 AM, edA-qa mort-ora-y<[hidden email]> wrote:
> 1) Floored division:
>  return Math.floor( card / suitSize );
> How can I exploit native Integral division to avoid the floor?
>
exploit your knowledge of the system. You know there are always 4
suits, and for card games that is not likely to ever change, so if you
construct your card integer so the suit is represented in the 2 least
significant digits, you can separate suit from the rank with fast bit
operations

suit from card:
return card & 3;

rank from card:
return card >> 2;

of course the objection to this is that you have hard-coded the size
of the suit into the logic, but in the case where you know some value
will never change (like the number of suits in a deck of cards) seems
like it is not really a problem. Also, you can of course hide this
implementation without penalty with HaXe, which is one reason I love
inline...

Regards,
Hudson

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

Re: Tips/help with optimization of some small pieces of code

edA-qa mort-ora-y
Hudson Ansley wrote:
> like it is not really a problem. Also, you can of course hide this
> implementation without penalty with HaXe, which is one reason I love
> inline...

This logic is hidden and I could change it, but it appears from testing
it isn't making a large different. I can also only go so far in this
direction since there are special cards in the deck which don't have
suits, or represent any suit. Also ace can be high or low depending on
the deck/game.  I'm trying to keep it all abstract for now -- meaning
likely I've hit a limit to the optimizations.

--
edA-qa mort-ora-y
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

BigTPoker uses haXe and DHLIB
        http://BigTPoker.com/?source=haxe-list

The dis-Emi-A haXe Library
        http://wiki.disemia.com/HaXe
       
A full set of tools, classes, and support facilities aimed at
simplifying and expediting game creation in Flash 9.

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Sign: Please digitally sign your emails.
Encrypt: I'm also happy to receive encrypted mail.


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

signature.asc (260 bytes) Download Attachment