Live CEOing Ep721: Language Design Review for Data Structures

Okay. Hi, everyone. This is a Wolfram language design review about data structure which we introduced, what, two years ago? Three years ago.

12.1.

So a few years ago. It's quite. Quite a few years.

Two years, three, whatever. I don't know, some number of years ago. Okay, take a look at the current data structures.

Yeah, fine.

So, well, current data structures. This is the list. Current in 13.3.

Let's talk about who uses them and for what. So, I mean, I've used them a few times. Basically, I have some code and I realize, oh, my gosh, I can make it much more efficient by using some known data structure rather than letting the system sort of figure that out for itself.

Right, right.

Yes.

Yes.

I wonder whether an LLM would have a fighting chance of figuring out what kind of data structure some particular. I mean, even a piece of code. What you know is, could this piece of code be optimized by using a given data structure?

Interesting.

Hard to know.

Yeah, no, it's worth trying, I think. I mean, and then. Okay, so which of these do you think have been most popular?

I think the. I mean, I'm just speaking. I think the bit vector. I think the. Probably the, you know, dynamic array or the. Or the extensible vector.

I think I've used the hash set before. I think another one that I think I've used, although this is a bit random, is I've used, I think, value because it's an easy way to basically make mutable stuff.

Right, right.

Does anybody remember what we used for that host tag system thing? I don't remember exactly, but. Okay. All right. So, and are there ones where. I mean, another question is sort of. There's sort of a connection between this and things like graph data structures. This doesn't quite get to graph.

Well, I mean, many of these things represent graphs, but they're not related to our general graph thing. The tree data structure uses a tree. You know, the tree feature uses a tree data structure. But we don't expose that. That tree trait because they decided to make. Make something different. It uses it.

Excuse me.

It uses it internally.

So, but.

So, for example, converting between, I don't know, a linked list and a. In that case, trivial graph. Is that useful?

Well, I mean, I don't think that's especially useful. I mean, one way this maybe could be used. Well, right. So, okay, in graph, I think there are like four different internal representations that graph uses. It can use list of edge and list of vertices. Adjacency matrix, sparse adjacency matrix, and like, One other, something like that. Right. So you know, and in general it's totally opaque and you don't usually care. I mean you could imagine a world where we sort of have, you know, where we're internally graph or maybe whatever future graph like thing uses. You know, maybe it has its four different internal representations. Each of those representations is data structure that you can call directly through this. But then the outer wrapper is just basically generalizes over those different data structures, if that makes sense.

Yeah, but who cares? I mean, so long as we get the automation right to work between data structures, who cares?

I guess, I mean, in the case of graphics, the answer is you never care. Because I don't think I've ever had a problem with graph quote unquote using the wrong representation for things like maybe mesh regions which are a lot more complicated. Like I think. Well actually mesh region I think is one. But like regions, they're like 20 different kinds of regions, something like that. And for that I've definitely run into things where I'm like, oh, you're using the wrong representation.

I think there should be a better way to hint it than to actually drop down to the level of data structure operations.

Yeah, yeah. I mean it might, it might be a matter of, you know, have a method option for.

Yeah, it might also be a matter of heuristics not being good enough. But. Okay, so let's look at data structure operations down at the bottom there.

Sounds good, right? Right.

So they work with this sub value mechanism.

So you create a data structure and.

That pushes push loads of things.

Do we like this? I mean we invented this as a. I like it.

Absolutely crucial because it's consistent with methods C, Java, Rust, Julia, all the data structures. And also it's a crucial way of being able to hierarchically represent one data structure through another through another. You can get access to say one data structure which means another, and then you can get properties of it and stuff like that and work with it rather than external functions that apply to the data structure. It's much nicer to have these to be sub.

I understand, but syntactically the natural way for us to have done this would have been verbosely to say, you know, data structure operation of, you know, linked list comma, push. That's a function that gets applied to the data structure rather than to have the sub value approach.

The sub values are faster than down values.

Actually I haven't tried exactly that, but.

I did do some experiments with. Well, we, we do care about speed. Okay, but, but, but like like, you know, stack comma, you know that that is, I don't like that that's noticeably slower.

So, but, but not just that. I mean that the method or the data or the thing is a property of the data structure is something inherent.

Right.

It reads the wrong way around.

Yeah, exactly.

Yeah.

Something external operating on something. And that's just, it's difficult to organize these things in a nice hierarchical, clean way.

What I would say is, you know, peek at the stack. It's a function you apply to the stack. Here we've got a sub value of the stack, which I think is weird.

Right.

