Those gamecache,global array and location-list hybrid CSTriples are

07-09-2006, 04:45 AM

As a continuation to http://www.wc3campaigns.net/showthread.php?t=85001 .

I should say it again, despite all the good things one can say about locations I still hate them for being real based and causing all those unexpected problems you with return bug besides of only taking 2 values.

I figured out the original attempt to make the Triples system had some flaws, it used gamecache for the index recycling and also had a bunch of extra function calls just for the handling of the array indexes out of 8192.

I remade the system. Got rid of extra function calls, and now use a location stack to save the free indexes. The time of the stack test went down to 5.06 seconds (used to take 9.46 seconds).

This is a huge improvement and in my opinion it is enough to kick locations' ass. That was my conclusion but everyone should have his own one, here are the facts.

Facts

I used always a bunch of stack usage for the test, it pushed 100 elements to a stack, then iterate the list to get the sum, and then pop the 100 elements out of the stack and it did that operation 500 times.
When you use locations directly in the stack usage it takes 3.03 seconds.
The first version of the triples took 9.46 seconds (that's overwhelming)
A pure table (gamecache) based version takes like 27 seconds (pwned)
Since triples store 3 values, I had to test locations in a way that stores 3 values per objects, You can see those triple functions in the thread up there. In this case the test takes 9.84 seconds. This is virtually a tie with the first version of the array-based triples.
After the optimizations, the stack test took 5.06 seconds.
If you trash the checks to use gamecache when the index is larger than 8192 instead of arrays. (And add a risk of malfunctioning if you use a lot of triples in the map) The test takes 4.37 seconds (so the difference is so small that is not worth the risk)

This is the code of the current Triples implementation:

JASS:

//5.53 s ! (with array func)
//5.06
//4.37     (direct array access)

function CS_i2r takes integer i returns real
    return i
    return 0.
endfunction

function CS_h2r takes handle h returns real
    return h
    return 0.
endfunction

function CS_r2i takes real r returns integer
    return r
    return 0
endfunction

function CS_lx takes location l returns location
    set udg_csint=CS_r2i(GetLocationX(l))
    return udg_csint
    return null
endfunction

function CS_ly takes location l returns location
    set udg_csint=CS_r2i(GetLocationY(l))
    return udg_csint
    return null
endfunction


function CS_i2l takes integer l returns location
    return l
    return null
endfunction


//=============================================================================================
// Triples
//
function NewTripleIndex takes nothing returns integer
 local integer i
 local location loc
    if (udg_csfreetriples!=null) then
        set loc=udg_csfreetriples
        set udg_csfreetriples=CS_ly(udg_csfreetriples)
        set i=CS_r2i(GetLocationX(loc))
        call RemoveLocation(loc)
        set loc=null
    else
        set i=udg_cstripledata1[0]
        set udg_cstripledata1[0]=i+3
        set i=i+1
    endif
 return i
endfunction



function NewTriple takes nothing returns integer
 local integer i=NewTripleIndex()
    //We don't want the user to crash threads, do we?
    if (i<JASS_MAX_ARRAY_SIZE) then
        set udg_cstripledata1[i]=0
        set udg_cstripledata1[i+1]=0
        set udg_cstripledata1[i+2]=0
    else //2 index spaces in the array are wasted in the name of speed
        call StoreInteger(CSCache(),"tripledata",I2S(i),0)
        call StoreInteger(CSCache(),"tripledata",I2S(i+1),0)
        call StoreInteger(CSCache(),"tripledata",I2S(i+2),0)
    endif

 return i
endfunction

function NewTripleFromValues takes integer a, integer b, integer c returns integer
 local integer i=NewTripleIndex()
    if (i<JASS_MAX_ARRAY_SIZE) then
        set udg_cstripledata1[i]=a
        set udg_cstripledata1[i+1]=b
        set udg_cstripledata1[i+2]=c
    else //2 index spaces in the array are wasted in the name of speed
        call StoreInteger(CSCache(),"tripledata",I2S(i),a)
        call StoreInteger(CSCache(),"tripledata",I2S(i+1),b)
        call StoreInteger(CSCache(),"tripledata",I2S(i+2),c)
    endif

 return i
endfunction


function DestroyTriple takes integer triple returns nothing

// Just move the id of triple to the recycle bin. In case the triple has been using the gamecache space clean it.
   if (triple>=JASS_MAX_ARRAY_SIZE) then
       call FlushStoredInteger(CSCache(),"tripledata",I2S(triple))
       call FlushStoredInteger(CSCache(),"tripledata",I2S(triple+1))
       call FlushStoredInteger(CSCache(),"tripledata",I2S(triple+2))
   endif
   
   //Move it to the stack (should this be a queue instead?)
   if (udg_csfreetriples==null) then
       set udg_csfreetriples=Location(CS_i2r(triple),CS_h2r(null))
   else
       set udg_csfreetriples=Location(CS_i2r(triple),CS_h2r(udg_csfreetriples))
   endif

   
endfunction

function SetTripleInt takes integer triple, integer index, integer val returns nothing
// Should I sacrifice speed for encapsullation? Let them use big index values and touch other memory sections, I don't care.
// This function expects index to be in the range [0,2]

    if (triple>=JASS_MAX_ARRAY_SIZE) then
        call StoreInteger(CSCache(),"tripledata",I2S(triple+index),val)
    else
        set udg_cstripledata1[triple+index]=val
    endif
endfunction

function GetTripleInt takes integer triple, integer index returns integer
// Should I sacrifice speed for encapsullation? Let them use big index values and touch other memory sections, I don't care.
// This function expects index to be in the range [0,2]
    if (triple>=JASS_MAX_ARRAY_SIZE) then
        return GetStoredInteger(CSCache(),"tripledata",I2S(triple+index))
    endif
 return udg_cstripledata1[triple+index]
endfunction

I need people to suggest improvements (if they agree with the idea and want to help it improve) or bash the idea completelly if they are against it.

What I can say about these Triples:
- They are like 5x faster than gamecache
- They are 2x slower than locations
- They are 2x faster than locations adapted to have 3 values
- In case you got more than 2730 triples active in the game the system will become much slower because it will use gamecache (only for triples that have indexes above 8192)
- Anyone can think about a situation where a map can use more than 2730 of them? If so I can make it so it can use another array so the thing is increased to 5460 triples before slowing down.
- In case having 4 values seems better for a general solution tell me. although 4 will reduce the max-before-using-gamecache too.

Aren't 2 values enough?
Yes, and no. 2 values mean single linked lists. 3 values mean double linked lists, binary trees and single linked lists of pairs.

Edit: I am sure the thread's title has scared everybody with common sense, don't expect to see their replies here.

07-09-2006, 05:01 AM

PipeDream

This is pretty good, and tested-it's basically Anitarf/Infrane's 3-vector system which works well. They use one array per slot though, which would cost you a branch. Branching only costs a couple JASS ops more than an addition, for 3x the space I think it's worth it.

Using a stack is something you can only do with atomic heaps and is way easier/cheaper than the two way list you need for a queue, so use it. Why not use an array for the stack though? You can use the same number of vars and use the last or first element as the stack pointer, although then you could only allocate/free 8191 elements.

The basic idea though is sound and should make a nice base for any graphy data structure.

Another thing Anitarf/Infrane's vector system does is the use of a separate array which indicates in use status. This is real nice for debugging. Double frees for example could be a real bitch to find otherwise.

07-09-2006, 05:09 AM

Vexorian

Where can I see that vector system? I wonder if an array allocates space for 8192 elements when allocated or if it just gets more space when used that would make it a hash I guess, but if it was a hash then it shouldn't have a limit. In case an array doesn't allocate much more memory than a location based based stack then better.

The reason behind the doubts about queue or stack is that the bigger indexes will end up using gamecache, if I use a stack then the later indexes are recycled the sooner they will get used again. In theory you could say that the indexes used recycled later are the higher ones, but I guess that's not so predictable...

07-09-2006, 05:17 AM	#4
PipeDream	What you really want is to keep it a little bit sorted. You could run on a periodic timer a single depth of quick sort. Take the middle element of the stack. Iterate through the stack top to the middle. Everything greater than 8192 in there gets swapped with something below that's less than.

07-09-2006, 05:19 AM

Vexorian

Hmnn having the words stack and sort in the same phrase seems to still cause me bad feelings, it is a good thing that I don't really have to call it a stack in this case so I can just move the thing without doing those awful stack operations....

But really where is their vector system? Cause I really couldn't understand your explanation of what it does

Now that I think about it, I should just use a list with beginning and end, and move the indexes greater than 8192 to the end but the other ones to the beginning.

Edit: duh!, Just don't recycle the ids greater than 8191!

07-09-2006, 05:25 AM

PipeDream

Apparently it isn't publically available. It's just like:

JASS:

function NewTriple takes nothing returns integer
 local integer i=NewTripleIndex()
    //We don't want the user to crash threads, do we?
    set udg_cstripledata1[i]=0
    set udg_cstripledata2[i]=0
    set udg_cstripledata3[i]=0
endfunction
constant function SetTriple1 takes integer triple, integer v returns nothing
    set udg_cstripledata1[triple] = v
endfunction
constant function SetTriple2 takes integer triple, integer v returns nothing
    set udg_cstripledata2[triple] = v
endfunction
constant function SetTriple3 takes integer triple, integer v returns nothing
    set udg_cstripledata3[triple] = v
endfunction

And what I meant by branching was to expose the same interface you do:

JASS:

SetTripleInt takes integer triple, integer index, integer value returns nothing
    if index == 0 then
        set udg_cstripledata1[triple] = value
    elseif index == 1 then
        set udg_cstripledata2[triple] = value
    else
        set udg_cstripledata3[triple] = value
    endif
endfunction

But I believe they stick to SetTriple1/SetTriple2/SetTriple3. For your intended purpose either is fine.

07-09-2006, 05:27 AM	#7
Vexorian	You know what I think about return bug exploiters mixed in final code, and it is going to be part of CSCache That's the reason SetTriple1 wouldn't work cause it would need a GetTriple1 , then you need 3 versions for each handle type, the pain. Anyways, they use 3 arrays, if elseif else, shouldn't be much worse than the + operator.

07-09-2006, 05:30 AM

PipeDream

People should write their interfaces directly into the return bugs for speed. That means they only write for the types they need from their triples for their objects.

You should still recycle IDs greater than 8191 because of the string leak. Appending those is definitely the way to go though. Oops. Can't do that with arrays, so that's a good reason to use locations.

The fixed size kind of blows. If you have to use pointers to implement larger objects your performance starts to vaporize. You could make it dynamic sized with another array to indicate size of the block and allocate/deallocate each integer one by one if that makes sense. Then it would be easy to implement potentially useful stuff like balanced trees.

07-09-2006, 05:44 AM	#9
Vexorian	People should do what they want, but the CSCache should have some consistency.

07-09-2006, 05:50 AM

#10

Vexorian

I made it use 3 arrays, so now it has 3x the space. It is actually faster now! , 4.84seconds, not a big difference but it is good that it didn't get slower.

Using stacks to recycle ids is too good I think it should also improve the speed of tables.

JASS:

function CS_i2r takes integer i returns real
    return i
    return 0.
endfunction

function CS_h2r takes handle h returns real
    return h
    return 0.
endfunction

function CS_r2i takes real r returns integer
    return r
    return 0
endfunction

function CS_lx takes location l returns location
    set udg_csint=CS_r2i(GetLocationX(l))
    return udg_csint
    return null
endfunction

function CS_ly takes location l returns location
    set udg_csint=CS_r2i(GetLocationY(l))
    return udg_csint
    return null
endfunction


function CS_i2l takes integer l returns location
    return l
    return null
endfunction


//=============================================================================================
// Triples pwn !
//
function NewTripleIndex takes nothing returns integer
 local integer i
 local location loc
    if (udg_csfreetriples!=null) then
        set loc=udg_csfreetriples
        set udg_csfreetriples=CS_ly(udg_csfreetriples)
        set i=CS_r2i(GetLocationX(loc))
        call RemoveLocation(loc)
        set loc=null
    else
        set i=udg_cstripledata1[0]+1
        set udg_cstripledata1[0]=i
    endif
 return i
endfunction



function NewTriple takes nothing returns integer
 local integer i=NewTripleIndex()
    //We don't want the user to crash threads, do we?
    if (i<JASS_MAX_ARRAY_SIZE) then
        set udg_cstripledata1[i]=0
        set udg_cstripledata2[i]=0
        set udg_cstripledata3[i]=0
    else //2 index spaces in the array are wasted in the name of speed
        call StoreInteger(CSCache(),"tripledata1",I2S(i),0)
        call StoreInteger(CSCache(),"tripledata2",I2S(i),0)
        call StoreInteger(CSCache(),"tripledata3",I2S(i),0)
    endif

 return i
endfunction

function NewTripleFromValues takes integer a, integer b, integer c returns integer
 local integer i=NewTripleIndex()
    if (i<JASS_MAX_ARRAY_SIZE) then
        set udg_cstripledata1[i]=a
        set udg_cstripledata2[i]=b
        set udg_cstripledata3[i]=c
    else //2 index spaces in the array are wasted in the name of speed
        call StoreInteger(CSCache(),"tripledata1",I2S(i),a)
        call StoreInteger(CSCache(),"tripledata2",I2S(i),b)
        call StoreInteger(CSCache(),"tripledata3",I2S(i),c)
    endif

 return i
endfunction


function DestroyTriple takes integer triple returns nothing

// Just move the id of triple to the recycle bin. In case the triple has been using the gamecache space clean it.
   if (triple>=JASS_MAX_ARRAY_SIZE) then
       call FlushStoredInteger(CSCache(),"tripledata1",I2S(triple))
       call FlushStoredInteger(CSCache(),"tripledata2",I2S(triple))
       call FlushStoredInteger(CSCache(),"tripledata3",I2S(triple))
   endif

   
   if (triple>=JASS_MAX_ARRAY_SIZE) then
   elseif (udg_csfreetriples==null) then //Move it to the stack
       set udg_csfreetriples=Location(CS_i2r(triple),CS_h2r(null))
   else
       set udg_csfreetriples=Location(CS_i2r(triple),CS_h2r(udg_csfreetriples))
   endif

   
endfunction

function SetTripleInt takes integer triple, integer index, integer val returns nothing
// Should I sacrifice speed for encapsullation? Let them use big index values and touch other memory sections, I don't care.
// This function expects index to be in the range [0,2]

    if (triple>=JASS_MAX_ARRAY_SIZE) then
        if (index==0) then
            call StoreInteger(CSCache(),"tripledata1",I2S(triple),val)
        elseif (index==1) then
            call StoreInteger(CSCache(),"tripledata2",I2S(triple),val)
        else
            call StoreInteger(CSCache(),"tripledata3",I2S(triple),val)
        endif

    elseif (index==0) then
        set udg_cstripledata1[triple]=val
    elseif (index==1) then
        set udg_cstripledata2[triple]=val
    else
        set udg_cstripledata3[triple]=val
    endif
endfunction

function GetTripleInt takes integer triple, integer index returns integer
// Should I sacrifice speed for encapsullation? Let them use big index values and touch other memory sections, I don't care.
// This function expects index to be in the range [0,2]
    if (triple>=JASS_MAX_ARRAY_SIZE) then
        if (index==0) then
            return GetStoredInteger(CSCache(),"tripledata1",I2S(triple))
        elseif (index==1) then
            return GetStoredInteger(CSCache(),"tripledata2",I2S(triple))
        endif
            return GetStoredInteger(CSCache(),"tripledata3",I2S(triple))
    elseif (index==0) then
        return udg_cstripledata1[triple]
    elseif (index==1) then
        return udg_cstripledata2[triple]
    endif
        return udg_cstripledata3[triple]
endfunction

Somehow string leaks never worry me. If they use the whole 8191 indexes they should worry about more things than it I guess, and making it a linked list would either increase the time or make me use another variable. Both seem worse than string leaks if there are many indexes. I would worry about that when the limit was 2734 but now it is 8191 which is quite big.

The only thing that may change is the function naming scheme, I might even replace the word triple.

---

Quote:

The fixed size kind of blows. If you have to use pointers to implement larger objects your performance starts to vaporize. You could make it dynamic sized with another array to indicate size of the block and allocate/deallocate each integer one by one if that makes sense. Then it would be easy to implement potentially useful stuff like balanced trees.

Fixed size of the thing I call Triples? Or the limit of Triples before it starts to use gamecache?

Without the fixed size of 3, it would be like peppar's heap and have all of its problems

07-09-2006, 06:14 AM

#11

PipeDream

Quote:

Somehow string leaks never worry me. If they use the whole 8191 indexes they should worry about more things than it I guess,

Fair enough.

Quote:

Without the fixed size of 3, it would be like peppar's heap and have all of its problems

Not if you let warcraft do the hard work with its internal heap with sequential locations like the quad example. Having a make-vec would just be so nice for improving the speed of things like fast timer loops. You could use triples when you only need 3 values or hack something together out of them when you need more but I'm sure we can do better than that.

07-09-2006, 01:38 PM

#12

Vexorian

Still, memory fragmentation would become a little issue. But well I think we can merge quads in the same fashion we did with locations before and this would be a little more effective cause we won't need return bug exploiters.

I can also modiffy the system to do this automatically, err, what about it

CreateArray(n) //I would use the 'vector' name for either the math vector or C++ vectors , not for this...

n would be 3,5,7 or 9 . I guess 10 is either "overkill " or "that's the job of a list you silly boy") But even so if n is bigger than 9 it could automatically use a linked list. The only problem is that it will need a value to store the size of the thing.

