bitwise trie

[idle]

fixed the AllocateMemory for linux
added ifs around set get

Code: Select all

;bitwise Trie wilbert, idle

Structure TrieNode   ; 4 * 4 bytes
  n.l[4]
EndStructure

Structure Trie
  *vt.l  
  nodes.TrieNode[256] ; offset 0
  firstMem.l          ; offset 4096
  currentMem.l        ; offset 4100
  memCount.l          ; offset 4104
  freeNodes.l         ; offset 4108
  nextNode.l          ; offset 4112
EndStructure

Structure TrieMem
  m.TrieNode[1023]    ; offset 0
  nextMem.l           ; offset 16368
EndStructure

Declare Trie_clear(*this.Trie)
Declare Trie_Free(*this.Trie)
Declare Trie_New() 
Declare Trie_SetValue(*this.Trie,key.l,value.l)
Declare.l Trie_GetValue(*this.Trie,key.l) 
Declare.s Trie_GetMemSize(*this.Trie) 

Interface Trie_Class 
  Clear()
  Free()
  Set(Key.l,value.l)
  Get(Key.l)
  GetSize.s()
EndInterface 

DataSection: vt_Trie: 
   Data.i @Trie_Clear()
   Data.i @Trie_Free()
   Data.i @Trie_SetValue()
   Data.i @Trie_GetValue()
   Data.i @Trie_GetMemSize()
EndDataSection
 

Procedure Trie_Clear(*this.Trie)
  Protected *mem.TrieMem, *nextMem.TrieMem, idx.l
  If *this
    *mem = *this\firstMem
    While *mem
      *nextMem = *mem\nextMem
      FreeMemory(*mem)
      *mem = *nextMem
    Wend
    FillMemory(*this\nodes[0], 4096)
    *this\firstMem = AllocateMemory(SizeOf(TrieMem))
    *this\currentMem = *this\firstMem
    *this\memCount = 1
    *this\freeNodes = 1023
    *this\nextNode = *this\currentMem
  EndIf 
EndProcedure

Procedure Trie_Free(*this.Trie)
  Protected *mem.TrieMem, *nextMem.TrieMem, idx.l
  If *this 
  *mem = *this\firstMem
  While *mem
    *nextMem = *mem\nextMem
     FreeMemory(*mem)
    *mem = *nextMem
  Wend
  FreeMemory(*this)
  EndIf 
  ProcedureReturn 0
EndProcedure

Procedure Trie_New()
  Protected *this.Trie
  *this = AllocateMemory(SizeOf(Trie))
  If *this
    *this\vt = ?vt_Trie 
     Trie_Clear(*this)
  EndIf  
  ProcedureReturn *this 
EndProcedure

Procedure.s Trie_GetMemSize(*this.Trie)
  Protected sz.s,size.i
  If *this
    size = SizeOf(Trie) + *this\memCount * SizeOf(TrieMem)
    If size < 1024
      sz = Str(size) + " bytes"
    ElseIf size < 1048576
      sz = Str(size/1024) + " kb"
    Else
      sz = Str(size/1048576) + " mb"
    EndIf
  EndIf 
  ProcedureReturn sz
EndProcedure

