Optimizing diffarray

24

I think it would indeed be useful to have unsafeIndex and unsafeSet functions, which just error when you use them on old versions of the list. That is a good suggestion. I have opened Issue #17 to track it.

Still, I think accessing older versions does not necessarily have to be very expensive. This removal of intermediate versions optimization already helps a bit. But I have been thinking about other ways to improve performance further.

For example, I also have another idea about copying after enough accesses have happened to off-set the cost (see Issue #10). If that works out as I hope, it could give O(1) amortized access to old versions.

25

Yeah, sorry, I meant “a regular linearly implemented array” instead of a Diff Array?
(i.e. why keep the diff if you’re using it linearly?)

26

You wouldn’t. Ideally I imagine a different type that can be a drop in replacement for the normal diff array that you would use when you care more about performance than code. This might force you to do some manual sequencing to ensure you’re really using only the newest array which would otherwise be masked by the diff functionality.

27

I would not be better to have opportunistic mutability?

28

Can you elaborate on your question? I think diff arrays are a kind of opportunistic mutability. What would the alternative that you have in mind look like?

29

No exactly, Monadic code adds an unnesesary order that makes parallisation harder.

30

I am not really sure, but I was thinking of better, getting some type like

data DynamicArray elementType length where
    DymanicArrayEnd :: DymamicArray elementType 0
    DynamicArrayCons :: (elementType, DynamicArray elementType (length -1))
                       -> DymanicArray elementType length

And the compiler automatically compiles it to an Dynamic Array, not just that, but because it has defined length in the constructor, accessing it’s elements would be optimized to O(1) by the compiler.

31

For chess the most convenient would be an A*/Dijistra algorithm that can be interrupted at any moment, and resumed in a different node if the situation requires it.

32

Just read through this whole thread. Haven’t looked into the code yet but this was such a beautiful collaboration on a problem. Can y’all turn this into a blog post?

33

It’s on my radar: Write a blog post · Issue #8 · noughtmare/fleet-array · GitHub, but I wont have time to work on it this week.

2 Likes
34

It wasn’t as much collaboration as it way me saying “here’s a cool thing I like that doesn’t get enough attention” and then @jaror doing all the work haha

2 Likes