--

If anything, I should make them Quads and not Triples, thought about "something" that requires 4 values.

07-09-2006, 08:15 PM

#13

Vexorian

First of all, I trashed Triples to use Quads, and made an array system based on quads, arrays can have lengths of 3,6,9 or 12

JASS:

//5.53 s ! (with array func)
//5.06
//4.37     (direct array access)

//4.84 ((3 arrays))
//4.75 (latest (4 arrays)) //They seem to take the same time, 4 is higher but there were time measuring mistakes



//Array version:
//L=3   6.68 seconds
//L=6  10.59 seconds
//L=9  16.09 seconds
//L=12 23.37 seconds


function CS_i2r takes integer i returns real
    return i
    return 0.
endfunction

function CS_h2r takes handle h returns real
    return h
    return 0.
endfunction

function CS_r2i takes real r returns integer
    return r
    return 0
endfunction

function CS_lx takes location l returns location
    set udg_csint=CS_r2i(GetLocationX(l))
    return udg_csint
    return null
endfunction

function CS_ly takes location l returns location
    set udg_csint=CS_r2i(GetLocationY(l))
    return udg_csint
    return null
endfunction


function CS_i2l takes integer l returns location
    return l
    return null
endfunction


//=============================================================================================
// Quads pwn !
//
function NewQuadIndex takes nothing returns integer
 local integer i
 local location loc
    if (udg_csfreeindexes!=null) then
        set loc=udg_csfreeindexes
        set udg_csfreeindexes=CS_ly(udg_csfreeindexes)
        set i=CS_r2i(GetLocationX(loc))
        call RemoveLocation(loc)
        set loc=null
    else
        set i=udg_csarray1[0]+1
        set udg_csarray1[0]=i
    endif
 return i
