Pool

12-06-2009, 06:04 PM

Pool Library

Background:
This is a library of code that gives you access to the pool data structure for integers. This finds the most use in maps where you want random numbers to be weighted so that certain outcomes are more probable than others.

Requirements:

(None)

Code:

Library:

library Pool
//******************************************************************************
//* BY: Rising_Dusk
//* 
//* This script gives the user access to general integer pools. A pool is a data
//* structure that allows you to give entries to it a weight. This weight
//* essentially scales how likely certain random accesses to the pool will be
//* returned by the internal .getRandomInt method. Pools can be useful in any
//* number of ways, such as item drops, randomizing enemy encounters, randomly
//* selecting rects weighted by area, and so forth.
//* 
//******************************************************************************
//* 
//* Example usage:
//*    local intpool ip = intpool.create()
//*    call ip.addInt(1, 1.0)
//*    call ip.addInt(2, 0.5)
//*    call ip.getRandomInt()
//*    call ip.getChance(2)
//*    call ip.getWeight(2)
//*    call ip.removeInt(1)
//* 
//* You will first need to create an intpool as shown above. Once you've done
//* that, you may use the .addInt method to add an entry to the pool with a
//* specific weight. The example above adds 2 integers, one twice as likely to
//* be randomly selected as the other. That means for the above example, the
//* .getRandomInt method will 66% of the time return 1 and 33% of the time
//* return 2. If you want to remove an entry from an intpool, the .removeInt
//* method is what you will want to use. If you would like to update an entry's
//* weight after already adding it, simply use .addInt again with the new
//* weight.
//* 
//* The .getChance and .getWeight methods are there for convenience. If you are
//* interested in the exact chance of the intpool returning a specific entry,
//* then you should use .getChance to obtain the decimal chance out of 1. If you
//* want to know the weight input for a specific entry, .getWeight will return
//* that for you.
//* 
//* When adding an entry to the intpool with .addInt, the actual magnitude of
//* the weight doesn't matter. What matters is its magnitude relative to the
//* magnitudes of all other entries in the intpool. This means that it is ok to
//* use very large or very small weights and is done at the user's discretion.
//* 
//* It is worth noting that if you use .getRandomInt on an intpool with no
//* entries, the function will return INTPOOL_NO_ENTRIES, which is about as
//* random an integer as possible so as to avoid people accidentally using it.
//* 
globals
    //These constants can be changed
    private constant integer MAX_INSTANCES         = 8191
    private constant integer MAX_ENTRIES           = 256
            constant integer INTPOOL_NO_ENTRIES    = 0x672819
            
    //Don't change the following global declaration
    private hashtable ht = InitHashtable()
endglobals

struct intpool[MAX_INSTANCES]
    private integer Cnt         = 0
    private real    WeightTotal = 0.
    private integer array Entries[MAX_ENTRIES]
    private real    array Weights[MAX_ENTRIES]
    
    method getWeight takes integer entry returns real
        return Weights[LoadInteger(ht, integer(this), entry)]
    endmethod
    method getChance takes integer entry returns real
        if WeightTotal > 0. then
            return Weights[LoadInteger(ht, integer(this), entry)]/WeightTotal
        endif
        return 0.
    endmethod
    method addInt takes integer entry, real weight returns nothing
        local integer in = 0
        if .Cnt == MAX_ENTRIES then
            //Can't hold any more entries
            debug call BJDebugMsg(SCOPE_PREFIX+"Error: .addEntry has reached MAX_ENTRIES")
            return
        elseif weight <= 0. then
            //Zero or negative weights make no sense
            debug call BJDebugMsg(SCOPE_PREFIX+"Error: .addEntry can't take zero or negative weights")
            return
        endif
        set in = LoadInteger(ht, integer(this), entry)
        if in > 0 then
            //Update old entry
            set .WeightTotal = .WeightTotal - .Weights[in] + weight
            set .Weights[in] = weight
        else
            //Make a new entry
            set .Cnt           = .Cnt + 1
            call SaveInteger(ht, integer(this), entry, .Cnt)
            set .Entries[.Cnt] = entry
            set .Weights[.Cnt] = weight
            set .WeightTotal   = .WeightTotal + weight
        endif
    endmethod
    method removeInt takes integer entry returns nothing
        local integer in = LoadInteger(ht, integer(this), entry)
        if in > 0 then
            call RemoveSavedInteger(ht, integer(this), entry)
            //Remove its entry in the arrays
            set .WeightTotal = .WeightTotal - .Weights[in]
            set .Entries[in] = .Entries[.Cnt]
            set .Weights[in] = .Weights[.Cnt]
            set .Cnt         = .Cnt - 1
        debug else
            debug call BJDebugMsg(SCOPE_PREFIX+"Error: .removeEntry entry doesn't exist")
        endif
    endmethod
    method getRandomInt takes nothing returns integer
        local real    r = GetRandomReal(0, .WeightTotal)
        local integer c = 0
        if .WeightTotal <= 0. then
            debug call BJDebugMsg(SCOPE_PREFIX+"Error: intpool has no entries")
            return INTPOOL_NO_ENTRIES
        endif
        loop
            set r = r - .Weights[c]
            exitwhen r <= 0
            set c = c + 1
        endloop
        return .Entries[c]
    endmethod