We could, we haven't done this, but we could have command completion for these things. So when you, you type this and then like now you get a completion.

Of all, it better be. We should have completion. The problem is we don't know what DS is.

Well, we, we do. Once it's been evaluated and sent to the front end, we, we, we, we do know. We, we could tell the front end, hey, there's this symbol and this is the continuations for it.

Well, it's.

And with the immutability, that might make some sense. I agree.

Yeah, yeah, I, I think that would be pretty, pretty neat actually. I mean the mutability is another key thing about these. So that's like absolutely breaking the mold.

Yeah, yeah, yeah, yeah. Right. But I mean, look, that would certainly help. Yeah, yeah, I mean that's a. Okay, so bring that up with the front end team. But I mean Mark, you're actually arguing that you like the sub value organization better than you would like functions.

Absolutely. Find it so much more natural.

I am in agreement with Mark.

When you work anything you do in another language and you take a data structures course in something else, and the way that they're all set up and there's a reason why they're built up in this kind of way, this kind of object centric way that you can get methods and data and all these kinds of things because it just fits into the paradigm that's used in other types of languages. So naturally. And I think that's. Well, I think it's quite important for these things.

I mean, another key point is you don't have to worry what context these, these methods are in.

You see.

Now for the core ones in the Wolfram language, yeah, that's fine. But when we write tons of these things internally in the compiler and it would be unusable if we had to, they were all in different contexts in different packages.

Yeah, yeah, yeah. Terrible context symbols and context that is one of the main problems with all this, structuring it in a kind of nice clean way. Whereas here it's just you can have.

A lookup, you've got a limited number of special data structures here, just like we have special functions.

No, no, but I'm talking in other places, like in the same things work inside the compiler. I mean, it's nice to have the same programming model and as we're compiling the compiler, we use the same techniques. So we get like a win, you know, a win in compiling the compiler is winning for, you know, in driving the language.

And also it's useful because somebody writes something it interactively like this will use the same syntax internally when they're using on working on the compiled data structure. It's identical. And I think that's important not to have two syntaxes, one, one for top level or sort of an evaluator sort of model of the data structure and one for the compile. The only thing that's different is the constructor. It's like data structure backtick, new or whatever instead of create data structure, but.

The rest data structure as well.

Yeah, the rest of the operations are identical and I think that's quite important. Yeah, make it kind of.

Wow. Okay. Well, by the way, Daniel on a live stream is asking all data structures implemented in Wolfram language run C. The answer is they're implemented with a compiler, right?

Yeah. Yes, yes.

So they are written. The source language is Wolfram language, but it is compiled into llvm and they're pretty.

Mark, you, you, you're a hard. You know, they're pretty, they, you know, we've been polishing them, but they work pretty well, actually.

I mean they work quite efficiently.

I think the hash table stuff in the compiler is faster than the kernel one now.

So I mean, they're pretty competitive with.

You know, C data.

Okay, so one of my purposes in this meeting was to discuss the subvalue mechanism and you guys are vehemently insisting that sub values are the right way to go.

We. Sorry, but yes, I really like it.

Yeah, that's good.

We've also done the sub value things for some other, you know, and these are more, you know, some more and some less documented. But, but two examples I can think of are interpolating function and, and sparse array. We have some.

I know which, which, which, I mean we have sub values for lots of other functions, but they don't. The difference is sub values don't usually do operations. Sub values, you know, extract properties of things. That's pretty Common.

Well, that's just because we don't have mutable stuff ever elsewhere.

Good point.

Yeah.

Okay, well, okay. I mean, all right, so then let's, let's talk, I mean.

People about getting continuation things. I mean, if I have to add stuff to the kernel to do that.

I'll, I'll do that.

Right, okay, so let's then look at, Let me, let me poke around at these data structures. Let me ask some questions. Okay, fine. One question is what about user interface data structures? Does that make any sense to have something in this framework that is a raw, you know, some raw user interface construct? Because I mean, obviously in, you know, in the libraries that we use to build notebooks and all that kind of thing, there's endless data structures that represent, you know, window on the screen and stuff like this. Does it make any sense to give access to those things?

I mean, we could build. It might be disjointed from the front end.

The front, you know, we could build access to sort of, you know, various libraries that do this.

The front end could expose data structures.

That could be manipulated in this way.

I don't know if they want to.

Do that, but they could.

The front end could use some of.

These things as well, if they wanted to.

I mean, the other thing about these data structures, they all have serializations, you know.

I know, I remember fighting for that.

Serializations. We put a lot of work into making these work nicely and then make them work faster, you know, so that's.

