Using streams with recursive and/or deeply nested schemas

The update/2 clause that comment is placed before pattern matches on the current socket to determine whether the entry is already set, and if so it avoids streaming the children. In effect, it ensures that the children of a parent are only ever rendered the first time the tree is rendered (via the second update/2 clause, which is only reached when entry is not yet set), and after that they have to be updated individually by a send_update.

In fact, as I read more closely, I don’t believe it’s possible to update the structure of the tree at all in this example - but of course it is only an example.

Ah, now I notice it. Cool, thanks.

In my rant about handling structure separately i conclude not having access to the structure via the LiveComponent for each node is probably a good thing. TL/DR: I’m given to the idea of splitting the problem to separate concerns - one dealing exclusively with structure and the other with the contents of each node.

PS. I did better catching the gist of the gist once I realised I should regard TreeComponent as the NodeComponent because it doesn’t operate on the tree, only on a Node.

Note that this is what I described in one of my more recent replies (about the maps), and I found that approach to be helpful when dealing with updates that come in (via PubSub in my case) which touch a given record. The reason I took that path is that, otherwise, I would have to write recursive functions to “patch” the tree and I prefer to just use indirection (especially since I have very complex functionality which lends itself to recomputing the final tree as I explained).

However, what I meant with regards to the example was simply that, because the children list is never re-rendered, the structure of the tree can never change: i.e. you could never re-order a set of nodes, or move a node elsewhere. But it is just an example.

Ah, but if you were a philosopher you would recognize that a Node is nothing more than a smaller Tree

I didn’t notice it to be the same, and still don’t to be honest. It’s similar, related or even converging, but you described (the map) as a way to keep the nodes in a flat structure but if I understood correctly each node would still contain its own child list, whether that’s in effect a copy or a list of references by map key, the structure is still within the data. I’m proposing taking that just one step further and moving the knowledge about each node’s children out of the flattened data. Practically this means the association representing the list of children of a node reverted to :not_loaded.

The structure exlusively lives in a different calculated value and passed to the appropriate LiveView component as an assign, and a very lightweight one at that since the structure data fits snugly into a list of either integers or 2-tuples with an integer and recursive list. Once the structure is in that form and completely independent from the data/HTML associated with each id in the tree, any updates to it can be succintly reduced to a series of primitives which becomes the basis for updating the rendered content correctly in any situation from loading a different root which replaces all the content to adding or moving child nodes to updating a parent without touching any children to moving any portion of the tree from one parent to another. Those are all things we know how to do with trees and therefore with simple nested lists with a small enough memory footprint so we can make and compare several interim copies of it if we need to at very low cost. Plus you only need to do it once, ever. None of what you implement in structure manipulation gets affected in any way when there are changes to the content schemas.

Really, O(1)? I’d buy O(log n), but for the map code to find the key it has to, one way or another, search through the keys. My understanding is that the keys are kept in a balanced tree of sorts to minimise the number of comparisons it needs to make on average to find a key, but unavoidably as the number of keys grow access time must eventually get slower. I was also lead to believe that maps, sets and mapsets all use the exact same mechanism anyway, so I think your assumption that, being sets, mapsets would unavoidably be slower might be a little off or even false.

The way lists live in memory means all access has to be from the head walking recursively into each tail. That fundamental recursion is reduced to mere iteration through the magic of (originally Erlang’s) tail recursion detection and optimisation. The array-like semantics of lists is purely an illusion. It does come with substantial benefits, not the least of which is that a list may contain not only variable size elements but also elements of different types. Most of the list versions of Enum has been operating at maximum optimisation levels for a long time resulting in really good performance, but it will never be actually possible to access it like an array by calculating an element offset from an index.

Several of the underlying Erlang data structures including sets and gb_trees if I remember correctly, use internally defined and managed memory constructs which are opague to the user. That allows them to forfeit variable length elements and store data in fixed element size arrays with actual array access performance, i.e. calculating the address of an element as a starting point plus an index times the element size. This resulted in some highly efficient techniques from the world of advanced data structures and algorithms becoming available in Erlang and through that also to Elixir where they ended up being put to use to implement maps.

Erlang didn’t have maps (it had records, with metadata only at compile-time, not runtime, which wasn’t great) until Elixir formulated and implemented the concept which ultimately made its way bak to Erlang. The core of Elixir is still written in Erlang and I believe the data structures used to create Map wasn’t custom written exclusively for Elixir’s Map type. Map either used pre-existing Erlang library functions or what was done to make Map run faster was not exclusively for Map but helped improve efficiency for many other structures as well.

Disclaimer: It’s all open source but I’ve never been directly involved in creating or maintaing any of the Erlang, OTP, Elixir, Phoenix, Ecto or LiveView code nor have I made any sort of habit of trying to understand the underlying code. I’ve merely been professionally aware of Erlang from before it was open-sourced, evangelised many of my peers into taking a look at it who built their entire careers and businesses around it since, written a few small systems in Erlang and planned to write my life’s work’s proper server in Erlang until I discovered how far I can get how fast using Elixir and Phoenix instead. Which is a long way of saying I don’t know these things for fact because I lived it, but through keen observation over a long time, albeit usually at a fairly abstract level only. I did recently go read a bit of the Elixir code for clues as to how I might implement this unicorn dual-natured structure I thought I needed. Only after that (and the confirmation that Elixir lists are directly based on Erlang’s lists) did i truly realise that what is called a linked list is really a completely unbalanced tree turned on its side. That’s when all the pieces of the picture fell into place for me and I was able to see that all the “pointers” I thought I’d have to implement and manage in keeping with both Elixir and Erlang’s immutable data principles are already present in the list construct. It is absolutely perfect for the job and I couldn’t have hoped for a more optimal set of tools to manipulate them with already tested to the fullest possible extent.

