Test and compare purebasic internal function and library

[UncleBen]

If you code a game or graphic , or some business applications , you will consider the speed and performance of the codes .
so to say , how you choose to use which data manipulation function , array or list or map ?

for gamer you may think array is the best for speed ,
but have you ever think about to test and compare purebasic array , list and map before ?

here is the test :

Code: Select all

; ===========================
;  Benchmark and Perfomance Test for PureBasic internal library function
;  MAP() vs List() vs Array()

OpenConsole("TEST MAP() vs List() vs Array()")
GuiWindow("TEST Map() vs List() vs Array() performance",800,600)

e=0
EditorGadget(0,5,5,790,590)
h
max=10000
LOOP=200000
LF$=Chr(10)

NewMap TestMap.l()
NewList  TestList.l()
Dim TestArray.l(max)

out$="Purebasic Map() vs List() vs Array() performance test and comparison"+lf$


out$+" Test on "+StrU(max)+" element size"+Chr(10)+Chr(10)

;-------------------------------------------------
Out$+"Sequential fill element with constant value test :"+LF$

start = ElapsedMilliseconds()            
For t=1 To max  ; fill map()
  TestMap(StrU(t))=t
Next 
fillMap=ElapsedMilliseconds() -Start

start = ElapsedMilliseconds()            
For t=1 To max  ; fill List()
  AddElement(TestList()):TestList()=t
Next 
fillList = ElapsedMilliseconds()-start            

start = ElapsedMilliseconds()            
For t=1 To max  ; fill Array()
  TestArray(t)=t
Next 
FillArray = ElapsedMilliseconds()-start            

out$ + "=== Test === Result ===( Sequential fill With "+StrU(max)+" elements" +lf$
out$ + "Fill Array = "+StrU(FillArray) + " ms"+ LF$
out$ + "Fill  MAP  = "+StrU(fillMap) + " ms"+ LF$
out$ + "Fill List  = "+StrU(fillList) + " ms"+ LF$+lf$

;------------------------------------------------
Out$+"Random index to fill element with constant value test :"+LF$

start = ElapsedMilliseconds()            
For t = 1 To LOOP
  TestMap(StrU(Random(max,1)))=5544  
Next
randomFillMap=ElapsedMilliseconds()-start

start = ElapsedMilliseconds()
max=max-1
For t = 1 To LOOP
  SelectElement(TestList(),Random(max-1,0))
  TestList()=5544  
Next
randomFillList=ElapsedMilliseconds()-start

max=max+1
start = ElapsedMilliseconds()            
For t = 1 To LOOP
  TestArray(Random(max,1))=5544
Next
randomFillArray=ElapsedMilliseconds()-start

out$ + "=== Test === Result ===(random fill into "+StrU(max)+" elements by "+StrU(loop)+"loops" +lf$
out$ + "Fill Array = "+StrU(randomFillArray) + " ms"+LF$
out$ + "Fill  MAP  = "+StrU(randomFillMap) + " ms"+ LF$
out$ + "Fill List  = "+StrU(RandomfillList) + " ms"+ LF$+lf$

;------------------------------------------------
Out$+"Random index to retrieve value from element test :"+LF$

start = ElapsedMilliseconds()            
For t = 1 To LOOP
  TestMap(StrU(Random(max,1)))=5544  
Next
randomGetMap=ElapsedMilliseconds()-start

start = ElapsedMilliseconds()
max=max-1
For t = 1 To LOOP
  SelectElement(TestList(),Random(max-1,0))
  TestList()=5544  
Next
randomGetList=ElapsedMilliseconds()-start

max=max+1
start = ElapsedMilliseconds()            
For t = 1 To LOOP
  TestArray(Random(max,1))=5544
Next
randomGetArray=ElapsedMilliseconds()-start