By the way, are the serializations binary or the serializations input form?

Serializations are full form type of things, but they might include things like byte.

Arrays and things like that.

But you could probably have a binary.

Wxf, but some of them do.

Bitvector does. So.

Okay, but one thing you could imagine what happens if you feed the data structure out to wxf.

It will get converted.

It will, it will get serialized into.

Full form and then the WXF will pick up that full form.

Then when it comes back, it'll be deserialized.

Is it efficient?

It, it.

I mean, it's order N. So if.

You have a billion elements, I understand.

That, but it probably depends on the data structure.

Yeah, I mean, it might get like unpacked. You might have a bit representation that gets unpacked to a byte representation.

Might be big, might end up split. So I mean, that's one possibility is whether there's a sense in which there is direct serialization to WXF from compiled stuff.

That's an interesting idea. I've never built a WXF interface direct.

From the compiler, but I've often thought you probably should, so.

And then, then we would take an expression data structure. Go ahead.

When I. I didn't know there was a way to do that. Like I thought wxf. I didn't know there was a way of extending it because it's like pretty documented.

What about Chris Cooley's stuff for the. The expression. What is that thing? The expression. Do you know what I'm talking about, Chris? Or you know what I'm talking about?

Yeah, you mean the, the standalone apps?

The, the.

The expression interface.

Yeah, expression interface.

Yeah, yeah.

Isn't that a binary interface to expressions?

Not in the same way. I mean that's about having, you know, exposing the expert struct to C.

I see. Okay, but so the idea that there might be something which could take a thing that is one of these data structures.

Just have a dangling array of sort of bits in the data structure.

It's.

It actually has a. You know, we've tried to make it so that it has.

So your leveraging.

Yeah, this is.

Yeah, yeah, that will get serialized out nicely. If it's a numeric array, it'll get serialized out nicely. Has the support of. Yeah, it already has the support of that. Of that. For numeric array types and stuff like that. So. So some of them, not all of them. I mean like a tree or something. There's no direct thing with the pointers and everything to do everything in the. Nice.

So why isn't there something like an MX file that is the memory image essentially of that tree?

Well, I don't know about that. You start getting into all sorts of things like endianness, Steven. I know. I mean already the serialization of these is. I mean, it takes as long to write the serialization for data structure as writing the code for the data structure itself. So already that is.

Well, okay, but I'm asking, is there a generic way to do this, given how it's laid out in memory? I mean, we solved the endianness problem in the end for MX files. How do we solve the endianist problem?

It's a lot of work to just, you know, write out bytes in a independent way and check what the platform is and then byte swap them and stuff like that. It was like month or two of work.

Okay, but mark you automatically.

But about.

About automatically serializing. I mean, I think it seems like. Right. If we could. So most data structures are basically product types containing other data structures. So in that, you know. And Integers and stuff like that that we can serialize. So in that sense it probably is possible to automatically serialize a lot of them. You know, there's some base ones that are harder because they have pointers and stuff like that. But I think that the ones that are easy to automatically serialize are probably also easy to write the serialization code yourself.

Yeah, I also, I don't think the serialization should reflect the low levels.

Yeah, absolutely. Then we can't optimize it.

That locks us into a low level storage, which we might.

That's exactly The.

I've got 100 megabyte data structure. Okay. I want to serialize it. Am I going to end up with 10 gigabytes of crud or I'm going to end up with something reasonably small?

Why don't you look at an actual full form?

Well, I mean, let's, let's come and do. Well, let's, let's.

Oh, there's one right there. Yeah, I mean there's the one for the stack there. Although the stack is a little bit uninteresting.

Push a million zeros onto a stack.

Right, okay. Zero. Right.

Okay, that was spectacularly fast. Prove to me that it has a million zeros on it, can you? How is there a stack depth? Yes.

Well, I mean, I mean these things are the speed of C, Steve. I mean, you could do.

Okay, I understand. Now I want to see 10 million.

10 million to 100 million operations on a list.

Let's see, how big is this thing? What if we say byte count of ds?

Yeah. Actually byte count is not.

Does it lie?

That's, that's not true.

It's only implemented for about half the data we've been.

We've been filling in Byte count.

Yeah, I've done hash to save all some of the filters, but not.

Fine, let's do binary serialize. Just do length of binary serialize. Or actually you don't even need the length because the summary box will say it in a nicer way.

So.

Yeah, I've never done this, but this.

Would tell us the size of the full form.

Right?

2 megabytes. That's not bad. Wait, how's that even possible? That means it's paying 2 bytes per.

