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

[kevin]

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

     
     wouldn't a 16bit range be enough (1 to 65536.0)

     or a 24bit range be enough (1 to 16777200.0) 


   in a 32bit environment having 32bit unique anything is actually impossible anyway..     



   this is stuff like MEDIA indexes...  So mainly Images/Sprites  and another other media

[stevmjon]

so i assume it is currently 32 bit? would say 16 bit values work better, or is it faster?

if you could explain the advantage / disadvantage please... i am interested to know the difference in how this effects PB code.

[kevin]

  The media indexs are limited to about 30bits since they're 32bit integers..   so 2^30  possible slots for EACH media type..  That's a LOT OF MEMORY (4gig in fact)


 I don't know off the top of my head, but I'd say that each slot in say the BANKS command set consumes about 32 bytes of info data..   Just to store the info about the BANK, it's size, pointer, and whatever else it needs.   Something like a  SPRITE would more like 200 (or more) bytes per sprite..   those are just the structures (TYPES) to hold the basic info about the object.


 So having big linear ranges is just overkill, given that very few examples thus far have ever used more than a few thousand of any one resource..  


 Current implementations use big linear arrays to house all of the data from each media library, there's some variations of that theme, but that's basically how it's down in PB/PBFX builds..

 But what you could do is use high bits of the MEDIA INDEX as a bank selector,  and split the big arrays into smaller chunks..  

PlayBASIC Code: [Select]

; PROJECT : MEDIA INDEX banked demo
; AUTHOR  : 
; CREATED : 11/05/2021
; EDITED  : 11/05/2021
; ---------------------------------------------------------------------


   //  Allow 256 tables of 2^16 banks of indexes
   //  so 2^24 possible indexes
   dim MediaTable(256)




function AllocIndex(MediaIndex)
   
      //  High Bits are the media table 
      mediaTableindex    = MediaIndex >>16
      index             = MediaIndex &  $ffff

      Thisbank=MediaTable(MediaTableIndex)
      if ThisBank=0
               //  Here we're Use a PB BANK TO simulate a memory allocation
               ThisBank = NewBank( (2^16)*4)               
               MediaTable(MediaTableIndex)=ThisBANK
      endif

      // Check if this was previously allocated ?
      if    PeekBankInt(ThisBank,Index * 4)   
            //  free this since it was in use
            FreeIndex(MediaIndex)
      endif

      // Tag This MEDIA INDEX as in use (this would be a pointer to the resoure in real life)
      POkeBankInt ThisBank,Index * 4, true   
   
EndFunction


function FreeIndex(MediaIndex)
   
      //  High Bits are the media table 
      mediaTableindex = MediaIndex >>16
      index           = MediaIndex & $ffff

      Thisbank=MediaTable(MediaTableIndex)
      if ThisBank
               //  here we'd release any data this thing uses
                                 
               //  then reset this index back to off
               POkeBankInt ThisBank,Index * 4, false   

      endif

   
EndFunction




Psub GetIndexStatus(MediaIndex)
   
      Status =0
      //  High Bits are the media table 
      mediaTableindex = MediaIndex >>16
      index           = MediaIndex & $ffff

      Thisbank=MediaTable(MediaTableIndex)
      if ThisBank
            // check if this is in use or not
            Status = PeekBankInt(ThisBank,Index * 4)
      endif
   
EndPsub Status










      //  Test Library
      
      setfps 60
      
      do
         cls         

         //  Randomly Alloc 
         mediaIndex = rnd($fffff)         
         AllocIndex(MediaIndex)



         //  Compute useds Indexs 
         Count=0
         For lp=0 to 255
            if MediaTable(lp)
               StartIndex = lp * $10000
               EndIndex       = (lp+1) * $10000
               for index=StartIndex to EndIndex-1
                  Count+=GetIndexStatus(Index)
               next
            endif
         next
         print "Media Count:"+str$(Count)
         print ""

         //  Show the used CHUNKS OF indexes

         Xpos=0
         Ypos_ScreenTop = GetCursorY()
         Ypos=Ypos_ScreenTop
         TH = GetTextHeight("|")
         for lp =0 to 255
            ThisBank = MediaTable(lp)
            if ThisBANK
               baseIndex = lp * $10000
               if Ypos+TH => GetScreenHeight()
                  Xpos   =Xpos+125
                  Ypos = Ypos_ScreenTop
               endif
               Text Xpos,Ypos, "Range:"+str$(BaseIndex)
               Ypos+=TH
            endif
            
            
         next


         sync         
      loop

     