endstruct
endlibrary

Function List:
This library provides the following datatype to the user that can be used as shown.

JASS:

function Example takes nothing returns nothing
    local intpool ip = intpool.create()
    call ip.addInt(1, 1.0) //Adds 1 as an integer entry with weight 1.0
    call ip.addInt(2, 0.5) //Adds 2 as an integer entry with weight 0.5
    call ip.getRandomInt() //Gets a random entry
    call ip.getChance(2)   //Returns the chance for a specific entry to be selected
    call ip.getWeight(2)   //Returns the weight for a specific entry
    call ip.removeInt(1)   //Removes integer entry 1
endfunction

I submitted this mostly because the approach used in this library is relatively slow, requires a library when it doesn't need to, and one version of it doesn't compile. This library matches the functionality of that one, is O(1) in create/destroy versus O(n) in that one's destroy, and doesn't have the library requirement of LinkedLists. Furthermore, I find that stringpools and handlepools are useless, as you can just use an intpool with entries that are array indexes for any other type. Poot helped me with the framework of this and I finished it up for release. Hopefully someone else finds it as useful as I do.

Enjoy!

12-06-2009, 08:36 PM	#2
Gamat	What about a CountItemsInPool?

12-06-2009, 08:45 PM	#3
Rising_Dusk	Pool != Stack != List. There is no use for counting items in a pool, because you would not use a pool if you needed to count things in it.

12-06-2009, 09:03 PM

Gamat

A pool is like a group, maybe the group/pool is empty, and it is good to know that in some cases.

Hidden information:

12-06-2009, 09:14 PM	#5
Rising_Dusk	If it is empty, then .getRandomInt will return INTPOOL_NO_ENTRIES. Anyways, a pool is not like a group, you do not do actions upon the entire pool. You get random entries from the group, that's all you'll do with it.

12-07-2009, 02:33 AM

Rising_Dusk

I did some benchmark's of Pyro's Pools versus my Pool in this thread. I came up with the following results @ 1250 iterations. It's worth noting that I had to use only 1250 iterations because Pyro's Pools crashed the thread at 1500+.

Click image for larger version

Name: Benchmark.JPG
Views: 33
Size: 14.8 KB
ID: 46846

Create:

Dusk's	0.016
Pyro's	0.052

Add:

Dusk's	0.025
Pyro's	0.151

Remove:

Dusk's	0.027
Pyro's	0.133

Destroy:

Dusk's	0.009
Pyro's	0.049

Using the following code:

JASS:

scope Bench initializer Init
globals
    private constant integer ITERATIONS = 1250
    private intpool array IP
    private Pool    array PO
endglobals