How do I deserialize?

Okay, yeah, now do deep binary deserialize. And ask for length of that.

Hang on. Ah, crap. Sorry.

I mean, you could even just say or I don't know if same Q works.

Yeah, yeah, let's do.

Does sameq work? Let's try it.

Yeah, yeah, yeah.

Yeah, I have a method we put.

How did it manage to get. Wait, wait a second. How is it 2 megabytes?

So look at the. If you look at the full form of it, my guess is that WXSETH is storing the integers in some sort of small way.

Yeah, it might be run length encoded or something.

Just try one more experiment. Could you do that do with a random integer there? Yeah, random integer there. Random integer of 10 to the 6.

Like that?

Yep.

Yeah.

Actually that's now going to add to the same stack, Right?

Fine.

Yes.

Okay, so now, now do binary serialize or whatever.

Okay, I did just check. So, so WXF uses varints. So integers are only the number of bytes that they need to be plus one.

Well, okay, five megabytes there is. So that's five bytes per integer, which is very respectable. Right, that's. That's very reasonable.

That's not terrible.

Now do binary serialize of that.

It's interesting that binary serialized seems to be a lot slower than just constructing it from scratch.

Yes, well, this is very respectable.

I mean, embarrassing, right?

Yeah, no, these are good. But now why aren't we using binary serialized? When you store this thing out to a file.

I often use WXF and it depends on how you want.

Which is binary serialized. Right? Binary serialized is producing wxf.

Yeah, I did some experiments with this like a little bit ago about WXF vs MX and I remember that they were very similar, but for deeply nested things, WXF did significantly better. And there was one case where MX did significantly better. I don't remember exactly what.

Okay, all right, let's come back. This is great. I mean, this is good. Let's come back to data structures, the list of data structures. And let's just talk a little bit about what. Okay, so another question is the visualizations of these data structures, which we sort of hope will be useful for educational purposes. Has that panned out anybody?

For us, We. We use it.

In what way?

Well, like when we're building them, we look.

Oh, when you add, add and delete elements from things, you want to see if your visualization is filling up with things in the right place or whether it's you've got something aligned wrong or, or, you know, so.

So doing the right thing. What's.

So my next question is, if I looked at, you know, the textbook list of data structures, what data structures would I find in the textbook that I don't find here?

So I think actually we have this. It didn't quite make it in 13.3. But a new balanced binary tree are better. So we have AVL tree, but we have a better one which is a red black tree, which is much more standard. And with that, there's a whole ton of other data structures that we can.

Build on top of it.

Like what. Which are for sorting, searching, type stuff.

So.

Yeah, that sort of thing. Fahim, what was you. You came up with tons of interesting things.

What were some of the things you were coming up with? One of them was a sorted set would be one of them.

Yeah, no, there were other things as well.

Oh, the rope data structure, which is the rope thing. That was it. That was interesting. Yes, that is what internally text editors use for implementing. Yeah, text editors, where you have.

So if I go to our friendly ChatGPT, for example. What's that?

Right, this, this is the rope thing. So it, it is kind of a, it's pretty interesting, actually.

So.

Okay, well, that's fine. But that's the thing. I, I'd never heard of it. I'm, I'm glad to learn about it. But that's.

I mean, and the thing is, once you have a really good red black tree, implementing this is very easy. You see, that's, that's the other nice thing is you get these things for free.

Okay, so let's just. I just asked our friendly LLM, you know, list some commonly used data structures. It said arrays. Okay, well, we got those linked lists, stacks, queues. What do we have in queues?

Queues.

Priority. We got queues. Priority queue.

Well, heaps.

What do we have in heaps?

Well, a priority queue is, is a heap, really.

So.

Okay, all right, so if we go. I mean, have we done this exercise of just going and looking for sort of other. I mean, there are, you know, in, in like computational geometry, there are tons of data structures. Right. Which we don't have here.

Not, not, not all. But we, we've been adding, like, whenever anybody asks for something, we, if, if it, if it's feasible, we, we, we. We add it.

So. Nice.

Yeah, like the KD tree was added because we've been doing some other computations.

Yeah, okay, but like, you know, you look at some random source, like Wikipedia, for example, and you'll see all kinds of, I mean, there's, there's several pages. You just say list of data structures. Just say list of data structures. By the way, I hope that our data structures make it onto these pages in Wikipedia where. When we have a version of it with visualizations and so on. Yeah, separate issue. Okay, but what is a multi map, for example?

Well, it's like a hash table, but where there are. You can have the same key can.