endfunction



function NewQuad takes nothing returns integer
 local integer i=NewQuadIndex()
    //We don't want the user to crash threads, do we?
    if (i<JASS_MAX_ARRAY_SIZE) then
        set udg_csarray1[i]=0
        set udg_csarray2[i]=0
        set udg_csarray3[i]=0
        set udg_csarray4[i]=0
    endif
    // No need to initialize in the gamecache

 return i
endfunction

function NewQuadFromValues takes integer a, integer b, integer c, integer d returns integer
 local integer i=NewQuadIndex()
    if (i<JASS_MAX_ARRAY_SIZE) then
        set udg_csarray1[i]=a
        set udg_csarray2[i]=b
        set udg_csarray3[i]=c
        set udg_csarray4[i]=d
    else
        call StoreInteger(CSCache(),"csarray1",I2S(i),a)
        call StoreInteger(CSCache(),"csarray2",I2S(i),b)
        call StoreInteger(CSCache(),"csarray3",I2S(i),c)
        call StoreInteger(CSCache(),"csarray4",I2S(i),d)
    endif

 return i
endfunction

function CloneQuad takes integer Quad returns integer
 local integer i=NewQuadIndex()
    if (i<JASS_MAX_ARRAY_SIZE) then
        if (Quad<JASS_MAX_ARRAY_SIZE) then
            set udg_csarray1[i]=udg_csarray1[Quad]
            set udg_csarray2[i]=udg_csarray2[Quad]
            set udg_csarray3[i]=udg_csarray3[Quad]
            set udg_csarray4[i]=udg_csarray4[Quad]
        else
            set udg_csarray1[i]=GetStoredInteger(CSCache(),"csarray1",I2S(Quad))
            set udg_csarray2[i]=GetStoredInteger(CSCache(),"csarray2",I2S(Quad))
            set udg_csarray3[i]=GetStoredInteger(CSCache(),"csarray3",I2S(Quad))
            set udg_csarray4[i]=GetStoredInteger(CSCache(),"csarray4",I2S(Quad))
        endif
    elseif (Quad<JASS_MAX_ARRAY_SIZE) then
            call StoreInteger(CSCache(),"csarray1",I2S(i),udg_csarray1[Quad])
            call StoreInteger(CSCache(),"csarray2",I2S(i),udg_csarray2[Quad])
            call StoreInteger(CSCache(),"csarray3",I2S(i),udg_csarray3[Quad])
            call StoreInteger(CSCache(),"csarray4",I2S(i),udg_csarray4[Quad])
    else
            call StoreInteger(CSCache(),"csarray1",I2S(i),GetStoredInteger(CSCache(),"csarray1",I2S(Quad)))
            call StoreInteger(CSCache(),"csarray2",I2S(i),GetStoredInteger(CSCache(),"csarray2",I2S(Quad)))
            call StoreInteger(CSCache(),"csarray3",I2S(i),GetStoredInteger(CSCache(),"csarray3",I2S(Quad)))
            call StoreInteger(CSCache(),"csarray4",I2S(i),GetStoredInteger(CSCache(),"csarray4",I2S(Quad)))
    endif
 return i 