private function Test4_1 takes nothing returns nothing
    local real    r1 = 0.
    local real    r2 = 0.
    local integer i  = 0
    local integer sw = StopWatchCreate()
    //DESTROY
    set i  = 0
    set r1 = StopWatchMark(sw)
    loop
        exitwhen i == ITERATIONS
        call IP[i].destroy()
        set i = i + 1
    endloop
    set r2 = StopWatchMark(sw)
    call BJDebugMsg("intpool Destroy: "+R2S(r2-r1))
    call StopWatchDestroy(sw)
endfunction
private function Test4_2 takes nothing returns nothing
    local real    r1 = 0.
    local real    r2 = 0.
    local integer i  = 0
    local integer sw = StopWatchCreate()
    //DESTROY
    set i  = 0
    set r1 = StopWatchMark(sw)
    loop
        exitwhen i == ITERATIONS
        call PO[i].destroy()
        set i = i + 1
    endloop
    set r2 = StopWatchMark(sw)
    call BJDebugMsg("Pool Destroy: "+R2S(r2-r1))
    call StopWatchDestroy(sw)
endfunction
private function Callback4 takes nothing returns nothing
    call ExecuteFunc(SCOPE_PRIVATE+"Test4_1")
    call ExecuteFunc(SCOPE_PRIVATE+"Test4_2")
endfunction

private function Test3_1 takes nothing returns nothing
    local real    r1 = 0.
    local real    r2 = 0.
    local integer i  = 0
    local integer sw = StopWatchCreate()
    //REMOVE
    set i  = 0
    set r1 = StopWatchMark(sw)
    loop
        exitwhen i == ITERATIONS
        call IP[i].removeInt(i)
        set i = i + 1
    endloop
    set r2 = StopWatchMark(sw)
    call BJDebugMsg("intpool Remove: "+R2S(r2-r1))
    call StopWatchDestroy(sw)
endfunction
private function Test3_2 takes nothing returns nothing
    local real    r1 = 0.
    local real    r2 = 0.
    local integer i  = 0
    local integer sw = StopWatchCreate()
    //REMOVE
    set i  = 0
    set r1 = StopWatchMark(sw)
    loop
        exitwhen i == ITERATIONS
        call PO[i].SetWeight(i, 0.0, true)
        set i = i + 1
    endloop
    set r2 = StopWatchMark(sw)
    call BJDebugMsg("Pool Remove: "+R2S(r2-r1))
    call StopWatchDestroy(sw)
endfunction
private function Callback3 takes nothing returns nothing
    call ExecuteFunc(SCOPE_PRIVATE+"Test3_1")
    call ExecuteFunc(SCOPE_PRIVATE+"Test3_2")
endfunction

private function Test2_1 takes nothing returns nothing
    local real    r1 = 0.
    local real    r2 = 0.
    local integer i  = 0
    local integer sw = StopWatchCreate()
    //ADD
    set i  = 0
    set r1 = StopWatchMark(sw)
    loop
        exitwhen i == ITERATIONS
        call IP[i].addInt(i, 1.0)
        set i = i + 1
    endloop
    set r2 = StopWatchMark(sw)
    call BJDebugMsg("intpool Add: "+R2S(r2-r1))
    call StopWatchDestroy(sw)
endfunction
private function Test2_2 takes nothing returns nothing
    local real    r1 = 0.
    local real    r2 = 0.
    local integer i  = 0
    local integer sw = StopWatchCreate()
    //ADD
    set i  = 0
    set r1 = StopWatchMark(sw)
    loop
        exitwhen i == ITERATIONS
        call PO[i].SetWeight(i, 1.0, true)
        set i = i + 1
    endloop
    set r2 = StopWatchMark(sw)
    call BJDebugMsg("Pool Add: "+R2S(r2-r1))
    call StopWatchDestroy(sw)
endfunction
private function Callback2 takes nothing returns nothing
    call ExecuteFunc(SCOPE_PRIVATE+"Test2_1")
    call ExecuteFunc(SCOPE_PRIVATE+"Test2_2")
endfunction