Appear more than once. Okay, multi sets, but not, not, not multi.

Okay, scroll down here. Let's just see what other things are. All kinds of random stuff here which I've never heard of. Mostly circular buffers. Do we have one of those?

We have a ring buffer.

I, I think, I think that's what.

Yeah, I hope we just have the, the keyword circular buffer to go along.

I would need to check that, but.

I'll, I'll make, I will check that.

Okay. Another question is in the. Scroll down here a bit.

Yeah, sure.

I mean many of these things we either have or don't have. I don't know. I think a lot of this is kind of a.

So one, One type of data structure. I think we should have more of. Are more immutable ones and we've been. We have one immutable one. But, but I'd like to have more of those. I think those are kind of interesting and they kind of fit obviously quite.

Well into the expression sort of notion.

So what's an example of an immutable data structure?

Well, association is an immutable data structure.

Fine, but why do we need that in the data structure system? We already have that in the main system.

We don't have, for example, a set version of it.

No, we don't. That would be useful.

That would be useful, right?

Yeah, that would be useful.

Yeah.

Scroll down. So that, that one to me is. Seems like a decent priority and one that could be promoted out of the pure, like tree was promoted out of the pure data structure world.

Yes.

Yeah, I, I think that's true. It's quite hard actually.

That's. To make a nice one. So.

But Fahima's been working on that. But it, it's, it's, it's quite hard. There's, I think immutable trees. Like, like an immutable balanced binary tree.

Would be kind of interesting. I think so.

Well, I mean. Okay, scroll down here. I mean many of these are just sort of amusing, but who cares?

Yeah, SPQR tree.

It's gotta have that.

Okay, scroll down. Is there anything else here? Scroll down. Asts, Abstract syntax trees. That's a, that's a place where we might.

Yeah, that's interesting. I mean, you have the expostruct, so.

That'S a bit like that.

But we don't have.

No, that's, that's interesting.

I think that will be an interesting one. And useful. Keep scrolling down.

Sure.

I was just.

Right.

So we've got, you know, representatives of these.

We've got, yeah.

Which may be enough.

We've got a very good cuckoo filter. Mark's just totally.

Okay, scroll down. Things like scene graphs. Okay, so hypergraph, by the way, Nick has been implementing in one of our institute projects, has been implementing a bunch of hypergraph related stuff. I don't know whether he's been using data structures.

I, I, he hasn't talked to me.

If, if he has, but I think.

Somebody should ping him and find out if he is right because he's built a whole elaborate thing for doing. Okay, so here's another category of data structure, okay. Is things. We can leave this page, I guess. I think we're, we're, I think we're.

At the end, right?

Yes, we can, we can go back to this. Okay, whatever. Okay, so you know that hypergraph thing that would be useful. So can somebody here please ping Nick?

I've made a note of that.

Oh, well, okay. Yeah, yeah.

Okay, now, abstract. Look, here's an interesting category, okay, including other work that Nick was doing on pattern matching representations. I wonder if there are other things which are more like the expression data structure that are things that are more sort of innards of our system. You know, partial representations of pattern matching, things like this.

That's interesting.

Where, you know, there are internal things in our system that could be exposed usefully. I mean, the abstract syntax tree will be an example. You know, it seems like what is the output of the parser?

An expression, but.

Yeah, okay, fair enough. But when is it.

I, I, sorry, I'm not trying to be flippant, but.

No, no, you're right, you're right. I mean, is there a previous stage? Even the Lexa, what's the output of the Lexa?

It's like bolted into the parser for.

Efficiency reasons if we want to. Oh, but hang on, what you're asking is feasible. And in the old days of Brenton, Brenton and I were talking about representing his parse trees as a data structure. And that, that would be not, not so, you know, that would interface into his C code. Now Connor's rewritten it, I think as rust, but that could be done to have a data structure view into, you.

Know, those structures might, might be interesting.

That seems useful because, I mean, we want to manipulate code.

Yep.

Yeah, it's a question of how do we do that. And I mean the, the expert is way too kind of digested to a semantic level.

It's completely it's totally correct what it is, it's a view into our expression.

So that's.

Yeah, right.

But okay, so let's ask this question. Let me ask a few more questions about other things that are sort of partial pieces of our system. Like I don't know, sparse arrays. Is there some intermediate representation there that will be useful to be able to get one's hands directly on?

Rob should. There is a sparse array type that Rob should.

So, so the sparse array. So, so one of the things I did with sparse array to, to make it work with the compiler is I set up a very data structure like.

Thing.