[stevmjon]

thanks for the demo kev.

i spend a some time going through it, but i initially only got the first 3 functions only. i was gonna mention there is no do-loop, but when i pressed reply to say this, the full code showed up then. now i can see all the code, lol. now it is 2 functions, 1 psub, and do-loop. it makes sense now.

i have already learned more about bits, bytes, bit shifting, and why we have a range of @+2gig to @-2gig. and that was from the first 3 functions i initially got earlier.
now to go through the rest of the code. learning is fun (that is what i tell myself when i am about to rage quit).

[kevin]

  Toying with BITS is fun STEVE :)  I'm serious.. it's fun and very useful


 Anyway..  There's a few annoying things I'm actually concerned about here,

      1)  if we have all the media data in one big table and that table needs to be resized,  there's  big bottle neck to expand/shrink the table..   Try setting the Sprites to a 1,000,000 for example..   on older system(s) it chokes big time

PlayBASIC Code: [Select]

   do
      cls 0
      frames++
      spritequantity 1000

      //  see how long it takes to resize from 1000 to a 1000000
      t=timer()
      spritequantity 1000000
      tt#+=timer()-t
      
      print "Average Resize Time:"+str$(tt#/frames)   
      sync
   loop spacekey()   

      2)  if the media resource table is being resized / shrunk, then I can't have a secondary thread read from the table as it's unsafe (see randomly crash)  

[stevmjon]

i am going through the code, step by step, and can now see how handy binary bits are. they are useful.

you used bit shifting to read the higher bits only, and also used & (AND) to only use the lower bits. also hex numbers are handy with binary too.
i wondered why you kept using hex, now i understand. saves typing large binary numbers.

i have a few more questions about the first demo code. i am not sure why you are allocating ((2^16)*4) bytes for the bank size. this is around 1/4 Meg.
16 bits = 2^16 = 65,536 numeric value. then this is multiplied by 4 ? this is done each time you enter a value into the MediaTable(n) array.

well it's late so i may not be thinking straight. the more i learn and understand, the more i want to know. it's a never ending cycle...lol.

[kevin]

i wondered why you kept using hex, now i understand. saves typing large binary numbers.

   just easier to have big numbers when you want groups of bits.   You could use integers, binary or hex...   but Hex makes more sense in this case.   

i have a few more questions about the first demo code. i am not sure why you are allocating ((2^16)*4) bytes for the bank size. this is around 1/4 Meg.
16 bits = 2^16 = 65,536 numeric value. then this is multiplied by 4 ? this is done each time you enter a value into the MediaTable(n) array.

   The Bank represents 2^16  integers..   so the index needs to scaled by 4,  as one integer takes 4 bytes. 

[kevin]

     Here's a version that lets the ranges to be user defined..    it's a bit pompous but you get the idea.

     Run in DEBUG mode (F7) and check console for output.

PlayBASIC Code: [Select]

//  use 2^12 bits per block and have 2^8 blocks 
   constant Index_Low_Bits         = 12
   constant Index_High_Bits         = 8

   #print "BIT MASKS"
   #print " Low Bit Mask "+bin$(( $ffffffff >> ( 32 - Index_Low_Bits      )))
   #print "High Bit Mask "+bin$(( $ffffffff >> ( 32 - Index_High_Bits      )))
   #print ""
   
   for MediaIndex =0 to 100000 step 100

      Bank      = (MediaIndex >> Index_Low_Bits)                  & ( $ffffffff >> ( 32 - Index_High_Bits   )) 
      Index      =  MediaIndex & ( $ffffffff >>Index_Low_Bits )    & ( $ffffffff >> ( 32 - Index_Low_Bits      ))  

      // dump this console 
       #print "Index#"+str$(MediaIndex)+"  Bank["+str$(bank)+"]   ["+str$(Index)+"]"
 
   next

   Sync
   
   waitkey
   

       
      For a bit of trivia,  you can swap the $ffffffff values for decimal -1