endfunction



function DestroyQuad takes integer Quad returns nothing

// Just move the id of Quad to the recycle bin. In case the Quad has been using the gamecache space clean it.
   if (Quad>=JASS_MAX_ARRAY_SIZE) then
       call FlushStoredInteger(CSCache(),"csarray1",I2S(Quad))
       call FlushStoredInteger(CSCache(),"csarray2",I2S(Quad))
       call FlushStoredInteger(CSCache(),"csarray3",I2S(Quad))
       call FlushStoredInteger(CSCache(),"csarray4",I2S(Quad))

   elseif (udg_csfreeindexes==null) then //Move it to the stack
       set udg_csfreeindexes=Location(CS_i2r(Quad),CS_h2r(null))
   else
       set udg_csfreeindexes=Location(CS_i2r(Quad),CS_h2r(udg_csfreeindexes))
   endif

   
endfunction



function SetQuadInt takes integer Quad, integer index, integer val returns nothing
// Should I sacrifice speed for encapsullation? Let them use big index values and touch other memory sections, I don't care.
// This function expects index to be in the range [0,2]

    if (Quad>=JASS_MAX_ARRAY_SIZE) then
        if (index==0) then
            call StoreInteger(CSCache(),"csarray1",I2S(Quad),val)
        elseif (index==1) then
            call StoreInteger(CSCache(),"csarray2",I2S(Quad),val)
        elseif (index==2) then
            call StoreInteger(CSCache(),"csarray3",I2S(Quad),val)
        else
            call StoreInteger(CSCache(),"csarray4",I2S(Quad),val)
        endif

    elseif (index==0) then
        set udg_csarray1[Quad]=val
    elseif (index==1) then
        set udg_csarray2[Quad]=val
    elseif (index==2) then
        set udg_csarray3[Quad]=val
    else
        set udg_csarray4[Quad]=val
    endif