With the sparse array, but it doesn't quite fit into this framework because. Because there are different, different underlying types like you know. So for example, we could probably compress the graph representation as a sparse array by using your unsigned integer 8 type sparse arrays instead of the machine integer types that we're using right now.

Ok, so the issue that we have is that the data structure. Data structure, the symbol deals with unparameterized data structures. Like as far as data structure is concerned, it's a linked list of expressions, right?

So where they are polymorph, not all of them are, you know, like, like a bit vector isn't polymorphic, it's just. But where they're polymorphic, what we instantiate is ones for expressions which, which is great but we could consider some mechanism of instantiating other ones, you know, specialized for machine integers or something.

Well, but how would that work? Doesn't the compiler already have that notion in a. You know the type specifiers.

Yeah, you write compiled code.

You do, but yeah, you'd need to build a library or something like that.

You need to write some compiled code.

And I'm working on. I'll just mention, I'm working on.

Rob has some very interesting things. Yeah, yeah.

So, so I'm working on. So for this tabular project I'm working on an underlying data structure. So, so the idea of the tabular is going to represent data in a column wise fashion because typically columns are consistently typed.

So.

So my basic data structure for there is something I'm calling it. It's. I'm actually setting up as a data structure but it's.

It.

It is type parameterized and I'm calling it for right now a data vector that may not be the right name but it could have type. The element type could be string or the element type could be expression and so on. And that allows us to have sort of a uniform structure for these things of different types and that's working out. I mean, you know, I think it's going to be very efficient.

Right.

I mean, there's the other thing, Rob, we were talking about, which was the string. String vector or string array.

String vector, yeah, because string list or something.

But the key point is that these data structures, structures as you have them here, there's sort of still a, you know, this is an application of the compiler where what's inside these data structures as expressions. The question is, if you want to go the next level of having one of these data structures but having what's inside it be, you know, eight bit integers or something.

Correct.

How would you do that when you.

Could write compiled code and I know.

That and use the compiler, but the question is, can you do the same thing that we're doing with the data structures where there is no compiler invisible?

Well, we would have to instantiate it. These only exist because they are pre built, you see.

I see what you're saying. So what we could in principle imagine doing is saying, but I mean, wouldn't it be okay, we could, we could pre build a bunch of obvious, I don't know, binary trees with, with integers on the nodes and then if you want a binary tree with some weird struct on the nodes, why couldn't you auto build it at the time when you define it?

You, you could do it. It's takes a bit of time, you know, it might take a long time.

Takes time. A long time.

Yeah.

Well, that's okay. The problem is that the compilation of that. But if, if. Okay, and it could be in a wfr, so what would happen if there was a, you know, a data structure? Is it conceivable that there should be a data structure repository?

That's an interesting idea. I think it's still a bit specialized.

To build these things is my answer. So.

Yeah, but so there's also, there's also.

Another issue because like with the compiler, you can compile it locally for your machine and it will use the best instruction set that you have. But if you put it into a function repository, you'd have to dumb it down like we do when we ship Mathematica. We dumb it down to the lowest x86 version we're willing to support. Whether so, so you put. You push some sort of version that's not quite so optimized.

Bit vector.

That's the real thing.

I mean things that use CD instructions and stuff. Stephen, that is a factor of four or more in efficiency. I mean it's not to throw away.

Okay. Let me ask.

A different data structure library optimized for your machine. That, that would be an interesting thing. That, that, that would be useful.

Well, okay, I mean, then that's a. But that requires a different plumbing. I mean, look, it took a lot of effort to get to the point where a compiled function is transportable, which it now is. Correct?

Yes.

I mean, within the same platform. It's pretty fast.

I mean, Christopher keeps heading.

Yeah, it's, it is, yes, but I mean, it works.

You can make a WFR with compiled code and it's transportable. Correct?

Yes, yes, that's, that's, that's true.

Right, but how much are we losing when we do that? I mean, Mark, you were speed demoning this and claiming a factor of four. Are we losing that when we make it transportable in that way?

Yeah, we're making a generic version.

Yeah, because you're built for a generic platform. So I mean, these things, these things you'll see with, with low level arithmetic bit operations, you know, stuff that can be optimized. Exactly. I mean, some, some you might notice it a lot less. I notice it because I work on arithmetic stuff. I know, but other people might not notice it. So I'm just pointing out it's an issue.

Okay.

No, they, they would.

I mean, let's throw away that issue for a second and ask the question. What. I mean, parameterized data structures, which, you know, where we could store. Yeah, I mean, okay, so look, there's some additional plumbing needed if we're going to do so. These are non parameterized data structures. Basically. These are data structures.