private function Test1_1 takes nothing returns nothing
    local real    r1 = 0.
    local real    r2 = 0.
    local integer i  = 0
    local integer sw = StopWatchCreate()
    //CREATE
    set i  = 0
    set r1 = StopWatchMark(sw)
    loop
        exitwhen i == ITERATIONS
        set IP[i] = intpool.create()
        set i = i + 1
    endloop
    set r2 = StopWatchMark(sw)
    call BJDebugMsg("intpool Create: "+R2S(r2-r1))
    call StopWatchDestroy(sw)
endfunction
private function Test1_2 takes nothing returns nothing
    local real    r1 = 0.
    local real    r2 = 0.
    local integer i  = 0
    local integer sw = StopWatchCreate()
    //CREATE
    set i  = 0
    set r1 = StopWatchMark(sw)
    loop
        exitwhen i == ITERATIONS
        set PO[i] = Pool.create()
        set i = i + 1
    endloop
    set r2 = StopWatchMark(sw)
    call BJDebugMsg("Pool Create: "+R2S(r2-r1))
    call StopWatchDestroy(sw)
endfunction
private function Callback1 takes nothing returns nothing
    call ExecuteFunc(SCOPE_PRIVATE+"Test1_1")
    call ExecuteFunc(SCOPE_PRIVATE+"Test1_2")
endfunction

private function Init takes nothing returns nothing
    call TimerStart(CreateTimer(), 5., false, function Callback1)
    call TimerStart(CreateTimer(), 10., false, function Callback2)
    call TimerStart(CreateTimer(), 15., false, function Callback3)
    call TimerStart(CreateTimer(), 20., false, function Callback4)
endfunction
endscope

In the following testmap:
TEST.w3x

Attached Images

Benchmark.JPG (14.8 KB)

Attached Files

TEST.w3x (59.8 KB)

12-07-2009, 02:34 AM

weaaddar

First, your variable names are terrible. o,r,c are not very meaningful.

second, I'm convinced that wrapping an itempool or a unitpool would be faster because a lot more of the code will happen in native space then slow jass function land. The function interface becomes a little uglier but this will probably be more performant.

Doing something like::

Zinc:

//! zinc
library Pool
{
    //These constants can be changed
    constant real MaxX = GetRectMaxX(bj_mapInitialPlayableArea);
    constant real MaxY = GetRectMaxY(bj_mapInitialPlayableArea);
    hashtable ht = InitHashtable();
    //Don't change the following global declaration
    
    

    struct intpool
    {
        itempool m_pool;
        method addInt(integer entry,integer itemId,real weight)
        {
            SaveInteger(ht,this,itemId,entry);
            ItemPoolAddItemType(m_pool,itemId,weight);
        }

        method removeInt(integer itemId)
        {
            ItemPoolRemoveItemType(m_pool,itemId); // who cares if it fails! And if you override it great. The leak is barely there.
            debug if(!HaveSavedInteger(ht,this,itemId)){ debug BJDebugMsg("Item not part of pool!");}
        }
        method getRandomInt()->integer
        {
            item it = PlaceRandomItem(m_pool,MaxX,MaxY);
            integer retVal = LoadInteger(ht,this,GetItemTypeId(it));
            RemoveItem(it);
            return retVal;
        }
        
        method onDestroy()
        {
            DestroyItemPool(m_pool);
            FlushChildHashtable(ht,this);
        }
        static method create()->thistype
        {
            thistype ret = thistype.allocate();
            ret.m_pool = CreateItemPool();
            return ret;
        }
    }
}
//! endzinc

Now if you provide a stack of some of the hundreds of regular item types you can use this faster moving pool. Sure you can't get the wieght after you added the thing, but who cares?

12-07-2009, 02:53 AM

Rising_Dusk

I was going to do the benchmarks, but yours won't compile in the testmap I provided above in place of my library. I also find it very lame that the user must provide as many valid item ids to addInt as they do entries. Lastly, I am not exactly sure that it would be faster. Once you factor in the stack handling for the item ids and the fact that you're actually creating a handle and doing that is slow, it may be just as fast as mine if not a bit slower.

12-07-2009, 04:13 AM

