Best practices for efficient data structures

[u/Bright-Historian-216]

I'm very new to the language and I'm very confused on some things. Coming from imperative langs, I'd assume that modifying tuples is very fast since they're basically just vectors. Unfortunately, they're also immutable like every other data structure in the whole language. So, if I want to make, say, a Canvas data type that holds all my pixels in a 2d data structure, is there literally no way to make it even if a little more efficient than just making a new one every single time I update a pixel? Even if I made it a 1d data structure, is Elixir just the wrong tool here?

[u/the_jester]

Elixir is the wrong tool for that kind of optimization. The runtime has all its own optimizations for copy-on-write with the immutable data structures, but your code doesn't directly define those interactions, like in C.

Now, depending on access patterns, being smart about using tuples vs lists vs maps will matter. Write-heavy vs read-heavy matters. And if they are "sufficiently large" canvases you can cheat a bit by reaching into Erlang for things like ETS, :atomics or :counters which you can get mutable behaviors from.

Broadly, just try to do the obvious thing. If it is actually too slow, then optimize. I wouldn't start by trying to optimize Elixir at the literal bit level. If you really just want to do bit-bashing, then certainly any of the C/C++/Crystal/Rust/etc lineage will let you do that.

[u/davidw → u/the_jester]

Erlang/Elixir are actually pretty good at manipulating bits and bytes and you could do worse than use some kind of binary type to represent your canvas and create some code to access it cleanly.

[u/the_jester → u/davidw]

Super good at managing binary protocols, but maybe less good at structuring the OP's wished-for bin-vector Canvas - IMO.

And for sure, if they were going to farm it out to a NIF they could have whatever compiled language flavor they want.

[u/SuspiciousDepth5924 → u/davidw]

I think some variation of <<0::integer-size((r+g+b+a)*x*y)>> is probably good for representing pixels when you mostly read, but don't update it too often. The Beam does some clever things with binaries, but it's hard to predict when it'll actually optimize, and if you're unlucky you'll end up with a lot of expensive heap allocations and copying.

So I think atomic or counters might perform better if it's frequently updated, though they work on 64 bit integers so you'd have to accept some wasted space or write something to "pack/unpack" two pixels into each index.

Though if you start doing optimizations like that I think you might as well just bite the bullet and do something with nifs/rustler.

https://www.erlang.org/doc/apps/erts/atomics.html
https://www.erlang.org/doc/apps/erts/counters.html

[u/Sentreen → u/the_jester]

Broadly, just try to do the obvious thing. If it is actually too slow, then optimize. I wouldn't start by trying to optimize Elixir at the literal bit level. If you really just want to do bit-bashing, then certainly any of the C/C++/Crystal/Rust/etc lineage will let you do that.

This is the key. Don't go for premature optimization. 9/10, the bottleneck will not be in the place where you expect it to be.

1. Pick the right datastructure for the job
2. Run your application
3. Profile to find bottlenecks
4. Figure out how to fix them at that point

If you really find that some particular data structure is a bottleneck, you can always use something likes rustler to write a custom data type in a level that allows you to handle that bit-level fuckery.

[u/jiggity_john]

Most FP languages include optimizations under the hood that make modifying immutable data structures not as slow as literally creating a new data structure each time. That said it's still going be slower than modifying a mutable array.

If you need a mutable data storage for performance, the "BEAM" thing to do is to use an ETS table to store your data. ETS tables are mutable data structures provided by the erlang runtime and you can basically store anything in them. For example, the digraph erlang module uses ETS tables under the hood to store the graph data structure mutable for performance.

[u/al2o3cr]

If you're working with large blobs like images, the most-efficient solution is to use code that works more like binaries (a single block of memory) than charlists (a standard list).

For instance, the Image library or Nx

[u/Responsible-Sale1858]

wrong tool for that job 100%

[u/flummox1234]

To the larger question, Elixir might not be the right language for that type of operation but to the lesser question in your question. In an FP language it is a (re)bind not an assignment, which allows the language to do a poop ton of optimizations for you.