STL map VS Game Cache Benchmark Jass

09-09-2006, 03:31 PM #1

JASS:



function Timer takes nothing returns nothing 
  local gamecache oldhash =InitGameCache("MapName.w3v")
  local integer i
  local integer p
  local integer e
  local location loc 
  local integer map = CreateMap()
  local integer time 
  local integer time2 
  local real r =0.0
  local location find = Location(4.0,4.0) 

  set i=0


call DisplayTextToForce( GetPlayersAll(),"START" )




call TriggerSleepAction(0.002)
set time =StopWatchCreate() 
loop 
  set loc =  Location(0.0,0.0)
 call StoreInteger(oldhash,"string" ,I2S(H2I(loc)) ,H2I(loc))
   // set e=   GetStoredInteger(oldhash,"string" ,I2S(H2I(loc)))
   if( i== 550) then
     call StoreInteger(oldhash,"string" ,I2S(H2I(find)) ,H2I(loc))
  endif 
    exitwhen i> 1000
set i=i+1
endloop 
set e=   GetStoredInteger(oldhash,"string" ,I2S(H2I(find)))
set r =StopWatchMark(time)



call DisplayTextToForce( GetPlayersAll(),"HASH TIME"+ R2S(r) )//.046 Seconds

set i=0

set time2 =StopWatchCreate() 
loop
set loc =  Location(2.0,2.0)
   call  SetMapValue(map, loc, loc)
   //set loc= GetLocationFromMap(map,loc)

     if (i== 550) then
      call  SetMapValue(map,find, loc)
   endif 
    exitwhen i > 1000
set i=i+1
endloop 
set loc= GetLocationFromMap(map,find)
set r =StopWatchMark(time2)


  
call DisplayTextToForce( GetPlayersAll(),"STL MAP TIME "+R2S(r))//.006 Seconds

call DeleteMap(map)
endfunction 




//===========================================================================
function CreateBenchMark takes nothing returns nothing
    local trigger t = CreateTrigger(  )
    call TriggerRegisterPlayerEventEndCinematic( t, Player(0) )
    call TriggerAddAction( t,function Timer )
endfunction

As You can See STL is ~5 Times Faster in this demo.
Best of All You dont need I2S or H2I.

C++ Code Used

PHP Code:


		
			
/**

 *  New Natives  

 *  

 * GetHandleFromMap has varis Alises for Jass So for typcasting handels and Ints

 * 

 */



void jNATIVE DeleteMap(map< JHandel, JHandel> *map2)

{

    delete map2;

}





map< JHandel, JHandel> * jNATIVE CreateMap()

{

  return new map< JHandel, JHandel>;

}







void jNATIVE  SetMapValue(map< JHandel, JHandel> *map, JHandel HandelKey, JHandel HandelVaue)

{

     (*map)[HandelKey]=HandelVaue;

}





JHandel jNATIVE  GetHandleFromMap(map< JHandel, JHandel>*map,JHandel HandelKey)

{

     return (*map)[HandelKey];

}









typedef __int64 watch_t;



watch_t *jNATIVE StopWatchCreate()

{

    watch_t *x = new watch_t;

    QueryPerformanceCounter((LARGE_INTEGER *)x);

    //*x = clock();

    return x;

}



//got to return int to make it go on eax instead of floating point stack

int jNATIVE StopWatchMark(watch_t *x)

{

    watch_t y,interval,freq;

    float f;

    QueryPerformanceCounter((LARGE_INTEGER *)&y);

    QueryPerformanceFrequency((LARGE_INTEGER *)&freq);

    //y = clock();

    interval = y - (*x);

    f = (float)interval/(float)freq;

//    f = (float)interval/(float)CLOCKS_PER_SEC;

    return *(int *)&f;

}



void jNATIVE StopWatchDestroy(watch_t *x)

