Page 2 of 3
Re: ArrayList - Doubly-linked Dynamic Array Data Structure
Posted: Sat Sep 23, 2023 5:17 pm
by Kuron
I keep forgetting to test this, but will do so later this evening when I jump on my system with PB on it. Extremely interesting!
Re: ArrayList - Doubly-linked Dynamic Array Data Structure
Posted: Sat Sep 23, 2023 6:06 pm
by jamirokwai
PrincieD wrote: Fri Sep 22, 2023 10:41 pm
jamirokwai: It's in the "Compiler Options" dialogue, there should be a checkbox called "Optimize generated code"
Found it, thanks!!
Here is the result
Code: Select all
List creation: 0ms
List population: 160ms
List iteration: 71ms
Array creation: 81ms
Array population: 15ms
Array iteration: 17ms
ArrayList creation: 0ms
ArrayList population: 127ms
ArrayList iteration: 127ms
List deletion/insertion: 195ms
ArrayList deletion/insertion: 226ms
List iteration: 56ms
ArrayList iteration: 27ms
List deletion/insertion: 196ms
ArrayList deletion/insertion: 190ms
List iteration: 60ms
ArrayList iteration: 25ms
Re: ArrayList - Doubly-linked Dynamic Array Data Structure
Posted: Sat Sep 23, 2023 6:14 pm
by PrincieD
jamirokwai: No worries and thanks! Wow, the ARM architecture is so much faster than x64 in general. With the ArrayList it seems like there's an initial iteration spike then it's super fast hmm
Re: ArrayList - Doubly-linked Dynamic Array Data Structure
Posted: Sat Sep 23, 2023 6:38 pm
by skywalk
If you see arrays are fastest, why use this?
For slower operations, you can use in memory SQLite tables.
Keep your code fast and lean and easily updatable.
Introducing new data structures should be for a strong reason.
It is fun to code and compare, but in the end, choose fastest and well tested.
Re: ArrayList - Doubly-linked Dynamic Array Data Structure
Posted: Sun Sep 24, 2023 8:02 am
by idle
There are all sorts of gotchas trying to get performance, cache locality is of course one you also need to consider structure alignment and eliminate branching where possible and to satisfy branch prediction. Out of order execution can give you more bangs for your buck if the branches an do independent code. Any lib function you call in your code that isn't inlined might cause a page fault and then you have to ask Is there a decent performace advantage to the time complexity of the algorithm in question otherwise you'll just be ecking out the last cycle of performance for a particular need which isn't bad but it's still O(n), or a binary search O(log n)or hash table O(1) or a trie O(k).
Also you have to be careful with the c backend doing speed tests, the optimizer is quite happy to throw out your test code if the results the same each loop.
Re: ArrayList - Doubly-linked Dynamic Array Data Structure
Posted: Sun Sep 24, 2023 12:47 pm
by PrincieD
idle:Thanks for the info, yes I agree at the end of the day it's about taking into consideration your needs and then using the most appropiate data structure. This algorithm for example is a good contender for updating lots of entities every frame where you need to remove and insert whilst preserving the order.
Re: ArrayList - Doubly-linked Dynamic Array Data Structure
Posted: Sun Sep 24, 2023 9:17 pm
by Kuron
This is all it gives me and then the window instantly closes. Very hard to get the info from the window before it closes.
Code: Select all
List creation: 0ms
List population: 587ms
List iteration: 227ms
Array creation: 367ms
Array population: 151ms
Array iteration: 146ms
ArrayList creation: 0ms
Re: ArrayList - Doubly-linked Dynamic Array Data Structure
Posted: Sun Sep 24, 2023 9:36 pm
by PrincieD
Kuron: Did you copy all of the code? sounds like you're missing the Input() command at the end of the source
Re: ArrayList - Doubly-linked Dynamic Array Data Structure
Posted: Mon Sep 25, 2023 1:30 am
by Kuron
Yes, the input command is there in the code I ran. Not sure why it instantly wants to close. I am using beta 9 of the 64 bit version. Have to be superhuman quick with ctrl+a and ctrl+c to snag the text before the window closes.
Re: ArrayList - Doubly-linked Dynamic Array Data Structure
Posted: Mon Sep 25, 2023 8:59 am
by NicTheQuick
Maybe it just crashes. What does the Log window in the IDE say? And what happens if you run it with the Debugger enabled?
Re: ArrayList - Doubly-linked Dynamic Array Data Structure
Posted: Mon Sep 25, 2023 6:28 pm
by Kuron
NicTheQuick wrote: Mon Sep 25, 2023 8:59 am
Maybe it just crashes. What does the Log window in the IDE say? And what happens if you run it with the Debugger enabled?
Nothing in the log window, unless run with debugger on. Sadly can't copy and paste from the log window, GRRR! Slightly paraphrased:
waiting for executable to start
executable type windows 64bit unicode
executable started
the debugged executable quit unexpectedly
On another note, that was the first time I have ever used the debugger since buying PB in Jan of '04.
*edit* Concerning for me that this is working for everybody else, but not for me. Reinstalled PB, still the same.
Re: ArrayList - Doubly-linked Dynamic Array Data Structure
Posted: Wed Sep 27, 2023 3:55 am
by moricode
Good try !
there was some info about unroll linkedlist
A few Method to improve the performance of ordinary linkedlist
viewtopic.php?t=81869
Re: ArrayList - Doubly-linked Dynamic Array Data Structure
Posted: Wed Sep 27, 2023 2:49 pm
by PrincieD
moricode: That's really cool, thanks for sharing! Funnily enough I've been thinking of something similar to the unrolled linked list the past couple of days!
Re: ArrayList - Doubly-linked Dynamic Array Data Structure
Posted: Sat Sep 30, 2023 7:47 am
by pjay
What I take away from this data ...
Code: Select all
Array creation: 196ms
Array population: 95ms
Array creation: 266ms
Array population: 91ms
Array creation: 284ms
Array population: 75ms
Array creation: 288ms 308ms 291ms
Array population: 69ms 81ms 69ms
Array creation: 112ms 112ms 112ms
Array population: 80ms 75ms 73ms
Array creation: 79ms
Array population: 26ms
Array creation: 81ms
Array population: 15ms
... is that the array creation time is a lot slower than I think it should be.
The time to AllocateMemory() the same contiguous memory size that the array uses here takes < 1ms on my system - can anyone explain to me what's going on "under the hood" during the array initialization that would cause this?
Re: ArrayList - Doubly-linked Dynamic Array Data Structure
Posted: Sat Sep 30, 2023 1:42 pm
by NicTheQuick
pjay wrote: Sat Sep 30, 2023 7:47 am
<...>
... is that the array creation time is a lot slower than I think it should be.
The time to AllocateMemory() the same contiguous memory size that the array uses here takes < 1ms on my system - can anyone explain to me what's going on "under the hood" during the array initialization that would cause this?
If you create an array the whole allocated memory has to be cleared first or else every element would contain old data that was allocated before.
Because of that the `CreateArrayList` procedure uses the flag `#PB_Memory_NoClear` to make the allocation faster. But the usual `Dim` always zeros out the allocated memory which makes it slower.
So basically if you know that you are going to overwrite the content of each element anyway you can skip the process of zeroing everything before.