endfunction

function GetQuadInt takes integer Quad, integer index returns integer
// Should I sacrifice speed for encapsullation? Let them use big index values and touch other memory sections, I don't care.
// This function expects index to be in the range [0,2]
    if (Quad>=JASS_MAX_ARRAY_SIZE) then
        if (index==0) then
            return GetStoredInteger(CSCache(),"csarray1",I2S(Quad))
        elseif (index==1) then
            return GetStoredInteger(CSCache(),"csarray2",I2S(Quad))
        elseif (index==2) then
            return GetStoredInteger(CSCache(),"csarray3",I2S(Quad))
        endif
            return GetStoredInteger(CSCache(),"csarray4",I2S(Quad))
    elseif (index==0) then
        return udg_csarray1[Quad]
    elseif (index==1) then
        return udg_csarray2[Quad]
    elseif (index==2) then
        return udg_csarray3[Quad]
    endif
        return udg_csarray4[Quad]
endfunction





// Valid L values are 3,6,9 and 12.
function NewArray takes integer L returns integer
 local integer i
    if (L==12) then
        return NewQuadFromValues(12,NewQuad(),NewQuad(),NewQuad())
    elseif (L==9) then
        return NewQuadFromValues(9,0,NewQuad(),NewQuad())
    elseif (L==6) then
        return NewQuadFromValues(6,0,0,NewQuad())
    endif
        return NewQuadFromValues(3,0,0,0)
endfunction

