Index ranges - Media Ranges - do we really need 32bit unique indexes ?

[kevin]

  Computing FREE MEDIA indexes  

      Our example is becoming more robust as the sessions go on, in older libraries we use a parallel linked list of used and Free indexes to keep track of them.    This is cool as it means pulling a FREE or NEW media index of some type.. Ie.  GetFReeBank()  / NewBANK()  or   GetFreeSprite() / NewSprite()   - Those kinds of functions all use this approach underneath.   This gives us a fixed time to find a free resource from the various lists.  But that doesn't really fit into our next blocked range solution..    The reason is the list is another big block of parallel data.   If we have a 100K quantity of indexes then we have 100K time the size of the data structure just to remember the free order.    Which is something I'm trying to avoid here.   So unfortunately this means searching linearly though the indexes to find a free one at the moment.  

      So since we're trailing the Banks library against the internal command set, how does calling GetFreeBank()  compare to it's new counter part  PB_GetFreeBank() ???

      Well, it's slower..          

  Results  

Code Select Expand




---[ GET FREE FUNCTIONTESTING ] ------------------------------


Creation Time:1
GetFreeBank Time:12.0 For #500000 Tests
PB GetFreeBank Time:779.0 For #500000 Tests


------------> Result:  Test 1 is [64.91666] times faster then test 2


---[ GET FREE FUNCTION TESTING DONE ] ------------------------------






 
  Test function  

  This is the as is build code and there fore is  not runable for users..  It's here just so you an see what were testing

PlayBASIC Code: [Select]

Function GUI_TEST_BANKS_GETFREE()
   IndexRange= 10000
   #print "" : #print ""
   #print "---[ GET FREE FUNCTIONTESTING ] ------------------------------"
   #print "" : #print ""

   BankQuantity IndexRange
   for index=1 to IndexRange
         if GetBankStatus(index)
            deletebank Index
         endif
         if PB_GetBankStatus(index)
            PB_deletebank Index
         endif
   next

   //  Create 1/4 of the range of banks 100 bytes  in size
   t=timer()   
   for index=1 to IndexRange/4
         createbank       index,100
         PB_createbank    index,100
   next
   #print "Creation Time:"+str$(Timer() - t)



   // TIme the get free functions
      MaxTests=100000
   t=timer()
   for lp =0 to Maxtests   
         Index=GetFreeBank()   
         Index=GetFreeBank()   
         Index=GetFreeBank()   
         Index=GetFreeBank()   
         Index=GetFreeBank()   
   next
   t1#=Timer()-t
   #print "GetFreeBank Time:"+str$(t1#)+" For #"+str$(lp*5)+" Tests"


   t=timer()
   for lp =0 to Maxtests   
         Index=PB_GetFreeBank()   
         Index=PB_GetFreeBank()   
         Index=PB_GetFreeBank()   
         Index=PB_GetFreeBank()   
         Index=PB_GetFreeBank()   
   next
   t2#=Timer()-t
   #print "PB GetFreeBank Time:"+str$(t2#)+" For #"+str$(lp*5)+" Tests"
   #print "" : #print ""

   #print "------------> Result:  Test 1 is ["+str$(t2#/t1#)+"] times faster then test 2"



   #print "" : #print ""
   #print "---[ GET FREE FUNCTION TESTING DONE ] ------------------------------"
   #print "" : #print ""

   
EndFunction

[stevmjon]

if the new method is better, but slower, it shouldn't matter because free indexes are really only use at the beginning when loading images etc.

[kevin]

if the new method is better, but slower, it shouldn't matter because free indexes are really only use at the beginning when loading images etc.

 Yeah.. that was my initial gut reaction too, then you start thinking about the Sprites command sets, where coders tend to  create / destroy things dynamically a lot across the frame.    This test does show worse case though (and it could be a lot worse than this), so it feels a lot like robbing Peter to pay Paul.    I did tweak it up a bit more (which was about 15% faster than the test above) but I think i'll have to link the smaller index blocks together.    That should give us a result much the same as the existing solution,  just annoying :)

 Editing that video atm

[kevin]

  PlayBASIC LIVE - Media Indexes & Threading Chit Chat - (2021-05-19)


 

[kevin]

 Computing FREE MEDIA indexes  - GetFreebank #2


     So the GetFreeBank() problem seems to be solved by linking the blocks together.     In the test results bellow, the replacement free item function is twice as fast as the old internal function.     There's some functional difference from the old approach, where the newest one will work within the sub blocks of indexes.   Meaning if the bank quantity is 1024 items, that is then broken down into four blocks of 256 possible indexes, calling the FreeBank function will pull from the first block of 256 first and if that's full, fall down to the next block.    Keep them managed within the allocated blocks.     There's a penalty though, if a sub block is full, then we have to bump up to the next used sub block.    Since we're trying to keep indexes within allocated blocks.     So worse case scenario is it'll will be bit slower, but generally it should be about the same speed or faster in the real world.

     

