A few Method to improve the performance of ordinary linkedlist

[moricode]

A few Method to improve the performance of ordinary linkedlist

In many projects, i need to randomly lookup a large set of unknown size dynamically created user data , this make it difficult or impossible
to use fixed size array.

Most the time using linkedlist is the simplest way, but the accessing performance is getting worst and worst with a
very large element size, like say a few hundred thousands items or even a million items.

To overcome this short fall , some way of improvement was developed.



Method 1 : (Indexing Purebasic native linkedlist)

Indexing your purebasic native linkedlist, similar to the (RDBMS) database server index, but not the same way.

Create and populated your main data set linkedlist , then build a index of the main linkedlist element, in a step of 100's or 200's , not for every element.

Rebuild you index when you Add/Delete/Insert Elements.

Pro:
Improve random access time
easy to implement

Con:
Need to take care the index list when modifying or destroying the main linkedlist


Implementation code:

Code: Select all

; Please disable Debugger

; A few Method To improve the performance of ordinary linkedlist 
; Method 1 (Indexing Purebasic native linkedlist) :

#Index_Step = 300

; How to Choose INDEX STEP  ::  #Index_Step = Total Element / (between 2500 ~ 3300 )

Procedure ReBuildIndex(List MainList(), List Indexing() )
   Protected k
   ClearList(Indexing())
   
   ForEach MainList()
      IF k % #Index_Step = 0 
         AddElement(Indexing()): Indexing()=@MainList()
      ENDIF
      k+1
   Next
   
EndProcedure