They're parameterized for expression.

I get it.

Right. So they are, they are parameterized.

Yeah. I mean, look, that stack example was very impressive. That was very nice and optimized. Let me ask one more question here. So this is relevant to Christopher's FFI stuff and so on. If we were to use data structures that come from external libraries and were to kind of merge them into this concept, would that make any sense?

We could, yes. You know, if we're using expressions, it wouldn't be so totally trivial. And it probably wouldn't. It might not work quite as well. Our compiler is very optimized to work with expressions.

No, I understand that, but I mean, let's say you're using some GIS data structure or something.

Well, sure, yeah. Well, we do that.

We have like this GEOS thing that.

Right, but the thing is that. Right, I mean, as we talked about earlier, there are several properties that data structures have in addition to just being Blocks of memory, I mean they're serializable, they're portable, you know, et cetera. This is not true for a generic thing you get from a library. And in fact a generic thing you get from a library, you know, it's either a number or it's a pointer. So I mean right now we represent things as numbers or pointers. When they come from the ffi, I think it's a fine, you know.

Okay.

Yeah.

The things that come from the FFI are not of the same sort. I won't say type as the things that have been.

Well, they often are. But we don't know nearly as much. Right. I mean we're just, you know, you're given very little. You're given a pointer which is basically a number.

Yeah.

And you don't know how it's memory managed. You don't know what methods it supports or how to call them. You don't know anything. Okay, have to make that yourself.

But if you could get things from the, from FFIs into the data structure world, are there things that are very juicy?

I just don't know what this would mean. I mean it would just be a matter of supporting kind of the syntax that data structure does of like sub.

Values and so on. To use a compiler interface than an FFI interface.

I think as well.

Okay.

Some overhead to the FFI maybe not very measurable the evaluator, but we should.

Probably wrap up here. But. But we got a couple of questions from this live stream towards is asking, are data structure sizes limited by machine integers?

Yes, but that's 64 bit integers, so that's not pretty big.

Right. So you will not be able to get enough memory to blow it up.

No, you'll never be able to. On a 64 bit machine you'll never be able to.

I mean, I mean that's, that's like exabytes, isn't it?

Yeah, it's impossible to.

I don't have that much memory actually.

Some of these platforms, like ARM platforms, they use the higher order bits for, you know, sort of, you know, for security purposes.

So.

So they've blown up 62 of the 64 bits or something.

They've taken a few of the higher.

Order bits and they put check sums and things in for security.

There's a question from Valued here. Any plans to integrate data structure more directly with the rest of Wolfram language? Eg, total of ds, if DS is a stack of integers? I think we made the decision.

Well, we do have iterators over data structures, so you could Write total or other operations as things that iterate through the data structure.

No, I understand. The question is. The question that's being asked is if I simply said total of ds, does it work?

No, at the moment, no. But it's implementable if it was written as an iterator. If Total had an iterator method that would just be independent of the data structure, something that would just say start at the beginning and iterate through. Then it would work for all data structures. So. So because it's polymorphic, it could be.

Done in a way that have a fold operation.

So.

Which is pretty. Pretty that, that's a nice access. Nice functional access.

Yes.

So I would say.

But I think it's a slippery slope if we start supporting total. What, what if we. Somebody asks for, you know, determinant or something or norm.

Right, right, good question.

Norm would be a better example.

Or.

To our down code. Fun. I mean, things like total that have down code or stuff. Then, then every, every extra thing we add we have to put an if is it this data structure? And then we have to check to make sure the data is compatible.

But we wouldn't do it that way. We would do it generically. Is it a data structure? Okay, then, you know, use an iterator.

Yes, that, that would be fine.

We'd probably use fold.

Right.

But the question is what functions? Is there a set of functions? I mean, look, throughout the system we make it be the case that typing, you know, some obvious function eats some other obvious function. So the question is, for these data structures, I mean, like if you say total of, for example, a bit vector, what on earth would that mean?

Yeah, God knows.

And it starts being a, you know, a pun or an analogy type thing of. What's this supposed to mean? I mean, in the case of total and Stack, it's fairly obvious.

Right, Right.

I mean, I think in general, if you said, I think in general, the outside functions are kind of, you know, like. I think the sub values are really the thing to use. The fact that any functions work on the outside other than maybe full form. The fact that like length works, I think is, you know, it's a nice little convenience, but it, you know, you shouldn't rely on.

Yeah, it's very questionable because I don't know what the hell length means for.

A tree number of elements.

