Hacker News Reader

Comment by cutler | Hacker News Reader

The deal-breaker for me with Elixir has always been the lack of real Elixir vectors rather than the crappy Erlang array library. Yes, I know you can use a Map with numeric keys but that's not the same.

View on HN

One of the many reasons I left Erlang is the lack of user types. I understand how the BeamVM got there. You build into the system the idea that there may be multiple nodes that communicate over the network. Those nodes will routinely pass through states where they are on different versions of code. Those types may have to be upgraded at upgrade time. Having no user types in your type system, just a fixed set of dynamic types that are relatively simple, mean that when it comes time to upgrade, you don't have to figure out how to load two method sets for the same module at the same time (and the corresponding multiplicity of states that can emerge beyond that); the new code can get the old value safely and easily since it has no methods on it, examine it, and upgrade it in a principled manner.

Nifty, powerful, and simple, like so much of Erlang.

But also like so much of Erlang, I think the modern approaches (several of them) that languages take to serialization is better. It's a good first pass cut at the problem, but I prefer all of the GRPC approach to the problem, the JSON approach to the problem, and honestly just letting the chips fall where they may with most modern serialization libraries. Treat the remote system as not entirely trusted and handle the messages with a bit of skepticism generally works out for quite a bit of scaling. And you get user types back, which means you are no longer stuck on the BeamVM's quite anemic data types.

If you look at the underlying implementations of an Erlang map, you'll see why you're not getting vectors anytime soon.

    1> dict:append(a, b, dict:new()).
    {dict,1,16,16,8,80,48,
          {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
          {{[],[[a,b]],[],[],[],[],[],[],[],[],[],[],[],[],[],[]}}}

It's a big pile of linked lists storing assoc lists held together by tuples, with all the component value being dynamically typed. It's nice they didn't cheat on that, but it is... not the most efficient approach to dictionaries, just the one enabled by their type system, such as it is.

Note that Erlang has maps since OTP 17, which I believe are implemented more efficiently than dicts.

Good point, though I think my point about user types still holds. It is very difficult to create any efficient user types of your own with the primitives Beam provides.

Yeah, the lack of user-defined types is definitely one of the biggest downsides of the BEAM.

Elixir builds types out of maps (using the struct) and you can build multiple dispatch operations over types using Protocol. If you want to pretty print your user types, you can implement the Inspect protocol.

For small fixed-length vectors, like 3D graphics, use tuples. They are contiguous in memory, fast to copy, and fixed O(1) time to access.

Interesting links:

- https://github.com/elixir-nx/nx

- https://github.com/elixir-explorer/explorer

So what do you use real arrays for? For 80% of programming lists are just fine. Are you doing cpu-bound numerical calculations?

Interviewing for when the interviewing is expecting an array (sarcasm intended).

All kidding aside, unless I'm interviewing at an Elixir shop, I've learned that Elixir is a little too weird for interviewers who don't know Elixir very well.

Same things arrays are used for in all mainstream languages ie. index-based access.

You want tuples. They've got index-based access, and all your useful things in erlang:element/2, setelement/3, append_element/3, delete_element/2, insert_element/3.

With a big caveat that modifying tuples isn't great for performance unless the compiler or optimizer determine that mutating the tuple is acceptable rather than providing a mutated copy.

I understood tuples are only optimised for a handful of elements.

This is correct. If you want a true array experience you have to use atomics or a nif.

That's not answering the question. I've written many thousands of lines of elixir and never used index based access.

Good for you but why do all mainstream languages, including Clojure, have them?

Because they're built on mutable datatypes. Elixir (and Erlang, and some flavors of lisp) are not. Instead of fudging it to make it syntactically "look like" an array access, elixir makes you flip through the list to understand the cost of what you're doing.

Even clojure's is a cheat.

Then maybe that's a shortcoming of absolute immutability.

The only time I've hit this is when implementing algorithms that assume constant time access and modification (a lot of algorithms assume this, and can't be swapped for index based maps easily)

This occurred somewhat recently when implementing stable topological sort. I ended up swapping List out for a Vector (Aja is library I used). I received a 100x performance improvement from it.

That's really the only time I've truly hit a List performance roadblock in 7+ years of Elixir.

What would be the difference between a "real vector" and a Map with numeric keys?

Maps are hashtables, Vectors are a contiguous area of memory where each element can be access by index referring to a specific address in that memory.

Vectors are usually also homogeneous about the data they hold, because each element should occupy the same fixed amount of memory, such as i*item_size gievs you back the offset of the element i in memory.

Anyway, in Elixir you can use the Erlang's :array module

I'm pretty sure erlangs :array is just a skin over tuple, so it's ~O(1) but not contiguous. might be O(log n) for dynamic arrays. The only truly array datatype in Erlang is :atomics

Erlang tuples are contiguous in memory for primitive values https://blog.edfine.io/blog/2016/06/28/erlang-data-represent...

Array doesn't guarantee to be put into a single tuple. It might be nested.

> What would be the difference between a "real vector" and a Map with numeric keys?

Access in O(1) instead of O(nlogn).

Data is immutable in Erlang. How do you know the runtime does not optimize Maps with numeric keys into arrays?

Data is also immutable in Clojure but it still has vectors.

Yeah, but Clojure vectors are actually trees built to be persistent based on ideas from Bagwell's hash array mapped tries (what Clojure maps are), so they're not technically O(1).

Both maps and vectors in Clojure are trees, albeit very shallow trees (32-way branching). The difference lies in the interfaces and the lookup methods. (Maps hash keys and use bits to know which subtree to descend, while vectors use index bits.)

Another thing with numeric maps is how insert would work. Swapping elements is trivial, but inserting a new one would require rewriting every subsequent entry.

Does nx not work for you? https://github.com/elixir-nx/nx/tree/main/nx#readme

There is an array library which creates a MapArray type but with list semantics and conforms to Enum and Collectable protocols -https://hexdocs.pm/arrays/Arrays.html. I've found it useful for when I need an array. Then there's NX for vectors - needing extra deps, granted.

Vs which other languages - do you have examples of better patterns?

all the C family

all the JVM languages

all the .Net languages

Rust

Ruby

Python

etc.

Thanks. What's the Ruby example? It's the one I'm most familiar in.

   irb(main):002:0> ["GFG", "GFG", "GFG", "GFG"].class
   => Array
   irb(main):003:0> {1 => "CFG", 2 => "CFG"}.class
   => Hash
   irb(main):006:0> {1 => "CFG", 2 => "CFG"}.keys.class
   => Array
   irb(main):007:0> {1 => "CFG", 2 => "CFG"}.values
   => ["CFG", "CFG"]
   irb(main):008:0> {1 => "CFG", 2 => "CFG"}.values.class
   => Array

Python lists are generally not contiguously allocated memory (I think it might be if you are storing integers less than 255), don't be fooled. That's why you need numpy.

I'm talking about Python arrays

https://docs.python.org/3/library/array.html

   >>> a = array('B', [1, 2, 3, 4, 5])
   >>> str(a.buffer_info()[1] * a.itemsize) + " bytes at address #" + str(a.buffer_info()[0])
   '5 bytes at address #4379640336'


   >>> b = array('l', [1, 2, 3, 4, 5])
   >>> str(b.buffer_info()[1] * b.itemsize) + " bytes at address #" + str(b.buffer_info()[0])
   '40 bytes at address #4380812752'

You can achieve a similar goal with the Akka framework on the JVM (functionally native with Scala). Uses the actor model and message passing for every concurrency goal achieved by Elixir. AND you can bundle in all your existing jars if the Java world matters to you.

Reply on news.ycombinator.com