function CloneArray takes integer id returns integer
 local integer L
 local integer a
 local integer b
 local integer c
    if (id < JASS_MAX_ARRAY_SIZE) then
        set L=udg_csarray1[id]
        set a=udg_csarray2[id]
        set b=udg_csarray3[id]
        set c=udg_csarray4[id]
    else
        set L=GetStoredInteger(CSCache(),"csarray1",I2S(id))
        set a=GetStoredInteger(CSCache(),"csarray2",I2S(id))
        set b=GetStoredInteger(CSCache(),"csarray3",I2S(id))
        set c=GetStoredInteger(CSCache(),"csarray4",I2S(id))
    endif
    if (L==3) then
        return NewQuadFromValues(3,a,b,c)
    elseif (L==6) then
        return NewQuadFromValues(6,a,b,CloneQuad(c))
    elseif (L==9) then
        return NewQuadFromValues(9,a,CloneQuad(b),CloneQuad(c))
    endif
 return NewQuadFromValues(12,CloneQuad(a),CloneQuad(b),CloneQuad(c))
endfunction


function DestroyArray takes integer id returns nothing
 local integer L
 local integer a
 local integer b
 local integer c
    if (id<JASS_MAX_ARRAY_SIZE) then
        set L=udg_csarray1[id]
        set a=udg_csarray2[id]
        set b=udg_csarray3[id]
        set c=udg_csarray4[id]
    else
        set L = GetStoredInteger(CSCache(),"csarray1",I2S(id))
        set a = GetStoredInteger(CSCache(),"csarray2",I2S(id))
        set b = GetStoredInteger(CSCache(),"csarray3",I2S(id))
        set c = GetStoredInteger(CSCache(),"csarray4",I2S(id))
    endif
    if (L==12) then
        call DestroyQuad(a)
    endif
    if (L>=9) then
        call DestroyQuad(b)
    endif        
    if (L>=6) then
        call DestroyQuad(c)
    endif
    call DestroyQuad(id)
endfunction

function GetArraySize takes integer id returns integer
   if (id<JASS_MAX_ARRAY_SIZE) then
       return udg_csarray1[id]
   endif
 return GetStoredInteger(CSCache(),"csarray1",I2S(id))
endfunction

//function SetArraySize should be doable

function SetArrayInt takes integer id, integer index, integer val returns nothing
 local integer L
  // This "type things multiple times" nightmare is what I get from focusing on speed
   if (id<JASS_MAX_ARRAY_SIZE) then
   //There is probably a better way to do this.
       set L=udg_csarray1[id]
       if (L==12) then
            if (index<4) then
                set id=udg_csarray2[id]
                //index stays the same
            elseif (index<8) then
                set id=udg_csarray3[id]
                set index=index-4
            else
                set id=udg_csarray4[id]
                set index=index-8
            endif
       elseif (L==9) then
            if (index==0) then
                set udg_csarray2[id]=val
                return
            elseif (index<5) then
                set id=udg_csarray3[id]
                set index=index-1
            else
                set id=udg_csarray4[id]
                set index=index-5
            endif
       elseif (L==6) then
           if (index==0) then
                set udg_csarray2[id]=val
                return
           elseif (index==1) then
                set udg_csarray3[id]=val
                return
           else
               set id=udg_csarray4[id]
               set index=index-2
           endif
       elseif (index==0) then
           set udg_csarray2[id]=val
           return
       elseif (index==1) then
           set udg_csarray3[id]=val
           return
       else
           set udg_csarray4[id]=val
           return
       endif
       
       
   else //The same but using gamecache o_O
       set L=GetStoredInteger(CSCache(),"csarray1",I2S(id))
       if (L==12) then
            if (index<4) then
                set id=GetStoredInteger(CSCache(),"csarray2",I2S(id))
                //index stays the same
            elseif (index<8) then
                set id=GetStoredInteger(CSCache(),"csarray3",I2S(id))
                set index=index-4
            else
                set id=GetStoredInteger(CSCache(),"csarray4",I2S(id))
                set index=index-8
            endif
       elseif (L==9) then
            if (index==0) then
                call StoreInteger(CSCache(),"csarray2",I2S(id),val)
                return
            elseif (index<5) then
                set id=GetStoredInteger(CSCache(),"csarray3",I2S(id))
                set index=index-1
            else
                set id=GetStoredInteger(CSCache(),"csarray4",I2S(id))
                set index=index-5
            endif
       elseif (L==6) then
           if (index==0) then
                call StoreInteger(CSCache(),"csarray2",I2S(id),val)
                return
           elseif (index==1) then
                call StoreInteger(CSCache(),"csarray3",I2S(id),val)
                return
           else
               set id=GetStoredInteger(CSCache(),"csarray4",I2S(id))
               set index=index-2
           endif
       elseif (index==0) then
           call StoreInteger(CSCache(),"csarray2",I2S(id),val)
           return
       elseif (index==1) then
           call StoreInteger(CSCache(),"csarray3",I2S(id),val)
           return
       else
           call StoreInteger(CSCache(),"csarray4",I2S(id),val)
           return
       endif
   endif
   // Now do the quad thing, but since we want speed, don't waste it with an extra fucntion call.
   if (id<JASS_MAX_ARRAY_SIZE) then
       if (index==0) then
           set udg_csarray1[id]=val
       elseif(index==1) then
           set udg_csarray2[id]=val
       elseif (index==2) then
           set udg_csarray3[id]=val
       else
           set udg_csarray4[id]=val
       endif
   elseif (index==0) then
       call StoreInteger(CSCache(),"csarray1",I2S(id),val)
   elseif (index==1) then
       call StoreInteger(CSCache(),"csarray2",I2S(id),val)
   elseif (index==2) then
       call StoreInteger(CSCache(),"csarray3",I2S(id),val)
   else
       call StoreInteger(CSCache(),"csarray4",I2S(id),val)
   endif

   