Right, well, that's not totally obvious to me.

Yeah, no, that's not obvious, but it's not crazy.

Right? So that's why it's much better just to have the data structure specific Property that's either, you know, leaf count or something or if it's called length, at least you know that stringy of length isn't. Doesn't necessarily have anything to do with bit vector of length.

Right. I think we need to transition to a different meeting which is also going to be live streamed. It's part of our LD series. But I think the main conclusion here.

Is that nice if we could promote these more. I don't think they get used enough.

Because they're very nice.

Well, but I keep finding random people in the company that, you know, come to me and say, oh, I love.

That you know this. I use it all the time and it's so. But anyway.

Well, okay, that's a different. The marketing of data structures is a different issue. First they have to work. Now that they work, what's that?

Not irrelevant. Yeah, so. Yes.

Well, maybe somebody should write a little book book about, you know, data structures that uses these data structures and shows people the nice pictures and so on.

Yep, yep, yep. That sounds.

Or at least a. I mean, I don't even know what the data structure guide page looks like. You bring it up. Does it. Is it attractive? Well, let's look at the listing of data structures. No, just, just go right, here we go.

Here's the guide page. I mean, it's functional.

Yeah, it's okay. I think. I mean, what will be a way to promote this? One thing would be if our code assistant system, if the LLM based code assistant system knows about this stuff, that will be one really good way to promote it.

Yeah, yeah.

In general, if we have a essentially LLM Persona that's all about optimizing code and it has a fighting chance of suggesting. Have you considered using a doubly linked list or something? I don't know whether it does have a fighting chance of figuring that out.

Yeah.

I mean, how would you go if you're presented with a piece of orphan language code and like my example of those tag systems.

Okay.

What does it take to be able to figure out here's a reasonable data structure to use?

Yeah, I mean that, that's a good question. I can look at it and I.

Can see, oh, you're doing this and that.

And in a sense that's how an.

LLM works, isn't it?

I mean, it's more or less yes. I mean the question is, could we.

Ask it why, why can't the LLM?

But I have years of experience of.

Like data structures and Wolfram language.

Right.

I mean, I'm just wondering if There's a sample. We could just ask the LLM right now whether it could. Let me think. I mean, this piece of code. Well, actually we could give it the tag system, give it the code for a tag system and see what it can do. I, I'd be amazed if it could do this because I think, I think that we're. When does it make sense to use a ring buffer? I can ask it.

Do you want to share?

No, actually, because I'm not, I'm. I don't have it set up correctly for that. I'm just gonna, I'm just gonna try this just for fun. I'm asking GPT4 a ring buffer, also known as a circular buffer or circular cube, makes sense in situations where fixed size storage, fixed amount of memory, need to manage it without allocating memory. Okay, so this is much more conceptual.

Yeah, yeah, yeah, yeah.

It's not code overwriting old data, blah, blah, blah. I mean, this is fine, but it's like, what does it take? This is really the question. What does it take to look at a piece of code? Like, like for example, if we looked at our internal code, the thing that we've long wanted to do. Okay, here's a challenge. Is there a way of scanning our internal code and predicting where we might insert a data structure?

I mean, maybe, you know, if you see a pen to, in, in a loop.

So I mean the.

Okay, so that's a, that's a, that's a clue. So that will be an interesting exercise to scan our internal code and look for appendoos. Yeah, yeah, that's a good thing to try doing. And what are some other clues? I mean, basically it's whenever one is using sort of small scale mutability.

Yeah, that's, that's one of them.

Yes.

So, okay, when there's mutability, I mean.

So I mean there's other things when you're using like set operations, it may be that the hash set, which is.

Blindingly fast and mutable, is quite good as well.

Right. Well, there are places where you're generating a whole giant expression and you probably want something more mutable.

Yeah, yeah.

But let's see if we can figure out what some of those criteria are. Maybe an LLM can find them for us. Or maybe if we're still continuing our rule based code assistance, we could use those or combination where we prompt the LLM with the rules. All right, I think we have to wrap up here, but that was useful. And I think there's, you know, fundamentally it seems like there's no major change here.

And there's good stuff.

Yeah. All right, well, and I think the promotion is, you know, whenever. I mean, look, here's the thing we could do. We could generate, you know, we're not yet doing this, but, I mean, we could generate. You know, the whole idea of code assistance was to generate default advisory messages for code. And so when we see append to, it's reasonable to guess that there's a sort of default advisory message that we can generate that says, consider using data structures. Okay. Anyway, we should wrap up here. Thanks, guys. See you later.