[stevmjon]

well, i read the code above, and actually understood it without my eyes glazing over.
using & + bit shifting sure is handy.

: Bank increased by 1 every 42 loops
: Index reset every 42 loops but with an offset increase +4  (0,4,8,12,16,20,24 etc)

trivia tip is cool. i wondered how the values worked. so the lower 31 binary bits are value 0 to 2gig+, and if the highest bit (32nd bit) is 1, then the number is negative, and a zero means positive?

yay, i'm learning.

[kevin]

 Yep, the top bit is the SIGN, it looks a bit weird when you look at the bits but they do make sense for  negatives.. 

Code Select Expand


-16  %11111111111111111111111111110000
-15  %11111111111111111111111111110001
-14  %11111111111111111111111111110010
-13  %11111111111111111111111111110011
-12  %11111111111111111111111111110100
-11  %11111111111111111111111111110101
-10  %11111111111111111111111111110110
-9  %11111111111111111111111111110111
-8  %11111111111111111111111111111000
-7  %11111111111111111111111111111001
-6  %11111111111111111111111111111010
-5  %11111111111111111111111111111011
-4  %11111111111111111111111111111100
-3  %11111111111111111111111111111101
-2  %11111111111111111111111111111110
-1  %11111111111111111111111111111111
0  %00000000000000000000000000000000
1  %00000000000000000000000000000001
2  %00000000000000000000000000000010
3  %00000000000000000000000000000011
4  %00000000000000000000000000000100
5  %00000000000000000000000000000101
6  %00000000000000000000000000000110
7  %00000000000000000000000000000111
8  %00000000000000000000000000001000
9  %00000000000000000000000000001001
10  %00000000000000000000000000001010
11  %00000000000000000000000000001011
12  %00000000000000000000000000001100
13  %00000000000000000000000000001101
14  %00000000000000000000000000001110
15  %00000000000000000000000000001111
16  %00000000000000000000000000010000




PlayBASIC Code: [Select]

   for lp = -16 to 16
      #print str$(lp)+"  "+bin$(lp)
next

sync
waitkey
   

[stevmjon]

so, after all this binary chatting, that i have enjoyed learning, i haven't answered the original question, lol.

i guess a reduction to 16 bit should be fine. i haven't used high values for images/objects/sprites etc.

[kevin]

It's one of those things that once you set a limit people have a instant negative reaction,  but the reality is that you've always been limited..

What prompted this question is those ugly truths about having common chunks of big blocks of memory and the subsequent ownership issues that arise
when trying to do even simple memory management into threading.     If you have two bits of code looking at the same table without some type of please and thank yous between them you inevitably end up one thread is deleting/creating/resize something that other was using and boom it dies..