Code Select Expand




---[ GET FREE FUNCTIONTESTING ] ------------------------------


Creation Time:1

      GetFreeBank Time:  10.0 For #500000 Tests
 PB GetFreeBank Time: 645.0 For #500000 Tests
PB GetFreeBank2 Time:     5.0 For #500000 Tests


------------> Result:  Test 1 is [64.5] times faster then test 2
------------> Result:  Test 1 is [0.5] times faster then test 3


---[ GET FREE FUNCTION TESTING DONE ] ------------------------------




[kevin]

   Computing FREE MEDIA indexes  - Media Quantities becoming obsolete


     Ok, so continuing with the Bank command set prototype,  some things are becoming obsolete such as theBankQuantity /GetBankQuantity()  which were for resizing the internal command sets tables for the command set.     In the replacement libraries these commands are really only for controlling the potential ranges, changing the Quantity just sets that range,  there's no allocation happening anymore.  

           
     

[kevin]

    Computing FREE MEDIA indexes  - BANK COMMAND SET (REPLACEMENTS)


      Picking through the old bank commands looking for odd behaviors and have found more than a few places where some data management & clipping was missing.   This mostly refers to how it manages the allocations for you, ideally things like resizing the bank.   Which now includes some limited logic for shrinking the buffer, which is handy if your constantly resizing the buffer down.   I'll include some logic for expansion too,  just haven't got there as yet.  

      But for today's little diddy..   Now  i'm looking at the  CopyBankBytes command.  Which seems to have some missing clipping functionality, in particular when you write to an address bellow the first byte in the bank, which rejects this copy, whereas if you copy to the end of the buffer it'll clip the target size correctly..  

      Run this in DEBUG mode F7 and check the console output.

PlayBASIC Code: [Select]

      A=NewBank(20)
      B=NewBank(20)

      Randomize 12234
   //   FillBANK(A,255)
      RandomizeBank(A)
      ShowBANK A

      #print "      CopyBankBytes A, 0, 5, B, 0"
      CopyBankBytes A, 0, 5, B, 0
      ShowBANK B
      FillBank(B,0)      


      #print "      CopyBankBytes A, 0, 5, B, 1000"
      CopyBankBytes A, 0, 5, B, 1000
      ShowBANK B
      FillBank(B,0)      



      #print "      CopyBankBytes A, 0, 5, B, 17"
      CopyBankBytes A, 0, 5, B, 17
      ShowBANK B
      FillBank(B,0)      

      #print "      CopyBankBytes A, 0, 5, B, -3"
      CopyBankBytes A, 0, 5, B, -3
      ShowBANK B
      FillBank(B,0)      


      sync
      waitkey
      
      
Function RandomizeBank(ThisBank)
      ptr=getbankptr(ThisBank)
      if Ptr
         Size=getBankSize(ThisBank)
         for lp=0 to size-1
            pokebankbyte Thisbank,lp, floor(rnd#(256)) 
         next
   

      endif   
EndFunction

Function FillBank(ThisBank,ThisByte)
      ptr=getbankptr(ThisBank)
      if Ptr
         Size=getBankSize(ThisBank)
         FillMemory Ptr,Size,ThisByte,1 
      endif
EndFunction


Function ShowBank(ThisBank)
      #print "Bank#"+str$(Thisbank)+" --------------------------"
      #print ""   
            if getBankStatus(ThisBank)
         ptr=getbankptr(ThisBank)
         if Ptr
            Size=getBankSize(ThisBank)
            for lp=0 to size-1
               thisbyte=PeekBankByte(Thisbank,lp)
   
               s$+=digits$(Thisbyte,3)+","
               row++
               if row > 100
                     #print s$
                     row=0
               endif
         
            next            
         
            if row
                  #print s$
            endif
            
         endif
      else
         #print "BAnk Doesn't Exist"+str$(Thisbank)   
   endif   
      #print ""   
      
EndFunction

      Output data

Code Select Expand


Bank#1 --------------------------

238,243,173,201,175,233,044,041,141,193,164,154,128,220,144,068,039,238,063,051,

CopyBankBytes A, 0, 5, B, 0
Bank#2 --------------------------

238,243,173,201,175,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,

CopyBankBytes A, 0, 5, B, 1000
Bank#2 --------------------------

000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,

CopyBankBytes A, 0, 5, B, 17
Bank#2 --------------------------

000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,238,243,173,

CopyBankBytes A, 0, 5, B, -3
Bank#2 --------------------------

000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,