{

    delete x;

}



    jAddNative(StopWatchCreate,"StopWatchCreate","()I");

    jAddNative(StopWatchMark,"StopWatchMark","(I)R");

    jAddNative(StopWatchDestroy,"StopWatchDestroy","(I)V");

    jAddNative(SetMapValue, "SetMapValue", "(IHhandle;Hhandle;)V");

    jAddNative(CreateMap, "CreateMap", "()I");

    jAddNative(DeleteMap, "DeleteMap", "(I)V");

    jAddNative(GetHandleFromMap, "GetTimerFromMap", "(IHhandle;)Htimer;");

    jAddNative(GetHandleFromMap, "GetUnitFromMap", "(IHhandle;)Hunit;");

    jAddNative(GetHandleFromMap, "GetTriggerFromMap", "(IHhandle;)Htrigger;");

    jAddNative(GetHandleFromMap, "GetGroupFromMap", "(IHhandle;)Hgroup;");

    jAddNative(GetHandleFromMap, "GetLocationFromMap", "(IHhandle;)Hlocation;");

    jAddNative(GetHandleFromMap, "GetDestructableFromMap", "(IHhandle;)Hdestructable;");

    jAddNative(GetHandleFromMap, "GetPlayerFromMap", "(IHhandle;)Hplayer;");

    jAddNative(GetHandleFromMap, "GetIntFromMap", "(IHhandle;)I");

09-09-2006, 04:09 PM	#2
Captain Griffen	Yet this is basically worthless due to the requirement for a custom loader, etc. The speed increase from dynamic arrays isn't worth it.

09-09-2006, 04:24 PM	#3
Vexorian	gamecache is a table of tables, it doesn't just link key to value it links mission to key to value. Then to fully emulate its flexibility you would need a map of maps? And that would be only 2.5 times faster?

09-09-2006, 06:17 PM	#4
COOLer	That was just with one look up. Just looking at the time for look ups it is 8 to 1 Also since gc seems to be one large hash several small maps should be faster. STL lookup is O Log O.

09-09-2006, 06:21 PM	#5
Vexorian	never said they weren't faster but just 2.5 times faster

09-09-2006, 06:29 PM	#6
COOLer	I would like to think its closer to 4 times faster using a map of maps for look ups. Buts just making a few global ints for maps would give you the same functionality at much greater speed. If you can think of a data structure with an even faster lookup time please let me know.

09-09-2006, 06:51 PM

PipeDream

Map of maps will be just as fast. 5x faster means the vast majority of time is spent in the VM.
you'll get faster look up times from hash tables and tries. Tries are particularly neat because you can still enumerate the elements in order. The hip implementation to use is http://judy.sourceforge.net/

However I think you will never find STL maps doing worse than either given the VM overhead. At 10,000 elements you've only got 16 or so cache lines to load to access the bottom of the tree which is nothing compared to the thrashing the VM does. Judy tries will roughly cut that in half, not a significant difference.

09-09-2006, 07:06 PM

COOLer

Pipe I think your right the hash table should be faster but because of the Jass overhead and it not being ment for fast look up in like we are using in wc3 it is inherently slower. But most maps should have less then 1000 elements in them as they are mostly used to attach unit data so it appears that they are faster to use in this case. In such a limited amount data to look up I wonder if making 2-3 faster then ~8-5 of gc would be worth it.

09-09-2006, 07:08 PM

PipeDream

Quote:

not being ment for fast look up in like we are using in wc3 it is inherently slower

What?

--

Oh, game cache.

09-09-2006, 07:20 PM	#10
COOLer	It was meant to be saved on HD and not read directly from memory. So when coding the gc they did not make it as efficient as it could be for normal hash tables. It was an after thought of the engine and the fact that it was limited by the HD speed made this effincently not needed.

09-11-2006, 10:23 AM	#11
Toadcop	COOLer - the idea is great ! but i have 1.18 so i can't test it =( PS if i could i would use it ! for the name of speed ! =)

09-11-2006, 11:34 AM	#12
DotA_DR	How it works? What it is based on?

09-11-2006, 11:49 AM	#13
Toadcop	DotA_DR - you need JAPI to launch it ! короче это отдельным .ехе запускаетьса ! но в принципе очень просто вот только версия должна быть 1.20д/е и так я попробывать не смог... PS he is rus =)

09-11-2006, 12:33 PM	#14
Blade.dk	That doesn't matter. English is the only language allowed at the forums. If you want to communicate in Russian, then you are welcome to, just do it with PMs.

09-11-2006, 05:21 PM	#15
PipeDream	Hm I hadn't noticed that you managed to register the base handle as a type. Good to know.