[kevin]

  Comparing Alternate BANK COMMAND set to internal command sets


     So enough talking bout this stuff, how does it work when implemented... Well..   on the surface our test library (a recreation of the bank commands) seems to be 2.9 times faster than the built in commands..

     Why is this ??  - Well I doubt that improvement is purely all about the INDEX mapping and structure caching which the newer approach uses solely,  but rather some of that gain is in how the runtime calls internal commands compared to externally bound command sets (LInkDLL's), which was vastly improved during the rebuilding of V1.65

 
     So can we just swap them over ?  - Not yet, the internal command sets have an Open/Close structure that linked DLL's don't have. meaning that when you start your program the command set is opened (stuff is initialized) and then when you END  or quit, then runtime calls the clean up routine to Close each command set, before shutting down the runtime.    So we'd need something like that build into the parser / runtimes for external DLLS..  

     But it does potentially take a step towards a more plug and plug command set.  

PlayBASIC Code: [Select]

Function GUI_TEST_BANKS()
   
   
   index=10
   for BankSize = 000 to 100000+1 step 5000
      cls
      size=banksize
      if Size<1 then size=1
      CreateBank index, Size
      PB_CreateBank   index, Size
   
   
   print "--[ BANK Info ]-------------------------------"   
   print "Bank Status:"+str$(PB_GetBankStatus(index))+ " Size:"+str$(PB_GetBankSize(index))+" Ptr:"+str$(PB_GetBankPtr(index))
   print ""
   maxframes = 10
         tt#=0
   for frame =0 to MaxFrames
      t=timer()
         for lp =0 to Size-1
            PB_PokebankByte index,lp,lp
            PB_PokebankByte(index,lp,lp)
            PB_PokebankByte(index,lp,lp)
            PB_PokebankByte(index,lp,lp)
            PB_PokebankByte(index,lp,lp)

            PB_PokebankByte(index,lp,lp)
            PB_PokebankByte(index,lp,lp)
            PB_PokebankByte(index,lp,lp)
            PB_PokebankByte(index,lp,lp)
            PB_PokebankByte(index,lp,lp)

            PB_PokebankByte(index,lp,lp)
            PB_PokebankByte(index,lp,lp)
            PB_PokebankByte(index,lp,lp)
            PB_PokebankByte(index,lp,lp)
            PB_PokebankByte(index,lp,lp)

            PB_PokebankByte(index,lp,lp)
            PB_PokebankByte(index,lp,lp)
            PB_PokebankByte(index,lp,lp)
            PB_PokebankByte(index,lp,lp)
            PB_PokebankByte(index,lp,lp)

         next
      tt#+=Timer()-t
next
R1#= tt#/Frame   
      print "Test #1: "+str$(r1#)+" Milliseconds"
         tt#=0

   for frame =0 to MaxFrames
      t=timer()
         for lp =0 to Size-1
            PokebankByte index,lp,lp
            PokebankByte index,lp,lp
            PokebankByte index,lp,lp
            PokebankByte index,lp,lp
            PokebankByte index,lp,lp

            PokebankByte index,lp,lp
            PokebankByte index,lp,lp
            PokebankByte index,lp,lp
            PokebankByte index,lp,lp
            PokebankByte index,lp,lp
            
            PokebankByte index,lp,lp
            PokebankByte index,lp,lp
            PokebankByte index,lp,lp
            PokebankByte index,lp,lp
            PokebankByte index,lp,lp

            PokebankByte index,lp,lp
            PokebankByte index,lp,lp
            PokebankByte index,lp,lp
            PokebankByte index,lp,lp
            PokebankByte index,lp,lp
            
            
         next
      tt#+=Timer()-t
next
R2#= tt#/Frame
   
      print "Test #2: "+str$(r2#)+" Milliseconds"
      
print ""
print "--[ RESULTS ]-------------------------------"   

print "         Result:  Test 1 is ["+str$(r2#/r1#)+"] times faster then test 2"
print "     Test Count:"+str$(MAxFrames)
print "Writes Per Test:"+str$((20*lp*MaxFrames)/(1000000.0))+" Megs "
;      for lp =0 to Size-1
;         #print PB_PeekbankByte(index,lp)
;         a=b
;   next

   #print "--[Words]---------------------------"
;   for lp =0 to Size-1
;         #print Hex$(PB_PeekbankWord(index,lp))
;         a=b
;   next
   #print "--[Integer]---------------------------"
;   for lp =0 to Size-1
;         #print Hex$(PB_PeekbankInt(index,lp))
;         a=b
;   next



   PB_DeleteBank Index   

   print ""
   print "--[ BANK After DELETE ]-------------------------------"   
   print "Bank Status:"+str$(PB_GetBankStatus(index))+ " Size:"+str$(PB_GetBankSize(index))+" Ptr:"+str$(PB_GetBankPtr(index))
   
   
   
   
   sync
 next



   waitkey   
   waitnokey
EndFunction

[stevmjon]

is this code something your experimenting with, because if i cut and paste the code and add at top the function name to call it, it must need a library/DLL also that you haven't included?

apart from this it's interesting...

[kevin]

    this is just some hodge podge test code atm..  

  interestingly though PB1.64P  outperforms 1.65 here for the internal command sets at least and is slower calling external functions.