[Implemented] Increasing speed of SelectElement

[MrMat]

Hi,

I'd like to see an increase in the speed of SelectElement as i mentioned in this thread:
viewtopic.php?t=12740&start=15

Here's code to demonstrate what i propose:

Code: Select all

#elements = 1000000

Structure test
  somedata.l
EndStructure

NewList list.test()

Structure elementdata
  *start.l
  *finish.l
  *current.l
  currentelement.l
  totalelements.l
EndStructure

Procedure.l NewSelectElement(*info.elementdata, newelement.l)
  *newpos.l
  loop.l
  distancecurrent.l = newelement - *info\currentelement
  If distancecurrent <> 0 And newelement >= 0 And newelement < *info\totalelements
    distanceend.l = *info\totalelements - newelement - 1
    If newelement <= distanceend And newelement <= Abs(distancecurrent) ; Closest to the start
      *newpos = *info\start - 8
      For loop = 1 To newelement
        *newpos = PeekL(*newpos) ; Loop forwards
      Next
      *newpos + 8
    ElseIf distanceend <= newelement And distanceend <= Abs(distancecurrent) ; Closest to the end
      *newpos = *info\finish
      For loop = 1 To distanceend
        *newpos = PeekL(*newpos - 4) + 8 ; Loop backwards
      Next
    ElseIf distancecurrent > 0 ; Closest to current position
      *newpos = *info\current - 8
      For loop = 1 To distancecurrent
        *newpos = PeekL(*newpos)
      Next
      *newpos + 8
    Else ; negative
      *newpos = *info\current
      For loop = 1 To -distancecurrent
        *newpos = PeekL(*newpos - 4) + 8
      Next
    EndIf
    *info\current = *newpos
    *info\currentelement = newelement
  EndIf
  ProcedureReturn *info\current
EndProcedure

For loopy = 1 To #elements
  AddElement(list())
  list()\somedata = loopy
Next

listinfo.elementdata
FirstElement(list())
listinfo\start = @list()
LastElement(list())
listinfo\finish = @list()
listinfo\totalelements = CountList(list())

; Test 1

runs = 100000
results.s = "Test 1 (forward access) with " + Str(#elements) + " elements and " + Str(runs) + " runs"
total = 0
time = - timeGetTime_()
For loop = 1 To runs
  SelectElement(list(), (loop-1) % #elements)
  total + list()\somedata
Next
time + timeGetTime_()
results + Chr(10) + "Standard method - Time (ms): " + Str(time) + " Total: " + Str(total)

FirstElement(list())
listinfo\current = @list()
listinfo\currentelement = 1

total = 0
time = - timeGetTime_()
For loop = 1 To runs
  ChangeCurrentElement(list(), NewSelectElement(listinfo.elementdata, (loop-1) % #elements))
  total + list()\somedata
Next
time + timeGetTime_()
results + Chr(10) + "New method - Time (ms): " + Str(time) + " Total: " + Str(total)

; Test 2

runs = 1000 ; Slower test so less runs
results + Chr(10) + "Test 2 (random access) with " + Str(#elements) + " elements and " + Str(runs) + " runs"
total = 0
RandomSeed(20)
time = - timeGetTime_()
For loop = 1 To runs
  SelectElement(list(), Random(#elements-1))
  total + list()\somedata
Next
time + timeGetTime_()
results + Chr(10) + "Standard method - Time (ms): " + Str(time) + " Total: " + Str(total)

FirstElement(list())
listinfo\current = @list()
listinfo\currentelement = 1

total = 0
RandomSeed(20)
time = - timeGetTime_()
For loop = 1 To runs
  ChangeCurrentElement(list(), NewSelectElement(listinfo.elementdata, Random(#elements-1)))
  total + list()\somedata
Next
time + timeGetTime_()
results + Chr(10) + "New method - Time (ms): " + Str(time) + " Total: " + Str(total)

MessageRequester("Results",results,#PB_MessageRequester_Ok)

This runs two tests, each of which compare the standard SelectElement to the procedure NewSelectElement which works by iterating to the required element either from the start of the list, from the end, or from the current element (whichever requires least iteration).

The first test is a simple loop through the elements. The speed increase is phenomenal (see below). You may say this speed increase could just as easily be programmed 'by hand' (with a PokeL) but why bother when SelectElement could do the work for us and bear in mind this code can give similar increases with other selections of elements and the coder doesn't even have to think about it.

The second test demonstrates random access. This is a bad test case for the proposed routine since it cannot latch onto a nearby known pointer as we jump all over the place. Even so it is still 2-3 times faster with the new method. If converted to assembler it should be even quicker.

Here are the results on my machine:

Test 1 (forward access) with 1000000 elements and 100000 runs
Standard method - Time (ms): 78418 Total: 705082704
New method - Time (ms): 6 8O Total: 705082704
Test 2 (random access) with 1000000 elements and 1000 runs
Standard method - Time (ms): 7992 Total: 512354336
New method - Time (ms): 2807 Total: 512354336

The total is a checksum to make sure both routines are accessing the same data. As a final note, this method, if written in assembler is almost guaranteed to always be faster than SelectElement. The only care needs to be taken when adding or removing elements to and from the list, in which case the elementdata structure needs to be updated. In practise i don't see this as a problem.

What do you think?

[Psychophanta]

I strongly support this request too.

[Fred]

I will see what can be done

[MrMat]

Awesome! Thanks for looking into it Fred

[GPI]

I will see what can be done

Maybe a sorted Pointer-Index-list. But please optional...

Code: Select all

 NewIndexList Test().string

[freak]

GPI: can you explain a little please? I'm not sure what you mean exactly..

[MrMat]

I think he means iterate through the list, creating an array of pointers to each element so that you can jump to any element instantly. That would be really fast but use up more memory and take time to set up each time the list is changed (eg. elements added or removed).