out$ + "=== Test === Result ===(random retrieve in "+StrU(max)+" elements by "+StrU(loop)+"loops" +lf$
out$ + "Get Array = "+StrU(randomFillArray) + " ms"+LF$
out$ + "Get  MAP  = "+StrU(randomFillMap) + " ms"+ LF$
out$ + "Get List  = "+StrU(RandomfillList) + " ms"+ LF$+lf$

Print(out$)
AddGadgetItem(e,0,out$)


Repeat : Until WaitWindowEvent()=#PB_Event_CloseWindow

Comparison Result

Purebasic Map() vs List() vs Array() performance test and comparison
Test on 10000 element size

Sequential fill element with constant value test :
=== Test === Result ===( Sequential fill With 10000 elements
Fill Array = 0 ms
Fill MAP = 8 ms
Fill List = 0 ms

Random index to fill element with constant value test :
=== Test === Result ===(random fill into 10000 elements by 200000loops
Fill Array = 2 ms
Fill MAP = 87 ms
Fill List = 547 ms

Random index to retrieve value from element test :
=== Test === Result ===(random retrieve in 10000 elements by 200000loops
Get Array = 2 ms
Get MAP = 80 ms
Get List = 557 ms

conclusion :
assigning value is as fast for array , list or map
but in random retrieve speed, map have a very good edge over list


so , i would recommend a priority for Array > Map > List

do not use LIST , use MAP instead !

cheers

[netmaestro]

Maps are actually a lot faster than your test shows. You are creating a map in its simplest form without specifying a bucket count. The default bucket count of a map created in this way is 512, which is far too small for 10k elements. You will have many many collisions, which result in the map being forced to create a sorted list for many (in this case probably all) of its buckets and this slows down its operation a great deal. A map is basically a combination of a hashing algorithm and an array, with the map key strings being hashed to decide which array element (bucket) they will be stored (or found) in. The idea in creating a map is to give it enough buckets to make collisions relatively rare so that most values can be stored and retrieved in the most efficient way possible. If say, three values all hash to bucket# 320 then storage and retrieval at element 320 require logic (a binary search iirc) to access the desired key. If no collisions exist at a given bucket, the value can be stored and retrieved there (after hashing, which is very fast) exactly as in a normal array. So the basic idea of a map is to trade memory redundancy, or inefficiency, for speed of search, which is usually a very good deal. Chess engines, for example, couldn't exist without them as they are in desperate need of search speed and don't care about memory.

All this to say, change your map creation code to this: NewMap TestMap.l(12500) and you should see a dramatic improvement in the speed test for the map.

[Bisonte]

All this to say, change your map creation code to this: NewMap TestMap.l(12500) and you should see a dramatic improvement in the speed test for the map.

- Very dramatic improvement !

Code: Select all

Purebasic Map() vs List() vs Array() performance test and comparison
 Test on 10000 element size

Sequential fill element with constant value test :
=== Test === Result ===( Sequential fill With 10000 elements
Fill Array = 0 ms
Fill  MAP  = 1 ms
Fill List  = 1 ms

Random index to fill element with constant value test :
=== Test === Result ===(random fill into 10000 elements by 200000loops
Fill Array = 1 ms
Fill  MAP  = 21 ms (With NewMap TestMap.l() = 73ms)
Fill List  = 536 ms

Random index to retrieve value from element test :
=== Test === Result ===(random retrieve in 10000 elements by 200000loops
Get Array = 1 ms
Get  MAP  = 21 ms (With NewMap TestMap.l() = 73ms)
Get List  = 536 ms

[mhs]

This is not a representative test of all use cases, it's just a presentation of some cases...

The true strength of a list is the fast adding and removing of elements when the maximum number of elements is unknown (in the beginning) or varies greatly. In this cases you would use a ReDim() on the array, which is slower (from a certain point) than the list.

[UncleBen]

Maps are actually a lot faster than your test shows. You are creating a map in its simplest form without specifying a bucket count. The default bucket count of a map created in this way is 512, which is far too small for 10k elements. You will have many many collisions, which result in the map being forced to create a sorted list for many (in this case probably all) of its buckets and this slows down its operation a great deal. A map is basically a combination of a hashing algorithm and an array, with the map key strings being hashed to decide which array element (bucket) they will be stored (or found) in. The idea in creating a map is to give it enough buckets to make collisions relatively rare so that most values can be stored and retrieved in the most efficient way possible. If say, three values all hash to bucket# 320 then storage and retrieval at element 320 require logic (a binary search iirc) to access the desired key. If no collisions exist at a given bucket, the value can be stored and retrieved there (after hashing, which is very fast) exactly as in a normal array. So the basic idea of a map is to trade memory redundancy, or inefficiency, for speed of search, which is usually a very good deal. Chess engines, for example, couldn't exist without them as they are in desperate need of search speed and don't care about memory.

All this to say, change your map creation code to this: NewMap TestMap.l(12500) and you should see a dramatic improvement in the speed test for the map.

Yes , it is way faster ...

but then what is the recommendation on the slot size ? something like 1.5x or 2x of needed element size ? or we just leave it by default ?

Purebasic Map() vs List() vs Array() performance test and comparison
Test on 10000 element size

Sequential fill element with constant value test :
=== Test === Result ===( Sequential fill With 10000 elements
Fill Array = 0 ms
Fill MAP = 4 ms
Fill List = 1 ms

Random index to fill element with constant value test :
=== Test === Result ===(random fill into 10000 elements by 200000loops
Fill Array = 2 ms
Fill MAP = 38 ms
Fill List = 550 ms

Random index to retrieve value from element test :
=== Test === Result ===(random retrieve in 10000 elements by 200000loops
Get Array = 2 ms
Get MAP = 30 ms
Get List = 539 ms

[UncleBen]

This is not a representative test of all use cases, it's just a presentation of some cases...

The true strength of a list is the fast adding and removing of elements when the maximum number of elements is unknown (in the beginning) or varies greatly. In this cases you would use a ReDim() on the array, which is slower (from a certain point) than the list.

is that you mean , if we don't know the total elements , and it is far larger than a 100k or 1m elements , even we have a map(slot 10k) , it will show the advantage of using list ?

if the map library was code as hash table array and ReDim ever since it grows , in this point i agree with you.

unless there is a different coding of map library , or giving a larger than know total slots , then it will beat the list at that mighty size ?

[UncleBen]

If we don't know how many slot to use

then by default (slot 512)
test on 200k elements

Code: Select all

Purebasic Map() vs List() vs Array() performance test and comparison
 Test on 200000 element size

Sequential fill element with constant value test :
=== Test === Result ===( Sequential fill With 200000 elements
Fill Array = 1 ms
Fill  MAP  = 1815 ms
Fill List  = 7 ms

Random index to fill element with constant value test :
=== Test === Result ===(random fill into 200000 elements by 200000loops
Fill Array = 3 ms
Fill  MAP  = 3147 ms
Fill List  = 11371 ms

Random index to retrieve value from element test :
=== Test === Result ===(random retrieve in 200000 elements by 200000loops
Get Array = 3 ms
Get  MAP  = 3136 ms
Get List  = 11295 ms

and if we put it (1000 slot ) when we still don't know how many to put
test on 200k elements

Code: Select all

Purebasic Map() vs List() vs Array() performance test and comparison
 Test on 200000 element size

Sequential fill element with constant value test :
=== Test === Result ===( Sequential fill With 200000 elements
Fill Array = 1 ms
Fill  MAP  = 531 ms
Fill List  = 8 ms

Random index to fill element with constant value test :
=== Test === Result ===(random fill into 200000 elements by 200000loops
Fill Array = 3 ms
Fill  MAP  = 1126 ms
Fill List  = 11217 ms

Random index to retrieve value from element test :
=== Test === Result ===(random retrieve in 200000 elements by 200000loops
Get Array = 3 ms
Get  MAP  = 993 ms
Get List  = 11257 ms

It show the edge of LIST is in adding new elements ....