ArrayList - Doubly-linked Dynamic Array Data Structure

[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!

[jamirokwai]

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

[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

[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.

[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.

[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.

[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

[PrincieD]

Kuron: Did you copy all of the code? sounds like you're missing the Input() command at the end of the source

[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.

[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?

[Kuron]

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.

[moricode]

Good try !

there was some info about unroll linkedlist
A few Method to improve the performance of ordinary linkedlist viewtopic.php?t=81869

[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!

[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?

[NicTheQuick]

<...>
... 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.