Procedure SelectElementFast(List MainList(), List Indexing(), ID )
   Protected k , predict , *Element
   
   ; ------------------------------------------
   predict = (ID / #Index_Step ) 
   SelectElement(Indexing(),predict)
   *Element = Indexing()

   ChangeCurrentElement(MainList(),*Element)
   
   K = (Predict) * #Index_Step
   While K < ID
      IF NextElement(MainList())
         K+1
      ENDIF
   Wend
   
   IF K = ID
      ProcedureReturn MainList()
   ENDIF
   ; ------------------------------------------
   
   ProcedureReturn 0 ; Null
   
EndProcedure



; ================================================

OpenConsole()


; Example :
#DataSize = 999999


NewList MyData()
NewList MyIndex()

For i = 0 To #DataSize
   AddElement(MyData())
   MyData() = i
Next

ReBuildIndex(MyData(), MyIndex() )


; ---------------------------------------------
PrintN( "Check accuracy :")
SelectElementFast(MyData(), MyIndex() ,2150 )
PrintN("Fast Method 1 Select : Element 2150  , Value = "+ Str(MyData()))


SelectElement(MyData(),2150)
PrintN("Purebasic Select : Element 2150 , Value = "+ Str(MyData()))
; ---------------------------------------------

PrintN(" ======================================================")
PrintN( "benchmark test And comparison")

#TestLoop = 10000
; --------------------------------------------------
; Fast Test
Time_S = ElapsedMilliseconds()

For i = 1 To #TestLoop 
   idx = Random(#DataSize)
   SelectElementFast(MyData(), MyIndex() ,Idx )
Next

Time_E = ElapsedMilliseconds()

Time_Fast = Time_E - Time_S

; --------------------------------------------------
; Ordinary Test
Time_S = ElapsedMilliseconds()

For i = 1 To #TestLoop 
   idx = Random(#DataSize)
   SelectElement(MyData(),Idx )
Next

Time_E = ElapsedMilliseconds()

Time_Slow = Time_E - Time_S

; --------------------------------------------------

PrintN(Str(#TestLoop )+" Random seek (Indexed) Time ="+Str(Time_Fast)+"ms")
PrintN(Str(#TestLoop )+" Random seek (Ordinary) Time ="+Str(Time_Slow)+"ms")

Input()

Result :

Code: Select all

Check accuracy :
Fast Method 1 Select : Element 2150  , Value = 2150
Purebasic Select : Element 2150 , Value = 2150
======================================================
benchmark test And comparison
10000 Random seek (Indexed) Time =14ms
10000 Random seek (Ordinary) Time =2565ms

the improvement result is 160x faster then pb linkedlist in random seek selectelement()

ENJOY !


(coming more method later)

[idle]

That's quite an impressive improvement and it's not really that far off the speed of a map though it'll still be ~10x slower at scale. A map provides O(1) lookup, assuming you have sized it and the closest you'll get with your method is something near O(log 2 N) which would be a binary search. Its a very good speed improvement but shouldn't you just use a map?

thanks for sharing.

[moricode]

That's quite an impressive improvement and it's not really that far off the speed of a map though it'll still be ~10x slower at scale. A map provides O(1) lookup, assuming you have sized it and the closest you'll get with your method is something near O(log 2 N) which would be a binary search. Its a very good speed improvement but shouldn't you just use a map?

thanks for sharing.

Hi idle, the reason why linkedlist is chosen because i need to maintain the sequence of element when added to list, unfortunately MAP does not
keep the sequence , unless it do , then i will just use the MAP .

By the way then , this was triggering me to develop a MAP with sequence maintained , it's on the way.

Cheers

[idle]

A trie preserves key sequence order.
You can take a look at Squint, it's O(k) performance.

viewtopic.php?p=586544#p586544

[moricode]

Method 2 : Implement Unrolled LinkedList

study :
https://en.wikipedia.org/wiki/Unrolled_linked_list


Unrolled linkedlist is like dividing a giant Array (eg. a million items) , into many small Array blocks (eg.100 items per Array )
and then linked all this small array with linkedlist,

An well coded unrolled linkedlist has performance near array , if not same as array




More study and example code:

https://www.geeksforgeeks.org/unrolled- ... roduction/




i had done a simple implementation and the test result is wow , it is too fast , so i increase the test Loop To 50000 seek , only then it take 1ms

Code: Select all

Check accuracy :
Fast Method 1 Select : Element 2150  , Value = 2150
Purebasic Select : Element 2150 , Value = 2150
 ======================================================
benchmark test And comparison
50000 Random seek ( Method 1 ) Time =74ms
50000 Random seek (Ordinary) Time =13002ms
50000 Random seek (UnRolled) Time =1ms

it is 13000x faster then ordinary linkedlist , and 74x faster then Method 1 .

best regards

[benubi]

Nice idea, I wonder why I never thought of that myself - I might simply be not as bright.

You can even cascade the methods, so you would have an index2 of index. The only drawback or difference to a RDBMS is that you can only add sequentially (autokey+1), and not delete without rebuilding the entire list structures. But if your DB only grows and there are no deletions this is a very elegant way to do it in PB without any additional DB plugins (or user made modules like Tries and other trees).

[moricode]

Nice idea, I wonder why I never thought of that myself - I might simply be not as bright.

You can even cascade the methods, so you would have an index2 of index. The only drawback or difference to a RDBMS is that you can only add sequentially (autokey+1), and not delete without rebuilding the entire list structures. But if your DB only grows and there are no deletions this is a very elegant way to do it in PB without any additional DB plugins (or user made modules like Tries and other trees).

hi , benubi , yes you are right. most of my project is add element and select element, very rare even not using delete element and insert element.

DB like purchased order , customer list or invoice system ,usually do not delete rows , they only mark flag as "inactive" or "cancelled" or "disabled" , never actual deleted.

as for unroll linkedlist , is merging the power of array and the versatile and flexible of linkedlist,
combine with method 1 (indexing) , this is even give you the power of two's , very very very fast ...

i prefer this way compare to trees and other type because easy to understand and easy to code , and fast, too


Cheers

[highend]

By the way then , this was triggering me to develop a MAP with sequence maintained , it's on the way.

Any progress on that?

[moricode]

By the way then , this was triggering me to develop a MAP with sequence maintained , it's on the way.

Any progress on that?

The unrolled linkedlist was fully developed and was used in my private project a few years ago , some 2016 or so ,
and the code has been review and rewritten fully recently to further improve the binary size and memory and speed performance .
by this moment everything is in production.

the full source of unrolled linked list will not be open.
but i may share the algorithm and design concept of it if you interest.


for the " MAP with sequence maintained , and accept INTEGER keys " was done in a very early stage ,
performance and hashing is not perfect but IT IS WORKING .
not ready for production yet. if you was to has a peep on it , i will share it here or some where ?

[Oso]

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

[wilbert]

Method 2 : Implement Unrolled LinkedList

Very interesting. I hadn't heard of that.

Instead of using a LinkedList to hold the arrays, you might also consider using a structured array for that (an array of arrays).
Most likely it would be faster to access random data.

[moricode]

Very interesting. I hadn't heard of that.

Instead of using a LinkedList to hold the arrays, you might also consider using a structured array for that (an array of arrays).
Most likely it would be faster to access random data.

Hi,
my initial motivation of developing this unrolled linkedlist is that i can't find a suitable library to use in my projects.

Requirement:
1. able to handle a very large dataset and not greatly affect the performance ( when often DIM/REDIM a very-very huge array is not practical )
2. able to grow or shrink dynamically with INSERT,DELETE,ADD , ( list can do this easily )
3. High performance in speed and code efficiency , (array is the best)
4. Easy to understand and easy to implement algorithm , (so far , ARRAY and LIST is very easy to understand)
5. able to maintain the data sequence by its order (PB native map doesn't maintain order )
6. less memory overhead , (ordinary linkedlist has veryhigh memory overhead >66% overhead)
7. small code size and binary , possible just less than a few KB in binary

so , after searching , studying and experiment , we decide to develop a "Unroll linkedList" ,
https://en.wikipedia.org/wiki/Unrolled_linked_list
https://en.wikipedia.org/wiki/Unrolled_linked_list


it combines the power of array and the flexible of linkedlist , very low memory overhead (<2%) ,
small code size and binary , robust performance.

it is so easy to understand , easy to implement , easy to maintain and debug , even anyone could do it by himself.

so finally , we happy with it.

P/S
array of array will be hard time when DIM/REDIM the master array with a very-very huge data set , which you do not know the total in advance

[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

Method 1 example is use to show people that : there is a way and you could improve the ordinary slow functions , like linkedlist.
surprisingly it dose 'quite well' random seek performance by indexing it, i was shocked because i never thought before.

anyway , this is showcase example , good for random seek requirement.

i never use this method so far, i use unrolled linkedlist in method 2 on all my projects.

[wilbert]

@moricode,
A few suggestions on the code in your first post.

Using an array for indexing is a lot faster and takes up less memory.
With an array, #Index_Step = 100 would require less memory compared to #Index_Step = 300 of your original code.

Division and modulo are slow operations.
If you use a simple counter you reset each time #Index_Step is reached, the indexing procedure gets significantly faster.

Predicting the nearest indexed item instead of the previous one speeds things up a lot when accessing a random item.

Code: Select all

; Please disable Debugger

; A few Method To improve the performance of ordinary linkedlist 
; Method 1 (Indexing Purebasic native linkedlist) :

#Index_Step = 300

; How to Choose INDEX STEP  ::  #Index_Step = Total Element / (between 2500 ~ 3300 )

Procedure ReBuildIndex(List MainList(), Array Indexing.i(1) )
   Protected i, k = #Index_Step
   Dim Indexing.i(ListSize(MainList()) / #Index_Step)
   
   ForEach MainList()
     If k = #Index_Step
       Indexing(i)=@MainList() : i+1 : k=0
     EndIf
     k+1
   Next
   
EndProcedure



Procedure SelectElementFast(List MainList(), Array Indexing.i(1), ID )
  Protected k , Predict, ls = ListSize(MainList())
  
  If ID < ls
    ; ------------------------------------------
    Predict = ((ID + (#Index_Step >> 1)) / #Index_Step ) 
    k = Predict * #Index_Step
    If k >= ls : Predict - 1 : k - #Index_Step : EndIf
    
    ChangeCurrentElement(MainList(), Indexing(Predict))
    
    While k < ID And NextElement(MainList())
      k+1
    Wend
    
    While k > ID And PreviousElement(MainList())
      k-1
    Wend
    
    If k = ID
      ProcedureReturn MainList()
    EndIf
    ; ------------------------------------------
  EndIf
  
  ProcedureReturn 0 ; Null
  
EndProcedure



; ================================================

OpenConsole()


; Example :
#DataSize = 999999


NewList MyData()
Dim MyIndex.i(0)

For i = 0 To #DataSize
   AddElement(MyData())
   MyData() = i
Next

ReBuildIndex(MyData(), MyIndex() )


; ---------------------------------------------
PrintN( "Check accuracy :")
SelectElementFast(MyData(), MyIndex() ,2150 )
PrintN("Fast Method 1 Select : Element 2150  , Value = "+ Str(MyData()))


SelectElement(MyData(),2150)
PrintN("Purebasic Select : Element 2150 , Value = "+ Str(MyData()))
; ---------------------------------------------

PrintN(" ======================================================")
PrintN( "benchmark test And comparison")

#TestLoop = 10000
; --------------------------------------------------
; Fast Test
Time_S = ElapsedMilliseconds()

For i = 1 To #TestLoop 
   idx = Random(#DataSize)
   SelectElementFast(MyData(), MyIndex() ,Idx )
Next

Time_E = ElapsedMilliseconds()

Time_Fast = Time_E - Time_S

; --------------------------------------------------
; Ordinary Test
Time_S = ElapsedMilliseconds()

For i = 1 To #TestLoop 
   idx = Random(#DataSize)
   SelectElement(MyData(),Idx )
Next

Time_E = ElapsedMilliseconds()

Time_Slow = Time_E - Time_S

; --------------------------------------------------

PrintN(Str(#TestLoop )+" Random seek (Indexed) Time ="+Str(Time_Fast)+"ms")
PrintN(Str(#TestLoop )+" Random seek (Ordinary) Time ="+Str(Time_Slow)+"ms")

Input()

With a bit of inline asm/c code it can be even faster

Code: Select all

; Please disable Debugger

; A few Method To improve the performance of ordinary linkedlist 
; Method 1 (Indexing Purebasic native linkedlist) :

#Index_Step = 300

; How to Choose INDEX STEP  ::  #Index_Step = Total Element / (between 2500 ~ 3300 )

Procedure ReBuildIndex(List MainList(), Array Indexing.i(1) )
  Protected i, k = #Index_Step
  Dim Indexing.i(ListSize(MainList()) / #Index_Step)
  
  ForEach MainList()
    If k = #Index_Step
      Indexing(i)=@MainList() : i+1 : k=0
    EndIf
    k+1
  Next
  
EndProcedure

Procedure StepElements(*Element, StepCount)
  
  ; *Element must be a pointer to an existing list element.
  ; StepCount can be both positive or negative.
  
  CompilerIf Defined(PB_Backend_C, #PB_Constant) And #PB_Compiler_Backend = #PB_Backend_C
    !struct {void *next; void *prev;} *node;
    !if (p_element){
    !  node = p_element - sizeof(*node);
    !  if (v_stepcount > 0){
    !    while ((node = node->next) && --v_stepcount);
    !  } else if (v_stepcount < 0){
    !    while ((node = node->prev) && ++v_stepcount);
    !  };
    !  p_element = node ? ++node : 0;
    !}
    ProcedureReturn *Element
  CompilerElse
    CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
      !     mov  rax, [p.p_Element]
      !     test rax, rax
      !     jz   .l3
      !     mov  rcx, [p.v_StepCount]
      !     cmp  rcx, 0
      !     je   .l3
      !     lea  rax, [rax-16]
      !     jl   .l1
      !.l0: mov  rax, [rax]
      !     test rax, rax
      !     jz   .l2
      !     sub  rcx, 1
      !     jnz  .l0
      !     jmp  .l2
      !.l1: mov  rax, [rax+8]
      !     test rax, rax
      !     jz   .l2
      !     add  rcx, 1
      !     jnz  .l1
      !.l2: lea  rax, [rax+16]
    CompilerElse
      !     mov  eax, [p.p_Element]
      !     test eax, eax
      !     jz   .l3
      !     mov  ecx, [p.v_StepCount]
      !     cmp  ecx, 0
      !     je   .l3
      !     lea  eax, [eax-8]
      !     jl   .l1
      !.l0: mov  eax, [eax]
      !     test eax, eax
      !     jz   .l2
      !     sub  ecx, 1
      !     jnz  .l0
      !     jmp  .l2
      !.l1: mov  eax, [eax+4]
      !     test eax, eax
      !     jz   .l2
      !     add  ecx, 1
      !     jnz  .l1
      !.l2: lea  eax, [eax+8]
    CompilerEndIf
    !.l3:
    ProcedureReturn
  CompilerEndIf
EndProcedure


Procedure SelectElementFast(List MainList(), Array Indexing.i(1), ID )
  Protected k, Predict, *Element, ls = ListSize(MainList())
  
  If ID < ls
    ; ------------------------------------------
    Predict = ((ID + (#Index_Step >> 1)) / #Index_Step)
    k = Predict * #Index_Step
    If k >= ls : Predict - 1 : k - #Index_Step : EndIf
    *Element = StepElements(Indexing(Predict), ID - k)
    If *Element
      ChangeCurrentElement(MainList(), *Element)
      ProcedureReturn *Element
    EndIf
    ; ------------------------------------------
  EndIf
  
  ProcedureReturn 0 ; Null
  
EndProcedure



; ================================================

OpenConsole()


; Example :
#DataSize = 999999


NewList MyData()
Dim MyIndex.i(0)

For i = 0 To #DataSize
   AddElement(MyData())
   MyData() = i
Next

ReBuildIndex(MyData(), MyIndex() )


; ---------------------------------------------
PrintN( "Check accuracy :")
SelectElementFast(MyData(), MyIndex(), 2150)
PrintN("Fast Method 1 Select : Element 2150  , Value = "+ Str(MyData()))


SelectElement(MyData(),2150)
PrintN("Purebasic Select : Element 2150 , Value = "+ Str(MyData()))
; ---------------------------------------------

PrintN(" ======================================================")
PrintN( "benchmark test And comparison")

#TestLoop = 10000
; --------------------------------------------------
; Fast Test
Time_S = ElapsedMilliseconds()

For i = 1 To #TestLoop 
   idx = Random(#DataSize)
   SelectElementFast(MyData(), MyIndex() ,Idx )
Next

Time_E = ElapsedMilliseconds()

Time_Fast = Time_E - Time_S

; --------------------------------------------------
; Ordinary Test
Time_S = ElapsedMilliseconds()

For i = 1 To #TestLoop 
   idx = Random(#DataSize)
   SelectElement(MyData(),Idx )
Next

Time_E = ElapsedMilliseconds()

Time_Slow = Time_E - Time_S

; --------------------------------------------------

PrintN(Str(#TestLoop )+" Random seek (Indexed) Time ="+Str(Time_Fast)+"ms")
PrintN(Str(#TestLoop )+" Random seek (Ordinary) Time ="+Str(Time_Slow)+"ms")

Input()

[moricode]

@moricode,
A few suggestions on the code in your first post.

Using an array for indexing is a lot faster and takes up less memory.
With an array, #Index_Step = 100 would require less memory compared to #Index_Step = 300 of your original code.

Division and modulo are slow operations.
If you use a simple counter you reset each time #Index_Step is reached, the indexing procedure gets significantly faster.

Predicting the nearest indexed item instead of the previous one speeds things up a lot when accessing a random item.

@wilbert

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