Super Fast Dynamic Jump/Hash Table routines!

Share your advanced PureBasic knowledge/code with the community.
Post Reply
PrincieD
Enthusiast
Enthusiast
Posts: 651
Joined: Wed Aug 10, 2005 2:08 pm
Location: Yorkshire, England
Contact:
Contact PrincieD

Super Fast Dynamic Jump/Hash Table routines!

Post by PrincieD »

Hi guys here are my dynamic jump/hash table routines with benchmarks (I'm getting just under 10ms per 5,000,000).
The principle behind it is "programming" the lookup by daisy chaining optimised asm using the bytes as direct indexes.
I'd be interested to see what benchmarks people get and if anyone can squeeze more speed out! or quicker methods :)

Cheers!

Code: Select all

#elements = 50
#numberOfTests = 5000000

Procedure aligned_malloc(size.l, align.l)
    *mem.INTEGER = AllocateMemory(size + align + SizeOf(INTEGER) - 1)
    ;Debug *mem % 16
    a.l = align - (*mem % align)
    If a < SizeOf(INTEGER) : a + align : EndIf
    PokeI(*mem + a - SizeOf(INTEGER), *mem)
    ProcedureReturn *mem + a
EndProcedure

Procedure aligned_free(*mem)
    FreeMemory(PeekI(*mem - SizeOf(INTEGER)))
EndProcedure

Procedure createJumpTable(range, *defaultAddress, bytePos = 0)
    
    size = 16 + (range * SizeOf(integer))
    *jumpTable = aligned_malloc(size, 16)
    VirtualProtect_(*jumpTable, size, #PAGE_EXECUTE_READWRITE, @oldProtect)
    CopyMemory(?selectJumpTable, *jumpTable, ?selectJumpTable_end-?selectJumpTable)
    
    *pb.byte = *jumpTable + 2
    *pb\b = bytePos
    *p.integer = *jumpTable + 6
    *p\i = *jumpTable + 16
    
    *p.integer = *jumpTable + 16
    Repeat
        *p\i = *defaultAddress
        *p + SizeOf(integer)
    Until *p > *jumpTable + size
    
    ProcedureReturn *jumpTable
    
    selectJumpTable:
    ! mov al, byte [edx+0x01] ; 3 bytes, last byte is index
    ! jmp dword [0xFFFFFFFF+eax*4] ; 7 bytes
    selectJumpTable_end:
    
EndProcedure

Procedure createJumpTable2(range, *defaultAddress, pos = 0)
    
    size = 16 + (range * SizeOf(integer))
    *jumpTable = aligned_malloc(size, 16)
    VirtualProtect_(*jumpTable, size, #PAGE_EXECUTE_READWRITE, @oldProtect)
    CopyMemory(?selectJumpTable2, *jumpTable, ?selectJumpTable2_end-?selectJumpTable2)
    
    *pb.byte = *jumpTable + 3
    *pb\b = pos
    *p.integer = *jumpTable + 7
    *p\i = *jumpTable + 16
    
    *p.integer = *jumpTable + 16
    Repeat
        *p\i = *defaultAddress
        *p + SizeOf(integer)
    Until *p > *jumpTable + size
    
    ProcedureReturn *jumpTable
    
    selectJumpTable2:
    ! mov ax, word [edx+0x01] ; 4 bytes, last byte is index
    ! jmp dword [0xFFFFFFFF+eax*4] ; 7 bytes
    selectJumpTable2_end:
    
EndProcedure

Procedure setJumpTableAddress(*jumpTable, index, *address)
    *p.integer = *jumpTable + 16 + (index * SizeOf(integer))
    *p\i = *address
EndProcedure

Procedure getJumpTableAddress(*jumpTable, index)
    *p.integer = *jumpTable + 16 + (index * SizeOf(integer))
    ProcedureReturn *p\i
EndProcedure

Procedure isJumpTable(*address)
    *p.integer = *address + 6
    If *p\i = *address + 16
        ProcedureReturn #True
    EndIf
    ProcedureReturn #False
EndProcedure

Macro SelectJumpTable(jumpTable, value)
    ptrVal = @value
    EnableASM
    mov ecx, jumpTable
    mov edx, ptrVal
    DisableASM
    ! movzx eax, byte [edx]
    ! jmp dword [ecx+16+eax*4]
EndMacro

Procedure setJumpTableValueAddress(*jumpTable, value, *jumpaddress)
    
    *p.Ascii = @value
    
    *address = getJumpTableAddress(*jumpTable, *p\a)
    If Not isJumpTable(*address)
        *new = createJumpTable($FF, *address, 1)
        setJumpTableAddress(*jumpTable, *p\a, *new)
        *jumpTable = *new
    Else
        *jumpTable = *address
    EndIf
    
    *p + 1
    
    *address = getJumpTableAddress(*jumpTable, *p\a)
    If Not isJumpTable(*address)
        *new = createJumpTable($FF, *address, 2)
        setJumpTableAddress(*jumpTable, *p\a, *new)
        *jumpTable = *new
    Else
        *jumpTable = *address
    EndIf
    
    *p + 1
    
    *address = getJumpTableAddress(*jumpTable, *p\a)
    If Not isJumpTable(*address)
        *new = createJumpTable($FF, *address, 3)
        setJumpTableAddress(*jumpTable, *p\a, *new)
        *jumpTable = *new
    Else
        *jumpTable = *address
    EndIf
    
    *p + 1
    
    setJumpTableAddress(*jumpTable, *p\a, *jumpaddress)
    
EndProcedure

Procedure setJumpTableKeyValue(*jumpTable, key, value, *foundJumpAddress)
    
    *p.Ascii = @key
    
    *address = getJumpTableAddress(*jumpTable, *p\a)
    If Not isJumpTable(*address)
        *new = createJumpTable($FF, *address, 1)
        setJumpTableAddress(*jumpTable, *p\a, *new)
        *jumpTable = *new
    Else
        *jumpTable = *address
    EndIf
    
    *p + 1
    
    *address = getJumpTableAddress(*jumpTable, *p\a)
    If Not isJumpTable(*address)
        *new = createJumpTable($FF, *address, 2)
        setJumpTableAddress(*jumpTable, *p\a, *new)
        *jumpTable = *new
    Else
        *jumpTable = *address
    EndIf
    
    *p + 1
    
    *address = getJumpTableAddress(*jumpTable, *p\a)
    If Not isJumpTable(*address)
        *new = createJumpTable($FF, *address, 3)
        setJumpTableAddress(*jumpTable, *p\a, *new)
        *jumpTable = *new
    Else
        *jumpTable = *address
    EndIf
    
    *p + 1
    
    size = 16
    *valueAsm = aligned_malloc(size, 16)
    VirtualProtect_(*valueAsm, size, #PAGE_EXECUTE_READWRITE, @oldProtect)
    CopyMemory(?valueAsm, *valueAsm, ?valueAsm_end-?valueAsm)
    
    *pi.integer = *valueAsm + 1
    *pi\i = value
    
    *pi = *valueAsm + 7
    *pi\i = *valueAsm + 11
    
    *pi = *valueAsm + 11
    *pi\i = *foundJumpAddress
    
    setJumpTableAddress(*jumpTable, *p\a, *valueAsm)
    
    ProcedureReturn *valueAsm
    
    valueAsm:
    ! mov eax, 0xFFFFFFFF ; 5 bytes, last 4 is value
    ! jmp dword [0xFFFFFFFF] ; 6 bytes, last for patched to end
    ! db 0xFF, 0xFF, 0xFF, 0xFF
    valueAsm_end:
    
EndProcedure

Procedure setJumpTableKeyValue2(*jumpTable, key, value, *foundJumpAddress)
    
    *p.unicode = @key
    
    *address = getJumpTableAddress(*jumpTable, *p\u)
    If Not isJumpTable(*address)
        *new = createJumpTable2($FFFF, *address, 2)
        setJumpTableAddress(*jumpTable, *p\u, *new)
        *jumpTable = *new
    Else
        *jumpTable = *address
    EndIf
    
    *p + 2
    
    size = 16
    *valueAsm = aligned_malloc(size, 16)
    VirtualProtect_(*valueAsm, size, #PAGE_EXECUTE_READWRITE, @oldProtect)
    CopyMemory(?valueAsm, *valueAsm, ?valueAsm_end-?valueAsm)
    
    *pi.integer = *valueAsm + 1
    *pi\i = value
    
    *pi = *valueAsm + 7
    *pi\i = *valueAsm + 11
    
    *pi = *valueAsm + 11
    *pi\i = *foundJumpAddress
    
    setJumpTableAddress(*jumpTable, *p\u, *valueAsm)
    
    ProcedureReturn *valueAsm
    
    valueAsm:
    ! mov eax, 0xFFFFFFFF ; 5 bytes, last 4 is value
    ! jmp dword [0xFFFFFFFF] ; 6 bytes, last for patched to end
    ! db 0xFF, 0xFF, 0xFF, 0xFF
    valueAsm_end:
    
EndProcedure

If #PB_Compiler_Debugger
    MessageRequester("", "disable the debugger!")
    End
EndIf

NewMap testMap.i()

*address = 0
! mov [p_address], t3NotFound
;*jumpTable = createJumpTable($FF, *address)
*jumpTable = createJumpTable2($FFFF, *address)

*mem = AllocateMemory(#elements*SizeOf(integer))

*p.integer = *mem
For i = 0 To #elements-1
    
    value = Random($7FFFFFFF)
    
    *p\i = value
    *p + SizeOf(integer)
    
    testMap(Str(value)) = Random($7FFFFFFF)
    
    ! mov [p_address], t3NotFound
    ;setJumpTableValueAddress(*jumpTable, *p\i, *address)
    ;setJumpTableKeyValue(*jumpTable, value, Random($7FFFFFFF), *address)
    setJumpTableKeyValue2(*jumpTable, value, Random($7FFFFFFF), *address)
    
Next

OpenConsole()

*p.integer = *mem + (Random(#elements-1)*SizeOf(integer))
selection = *p\i

! mov [p_address], t3Found
;setJumpTableValueAddress(*jumpTable, selection, *address)
;setJumpTableKeyValue(*jumpTable, selection, 1337, *address)
setJumpTableKeyValue2(*jumpTable, selection, 1337, *address)

testMap(Str(selection)) = #True

Repeat
    
    If n % 2 = 0
        selection = Random($7FFFFFFF)
    Else
        selection = *p\i
    EndIf
    
    i = 0
    t = ElapsedMilliseconds()
    Repeat
        For *test.integer = *mem To *mem + ((#elements-1) * SizeOf(Integer)) Step SizeOf(Integer)
            If *test\i = selection
                t1FoundCount + 1
                Break
            Else
                t1NotFoundCount + 1
            EndIf
        Next
        i + 1
    Until i > #numberOfTests
    t = ElapsedMilliseconds()-t
    t1 + t
    PrintN("Test1: " + Str(t))
    
    
    i = 0
    t = ElapsedMilliseconds()
    Repeat
        *test.integer = *mem
        Repeat
        
            If *test\i = selection
                t2FoundCount + 1
                Break
            Else
                t2NotFoundCount + 1
            EndIf
            *test + SizeOf(integer)
        Until *test > *mem + ((#elements-1) * SizeOf(Integer))
        i + 1
    Until i > #numberOfTests
    t = ElapsedMilliseconds()-t
    t2 + t
    PrintN("Test2: " + Str(t))
    
    
    i = 0
    t = ElapsedMilliseconds()
    Repeat
        
        ;! mov ecx, [p_jumpTable]
        ;! mov edx, v_selection
        ;! movzx eax, byte [edx]
        ;! jmp dword [ecx+16+eax*4]
        ;SelectJumpTable(*jumpTable, selection)
        
        ! mov ecx, [p_jumpTable]
        ! mov edx, v_selection
        ! movzx eax, word [edx]
        ! jmp dword [ecx+16+eax*4]
        
        ! align 16
        ! t3Found:

            t3FoundCount + 1
        
            ;test = 0
            ;! mov [v_test], eax
            ;Debug "cool: " + test
            
            ! jmp t3Continue
            
        ! align 16
        ! t3NotFound:
        
            t3NotFoundCount + 1
        
        ! align 16    
        ! t3Continue:
        
        i + 1
        
    Until i > #numberOfTests
    t = ElapsedMilliseconds()-t
    t3 + t
    PrintN("Test3: " + Str(t))
    
    
    i = 0
    t = ElapsedMilliseconds()
    Repeat
        
        If testMap(Str(selection)) = #True
            t4FoundCount + 1
        Else
            t4NotFoundCount + 1
        EndIf
        
        i + 1    
    Until i > #numberOfTests
    t = ElapsedMilliseconds()-t
    t4 + t
    PrintN("Test4: " + Str(t))
    
    
    i = 0
    t = ElapsedMilliseconds()
    Repeat
        
        If selection = *p\i
            t5FoundCount + 1
        Else
            t5NotFoundCount + 1
        EndIf
        
        i + 1    
    Until i > #numberOfTests
    t = ElapsedMilliseconds()-t
    t5 + t
    PrintN("Test5: " + Str(t))
    
    Delay(1000)
    
    n + 1
Until n >= 6

PrintN("Test1 (for next comparison)     total: " + Str(t1))
PrintN("Test2 (repeat until comparison) total: " + Str(t2))
PrintN("Test3 (dynamic jump tables)     total: " + Str(t3))
PrintN("Test4 (hashmap)                 total: " + Str(t4))
PrintN("Test5 (single if comparison)    total: " + Str(t5))

Input()
ProGUI - Professional Graphical User Interface Library - http://www.progui.co.uk
Top
User avatar
STARGÅTE
Addict
Addict
Posts: 2090
Joined: Thu Jan 10, 2008 1:30 pm
Location: Germany, Glienicke
Contact:
Contact STARGÅTE

Re: Super Fast Dynamic Jump/Hash Table routines!

Post by STARGÅTE »

interesting approach, but the memory consumption is huge.
1.3 GB for just 5000 elements ... and it increases with increasing elements but why?
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Lizard - Script language for symbolic calculations and more ― Typeface - Sprite-based font include/module
Top
PrincieD
Enthusiast
Enthusiast
Posts: 651
Joined: Wed Aug 10, 2005 2:08 pm
Location: Yorkshire, England
Contact:
Contact PrincieD

Re: Super Fast Dynamic Jump/Hash Table routines!

Post by PrincieD »

STARGÅTE wrote:interesting approach, but the memory consumption is huge.
1.3 GB for just 5000 elements ... and it increases with increasing elements but why?
Hi STARGÅTE yep it does sacrifice memory for speed espicially whe "word" version, the byte version should be more respectable.
ProGUI - Professional Graphical User Interface Library - http://www.progui.co.uk
Top
PrincieD
Enthusiast
Enthusiast
Posts: 651
Joined: Wed Aug 10, 2005 2:08 pm
Location: Yorkshire, England
Contact:
Contact PrincieD

Re: Super Fast Dynamic Jump/Hash Table routines!

Post by PrincieD »

This is the byte version around 13 meg 5000 elements:

Test1 (for next comparison) total: 24355ms
Test2 (repeat until comparison) total: 28045ms
Test3 (dynamic jump tables) total: 7ms
Test4 (hashmap) total: 304ms
Test5 (single if comparison) total: 6ms

Code: Select all

#elements = 5000
#numberOfTests = 500000

Procedure aligned_malloc(size.l, align.l)
    *mem.INTEGER = AllocateMemory(size + align + SizeOf(INTEGER) - 1)
    ;Debug *mem % 16
    a.l = align - (*mem % align)
    If a < SizeOf(INTEGER) : a + align : EndIf
    PokeI(*mem + a - SizeOf(INTEGER), *mem)
    ProcedureReturn *mem + a
EndProcedure

Procedure aligned_free(*mem)
    FreeMemory(PeekI(*mem - SizeOf(INTEGER)))
EndProcedure

Procedure createJumpTable(range, *defaultAddress, bytePos = 0)
    
    size = 16 + (range * SizeOf(integer))
    *jumpTable = aligned_malloc(size, 16)
    VirtualProtect_(*jumpTable, size, #PAGE_EXECUTE_READWRITE, @oldProtect)
    CopyMemory(?selectJumpTable, *jumpTable, ?selectJumpTable_end-?selectJumpTable)
    
    *pb.byte = *jumpTable + 2
    *pb\b = bytePos
    *p.integer = *jumpTable + 6
    *p\i = *jumpTable + 16
    
    *p.integer = *jumpTable + 16
    Repeat
        *p\i = *defaultAddress
        *p + SizeOf(integer)
    Until *p > *jumpTable + size
    
    ProcedureReturn *jumpTable
    
    selectJumpTable:
    ! mov al, byte [edx+0x01] ; 3 bytes, last byte is index
    ! jmp dword [0xFFFFFFFF+eax*4] ; 7 bytes
    selectJumpTable_end:
    
EndProcedure

Procedure createJumpTable2(range, *defaultAddress, pos = 0)
    
    size = 16 + (range * SizeOf(integer))
    *jumpTable = aligned_malloc(size, 16)
    VirtualProtect_(*jumpTable, size, #PAGE_EXECUTE_READWRITE, @oldProtect)
    CopyMemory(?selectJumpTable2, *jumpTable, ?selectJumpTable2_end-?selectJumpTable2)
    
    *pb.byte = *jumpTable + 3
    *pb\b = pos
    *p.integer = *jumpTable + 7
    *p\i = *jumpTable + 16
    
    *p.integer = *jumpTable + 16
    Repeat
        *p\i = *defaultAddress
        *p + SizeOf(integer)
    Until *p > *jumpTable + size
    
    ProcedureReturn *jumpTable
    
    selectJumpTable2:
    ! mov ax, word [edx+0x01] ; 4 bytes, last byte is index
    ! jmp dword [0xFFFFFFFF+eax*4] ; 7 bytes
    selectJumpTable2_end:
    
EndProcedure

Procedure setJumpTableAddress(*jumpTable, index, *address)
    *p.integer = *jumpTable + 16 + (index * SizeOf(integer))
    *p\i = *address
EndProcedure

Procedure getJumpTableAddress(*jumpTable, index)
    *p.integer = *jumpTable + 16 + (index * SizeOf(integer))
    ProcedureReturn *p\i
EndProcedure

Procedure isJumpTable(*address)
    *p.integer = *address + 6
    If *p\i = *address + 16
        ProcedureReturn #True
    EndIf
    ProcedureReturn #False
EndProcedure

Macro SelectJumpTable(jumpTable, value)
    ptrVal = @value
    EnableASM
    mov ecx, jumpTable
    mov edx, ptrVal
    DisableASM
    ! movzx eax, byte [edx]
    ! jmp dword [ecx+16+eax*4]
EndMacro

Procedure setJumpTableValueAddress(*jumpTable, value, *jumpaddress)
    
    *p.Ascii = @value
    
    *address = getJumpTableAddress(*jumpTable, *p\a)
    If Not isJumpTable(*address)
        *new = createJumpTable($FF, *address, 1)
        setJumpTableAddress(*jumpTable, *p\a, *new)
        *jumpTable = *new
    Else
        *jumpTable = *address
    EndIf
    
    *p + 1
    
    *address = getJumpTableAddress(*jumpTable, *p\a)
    If Not isJumpTable(*address)
        *new = createJumpTable($FF, *address, 2)
        setJumpTableAddress(*jumpTable, *p\a, *new)
        *jumpTable = *new
    Else
        *jumpTable = *address
    EndIf
    
    *p + 1
    
    *address = getJumpTableAddress(*jumpTable, *p\a)
    If Not isJumpTable(*address)
        *new = createJumpTable($FF, *address, 3)
        setJumpTableAddress(*jumpTable, *p\a, *new)
        *jumpTable = *new
    Else
        *jumpTable = *address
    EndIf
    
    *p + 1
    
    setJumpTableAddress(*jumpTable, *p\a, *jumpaddress)
    
EndProcedure

Procedure setJumpTableKeyValue(*jumpTable, key, value, *foundJumpAddress)
    
    *p.Ascii = @key
    
    *address = getJumpTableAddress(*jumpTable, *p\a)
    If Not isJumpTable(*address)
        *new = createJumpTable($FF, *address, 1)
        setJumpTableAddress(*jumpTable, *p\a, *new)
        *jumpTable = *new
    Else
        *jumpTable = *address
    EndIf
    
    *p + 1
    
    *address = getJumpTableAddress(*jumpTable, *p\a)
    If Not isJumpTable(*address)
        *new = createJumpTable($FF, *address, 2)
        setJumpTableAddress(*jumpTable, *p\a, *new)
        *jumpTable = *new
    Else
        *jumpTable = *address
    EndIf
    
    *p + 1
    
    *address = getJumpTableAddress(*jumpTable, *p\a)
    If Not isJumpTable(*address)
        *new = createJumpTable($FF, *address, 3)
        setJumpTableAddress(*jumpTable, *p\a, *new)
        *jumpTable = *new
    Else
        *jumpTable = *address
    EndIf
    
    *p + 1
    
    size = 16
    *valueAsm = aligned_malloc(size, 16)
    VirtualProtect_(*valueAsm, size, #PAGE_EXECUTE_READWRITE, @oldProtect)
    CopyMemory(?valueAsm, *valueAsm, ?valueAsm_end-?valueAsm)
    
    *pi.integer = *valueAsm + 1
    *pi\i = value
    
    *pi = *valueAsm + 7
    *pi\i = *valueAsm + 11
    
    *pi = *valueAsm + 11
    *pi\i = *foundJumpAddress
    
    setJumpTableAddress(*jumpTable, *p\a, *valueAsm)
    
    ProcedureReturn *valueAsm
    
    valueAsm:
    ! mov eax, 0xFFFFFFFF ; 5 bytes, last 4 is value
    ! jmp dword [0xFFFFFFFF] ; 6 bytes, last for patched to end
    ! db 0xFF, 0xFF, 0xFF, 0xFF
    valueAsm_end:
    
EndProcedure

Procedure setJumpTableKeyValue2(*jumpTable, key, value, *foundJumpAddress)
    
    *p.unicode = @key
    
    *address = getJumpTableAddress(*jumpTable, *p\u)
    If Not isJumpTable(*address)
        *new = createJumpTable2($FFFF, *address, 2)
        setJumpTableAddress(*jumpTable, *p\u, *new)
        *jumpTable = *new
    Else
        *jumpTable = *address
    EndIf
    
    *p + 2
    
    size = 16
    *valueAsm = aligned_malloc(size, 16)
    VirtualProtect_(*valueAsm, size, #PAGE_EXECUTE_READWRITE, @oldProtect)
    CopyMemory(?valueAsm, *valueAsm, ?valueAsm_end-?valueAsm)
    
    *pi.integer = *valueAsm + 1
    *pi\i = value
    
    *pi = *valueAsm + 7
    *pi\i = *valueAsm + 11
    
    *pi = *valueAsm + 11
    *pi\i = *foundJumpAddress
    
    setJumpTableAddress(*jumpTable, *p\u, *valueAsm)
    
    ProcedureReturn *valueAsm
    
    valueAsm:
    ! mov eax, 0xFFFFFFFF ; 5 bytes, last 4 is value
    ! jmp dword [0xFFFFFFFF] ; 6 bytes, last for patched to end
    ! db 0xFF, 0xFF, 0xFF, 0xFF
    valueAsm_end:
    
EndProcedure

If #PB_Compiler_Debugger
    MessageRequester("", "disable the debugger!")
    End
EndIf

NewMap testMap.i()

*address = 0
! mov [p_address], t3NotFound
*jumpTable = createJumpTable($FF, *address)
;*jumpTable = createJumpTable2($FFFF, *address)

*mem = AllocateMemory(#elements*SizeOf(integer))

*p.integer = *mem
For i = 0 To #elements-1
    
    value = Random($7FFFFFFF)
    
    *p\i = value
    *p + SizeOf(integer)
    
    testMap(Str(value)) = Random($7FFFFFFF)
    
    ! mov [p_address], t3NotFound
    ;setJumpTableValueAddress(*jumpTable, *p\i, *address)
    setJumpTableKeyValue(*jumpTable, value, Random($7FFFFFFF), *address)
    ;setJumpTableKeyValue2(*jumpTable, value, Random($7FFFFFFF), *address)
    
Next

OpenConsole()

*p.integer = *mem + (Random(#elements-1)*SizeOf(integer))
selection = *p\i

! mov [p_address], t3Found
;setJumpTableValueAddress(*jumpTable, selection, *address)
setJumpTableKeyValue(*jumpTable, selection, 1337, *address)
;setJumpTableKeyValue2(*jumpTable, selection, 1337, *address)

testMap(Str(selection)) = #True

Repeat
    
    If n % 2 = 0
        selection = Random($7FFFFFFF)
    Else
        selection = *p\i
    EndIf
    
    i = 0
    t = ElapsedMilliseconds()
    Repeat
        For *test.integer = *mem To *mem + ((#elements-1) * SizeOf(Integer)) Step SizeOf(Integer)
            If *test\i = selection
                t1FoundCount + 1
                Break
            Else
                t1NotFoundCount + 1
            EndIf
        Next
        i + 1
    Until i > #numberOfTests
    t = ElapsedMilliseconds()-t
    t1 + t
    PrintN("Test1: " + Str(t))
    
    
    i = 0
    t = ElapsedMilliseconds()
    Repeat
        *test.integer = *mem
        Repeat
        
            If *test\i = selection
                t2FoundCount + 1
                Break
            Else
                t2NotFoundCount + 1
            EndIf
            *test + SizeOf(integer)
        Until *test > *mem + ((#elements-1) * SizeOf(Integer))
        i + 1
    Until i > #numberOfTests
    t = ElapsedMilliseconds()-t
    t2 + t
    PrintN("Test2: " + Str(t))
    
    
    i = 0
    t = ElapsedMilliseconds()
    Repeat
        
        ! mov ecx, [p_jumpTable]
        ! mov edx, v_selection
        ! movzx eax, byte [edx]
        ! jmp dword [ecx+16+eax*4]
        ;SelectJumpTable(*jumpTable, selection)
        
        ;! mov ecx, [p_jumpTable]
        ;! mov edx, v_selection
        ;! movzx eax, word [edx]
        ;! jmp dword [ecx+16+eax*4]
        
        ! align 16
        ! t3Found:

            t3FoundCount + 1
        
            ;test = 0
            ;! mov [v_test], eax
            ;Debug "cool: " + test
            
            ! jmp t3Continue
            
        ! align 16
        ! t3NotFound:
        
            t3NotFoundCount + 1
        
        ! align 16    
        ! t3Continue:
        
        i + 1
        
    Until i > #numberOfTests
    t = ElapsedMilliseconds()-t
    t3 + t
    PrintN("Test3: " + Str(t))
    
    
    i = 0
    t = ElapsedMilliseconds()
    Repeat
        
        If testMap(Str(selection)) = #True
            t4FoundCount + 1
        Else
            t4NotFoundCount + 1
        EndIf
        
        i + 1    
    Until i > #numberOfTests
    t = ElapsedMilliseconds()-t
    t4 + t
    PrintN("Test4: " + Str(t))
    
    
    i = 0
    t = ElapsedMilliseconds()
    Repeat
        
        If selection = *p\i
            t5FoundCount + 1
        Else
            t5NotFoundCount + 1
        EndIf
        
        i + 1    
    Until i > #numberOfTests
    t = ElapsedMilliseconds()-t
    t5 + t
    PrintN("Test5: " + Str(t))
    
    Delay(1000)
    
    n + 1
Until n >= 6

PrintN("Test1 (for next comparison)     total: " + Str(t1))
PrintN("Test2 (repeat until comparison) total: " + Str(t2))
PrintN("Test3 (dynamic jump tables)     total: " + Str(t3))
PrintN("Test4 (hashmap)                 total: " + Str(t4))
PrintN("Test5 (single if comparison)    total: " + Str(t5))

Input()
ProGUI - Professional Graphical User Interface Library - http://www.progui.co.uk
Top
box_80
Enthusiast
Enthusiast
Posts: 113
Joined: Mon Sep 03, 2012 8:52 pm

Re: Super Fast Dynamic Jump/Hash Table routines!

Post by box_80 »

Interesting stuff, you have my attention. :)
Top
User avatar
Kwai chang caine
Always Here
Always Here
Posts: 5357
Joined: Sun Nov 05, 2006 11:42 pm
Location: Lyon - France

Re: Super Fast Dynamic Jump/Hash Table routines!

Post by Kwai chang caine »

Very interesting
Thanks for sharing 8)
ImageThe happiness is a road...
Not a destination
Top
PrincieD
Enthusiast
Enthusiast
Posts: 651
Joined: Wed Aug 10, 2005 2:08 pm
Location: Yorkshire, England
Contact:
Contact PrincieD

Re: Super Fast Dynamic Jump/Hash Table routines!

Post by PrincieD »

Kwai chang caine wrote:Very interesting
Thanks for sharing 8)
No worries :) I've gone down a bit of a rabbit hole with this technique the past week or so (ahh! I should be working on ProGUI :oops:) and should have some more code to post soon.
ProGUI - Professional Graphical User Interface Library - http://www.progui.co.uk
Top
kinglestat
Enthusiast
Enthusiast
Posts: 732
Joined: Fri Jul 14, 2006 8:53 pm
Location: Malta
Contact:
Contact kinglestat

Re: Super Fast Dynamic Jump/Hash Table routines!

Post by kinglestat »

I get "assembler error" when I compile. What am I doing wrong?
I may not help with your coding
Just ask about mental issues!

http://www.lulu.com/spotlight/kingwolf
http://www.sen3.net
Top
Cyllceaux
Enthusiast
Enthusiast
Posts: 469
Joined: Mon Jun 23, 2014 1:18 pm
Contact:
Contact Cyllceaux

Re: Super Fast Dynamic Jump/Hash Table routines!

Post by Cyllceaux »

kinglestat wrote:I get "assembler error" when I compile. What am I doing wrong?
You mean:

Code: Select all

---------------------------
PureBasic - Assembler error
---------------------------
PureBasic.asm [696]:

 jmp dword [ecx+16+eax*4]

error: illegal instruction.
Maybe a x86/x64 bug?
Top
kinglestat
Enthusiast
Enthusiast
Posts: 732
Joined: Fri Jul 14, 2006 8:53 pm
Location: Malta
Contact:
Contact kinglestat

Re: Super Fast Dynamic Jump/Hash Table routines!

Post by kinglestat »

yes, exactly that (error)
I only use x64
I may not help with your coding
Just ask about mental issues!

http://www.lulu.com/spotlight/kingwolf
http://www.sen3.net
Top
Post Reply

Return to “Tricks 'n' Tips”