endfunction

function GetArrayInt takes integer id, integer index returns integer
 local integer L
  // This "type things multiple times" nightmare is what I get from focusing on speed
   if (id<JASS_MAX_ARRAY_SIZE) then
   //There is probably a better way to do this.
       set L=udg_csarray1[id]
       if (L==12) then
            if (index<4) then
                set id=udg_csarray2[id]
                //index stays the same
            elseif (index<8) then
                set id=udg_csarray3[id]
                set index=index-4
            else
                set id=udg_csarray4[id]
                set index=index-8
            endif
       elseif (L==9) then
            if (index==0) then
                return udg_csarray2[id]
            elseif (index<5) then
                set id=udg_csarray3[id]
                set index=index-1
            else
                set id=udg_csarray4[id]
                set index=index-5
            endif
       elseif (L==6) then
           if (index==0) then
                return udg_csarray2[id]
           elseif (index==1) then
                return udg_csarray3[id]
           else
               set id=udg_csarray4[id]
               set index=index-2
           endif
       elseif (index==0) then
           return udg_csarray2[id]
       elseif (index==1) then
           return udg_csarray3[id]
       else
           return udg_csarray4[id]
       endif
       
   else //The same but using gamecache o_O
       set L=GetStoredInteger(CSCache(),"csarray1",I2S(id))
       if (L==12) then
            if (index<4) then
                set id=GetStoredInteger(CSCache(),"csarray2",I2S(id))
                //index stays the same
            elseif (index<8) then
                set id=GetStoredInteger(CSCache(),"csarray3",I2S(id))
                set index=index-4
            else
                set id=GetStoredInteger(CSCache(),"csarray4",I2S(id))
                set index=index-8
            endif
       elseif (L==9) then
            if (index==0) then
                return GetStoredInteger(CSCache(),"csarray2",I2S(id))
            elseif (index<5) then
                set id=GetStoredInteger(CSCache(),"csarray3",I2S(id))
                set index=index-1
            else
                set id=GetStoredInteger(CSCache(),"csarray4",I2S(id))
                set index=index-5
            endif
       elseif (L==6) then
           if (index==0) then
               return GetStoredInteger(CSCache(),"csarray2",I2S(id))
           elseif (index==1) then
               return GetStoredInteger(CSCache(),"csarray3",I2S(id))
           else
               set id=GetStoredInteger(CSCache(),"csarray4",I2S(id))
               set index=index-2
           endif
       elseif (index==0) then
           return GetStoredInteger(CSCache(),"csarray2",I2S(id))
       elseif (index==1) then
           return GetStoredInteger(CSCache(),"csarray3",I2S(id))
       else
           return GetStoredInteger(CSCache(),"csarray4",I2S(id))
       endif
   endif
   // Now do the quad thing, but since we want speed, don't waste it with an extra fucntion call.
   if (id<JASS_MAX_ARRAY_SIZE) then
       if (index==0) then
           return udg_csarray1[id]
       elseif(index==1) then
           return udg_csarray2[id]
       elseif (index==2) then
           return udg_csarray3[id]
       endif
           return udg_csarray4[id]
   elseif (index==0) then
       return GetStoredInteger(CSCache(),"csarray1",I2S(id))
   elseif (index==1) then
       return GetStoredInteger(CSCache(),"csarray2",I2S(id))
   elseif (index==2) then
       return GetStoredInteger(CSCache(),"csarray3",I2S(id))
   endif
       return GetStoredInteger(CSCache(),"csarray4",I2S(id))  
endfunction

All right, unlike my calculations these arrays are much slower than Quads. Worth it ? The Array of Length 12 is even slower than gamecache... I am just about to get crazy and use 12 different global arrays...

Anyways Arrays should be slower when allocating but as fast as The last triples or quads when accessing. Should come up with a test that benchmarks access speed and not allocation/deallocation

In theory, making the array system use 12 global arrays directly instead of trees made out of quads it should be as fast as quads. 12 is a lot so maybe I'll use a size of 10. But even so that would be a waste of memory most of the times , if you allocate an array to use 2 values you would be wasting 8 spaces.

Maybe I'll stick to the Quad + Array strategy. That depends on the read/write speed comparissions

07-09-2006, 10:47 PM

#14

PipeDream

Variable length allocation turned out to be a lot easier to do than I thought. This uses blocks of power of 2 sizes in a heap array managed the same way as your triples. It should be very very fast. Limited to 8191 cells, or 8192 at a very very tiny performance hit. Actually I guess that performance hit is only on the first call to alloc, I should probably just make it 8192.

JASS:

globals //We don't need 3 arrays, but I wanted this to be readable
    location array udg_pool
    integer array udg_heap
    integer array udg_pow2
endglobals

function ItoR takes integer i returns real
    return i
    return 0.