weaaddar

you probably have to rename the library, and I tested it compiled and spewed results but not much else. Are you using the latest Jasshelper?

I agree completely it would suck to have to provide itemtypes. But if the users have a small set, and I imagine the pool is relatively static, you can probably get away with it pretty handily.

Creating a handle is probably going to be faster then getting a random number, and suffering that nasty o(n) int fetch.

12-07-2009, 04:27 AM

#10

Rising_Dusk

It compiles, but you didn't make your struct public so it didn't work in my benchmarking map. That's what the problem was. Anyways, for purposes of benchmarking, I need something like 1000 unique item id's.

If I'm particularly motivated, I will use GMSI to pull all item ids from standard WC3 and benchmark with them. Until such time as that benchmark can be done, can't really say which would be better. Gotta say, though, definitely need to abstract the stack of item ids away from the user. The user really shouldn't have to deal with that on their own.

12-07-2009, 04:59 AM	#11
weaaddar	Yeah, can you try a simple exampler, just to test fetch speed which should be the slowest fetcher? Try adding 5 things to each pool and just ask for a result like a couple thousand times see which is better. If the native creating and removing is really that costly then I'll concede my request.

12-07-2009, 12:44 PM

#12

Rising_Dusk

That wouldn't be too tough if I test just the get. I'll do so.

EDIT:
Just tested the getRandomInt for both systems @ 1250 iterations apiece to the following results:

Using the attached testmap and following code:

JASS:

scope Bench initializer Init
globals
    private constant integer ITERATIONS = 1250
endglobals

private function Test4_1 takes nothing returns nothing
    local real    r1 = 0.
    local real    r2 = 0.
    local integer i  = 0
    local integer sw = StopWatchCreate()
    local intpool ip = intpool.create()
    call ip.addInt(1, 1.0)
    //GET
    set i  = 0
    set r1 = StopWatchMark(sw)
    loop
        exitwhen i == ITERATIONS
        call ip.getRandomInt()
        set i = i + 1
    endloop
    set r2 = StopWatchMark(sw)
    call BJDebugMsg("dusk get: "+R2S(r2-r1))
    call StopWatchDestroy(sw)
endfunction
private function Test4_2 takes nothing returns nothing
    local real    r1 = 0.
    local real    r2 = 0.
    local integer i  = 0
    local integer sw = StopWatchCreate()
    local Intpool IP = Intpool.create()
    call IP.addInt(1, 'crys', 1.0)
    //GET
    set i  = 0
    set r1 = StopWatchMark(sw)
    loop
        exitwhen i == ITERATIONS
        call IP.getRandomInt()
        set i = i + 1
    endloop
    set r2 = StopWatchMark(sw)
    call BJDebugMsg("weaadd get: "+R2S(r2-r1))
    call StopWatchDestroy(sw)
endfunction
private function Callback4 takes nothing returns nothing
    call ExecuteFunc(SCOPE_PRIVATE+"Test4_1")
    call ExecuteFunc(SCOPE_PRIVATE+"Test4_2")
endfunction

private function Init takes nothing returns nothing
    call TimerStart(CreateTimer(), 5., false, function Callback4)
endfunction
endscope

It would appear that handle creation is slow enough to make mine faster to use by a factor of nearly 10.

Attached Images

Bench.JPG (4.3 KB)

Attached Files

TEST.w3x (54.3 KB)

12-08-2009, 05:54 AM	#13
Rising_Dusk	I wanted to test a more extreme case for my library and see how well it performed. That last test was with only 1 entry in my intpool, so it might not be that representative. The test in this post was made with 50 entries in my pool, which is a lot for any pool. It still outperformed the itempool method you proposed, Weadd. See below: This was at 250 executions.

12-08-2009, 06:10 AM	#14
Pyrogasm	Saying that my library doesn't even compile is not entirely true. It does compile, but the version I wrote that was supposed to use Stack doesn't, and rightly so because I never syntax checked it.

12-08-2009, 06:43 AM	#15
Rising_Dusk	Sorry, I fixed that.