Procedure Trie_SetValue(*this.Trie, key.l, value.l)
   EnableASM
   MOV edx, *this
  MOV ecx, key
  !cmp edx, 0 
  !je lexit
  !add edx, 4
  !push ebx
  !push esi
  !rol ecx, 12
  !mov esi, ecx
  !and esi, 0xffc
  !add esi, edx
  !mov bl, 11
  !trie_set_loop:
  !mov eax, [esi]
  !and eax, eax                 ; check for zero pointer
  !jnz trie_set_cont
  ; ** allocate **
  !mov eax, [edx + 4112]        ; eax = *this\nextNode
  !mov [esi], eax
  !add dword [edx + 4112], 16   ; *this\nextNode + 16
  !dec dword [edx + 4108]       ; *this\freeNodes - 1
  !jnz trie_set_cont
  !push ecx
  !push edx
  CompilerSelect #PB_Compiler_OS
    CompilerCase #PB_OS_Windows 
      !push dword 16372
      !call _PB_AllocateMemory@4
    CompilerCase #PB_OS_Linux
      !PUSH   dword 16372
      !CALL   PB_AllocateMemory
       !add esp, 4
    CompilerCase #PB_OS_MacOS
      !sub esp, 4
      !push dword 16372
      !call _PB_AllocateMemory
      !add esp, 8
 CompilerEndSelect
  !pop edx
  !mov ecx, [edx + 4100]        ; ecx = *this\currentMem
  !mov [ecx + 16368], eax       ; set nextMem
  !mov [edx + 4100], eax        ; set currentMem
  !mov [edx + 4112], eax        ; set nextNode
  !inc dword [edx + 4104]       ; memCount + 1
  !mov dword [edx + 4108], 1023 ; freeNodes = 1023
  !pop ecx
  !mov eax, [esi]
  ; ** continue **
  !trie_set_cont:
  !rol ecx, 2
  !mov esi, ecx
  !and esi, 0xc
  !add esi, eax
  !dec bl
  !jnz trie_set_loop
  !mov eax, esi
  !pop esi
  !pop ebx
  MOV edx, value
  MOV [eax], edx
  DisableASM
  !jmp lexit1
  !lexit:
  !xor eax,eax
  !lexit1:
EndProcedure

Procedure.l Trie_GetValue(*this.Trie, key.l)
  EnableASM
  MOV edx, *this
  MOV ecx, key
  !cmp edx, 0 
  !je lexit2
  !add edx, 4
  !push esi
  !rol ecx, 12
  !mov esi, ecx
  !and esi, 0xffc
  !add esi, edx
  !mov dl, 12
  !trie_get_loop:
  !mov eax, [esi]
  !and eax, eax       ; check for zero pointer
  !jz trie_get_exit
  !rol ecx, 2         ; next 2 bits
  !mov esi, ecx
  !and esi, 0xc
  !add esi, eax
  !dec dl
  !jnz trie_get_loop
  !trie_get_exit:
  !pop esi
  DisableASM
  !jmp lexit3
  !lexit2:
  !xor eax,eax
  !lexit3:
  ProcedureReturn
EndProcedure


Global mt.Trie_Class = Trie_New()

Global size = 1024*1024
Global NewMap mp(size) 

start = ElapsedMilliseconds()
For a = 0 To size
  mt\Set(a,size-a)
Next

stop = ElapsedMilliseconds()
Trie_Add = stop-start

start = ElapsedMilliseconds()
For a = 0 To size
  mp(Str(a))=size-a; this line results in a crash on OS X when compiling without debug
Next
stop = ElapsedMilliseconds()
Map_add = Stop-start 

start = ElapsedMilliseconds()
For a = 0 To size
  x = mt\Get(a)
Next

stop = ElapsedMilliseconds()
Trie_time = stop-start

start = ElapsedMilliseconds()
For a = 0 To size
  x = mp(Str(a))
Next

stop = ElapsedMilliseconds()
map_time = stop-start

