PureBasic Forums - English

http://www.purebasic.com
https://www.purebasic.fr/english/

Super Fast Dynamic Jump/Hash Table routines!

https://www.purebasic.fr/english/viewtopic.php?t=75373

Page 1 of 1

Super Fast Dynamic Jump/Hash Table routines!

Posted: Sat May 23, 2020 5:37 pm
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()

Re: Super Fast Dynamic Jump/Hash Table routines!

Posted: Sat May 23, 2020 6:47 pm
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?

Re: Super Fast Dynamic Jump/Hash Table routines!

Posted: Sat May 23, 2020 7:03 pm
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.

Re: Super Fast Dynamic Jump/Hash Table routines!

Posted: Sat May 23, 2020 7:10 pm
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()

Re: Super Fast Dynamic Jump/Hash Table routines!

Posted: Sun May 24, 2020 7:04 pm
by box_80
Interesting stuff, you have my attention. :)

Re: Super Fast Dynamic Jump/Hash Table routines!

Posted: Tue Jun 02, 2020 5:14 pm
by Kwai chang caine
Very interesting
Thanks for sharing 8)

Re: Super Fast Dynamic Jump/Hash Table routines!

Posted: Tue Jun 02, 2020 5:46 pm
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.

Re: Super Fast Dynamic Jump/Hash Table routines!

Posted: Thu Jun 04, 2020 5:51 am
by kinglestat
I get "assembler error" when I compile. What am I doing wrong?

Re: Super Fast Dynamic Jump/Hash Table routines!

Posted: Thu Jun 04, 2020 7:41 am
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?

Re: Super Fast Dynamic Jump/Hash Table routines!

Posted: Thu Jun 04, 2020 8:31 am
by kinglestat
yes, exactly that (error)
I only use x64
All times are UTC+01:00
Page 1 of 1

Powered by phpBB® Forum Software © phpBB Limited