A few Method to improve the performance of ordinary linkedlist

[wilbert]

wow , great , very nice idea, i have no knowledge about asm , thanks

Using pointers to repeatedly move to the next / previous element could have been done with PB code as well but asm is more optimized.
The main goal is to avoid having to call NextElement() or PreviousElement() repeatedly since that takes more time.

[idle]

Make it powers of 2 and it with p2-1 no div or mod required.

[StarBootics]

Make it powers of 2 and it with p2-1 no div or mod required.

Bit shifting is kind of fast. If some need a function to calculate NextPowerOfTwo() of a specific value there it is :

Code: Select all

  Procedure.i NextPowerOfTwo(Value.i)
    
    Value - 1 
    Value = Value | Value >> 1
    Value = Value | Value >> 2
    Value = Value | Value >> 4
    Value = Value | Value >> 8
    Value = Value | Value >> 16
    Value = Value | Value >> 32
    Value + 1
    
    ProcedureReturn Value
  EndProcedure

Best regards
StarBootics

[pjay]

To me this is all unecessarily complex; If you must access a linked list randomly then why not just create a full array index?

It'd probably be >10x faster than the method here - the only argument I can see against it is memory usage, but we're talking < 8mb for 1 million 64bit pointers in an era where we have gigabytes of ram on almost all devices.

[StarBootics]

To me this is all unecessarily complex; If you must access a linked list randomly then why not just create a full array index?

It depend on what you need to do with your data structure, if the order of the element is important and you want to delete or insert an item from the list it's easy. Try to do something similar with an array.

Each data structure have their pros and cons depending on what you want to do. If you want to see why sometime creating a custom data structure that can beat the standard data structure I recommend you to watch these videos on YouTube :

https://www.youtube.com/watch?v=sx4IIQL0x7c
https://www.youtube.com/watch?v=oewDaISQpw0

Best regards
StarBootics

[pjay]

Either you missed my point, or I didn't explain myself clearly.

Instead of building a partial index that requires an additional stage of navigation to get to the desired record, just build a full index, it should be far more performant.

[moricode]

Interesting demonstration of how PB is very fast at moving sequentially through List elements, but not so at random access. If you happen to traverse through the list sequentially though, or at least less randomly than the example, then this index method 1 becomes slower than PB's native SelectElement() — see below. We may need a bounds check, depending on usage, which slows it down only very slightly, otherwise it enters an infinite loop if the element doesn't exist. Very interesting though and of course all depends on the need.

Code: Select all

; Fast Test
For i = 0 To #DataSize
   SelectElementFast(MyData(), MyIndex(), i)
Next

[...]

For i = 0 To #DataSize
   SelectElement(MyData(), i)
Next

999999 [sequential ] seek (Indexed) Time =1436ms
999999 [sequential ] (Ordinary) Time =12ms

For the bounds check, I needed to add the below, otherwise a missing element caused it to go on forever...

Code: Select all

   K = Predict * #Index_Step
   While K < ID  ; <---- And K < 999999
      IF NextElement(MainList())
         K+1
      ENDIF
   Wend

Hi , Oso , please note that ,

Code: Select all

SelectElement Doc:

As lists don't use an index internally, this function will jump compulsory to every element in the list until the target position is reached which will take time if the list is large. If a faster method is needed, ChangeCurrentElement() should be used. 

the original selectelement() is not fast , and not make for sequential access . it is make for Random access , but it is slow in design seems it has no index build in , what i do is implement a index to boost the selectelement() speed , so call selectelementfast().

for any other things that need a sequential access , please use FOREACH/NEXT , or While NextElement() Wend .
this is what it make for.

thanks and best regards guy.