endfunction
function HtoR takes handle h returns real
    return h
    return 0.
endfunction
function ItoL takes integer i returns location
    return i
    return null
endfunction
function RtoL takes real r returns location
    return r
    return null
endfunction
function RtoI takes real r returns integer
    return r
    return 0
endfunction

//size is the exponent of 2
//Push the block into the appropriate list
function free takes integer begin, integer size returns nothing
    set udg_pool[size] = Location(ItoR(begin),HtoR(udg_pool[size])) 
endfunction

//udg_pool is an array of lists of free blocks of size 2^i
function initheap takes nothing returns nothing
    local integer i = 0
    local integer s = 1
    local integer accum = 0
    loop
        exitwhen s > 4096
        call free(accum,i)        //Initialize to one block of each size.  waste one cell.
        set accum = accum + s
        set udg_pow2[i] = s
        set s = s * 2
        set i = i + 1
    endloop
endfunction


function alloc takes integer size returns integer
    local integer block
    local location next
//First check if we have a block of appropriate size
    if udg_pool[size] != null then
        set block = RtoI(GetLocationX(udg_pool[size]))
        set next = RtoL(GetLocationY(udg_pool[size]))
        call RemoveLocation(udg_pool[size])
        set udg_pool[size] = next
        set next = null
    else    //We're out of block of the right size
        if size >= 12 then
            call BJDebugMsg("Error, did you initheap?  otherwise out of memory-gamecache me")
            return -1
        endif
        set block = alloc(size+1)    //Get one that's twice as big.  This might be made marginally faster with a loop instead of recursion.
        call free(block+udg_pow2[size],udg_pow2[size])    //Split it in two
    endif
    return block    //Hand back the bottom part
endfunction

//If we run out of large enough blocks, we need to join old ones back together
//Write this if you need it, but you probably won't if you use blocks of all small sizes
function compact takes nothing returns nothing
//iterate from 0th level to 12th and compact each one by one
//In each, scan for adjacent free blocks by inserting them into an array at their beginning 
//and checking for neighbors on either side.  if you find one, join them by freeing the lower 
//one as level + 1 and remove both from the list.  this will be tricky when the list begins 
//with one of them.  you could make it easy by starting the lists with an empty location.
//You could also rebuild the list from scratch
//Using something binary heap like and just sorting them would also work but balance would be a major hassle
endfunction

JASS:

function test takes nothing returns nothing
    local integer a = alloc(3) //8  allocation example
    local integer b = alloc(3) //8
    local integer c = alloc(0) //1
    local integer d = alloc(4) //16
    local integer e = alloc(5) //32
    call free(a,3) //deallocation example- have to mention how big block is
    call free(b,3)
    set a = alloc(3)
    set b = alloc(3)
    call BJDebugMsg("8 "+I2S(a))
    call BJDebugMsg("8 "+I2S(b))
    call BJDebugMsg("1 "+I2S(c))
    call BJDebugMsg("16 "+I2S(d))
    call BJDebugMsg("32 "+I2S(e))
    set udg_heap[a+4] = 4 //Accessing
    set udg_heap[e+31] = udg_heap[a+4]
endfunction
function start takes nothing returns nothing
    call initheap()
    call test()
endfunction

The downside of course is only 8192 cells, but you could use any of the techniques you've suggested for expanding this. You also have to know how big your blocks are. You could lose one cell in exchange for keeping size around, but I think there are few moments where it would help to automate it.

07-10-2006, 01:42 AM

#15

Vexorian

heh during my inactivity time I thought about something similar, but not using powers of two but any number and not requiring that kind of initializing but another one I guess both would be as fast.

My way of doing it would always be slower than yours. Cause in yours the user just needs to use the array, on mine it will have functions for Get and Set . When I make things for CSCache and the caster system I am always making it so users stay in the high level, that's bad and good depending on the point of view.

I was going to benchmark using the stack test, but I am either doing something wrong or I don't understand how it works or something:

JASS:

function Stack_Empty takes integer s returns boolean
 return udg_heap[s]==0
endfunction

function Stack_Push takes integer s, integer i returns nothing
 local integer F=udg_heap[s]
 local integer G
    set G=alloc(4)
    set udg_heap[G+1]=F
    set udg_heap[G]=i
    set udg_heap[s]=G
 
endfunction

function Stack_Pop takes integer s returns integer
 local integer F=udg_heap[s]
 local integer q
 local integer i
    if (F==0) then
        return 0
    endif
    set i=udg_heap[F]
    set q=udg_heap[F+1]
    call free(F,4)
    set udg_heap[s]=q
 return i
endfunction

function NewStack takes nothing returns integer
   return alloc(4)
endfunction

function Stack_Destroy takes integer s returns nothing
 local integer t=udg_heap[s]
 local integer q
 
   loop
       exitwhen (t==0)
       set q=t
       set t=udg_heap[t+1]
       call free(q,4)
   endloop
   call free(s,4)
endfunction

function List_Sum takes integer l returns integer
 local integer q=udg_heap[l]
 local integer S=0
    loop
        exitwhen (q==0)
        set S=udg_heap[q]+S
        set q=udg_heap[q+1]
    endloop
 return S
endfunction

It gets into an infinite loop and ends telling me that I should gamecache it