MessageRequester("Times","Trie Add = " + Str(Trie_Add) + " Trie Look = "+ Str(Trie_time)+#CRLF$+" Map Add= "+ Str(Map_add) + " Map look= " + Str(map_time))

mem.s = mt\GetSize()
MessageRequester("",mem)

mt\Free()

[idle]

Thanks wilbert,

I updated code to the first post.

I don't know why you're getting random IMA's on OSX from the test against the map but the speed difference is quite noticeable

Trie Add=90 , Trie Look = 71
Map Add=634, Map Look=291

[Zach]

I am once again humbled by idle's work...

I'd like to play around with this, not modify but actually use it. If that is what it is intended for..

But I'm not sure how can we get a brief overview of "how to use it" ?

Just a small example (make a list of cars, with some properties or something?) with some brief comments on the trie building/usage process.

[idle]

I am once again humbled by idle's work...

No that would be wilberts work, my version was slow.

I'd like to play around with this, not modify but actually use it. If that is what it is intended for..
But I'm not sure how can we get a brief overview of "how to use it" ?
Just a small example (make a list of cars, with some properties or something?) with some brief comments on the trie building/usage process.

It behaves just like using a map() except your keys are integers!
They're generally used for things like IP lookups in routers but it can be used for anything

Reasons to use it as opposed to using a map
your keys are numeric
you want a dynamic structure due to having an unbounded upper limit
you need to set and get items as fast as possible
you need a constant access time

Say you want to use it to access structured data like you've got 100 to 10,000,000 items
to lookup and it's impracticable to use an array because your key is in 32 bit range
plus you need to access the items randomly so a list is out (kind of)
and, a map would be fine but since you don't know how many items you're going to get
why gobble up all that ram and if you don't allocate the map it will slow to a crawl since it
will need to rehash all the data when it hits it's load limits.

so to use a trie for structured data
Load the items (cars) into the list of cars as they arrive and then set the trie to the address of the cars list element

Code: Select all

 
numeration 
  #salloon
  #hacthback 
  #stationwaggon
  #van
EndEnumeration

Structure cars 
  type.i
  color.i
  id.i
EndStructure 

Global NewList listCars.cars()  ;create a list of cars that you want random access to 
Global myTrie.Trie_Class = Trie_New()  ;create a Trie 

For a = 1 To 100   
  AddElement(listCars()) ;add items To the List 
  listCars()\color =a 
  listCars()\type = a % 4  
  listCars()\id = a*10000
  myTrie\Set(a*10000,@listCars()) ;add the index (key) to the Trie along with the address of the list element  
 Next 

 For a = 1 To 100  
  car = (Random(99)+1)*10000  ;pick a random car to look up 
  ChangeCurrentElement(listCars(),myTrie\Get(car)) ;change the list element to the item returned from the trie 
 Debug "look up car " + Str(car)
 Debug listCars()\color
 Debug listCars()\id 
 Select listCars()\type
   Case #salloon
     Debug "salloon"
   Case #hacthback
     Debug "hatchback"
   Case #stationwaggon
     Debug "Station Waggon"
   Case #van 
     Debug "van"
 EndSelect
Next  

myTrie\free()

does that help zac?

[idle]

Added a Foreach, I'm not certain if it's 100% though
It appears to be working properly performing a linear Scan and exploiting the properties of the data layout
which has distinct advantages since there's no need to use recursion or a stack to walk the tree.

[wilbert]

Another real world example is object association.
Objects (pointers) are usually very high values.
Using such a Trie, you can create a 'link' between objects; the key the pointer to one object, the value the pointer to another object.

[Zach]

Yes, that does help a little. Thank you

[void]

I don't suppose anyone has a version of this that will work for a 64bit application?

[wilbert]

I don't suppose anyone has a version of this that will work for a 64bit application?

It would have to be rewritten because of the 64 bit pointers and different ASM code.
The problem with using 64 bit values is that the Trie would consume much more memory and be significantly slower compared to the 32 bit version.

[void]

I don't suppose anyone has a version of this that will work for a 64bit application?

It would have to be rewritten because of the 64 bit pointers and different ASM code.
The problem with using 64 bit values is that the Trie would consume much more memory and be significantly slower compared to the 32 bit version.

I'm making a 64-bit application, though, and I don't see a way of using the 32-bit assembly code in a 64-bit PB application.

At the moment I'm using maps, since they work, but I was really hoping to have something better.

edit: in a private message, I was linked to the older non-assembly implementation, so I know about it, but it's so much slower than maps there doesn't seem to be much point in using it.

[wilbert]

For the current code, both keys and values are 32 bit integers.
What kind of key and value ranges do you need ?
It might help if you can describe what you are looking for.

[void]

It might help if you can describe what you are looking for.

This.

[kinglestat]

This is truly great work