It is clear as day to me that nested lists of primary key values represents the structural part of a tree so accurately and effeciently that there is not a shred of doubt in my mind that it’s the ideal choice of how to keep the strucure of any portion of the data in memory.

Yeah, or because I am one I differentiate between a Node and a Tree.

Well no, not exactly. Associative arrays in most programming languages are built on hash tables, which are O(1) if there are no hash collisions. Which is a big if, but people usually call them O(1) even though I think it’s technically Omega(1) for that reason. Note that the trade-off versus a tree here is that hash tables are not order-preserving.

Erlang maps are actually technically hash array-mapped tries which are a more exotic hybrid data structure. I’m not sure the exact performance characteristics but you can investigate further if you are interested

But sets have no method to retrieve an object by key at all - you would have to brute-force iterate through the whole thing.

The use-case I was describing was to store the tree in one data structure (like you said) and then join it with the associated records by looking them up in a map. You would not use a set for this.

The fact that sets internally use maps is an implementation detail.

Not quite. Let me try to demonstrate what I did but in the context of the (simpler) files/folders example.

There are three database tables with corresponding Ecto schemas: nodes, files, and folders. The nodes store the structure of the tree and contain foreign keys pointing to files and folders. The files and folders tables then store metadata, like names and so on.

%Node{id: 1, folder_id: 1, file_id: nil, parent_id: nil} # Root folder node
%Node{id: 2, folder_id: nil, file_id: 1, parent_id: 1} # File node
%Folder{id: 1, name: "elixir stuff"} # Folder metadata
%File{id: 1, name: "elixir.jpg"} # File metadata

This tree only has two nodes, but you could imagine an arbitrary filesystem structure. Now, you could write a recursive query to load the tree from the database. You then might join every Node with its associated Folder or File to get the whole tree.

The annoying bit, though, is that now if the user updates a folder (a rename, say) then the new version will come in over PubSub. And you have to recursively walk the tree, find that Folder node, and update it. This is valid, but there is another approach: use indirection.

Instead, you could avoid joining the files and folders to the nodes in the query, and instead load them separately. Then you can store them in maps (files = %{file.id => file} and so on) and join them at runtime by looking up the File for a file_id on a Node.

Now you can simply update the folders map when a new Folder comes in over PubSub, and then it will appear next render. I think this is in the same vein as what you are talking about, but correct me if I’m wrong.

There is one problem with this approach: LiveView is not smart enough to diff the arbitrary folders lookups, so any change to folders would re-render the entire tree and send the whole thing down the wire. I avoid that problem by materializing the tree myself into a simplified representation which I then pass to the LiveComponents. So the “simplified tree” comes out looking like:

%{
  id: 1, type: :folder, name: "elixir stuff", children: [
    %{id: 2, type: :file, name: "elixir.jpg"},
  ],
}

This might sound like a lot of extra complexity, but my use-case is very complicated because the UI is highly interactive and has a lot of moving parts. I iterated several times before arriving at this design, which I found to be radically simpler and more performant. Your situation may vary of course.

I think we’ve misunderstood each other on this. Map for the flattened content is spot on and I was discussing how one can store the structure as nested lists. I believe you made reference to using maps in the context of the streams discussion before I decided to physically split the structure and content. But it’s no issue, we’re in agreement that the bulky node data can live in maps if you’re going to keep them in memory, or loaded from database if you need to save on memory and if you need it, they can go into streams as well. As long as you can “surgically” remote control the DOM, i.e. to change the children shown content of container or not depending on how the structure changes, it should work well.

I haven’t yet figured out if it really will require a LiveComponent per node as per the example or not or what the overheads for that is like, but I’ll get there.

If you want to minimize diffs over the wire you will probably want one LiveComponent per node as discussed previously. The overhead for LiveComponents is not very large, they are really just a vehicle for maintaining the diffs and that overhead is obviously unavoidable. Importantly LiveComponents live in the same process as the parent LiveView so when you pass things to them they will share that memory (no copying).

Yes, that is a LiveView challenge that to date we’ve only seen one viable solution for. I’m hoping more will come to light.

Our approaches are converging. I’ve taken the simplification of the tree view a whole lot further until it genuinely only contains the IDs by which to find the actual content from whereever they are, but it’s the same principle. You’re storing the simplified tree still in nested maps, I’m using essentially nested lists or lists of either integers (meaning it’s a leaf node) or tuples {id, child_id_list} meaning it’s a branch or node with children.

For completeness, I’m actually storing the structure in two parts. Both are list based, but the semantics are slightly different. The first is a straight list of ids representing the path to the node that forms the “root” of the tree data being displayed, like breadcrumbs. All the nodes in that list (must have) children (in order to be part of the path) but I’m not storing any detail about how many other siblings each node miight have or such as that’s not relevant data. The second part is the recursive structure of the part of the data for which HTML has been generated and sent to the client that’s been extracted from the nested associations before they’re flattened (with the recursive association reset to not_loaded).

The jury is still out (in my case) about that (both the diffs part and the unavoidability of the overhead). I don’t have sufficient command over all the tools at my disposal just yet. It is obviously in my interest to keep the load per user session to a minimum, but there’s still too many variables and at some point it will have a run-in with the law of diminishing returns.