Memory Management Experiments in Rust

all right looks like we're alive hello everyone and welcome to yet another voicing session how about that how about that but bacterium expo let's make a little bit of announcement on our discord server so we are currently live on twitch if i'm not mistaken right live on twitch and what are we doing today we are programming in rust rust rust uh we are programming rust specifically we're implementing persistent stack which is a rather interesting way get to what it is a little bit later so she's best which the tvs are starting and we're going to ping everyone who wants to be pinked and there we go this stream has officially started hello everyone hello hello hello welcome welcome welcome chat tell me what do you think about rust anyway so what is a persistent data structure right so specifically we're implementing persistent stack but generally there is like a whole class of data structures called persistent data structures so let's actually google it up uh persistent data structure right i'm going to prepare the description because i want to put the link about this thing in the description as well in computing a persistent data structure or not ephemeral data structure i never heard like the term ephemeral data structure to be fair i only heard persistent one it's a data structure that always preserves the previous version of itself when it's modified that is very interesting so uh so specifically quite often uh the like persistence is applied to trace and stuff like that but but we're going to apply it to uh to stacks specifically linked lists so i really want to give the link to this thing in the description but if i just copy paste this entire stuff it will contain some garbage that google put in there uh you put in here um i don't know what's what's going on with my speech today so um i have to specifically remove all of that this kind of stuff it's so annoying i don't know why google keeps doing that and it's so difficult to get rid of that and it's just like they think it's helpful but it's not helpful at all it's just like puts a lot of garbage in your url and if you want to share something it's just like you have to do this extra work of removing all of that it's just so annoying i don't know anyway so um okay so why do we even need a persistent data structure so believe it or not this entire stream is actually related to porth right so i've been developing uh my own programming language called port for like more than two months already i think right so i'm gonna give the link to uh to this language here in description if you're watching uh if you're watching live i'm gonna put that in the chat so here it is you can find it in here uh support programming language here's the port programming language and it's a stack based programming language meaning that all of the operations like literally everything is done by the data stack right so we can take a look at some of the examples of this language um uh soon uh chiropractor thank you so much for 29 months of tier 1 subscription uh thank you thank you thank you and welcome to our epic rust club um okay so let's take a look at some example uh brain is a brainless jellyfish thank you so much for two months of turkish prime subscription thank you and welcome to our epic rust club it's not a rust club yet it's still a port clap but after we're done with port we're gonna do some rust uh binder18 thank you so much for two months after we prime the twitch prime subscription and welcome to our epic port club um okay so let's take a look at hello world right so hello uh porth okay emacs emacs what is going on uh hello fourth there we go so i need to include the standard library right and then i don't think hello world is actually pretty good example of this you know stack orientedness of the language so let's actually do something like a thing that sums up two numbers uh so if you type 34 that is a command within the language to put that number onto the stack right if you uh type another number it will put another number onto the stack uh right and then you have operations that operate on the top elements on the stack like plus right so this thing takes top two elements on the stack sums them up and puts the result back on the stack and uh here at the top of the stack after this plus separation you're going to have uh the sum on the stack and then you can do print and that the thing will print the um the result of the sum on to the screen right so i think we don't need at least 10 library for that so this is a very simple program and if i try to compile and execute that program uh it is going to print 69 right as you can see uh it compiled this entire thing and printed the result okay that's pretty cool so this entire this is what it means for a language to be stack oriented right if you want to learn more about stack oriented languages i really recommend to just google up that term or specifically google up fourth i think this is the most prominent uh stack oriented language right a lot of people get into this tech oriented paradigm by looking into fourth so i really recommend to check it out uh so i'm going to put the link to the fourth wikipedia article in the description as well just for anyone who's interested okay one interesting thing about porth is that it is uh statically typed right it is statically typed so essentially during the compilation the compiler actually checks that you're not trying to do things that you're not supposed to do for instance here for a plus separation to actually work properly you need to have at least two elements on the stack and this is ensured by the compiler for instance if you remove one of the elements this is not going to compile because the compiler cannot prove that should have enough elements on the stack so it will tell you not enough uh arguments for the plus separation uh so if you try to compile this entire i think basically it will tell you that so it tells a lot of things in here and this is because the plus separation is overloaded right it can sum up integers it can sum up pointers and integer end points and stuff like that and basically for each uh overloaded plus operation it tells you that you you've got an error so so the the entire error reporting is not really well you know polished uh so i just hacked together something just for the compiler to report so it's not really that important but any case it just tells you that there is not enough arguments for the plus right and uh yeah so that's basically it and uh interestingly enough these uh static type checking actually works for if conditions right so for instance uh what we can do in here for instance we summed up these two numbers and then put 69 onto the stack and we compared and this entire thing will give us boolean and we can dispatch we can basically do a conditional check on uh upon that boolean right so um uh the execution will go here if this condition is true and it will go here if this condition is false right so you can even do something like uh true and you can print this thing under the screen and then you can do false and you can also bring that onto the screen so uh just a second i i think i forgot about very important thing in here uh i forgot to put something behind my camera right so i usually just put some sort of a window behind my camera just in case i actually start typing somewhere where you can't see uh right so it just makes it easier for me to know whether you can see what i'm typing or not so it's pretty convenient uh okay so and uh what's interesting is that our type checker is capable of even checking this kind of stuff uh right so yeah so we can even remove puts and we can put puts in here uh right and the the compiler will check that both of the branches put enough arguments for the puts to consume right so here's the very important so if one of the branches don't have enough arguments for puts to consume right so the program may work only when this condition is true but when this condition is false there will be no arguments for this thing so it will crash or you know yeah it will basically crash and sequoia so our compiler will ensure that in both of all in both of the branches you have enough of the arguments for this operation uh right so if i try to do something like this um it's uh it doesn't have puts because it's located in the standard library right it is located in the standard library so as you can see it just says true if i compare it with 70 it will say false right but if in one of the branches you don't have enough arguments for the puts to consume this will not compile and it will explicitly say not enough arguments provided for puts right uh so and then you'll have to go and fix one of these things so the question is how does it do that umbrella marilla thank you so much for 10 months of the week prime suppression thank you thank you thank you and welcome to epic port so the way it does that right so the the way it type checks the program generally during the compilation it maintains the type stack right during the execution we have the data stack where you put the data that you operate on but during the compilation we have a type stack and what the program does it just goes through each individual operation and just puts the data type of this thing onto the type stack right and then checks if the you know types you know match together right so when it encounters 35 it will put integer onto the stack then another integer onto the stack then it will encounter plus and it knows that plus consumes two integers so it will look at the type stack c2 integers and say okay that's type checks that actually type checks so everything's fine so and when it encounters if something interesting is happening it splits this stack in two right so essentially it has an execution context uh which has its stack of the types and stuff like that and if it encounters if it splits the entire context and continues the type checking uh in two contacts simultaneously so basically it will type check the execution if it goes here and then it will type check if the execution goes here and then both of the executions will merge together in here right so basically what we do we do like a small bfs on the control flow of the entire program right we bfs the entire control flow of the program so for this one there's no bfs it's a algorithm on graphs so uh yeah essentially you have a graph or like in our case it's a tree i think yeah it's actually a graph it's a directed graph and you're basically sending a wave um through that graph like this here is the wave going on and that's basically what we're doing we're just basically sending and type checking wave through the entire program right and that requires again as i already said copying the stack copying the execution stack and uh we can even take a look at how it's done in the python program so type check i think it's somewhere here type check program type check program uh so here is the execution context right uh i think it's here yeah there we go so we have a variable called context which is a list of contexts right and we start with a single context which starts at the instruction zero and as we go further and further uh when we encounter ifs and maybe if stars and maybe while and stuff like that well while doesn't split anything do splits uh we're actually copying the entire context we create a new one which copies the stack uh copies some other like expected outputs of the execution so this is just details but you see there is like the uh situation of splitting um the stack and stuff like that so in in python it's relatively easy to implement because python is a dynamic garbage collected and so on and so forth but we are currently re-implementing a porth in itself right and porth is closer to assembly than to um then to scripting language right so essentially we don't really have any uh automatic memory management and just copying stacks around is kind of tedious and kind of like error prone so what i was thinking is that we need to develop a data structure and approach where doing this kind of stuff in such a low level language would be easier right you see what i'm talking about so essentially like type checking requires like you know sophisticated algorithms and data structure they're not that sophisticated but you have to implement them in a low level language right um so and we need to come up with something that is easier to manage right we need to come up with something that is easier to manage right and the idea that i have in my mind is some sort of like a persistent data stack right persistent type stack right because we are operating on the on the level of types so and that could be achieved by implementing the stack using linked lists right so which is rather interesting so i'm going to show you let's actually open up my paint and in my opinion i'm gonna show you what i mean [Music] okay let me let me let me try to use this thing so essentially how do you implement a stack uh using linked lists right so essentially you um create a bunch of notes right so when you push a one you create a node uh that puts uh one like so i think i need to switch this entire thing right so here's the first element on the stack then you want to push two onto the stack right you create a new node you link the previous thing to one um the previous thing for a one would be null probably right uh and the top of the stack is going to be here so here is the top of the stack so you have two elements on the stack and then if you want to put three on the stack uh you create a new node and you link it with the previous one here is your new top and this is how you implement stack uh with linked lists if you want to pop an element from the stack you essentially look at the top you follow its previous element and you set the new top in here and you do something with this note you forget it if you're working in a garbage collecting language you remove it uh manually if you work in the menu um you know had manually managed language uh and so on and so forth so this is basically how you do that so what's interesting is that this kind of approach makes it super easy to copy and split the stack into so let's actually re-orient the stack a little bit uh let's actually orient it like vertically i also want to just make it a little bit more saturated if you know what i mean uh so i'm just trying to find a good color for this entire i think i think this is a good color okay so imagine that you're pushing some stuff onto the stack right so we have one so this is basically the first element in the stack this is null then you have two uh right and then you have three and then at at this point you decided you want to split this stack right so your top is currently pointing here and at this point you want to copy the stack and just split it right so what you do uh you keep this top as a separate pointer and then you create a new pointer right and you put something like four uh right so maybe i want to choose a different color let's actually choose like a red one like a pink one so this is a four and uh you have two stacks in here so one stack pointing here and another one pointing in here right and then you decide that you want to put an element into the green stack right in that case um uh you would do something like uh this so this is going to be five and uh basically um you're gonna have uh this node that is shared between two stacks right so the first stack is here right if you follow down here is the stack and uh if on the second stack you have this stack but in these sort of sheer like a part they sort of share a part so when the elements of these stacks are shared uh it's kind of dangerous to just like blindly remove them right so if you start popping elements out of the stack you can't really remove elements that are shared so in our case we probably want to forget them right so imagine that you want to pop an element from this thing so you basically go into follow uh and uh make this your thing your new top and you're basically gonna forget this thing uh right then you decide okay let's actually pop another element out of this thing and this is gonna be our new top and then you decide okay i wanna push a new element in here right i wanna push a new element in here so i'm gonna put it here so this is gonna be something like six and this is my new top right so you have two stacks in here the first stack starts somewhere here and the second stack starts somewhere here so here is the first stack and here's the second stack and this basically becomes unreachable node right this becomes an unreachable node uh but you quite easily uh can copy this entire thing so it's super easy to implement something like that in a lower level language where you just like create and dig the nodes and you don't have to copy like chunks of like memories and stuff like that you just like pile things on top and it makes it super easy so the question is um what do we do with sort of like a leaked nose is it is everything clear so far by the way because i'm not sure if i make any sense right is everything clear what i'm trying to say so is there something like yeah so you have this approach where you can just pile and leak the notes and don't get scared of the idea of leaking notes right i know that uh like we i have a lot of cs grads in the chat who are super scared about leaking anything right because it's super dangerous because their professor is to like punish them for for that right but uh here there's no your professor in here uh trust me it is okay to lick a little bit of memory it is totally okay to lick a little bit uh as long as it is as it doesn't consume your entire memory it's okay to do that so anyway it's 20 21 just buy more ram exactly that's exactly what i'm talking about uh so here's an interesting thing um we can [Music] basically pre-allocate a fixed amount of notes so usually when i uh work with like trees or linked lists and stuff like that uh the things that have fixed uh size nodes right they have thick sick um i'm reading your nickname and i'm trying to say thick or fixed with thick size notes yes thick auger thank you so much for twitch prime subscription i really appreciate it okay so usually when i'm working with a data structure with a fixed size nodes i like to pre-allocate a fixed amount of uh such nodes right so i like to pre-allocate like an array somewhere in the in the static memory right [Music] somewhere in the static memory thank you so much dms ve for twitch prime subscription um so maybe i want to actually make this entire thing a little bit thicker so you can see so here is what we have and each of these elements of that array is going to become a node uh that you can use for building this data structure right so and essentially i would uh implement a simple like bump allocator on top of that array uh every time i need to allocate a new node i will just grab this node and move uh the point to uh to the next thing right so i move it in here and then i locate another one and then move it in here and so on and so forth so that way i just like linearly like um you know allocating these nodes and within these nodes you can refer to other nodes while the pointers and stuff like that so basically this entire data structure can be linearly stored in some sort of like a global array with fixed pre-allocated uh nodes right and that way i'm basically allocating the um the nodes myself right and here is an interesting thing as i already said this entire approach is leaking the nodes right it is leaking the nodes but maybe for our type checking process it is okay to dig them right maybe our type checking process is not going to produce that much of a waste right uh it doesn't produce that much of waste that it will be okay if some of these nodes are leaked right and if there is not enough nodes we for the time being we can just basically allocate bigger buffer and as we uh get to some you know stable point we can implement like a dynamic uh dynamic growing thing in here uh that basically grows as you need more and more notes and you don't have to uh deal with the fixed ones uh but maybe it's not going to be okay so we'll have to somehow estimate how much waste our type checking process produces and if it does produce waste that we want to clean up how we're going to clean up uh sort of like this um leaked nodes right how we're going to clean up this uh you know leaked nodes so i think we're gonna uh we can implement a more sophisticated allocator in here right we're not going to only like bump allocate things right we want to be able to free the nodes right we need an ability to free the nodes uh since we don't need them and how i usually do that usually i create a second uh array where i keep track of the three nodes right so essentially i allocated a bunch of nodes in here and then i want to free this one before freeing this one i will grab its index i'm gonna put it in the array of three uh nodes right so i know that this thing is free and this is in my list and the next time i need to allocate a node again instead of like bumping these nodes all right allocated nodes i will just look at the array of three uh free nodes and grab the one by index two and reuse it right so basically by adding another array we have an ability to not only allocate nodes but also free them right and then later we use them so it's a very simple allocator right implementing an allocator for fixed sized objects is actually super easy it is difficult to implement an allocator for objects of variant uh sites right as a matter of fact i think i made like a series of videos on that on my uh on my youtube channel i'm i'm pretty sure i did it's something about writing your own malocan free and also writing your own garbage collector and stuff like that so i really recommend to check it out um so let me see sorting malloc uh let me let me see so write in your own malocan scene right i really recommend to check this out i think i think that stream was actually very interesting i really enjoyed doing it uh okay so i'm gonna put that thing in the description i'm gonna put that thing in the description so writing my own malloc in c right but here we were trying to implement an allocator for like a variable size object which is rather difficult to do fast uh here we have an allocator for a fixed sized object which is super easy you just have to erase the first array is pre-allocated objects and the second array is the index of you know free objects that you can reuse in the future it makes it super easy okay so we have an ability to allocate nodes for our weird data structure and we have an ability to de-allocate them but the question is how do we even detect that some of these nodes are leaked right because we cannot just delicate nodes as you pop them right because if you if you have a stack in here you pop this thing you de-allocated okay but now you're pointing in here and now you pop again and you delocate this thing but this thing is pointed by this stack right so uh you have to be careful you cannot just like blindly de-allocate nodes right which can be like reused by other things so we could take an approach of um you know reference counting as you can see we can clearly see that that node is actually pointed by uh two things but here is an interesting thing um okay so this thing is pointed by um maybe we can actually use that can we um maybe we can use a reference counter this is actually rather interesting so uh yeah we can try to use a reference counter another interesting approach like instead of reference counting would be to do a simple mark and sweep garbage collector uh as well um i'm not sure if reference counter is going to actually work properly we'll see we'll see but then the second option is going to be um basically mark and sweet because we know where uh the stacks start right so we can take these roots and we can bfs this entire thing marking what's reachable and then since we have an array of all of the nodes we can quite easily see what's unreachable and just de-allocated like that so this could be another way of doing this kind of stuff um so but if we implement this simple mark and sweep that means we'll need to decide at which point to call that mark and sweep um this could be interesting actually so we could call it when there's no more nodes right so it's actually rather interesting so if you're trying to allocate a new node you see there's no more nodes uh right you can try to do mark and sweep and just like delegate some memory but if you can find anything it's basically overflow okay so and the question is which one is going to be easier to implement we can actually explore uh different approaches in here right so we can try to implement reference counter and then maybe mark and sweep uh if we have enough time right is everything clear so far what we're trying to achieve is everything clear the cool thing about this approach is that it doesn't require like garbage collection or anything like that because effectively we're implementing our own allocator and our orange collector but since we're implementing a very specialized garbage collector and very specialized allocator it is actually easier than implement like a general purpose malecon free and general purpose garbage collector that has to work across several effects and stuff like that right we're not trying to implement our own garbage collector that is like in python or like in go because these garbage collectors are very very very generic they have to work for all of the possible sizes of the objects all of the possible use cases they're very sophisticated a lot of computer scientists like uh defended like a lot of phd thesis on that and stuff like that we're not doing that we're implementing like a very speed uh like a garbage collector for a very very small specific case which is a hundred times easier hundreds time easier so and this is kind of like kind of reminds me about uh the situation with like um game engines right so i used to implement like games on this channel i'm gonna do game development uh at some point again so and people were constantly asking me like why do you implement your own engine [Music] uh drake zorn thank you so much for 11 months thank you thank you thank you thank you so people were asking why do you implement an engine and this is because when people hear a game engine they instantly in in their head imagine something like unity or unreal engine and something like that but the reality is i was not trying to implement unity or unreal engine because they are very generic very big engines what i was trying to implement is a very small uh engine in which i can implement my very small game right to implement a very simple small game you don't need whole unreal you don't need whole unity you like actually need like a small very small fraction of the functionality of this engines and implementing that fraction is way easier than implementing the like unreal engine or unity or whatever dot or how many engines we have these days i don't know i never used any of them so uh and this is kind of a similar situation right so uh why would you implement your own garbage collector well i'm not trying to implement a garbage collector like in java or like in python or like and go like i'm not doing that i'm implementing garbage collector that works in very very specific narrow situation very very specific narrow situation which is 100 times easier than implementing something like in java right here we have to just like you know garbage collect like fixed size nose for a very specific data structure you see what i'm talking about it's kind of like similar this entire idea of like implementing like a small portion of functionality that does your job like works not only in game development it like works across the like software development generally um [Music] [Music] okay so i'm not really sure uh it looks like we can use counter ref because counterfeit will probably make it super easy uh but i also kind of want to have an excuse to implement market swim mark and sweep garbage collectors so we'll see anyway let's actually start uh prototyping this entity i think i decided to um try to prototype this thing in rust uh because why not um so because prototyping this kind of stuff in port is kind of difficult because sports is really low level language and it's kind of difficult to follow right now because it doesn't have like a lot of good semantical and syntactical um sugar and stuff like that so i decided let's just prototype this idea in rust see how it works in rust and then i'm going to just pause the port pour this entire thing to port right and then re-implement the type checking of forest import anyway hope everything is clear i'm not gonna close this thing yet and uh let's go ahead and implement this entire thing forthport so uh how should i call this thing a persistent stack right so here is the folder and i'm gonna do main.rs more like my ass haha got him anyway so let's write a simple hello world right so here's hello because i haven't programmed in rust for quite some time so i don't remember a lot of things so let me see if i still remember how to write a simple hello world if i remember correctly you have to do rust c right so it will take some time if we need to recompile everything okay and it compiled uh so and then uh if we take a look at what we've got we've got a single executable 3.3 megabytes executable uh so what's the size of the entire port compiler uh okay so the size of the entire port compiler is actually for 428 kilobytes but the size of a single hello world is 3.3 megabytes so uh yeah i mean it probably has like debug information or something like that uh anyway so here's hello world um so i wonder how big is it going to be if we like strip it is it going to be smaller oh it's actually smaller it's actually smaller than the entire port how about that uh anyway so it was primarily some debug information um okay cool so we need to implement uh the type stack right we need to implement the type stack and to implement the type stack we need uh the data type right so let's actually introduce it so i think i'm gonna since porth has like three types right it has integers pointers and booleans uh let's actually encode them as enumeration right so we're gonna say data type and the first data type is going to be an integer so here's an integer then we're going to have a pointer and then we're going to have a boolean right so this is primarily for the demo purposes right so it's not going to have any meaning it's just something that we want to put into the stack right so and on top of that we probably want to actually derive something like the box so we can um you know read that and so on and so forth so maybe this entire thing is going to be cloneable and copyable right uh in 82. thank you so much for two months of tier one subscription thank you thank you thank you and welcome to our epic rust club finally we're doing rust we've been talking for like half of an hour about ports and stuff like that but finally we're programming in rust uh anyway so let's actually implement uh like a single node that is going to hold our data type uh right so let me let me think so it's going to be basically a structure and i want to call it a frame right because since we're doing a stack uh the elements of the stack are usually called frames i think right usually right i don't know maybe it's specifically for call stacks all right so this is gonna be uh a frame and uh we're going to have uh something like type type is already taken so let's call it data type right and this is going to be just a data type and we need to keep track of the previous frame right we need to keep track of the previous frame so i'm going to do previous which is going to be basically a box to a frame uh but suppose it has to be optional right so uh something like this but here is an interesting thing since i want um since i want to pre-allocate a lot of frames right i want to pre-allocate a lot of frames um maybe it would be easier to actually refer to those frames as why the indices in the pre-allocated array if you know what i'm talking about right so essentially we can have something like struct uh frame a lock right frame allocator uh let's call it a frame eight or right so basically ater stands for allocator the same way ctor in c plus stands for constructor constructor detour stands for destructor destructor in our case ator is going to stand for allocator allocator right so so we're going to call it frame ater sounds good sounds good sounds to my gucci okay so and uh basically what we can have in here we can have frames right so it's going to be a vector of frames and frames essentially are going to refer to a specific index within that array of frames right it's going to be something like you size and by doing that by the way we will make the borrow checker shut up right so essentially here is the trick if you don't want to deal with the borrow checker and all of this nasty stuff lifetimes and whatnot just switch from pointers and reference and stuff like that to indices within array and that way you disable borrow shaker this is like a small trick for all of your ass developers out there who got tired of borrow checker this is how you do that and so yeah so not everybody knows that but in rust there is a way to disable borrow checker without unsafe block you don't even need unsafe block you just like use indices instead of pointers and there you go you you have no borrow checker uh so uh indices instead of pointers is actually more common pattern for more complex data structure of course because for more complex data structures you need to disable borrow checker of course it is a common power for that so obviously if you're doing anything complicated you want to make the borrow checker to shut the up uh so that's why you're gonna start using innocence anyway so here are the frames and um so we also need to um keep a list of the free frames right so let's actually do something like this free vector use size um okay so uh to do two i have a couple of interesting ideas so uh let me see let's make an implementer an implementation for frame a time it's a little bit cold in here to be fair it's a little bit cold in here maybe i should put on my uh my sweater anyway uh okay so what do we need in here uh we need to be able to allocate a frame right uh so so let's implement some stuff in here i'm gonna derive the default for this one and also the default for this one uh and we need two operations we need an operation that allocates a frame right so this thing will take immutable self and will return the actually it will return your size uh and then we need a way to free uh free a specific node so it's going to take immutable self and then uh let's call it an index right use size and stuff like that so i'm gonna mark this as to do uh here's a very annoying thing um it's unclear like use size it is unclear that by you size we mean an index within this allocator so i think it would be nice to have and a type ls called something like frame uh frame index right so it's gonna be frame index is gonna be basically use size uh i don't remember if you have to put semicolon here maybe maybe you have to so and uh now instead of few size if we mean uh like an index we're gonna actually use a frame index in here frame index so uh all righty cool uh another interesting thing i want to have in here i want to be able to dereference the index if you know what i'm talking about right so you have an index and uh you want to take the reference to the frame by that index so let's actually implement something like uh draft uh all right draft is the ref like a special method in one of the traits it feels like it is but i'm not a rust developer so i'm gonna stay ignorant and just like use this word uh right so this thing uh if drf is gonna be actually immutable so i think we're gonna grab it as immutable we're gonna accept the index and i want this thing to return um immutable reference to the frame right so and of course uh we have to have a mutable variant of this method as well so we're going to have direct from youth and this thing is going to just return an immutable reference so this thing i think this is all of the operations that we want to have for this specific allocator right uh let's go ahead and implement them all so first i want to check if this thing even compiles so it's going to be rust c main rs so data type there is no default for the data type which is rather interesting uh so maybe we don't wanna it's interesting so i think we don't need that okay so everything's fine everything's fine we have a bunch of a bunch of warnings but they don't matter they don't matter at all uh okay so when we are allocating a thing uh first thing i want to do uh so imagine that you have a frames right so we have a bunch of frames in here so frames is equal to like uh something um a b and c and d so what's interesting is that if you take a length of the frames right if you do length uh it will point to the element after the last one right so length is equal four the elements are numbered from zero zero one two three and four is pointing here so that means this is basically what you need to return uh to the user who calls a lock right so we're gonna do something like uh result right here is the result uh and then uh we need to basically push a new frame which essentially means that we need to have maybe a default implementation for the frame or maybe we're going to accept initial value through that method which we're going to move inside in here so we're going to actually accept it by value which essentially moves if i remember correctly rust moves the elements by default into this thing and we're gonna just move it into the uh into the vector right and after that we're gonna just return the result there we go so we implemented a simple allocator but it doesn't take into account the free right so um we're going to implement that a little bit later i'm going to implement that a little bit later or maybe we're going to implement that way later when we actually try to implement the you know memory reusage strategies maybe for now i'm gonna just leave it as it is uh we won't be able to free anything uh and i'm gonna go ahead and try to derive this thing right so uh what we're gonna do in here we're gonna take the frames uh right and i'm gonna try to get though we can actually try to be a little bit more safe in that regard right because if i remember correctly if i remember correctly rest up dogs api so let's take a look at the vector where is the vector so here's git could have actually searched specifically for vector get right can you do something like that in in here uh it does not return me it's very very weird because is that because vector doesn't have get or is that because this uh website is just like not working correctly because remember vector had get uh or am i no it doesn't have get huh it's very strange okay um does it have get or not i remember um get to get get get there is get okay there is gets all right that makes sense uh anyway so essentially the reference is going to mean that we just do get right so we just get by that index and index could be incorrect by the way so and we're also gonna do a similar thing for a mutable one right i'm gonna do a similar thing for immutable one so if i try to build this entire thing so it fails because this thing is supposed to return option uh right so is it gonna compile now uh what do we have in here uh consider change this to mutable yeah this one has to be immutable oh sure and there we go so everything seems to be working okay so we have uh frames we have data types we have allocators and stuff like that i think the time has come to implement a stack on top of that allocator right the time has come to implement a stack on top of that allocator so let's actually create a structure and um so how we're going to call that i'm going to call it type stack right so this is going to be type stack and that type stack is going to have just a pointer to the top right so this is going to be just that option um frame index there we go so this is basically what we have in here uh type stack and in here uh what we're gonna have we're gonna have an operation that pushes uh a specific data type right so we're gonna have data uh type uh of course we're gonna take uh a mutable self then we're gonna take data type and another important thing is we're also gonna take an allocator right we're gonna take an allocator maybe i'm going to take it as the second uh parameter in here because this operation will allocate a node and it will allocate it into this uh allocator right so we're going to take it as mutable one so this is going to be called frame ater uh and there we go uh so this is what we need in here and uh when we pop something uh since popping does not really does not really free anything because we're not implementing any memory preserving strategy uh we're not gonna take an allocator right so if we we're gonna do pop we're gonna just pop that thing uh there we go cool so uh let's actually you know create the allocator somewhere uh so this is gonna be a mutable eta uh and we're gonna do frame a to default all right so we're gonna create a default frame allocator then we're going to create the stack type stack default and we're going to try to push a bunch of things onto that stack right so i'm going to do stack push um so we're going to do a mutable ator data type uh pointer the data pointer uh then integer and then the boolean and then i want to be able to basically dump the content of that stack just to see if it even works or not so we're gonna do something like stack uh dump uh right and it will just dump it to the standard output so we'll have to implement this entire thing is everything clear so far what we're trying to do in here right so we implemented like a simple frame uh we implemented allocator that pre-allocated a bunch of frames and now we're implementing stack that allocates all of its nodes into into that allocator right so we're not doing anything special so far right so we're only preparing so it's just like a setup and the punch line is going to be a little bit later hopefully if there will be one i'm not even sure if there will be proper punch line but we're just exploring things um okay so we're gonna take um a mutable self yeah immutable one so let's see if this thing even compiles still so we don't have a default thing so let's create it like that derive default uh let me see okay everything seems to be fine and if i try to just call this entire i think it should fail with not implemented right so it panicked at 48 and it couldn't push anything in here okay cool so uh what we want to do um we want to create a frame right so in allocator fnl uh oak we have to provide the frame so and inside of the frame uh right inside of the frame we have to provide the data type so i can just do data type uh right so they have the same name so i can just use it like that and now i can do a very interesting thing i can set the previous to the top of the stack so i can just do self top and so this is the previous right there we go uh so and previously if i remember is optional yeah it is optional so and then i'm basically allocating this frame and i'm moving it inside of the allocator and this thing returns me a new index that i wanna uh assign to the top i wonder if the borrow checker is going to be okay with that so and also this thing has to be wrapped in some and i think this is basically the entire push i think am i missing anything i don't think i'm missing anything right so the only problem is that this kind of stuff could be you know like maybe borrow checker is not going to be okay with that we'll see um we'll see we'll see uh why are you not trusted really sorry so let me actually quickly trust you so the bot is not gonna ban you anymore really sorry uh self top uh needs some uh well we'll see the compiler will tell us okay uh wasn't even link well self top was a link so is there even a top domain right there should be like a pair of the main top and bottom domain right uh all right so there we go so it's not really compiling so it's 56. uh okay so that actually worked uh that actually worked uh cool the borrowed checker has improved over the years so we can even now write one liners like that i don't know why i feel like the bro checker would be not okay with that but it's totally fine uh okay so now if we want to dump something how we're gonna dump that um we can just basically iterate through the through this thing right so we can do something like uh mutable uh top and then i can just copy the top and basically while let some index equal top we're going to oh we need an allocator to reference the index that's very interesting actually right so you have an index but you can't access the frame without the allocator so we'll have to actually uh grab this thing like so eta uh actually we don't need to be uh we don't need the uh editor to be mutable so we're gonna grab it as a mutable one uh right then i do draft right i derive the index and that gives me the frame which i can now print uh so let me quickly try to do that so this is going to be something like this uh right so i de-reference this thing and i just grab the data type within that stuff so it will just you know dump all the elements of that stack and then here uh top is going to be equal to you know what i think we need to save that pointer right so this is going to be frame uh right then i use the frame like this and then the top frame uh previous so it's gonna be it's gonna bring that in like a reversed audio but that's fine i guess it because it's like a debug information anyway uh right so let's actually try to compile this entire thing and something didn't really work well because this thing has to be debug right it has to be debug output uh are you gonna be fine now let me see so data type uh no field the oh this one is optional one okay so we know for a fact that index is a valid index right so and if it's invalid index that means we made a mistake somewhere so we're gonna unwrap it in here by the way this is an equivalent of the uh of sac fault right if you have an invalid index and you try to put an invalid index in here and you unwrap like that this is essentially trying to touch the memory that you're not supposed to touch this is literally a sackfold right we do we disable the borrow checker to the point that we can now have segfaults or something that's you know simulates segfault like imitates the sac faults you know what i'm talking about isn't that interesting actually when you start using indices instead of pointers you're actually getting back to all these problems that borrow checkers supposed to solve so you have to be constantly aware of that while you program programming in in rust right so you have a way to disabling borrower checker but once you do disable borrow checker you have to be aware that you're bringing back all of these problems that borrow checker is solving right so and this is basically where you can suck fold if you have like incorrect index [Music] so an anonymous user gifted a tier one sub to olive is a word thank you so much anonymous user for a gift it's up and all with the word welcome to our epic rust club cheers by the way okay so let me let me see so that's fine let's see if it's gonna work okay so uh we have to supply the allocator uh and it worked look it printed boolean integer and pointer and we push them in a different order in the reversed order right pointer integer and boolean so the stack actually works uh so then we can try to do some other things so we can try to pop pop the stack and as we pop it uh i think we don't really need anything right so let's give it a try uh because popping the stack is essential well yeah we we need to take the allocator but we need to take the allocator as an immutable one right because we don't need to allocate anything within that allocator so this is gonna be frame eta uh there we go and then what i have to do i have to do frame a to the ref uh dear ref um this one is interesting so right if you try to pop the empty stack right so the empty stacker will have nothing should we allow popping from the empty stack let's actually allow that so if let some index equal self top right we're going to dereference that index and we're going to unwrap it right and then i'm going to do self top frame uh previous right there we go so that's basically what i have in here so then i'm popping this entire thing uh okay okay so i have to provide the immutable data uh okay still doesn't work type different immutability are you sure about that because yeah i don't think we need that there we go so as you can see we pushed a pointer integer and boolean then we popped one element right now we have integer and pointer uh and then i can do push right i can push this thing back uh let's actually push another point right so what we should see we should be able to see pointer integer point uh without any boolean uh and as you can see everything works but there is an interesting thing in here uh this pop licked a node right there's only three elements there's only three elements on the stack but we allocated um basically there's four nodes taken we can even see that um okay we can do something like uh to the two allocated uh nodes and we can just go into the allocator uh it's actually frames uh frames and take the length of the frames right so this is basically what we can do uh to to to print ln has to be a macro there we go so as you can see uh there is three elements on the stack but we allocated four frames so some of them are um you know actually wasted so which is rather interesting which is rather interesting so uh the most important thing here is um being able to copy this stack right we want to be able to clone this stack um and to be fair i think we don't really need to do anything special to do that right so if we just enable clone and copy just copying a single number is already copying the whole stack so this is the beauty of this approach you need to split the stack you don't have to copy anything you just have to copy a single number and there you go now you have two stacks it's pretty cool uh azura akumori thank you so much for tuning in uh thank you so much for two months of uh twitch prime subscription thank you thank you thank you and welcome to our epic rust club uh okay so that's pretty pogue so if we just allow link in the memory so it's already working so you can actually split the stacks and you know do this stuff quite easily so uh thomas thomas 1992. thank you so much for the wish from submission thank you thank you thank you and welcome to epic uh rust club okay so let's actually test how this thing is going to work so here is the stack so let's call it something like stack one right so uh we allocated or we basically pushed a bunch of stuff onto the stack right then uh i want to create a copy of that stack so i'm gonna do stack one uh stack two and i'm gonna assign stack one to that basically copying it hopefully am i copying it i think i have to explicitly say clone well i mean i don't have to explicitly say clone because i said copy but let's actually remove copy so we have to explicitly do the clone so we can see that we're actually cloning the stack okay so we created the stack we cloned it and now we can try to modify the stack one right so stack one uh i'm gonna pop the elements from the stack so it's gonna be eta and uh then i'm gonna push uh eight uh data type uh pointer right so and what i wanna do in here is uh i want to print both of the stacks and just see that the um the copied stack still retains uh its original structure right i want to just confirm that copying the stacks actually works and no matter what you do with other stack without a copy of the stack the copy of the the other copy of the stack is actually stays retained right if you know what i'm talking about um okay so let me see so we want to print something like println uh stack one right so here's a stack one and then we want to do this thing and this is going to be stack two so let me see all right so maybe i should have actually put a little bit more spaces in here right so we're gonna just do something like printer lan just to add more spaces is it gonna be sufficient yeah it is seems to be sufficient okay stack one uh as you can see it contains pointer integer pointer because we pushed pointer integer boolean then after cloning it we popped the boolean and we pushed the pointer so that's why on stack one you have pointer integer pointer but stack two still retained its original structure boolean integer pointer the one that we had before colon in it um right so yeah the one we had before calling it so it still retained it uh even though we popped uh this stuff and uh you know the other stuff and it's still allocated four frames so essentially instead of like linked list in reality we have a tree right so it kind of resembles the git history if you think about it yeah it actually kind of does this is basically a git history right we can even try to maybe dump this structure of the let's actually dump a graph with how about that because we can do that all right uh allocator has an access to all of the frames right so and in the frames we have the the pointers to the previous one so we can quite easily dump the graph with data and just look at this entire thing so let me quickly do that uh frame eternal we're going to do dump dot right so we're going to take it as irritable it's actually pretty cool [Music] i love how every stream turns into graphic stream only the ones where we have to work with the uh three data structures right because every time you work with the tree data structure you want to kind of visualize the the tree and the easiest way to do that uh is graphics so why not um all right so let's do print ln and this is gonna be d graph and we're gonna call it frame um i don't know stacks something like that right so this is gonna be stacks uh println and we'll just do something like this so in here uh by the way visualizing this entire thing is going to be super easy because we don't even need any recursive algorithms so we can just iterate through all of the frames uh right and just dump them as edges so that should be sufficient i think uh i think that should be sufficient so uh let me do it like so frame in self frames right there go here we have a frame and um let's do it like this print ln one two three four uh it's going to be um node and then id of the node and then we can have a label uh like so uh this has to be like a debug one uh and then i can say okay i probably need to enumerate this entire thing right so i want to enumerate it so i have an index and the frame right so this is what i want to have in here so here's the index and uh then for the frame i have to take its data type uh and that should be sufficient enough and the thing the second thing i want to do in here well it only makes sense if you have the previous one right so we have to do something like if uh let some priv index equal frame previous we need to basically connect together these two nodes uh know that to node that so the first one is going to be just the index and uh this one is going to be the previous index and it only makes sense if you do have that previous right that's why we we have a condition here and that should be enough uh so let's actually try to compile this entire thing so uh you have to do it like that thank you compiler very cool uh oh do i have to like escape this entire thing i don't really know how do you type do i have to do double of this thing uh i think i think you have to do double actually like you guessed it i think enumerate uh exists only for word but it's straight is not satisfied uh so do you want me to do eater do you want me to do eater or something yeah i wanted him to do either okay cool uh so let me see now instead of doing that we can do something like either dumb dot right so let's just dump the dot uh and uh here is the basically graph these data structure of these nodes it would be nice to actually save that to some sort of a file right um so to save it as some sort of a file i think dump dot should accept uh you know the sync into which you want to save all of that right so and sync is basically going to be anything that implements um you know writable interface right so we want to have something like this if i remember correctly to write into this writable interface you have to do something like write a len right and then you just use sync and i feel like we have to get it by a mutable reference right so i don't quite remember how to do that so the compiler will tell me hopefully hopefully the compiler will tell me but anyway uh right is not found okay so let's actually try to see where right is located where right is located so it's located in somewhere in iur right so we have to do something like use std are you right okay so uh okay this entire thing expected nothing um expected results so we have to what would be easier i think the easiest thing to do in here would be to like dump dot to return io result nothing right like this and for each individual right we could like put a question mark in here so in case of like error uh it will just fail and then at the end here we can just do okay is that how we do that in uh in rust i think i think this is how we do that in rust right the usual thing so and let's use stdio right so and then here i guess at the end in here we want to like unwrap this entire thing but it complains about not being able to find the you know instance of writable interface so we'll have to open the file so if i remember correctly you have to like use file and you can basically create it right you can do file create in here yeah there we go so this is what we can do uh so let me try to do that i'm gonna do use stdfs file uh right and i can just can i just like you know file create file create uh output dot right uh output dot uh it didn't really well uh we have to unwrap it i suppose right so well so create a should return option right or a result rather should return a result and we accept by immutable so we can just do unwrap and then just do something like this this should work right so it seems to be working uh okay so and now if you take a look at output dot there we go here is our output dot isn't that cool i think that's pretty cool so um now what we can do we can just do dot tsvg o output dot and it generated an svg file which we can finally open in chromium and there you go so here are the two stacks the first stack uh has pointer integer pointer and the second stack has boolean integer pointer right so we have two stacks and they share two elements uh they share two elements and we derive that information from the allocator right we derive that allocate the information from the allocator that's actually pretty cool so we have a very simple debug tool um cool but again uh i want to do the same thing as i did for the tree stream i want the program itself to actually you know call graphies and stuff like that but uh luckily in rust it's a little bit easier um right in russ it's a little bit easier to do because it has like command interface or something like that i don't quite remember um anyway so let's actually do like this let me output file path i'm going to say this thing i'll put file path in here and we want to do a login we're going to say info generating uh this thing uh output file path right file pass there we go so then we generated this entire thing and then i wanna call an external command but i don't quite remember how to do that so command uh i do remember there was a command there we go so the process command and that's pretty straightforward not gonna lie so you just create the command you provide the arguments and you take the output and then you expect that it didn't fail so okay so let's actually use that can your c do that by the way no it cannot do that uh process uh command in your stupid c you have to do fork exec and stuff like that you have to first fork a child then you have to execute the child you know the usual stuff anyway so um sorry new dot and then we have to provide the arguments so this is going to be arcs and what going to be the arguments uh the first argument is going to be t svg then o and then we have to use output file path right and then we have to call the output and do we have to do the output because i don't really care about the output uh right but it feels like that you have to um so fn output so execute the command as the child process waiting for the finished well you you have to do that apparently okay so but maybe i can just throw it away um so it's gonna be args then the output then expect um expect dot uh command should have uh executed success successfully but it didn't right okay so if i try to now around this entire thing uh it didn't freaking work because this thing is not a macro yet again uh okay so what do we have in here consider using uh okay so we have to put a semicolon in here and uh cool it generated this thing but it didn't log the command that it was executing is there any way for the command to actually log while it's executing because it's not particularly convenient i think [Music] ever so there's a status uh i didn't think so is there something like echo [Music] status so you can use status instead of output is it gonna echo the command uh is it going to echo executes a command the child process is waiting for the finish by default it doesn't echo so i need like echoed the command because i want to see what's currently the command executing okay whatever so uh let's continue let's continue what's going to be the next thing uh the next thing that we wanted to explore is basically um some sort of a reference counting right um some sort of a reference counting but for a reference counting we need to be able to free the nodes right we need to be able to free the notes i think the easiest way to free a node is just straight up add that node to uh i mean yeah no to the list of free ones right there we go so uh right so you're trying to free a specific index and it goes into the list in here and when we're trying to allocate a new node uh instead of grabbing it from the uh from the vector first we have to check uh whether we have anything in the free right so this is what we can do in here so if a self-free len is greater than zero we have to basically reuse a single note from here otherwise we have to like allocate a new one so oh and here is an interesting thing here is an interesting thing you get back to all of these problems that borrow checker is supposed to solve what if you double free a node accidentally you're gonna add this node twice to the list so the next alloc is gonna you reuse already allocated node so you'll have to add some sort of a check that checks that you're not trying to free already free node or that the node that you're trying to free is even correct so you're getting back you're getting back to all of these problems this is actually pretty amazing i think uh you're starting to have sex faults you're starting to have like double freeze and stuff like that uh um should use static size arrays vec is kinda cheating uh i feel like you don't fully understand the meaning of word cheating cheating is going against the rules right at least this is the definition and now there's no rules what rules are you talking about so oh my god anyway imagine like accusing me of cheating in the environment there where there is no rules like you by definition in that environment you can't cheat like it's just like you made up and you had your own rules and you're accusing me of breaking rules that you made up in your head well cool so i'm happy for you uh anyway so i think i want to make a small break because i need to make a cup of tea so and after the break we're gonna uh we're gonna implement the you know allocation from a list of three nodes anyway um okay so let's continue so how we're gonna actually get the free node i think we have to do a pop if i remember correctly in vec there is a very convenient uh method called uh let me see so where is here is the and what's interesting about is that it returns an option right uh which means that if this thing is empty it will return nothing so we don't really have to check uh the length uh what we can do is just like instead of playing we can do and uh here we can have some uh index uh rather some result right uh which we can just reuse in here so here is some result uh and essentially i need to do self frames result and i need to move the initialize thingy in here right so this is going to be init and then i just return the result how about that how about that how bad paint looks cool yeah so that's basically what we're doing here i think um two to the two so here's the result and then you need result result blah blah blah blah blah blah i'm just thinking like my brain sees a result in both of the branches and i keep thinking can i compress that if you know what i'm talking about and it feels like i can't really compress that and maybe i shouldn't bother trying to compress that so maybe that's fine that looks fine because the most logical thing in here is just like move it away like this but you can't do that because the result in one branch and result in another one are two different things um right yeah it's kind of difficult to compress this code i didn't see a good way to do that and anyway is going to be just like meh okay gum uh so we implemented free and every time we pop something we can now um we can have three things how can we test this entire stuff uh let's go ahead and just remove uh the stack two and let's just work with the stack uh stack one right so we're gonna only have stack one and every time i pop something from the stack right so we are essentially referencing this thing uh right i can try to do either three and three in the index right i'm freeing the index uh so after that i can do stack one pop and i can pop it three times and what i want to see at the end of the day is how many nodes we have located allocated uh these frames and i can do eta frames this one is actually kind of difficult to tell because we are reusing the frames so the length of the frames is going to be uh equal to three no matter what right right allocated these frames um okay let me let me see what's going on so here's the pop uh so we've got some sort of the name holy that's a pretty big just a second i need for for my streamlabs too uh thank you anonymous for 50 donations are you mr beast you're donating so much money thank you so much thank you for the streaming i always learn something you're welcome you're welcome thank you for for the support i really appreciate the support thank you mr beast cheers um all right so uh thank you thank you so much really really appreciate it you didn't have to i didn't think i deserved this much to be fair right uh i'm just like posted on the internet come on um not as much as the previous guy but thanks for the content from amazon uh thank you so much ben dershow for 14 months after one subscription thank you thank you thank you really appreciate it if flat is basically a match statement with just one pattern match yeah and this this is something that kind of annoys me to be fair uh because it makes it difficult difficult syntactically to evolve into a match statement you see quite often um you start with e flat because you want to handle only one case but then you want to start handing more cases and that means you have to rewrite the entire structure to just migrate to match it would be kind of cool if this e flat construction was was designed so it's super easy to turn it into match because that's quite often what you want to do you know what i'm talking about there's just like something really like there's some friction between e-flat and match that always annoyed me for some reason [Music] sorry for being rude in apr before i tried to refactor your code once again using generators but eventually i got into heterogeneous data structures which i could not implement using rust type system don't worry about being rude in pull requests at all this is totally fine i do not read pull requests so i didn't even see that i have no idea what you're talking about so don't even worry about that so um yeah don't worry about it that's totally fine um so let's continue [Music] so i want to do a pop i just want to see yeah i want to see that we are located like three frames right so this is what i was talking about uh let me let me see um pop so we have to provide a time i think i can use a little bit of emax magic right uh okay so here's the eight or three uh consider changing this mutable reference okay oh yeah you see pop before never delocated anything so it never modified the state of the allocator so now uh it frees things and now it needs to modify the state of the allocator so let's go ahead and do that uh okay so we've got this thing and this thing has to be immutable now man i love busy work the rust actually forces them i really love that uh looking like you know you program in rust and it forces you to constantly change like mutable reference to immutable ones like change that and that and that and it feels so productive it feels like you're doing a lot of things you know what i'm talking about uh okay cannot borrow as mutable because it's also borrowed hmm [Music] oh i see what you're talking about i do in fact see what you're talking about the person of fun subscribe with twitch prime thank you so much uh the person of fun uh for subscribing which one welcome to our epic roswell so essentially the only reason we need this frame is because we want to get it like the previous value so what we can do here is we can grab this thing and just literally inline it like so and put it here that way we briefly uh basically borrowing the atom and then we release it so we can borrow it again hey what do you think einstein for uh four months of twitch prime submission thank you thank you thank you and welcome to epic gross clock so that way the borrow checker is not going to complain we have so many subs today polish it thank you thank you jay riesel for twitch prime subscription thank you thank you thank you welcome to our epic rock club uh rust compiler is so helpful to be honest such pretty error message speaking of pretty error messages like vm compilation mode or whatever the it's called you know the thing that handles the make command it has a hard time parsing this thing without custom regular expressions swimmers do you know what i'm talking about i think majority of the viewers just use the like a specialized plugin or extension for us which kind of handles that but by default veeam has a hard time actually processing this thing it's kind of funny uh i can actually show you because i was planning to use veeam uh for today's stream and then i encountered that problem and then i thought like i don't want to deal with that so uh let me let me see so persistent data stack right so if you go to here and if you try to first you have to say it make prg program right so let's set it to russ c main dot rs right and if you do make uh right so here is an interesting thing it calls the compiler and then it will parse the first error right it will parse the first error and then it will jump to that error but here's an interesting thing it will parse this as a file name to which it has to jump right so and if you press enter your entire screen is going to be empty and you're going to be wondering why until you try to save your file and it will say say it saved it to dash dash grader space main.rs right so then you can quit vim and you will find that you have this file which you can't even like delete properly right because it looks like it's a flag to a ram so to delete it you have to put like dot slash well i google the lives like around the internet so the usual solutions are to mess with error format right in vim there's a thing called uh error um i think it's error fmt um help error format yeah it's error format so basically it's a list of regular expressions that are responsible for parsing this thing and the other solution is to use specialized extensions for rust which parse these kind of things themselves and they don't have that problem uh so since every beamer uses these specialized extensions i'm the only one who's encountered that problem so i just thought that i don't want to deal with that so yeah here we go i just wanted to share that information with you uh emacs has no problems parsing all of that so it's just like it's just that it's kind of funny choose by the way can your emacs do that by the way can you do that i don't think so you know about error format i think it's like an archaic thing that nobody uses almost like the make command the cate has the same problem with those errors well the problem with the error format is that it's very annoying to modify so if you want to fix that problem you have to go through a lot of pain to put regular expressions in an error format in a particular order so it's kind of like something that you don't want to mess with anyways so uh i think we should fix the problem now there we go so the problem has been fixed and now as you pop things around uh it will delicate this thing but it still says that it has allocated three frames you see it still says that it has allocated three frames and this is because uh the allocated frames are located in the free list right so and if we do something like um bring to len right to do something like paint on uh freed uh this amount of frames so it's gonna be 803 len so it will say how many frames it's allocated and then three three frames so yeah uh and if you try to allocate um some stuff afterwards right if you try to maybe push integer one time uh you're gonna have still allocated three frames but three two uh two frames because one is already taken right so that's actually pretty pretty interesting uh so we have a thing that can free the frames now the next thing is to free the frames automatically right so one of the solutions that we want to explore is the reference counting right we want you to explore the reference counting and um where are we gonna do a reference counting the the most logical thing to do uh the reference counting in is in the frame itself uh right so let's actually put uh like some sort of a field in here ref count which is going to be your size uh is that a good idea to do it like that i think so i think so um and who's going to be responsible for the ref count i think the allocator should not be responsible for the ref count i think i think it should not be responsible for that uh it should be responsible the stack itself should be responsible for that right as you pop an element uh right you decrement the ref count for for the new top and then as you know the the ref count reaches zero right uh you essentially you essentially delete this entire thing all right so that's pretty cool uh so that also means that we cannot uh we cannot clone this stack like this anymore you you can't clone it anymore like that so essentially what we have to do is to implement our own clone method that also increments the ref count for the current thing in here yes that's what we need to do so i'm going to remove the clone from here right so i'm removing the clone and i'm going to implement my own clone in here there we go so and this thing is going to take oh this one is interesting by the way i do need my own clone by the way right because i will be dereferencing the um the pointer and to the reference the pointer i need allocator so this is going to be like a special clone that on top of taking um i think it will take immutable self it will also take a mutable allocator frame beta like this and it will return i suppose self right it will return self um cool all righty so here's the frame so here's the data type the previous one is gonna be that and uh what's interesting is when you create a new frame right so we're pushing a new frame onto the stack uh ref count is gonna be one because the only thing that is uh pointing at that frame is the type stack itself right so it's gonna be just one uh when we're popping the uh the thing right when we pop in the thing i need to de-reference this entire thing take the previous but on top of that i also have to decrement the ref counter decrement the ref counter [Music] so let me see how we can we're going to do that so here's the frame i think it has to be mutable i think i need a mutable frame so this thing is going to be basically mutable uh then within that thing i'll have to take the rif count and decrement it right i'm decrementing this thing and then um this one is going to be rather interesting actually so i assign frame to the previous one and the only time i need to free it is when frame ref count becomes zero right it reaches the zero unless then i wanna free it but that creates a lot of like weird stuff uh because we borrow ater in here and we keep it borrowed up until in here so we cannot borrow it for mutable again so that means we have to do all of this stuff like in a very confined um scope right we have to do that in a very confined scope and the question is how can we even do all of that so we can actually wrap this entire stuff in its own scope so the ater is gonna stay the editor is gonna stay uh borrowed only within that scope right and um here we're going to move this condition at the end of that scope right we're moving it at the end of that scope and we're going to assign it to some sort of a variable um something like delete right and then if delete you go and freeze so you see uh we only keep eight are borrowed here and then we unborrow it and then if we need to delete it you borrow it back so basically we're moving that condition from here to here so and borrow checker forces us to do that so the only reason we do it like that is because borrow checker wants us to do things like that uh it would be kind of cool if i could have a block as a condition like that if you know what i'm talking about rust developers do you know what i'm talking about right so i could just have a block that is like an expression is that even possible can i just take this can you do i have no idea can i so that's my question uh that would be actually kind of cool so basically i say borrow it for the duration of calculating the condition and then unborrow it and then borrow it back to do the separation so okay first first of all i want to check if this entire thing compiles right because maybe maybe i did a okay i didn't uh so now let's give it a try uh right so i'm gonna put it like that this is the wackiest code i've ever written and it works what the this will confuse anyone so essentially you can have sequence of like statements that lead to a condition this is so cool you can do that you can do that uh so and the reason why i even thought about that is because you can do this kind of stuff uh in in port right in porth there is like a whole paradigm that i discovered right i discovered the whole part and fourth where like you have a wild do right and you have a condition in here uh condition uh but since porth is like it doesn't have any blocks in here you can actually use the space between while and do as the body of the condition right so and in fact it's it's used quite often in uh in parsing to break out earlier and this is basically what gave me the idea of using like a block of code as the condition for eve so and i'm surprised it works so maybe gonna do it like that that's actually pretty interesting it's really whacky do people live in the right rust like that [Music] yeah so this thing does in fact feel so ill like somebody's gonna look at that code and then they're gonna go like what the like what what the does it even mean like holy lots of people do okay that's actually pretty cool uh because it's kind of convenient to defend right it is kind of cool uh okay so we take uh we borrow this ater we the reference we remove its reference right then we set it to the previous and if a reference actually reaches the zero then we do free it uh then we do free it and it's kind of it's kind of important because you cannot just move this thing in here because you have to unborrow it first and then borrow it back that's what you have to do okay so on pushing we do reference count one here we decrement the reference when we dump we don't have to do anything on clone this one is rather interesting right on clone what we have to do is we have to take eta uh first of all uh if let some index self top now go and i do ater uh the ref as mutable right so this is gonna be index and then i'm gonna take a mutable frame there we go so and when you clone it you have to do a ref count plus one right so there is another count another reference uh pointing at that specific thing okay that's pretty cool that makes a lot of sense actually makes a lot of sense uh and then um i have to return self which uses well this just close and clones itself i suppose um self top top soft top i guess that's it right so we just check if top has anything and we de-reference that top and we increment its ref counter and we just like clone them ourselves it might be awkward if you ever need to debug that if but i find it easier to read that chanting that to function as people usually do do people even step debug rust because like i tried to step debug rust and the tooling for that was actually very horrible so i'm not sure about that um so rudeblack45 thank you so much for watching thank you thank you thank you and welcome to our epic rust club so i think karen need to unwrap this entire thing and everything seems to work i think we implemented like a reference counting what the did we did we implemented reference counting i think we do um so how can we test all of that how can we test so we can actually log something uh when every time we free um every time we free so um [Music] can the reference counter count itself i don't understand the question it is possible but i think you need ldb for some reason i don't think i said it's impossible i said that it's very annoying uh and i said that i tried that and it was in fact very annoying um so in like quite often if you want to debunk something without with the rust it's just like easier to do pretty type debugging um ldb can get painful yeah it's kind of interesting that modern environment kind of encourages you to do printf debugging because step debugging can be pretty powerful it can be pretty powerful and can help you to find very nasty bugs you can blame nasty bugs for for like a week type system or something like that but then at the end of the day step debugging actually very useful when you get used to it um so uh we probably want to okay i want to dump the the current state and just see how useful that is but on top of that i want to be able to to see what frames are freed you see like the current dump is not going to work right because uh some of the frames that you're referring to they could be freed so they're not available anymore but what's funny is that maybe it doesn't even matter you know maybe it doesn't even matter because we can just mark those nodes in a very special way right the question is how can we mark them so i can basically set up the connection between nodes in here i set up the conver connections in here and then after that um i can do the rest of this stuff it would be easier if the three notes were set right it would be super easy if they were set in the final implementation they don't have to be sets uh we just need to be well maybe it doesn't really matter right so we're not trying to be fast or anything does vector even support something like find can you find uh or it contains yeah it does have contains okay so i can just search for a specific element uh right so and essentially i can do uh so frame we found a frame and we can do something like if uh self free contains index and it does not contain uh we basically not gonna even render this entire thing so it is slow it is linear search but this is the debug output right so this is not gonna be like a final production solution and in the final production solution we don't even need to do the separation so this operation is only needed for debug purposes so yeah that's totally fine i think that is totally fine uh so let me let me see so uh can we have on top of the label i also want to have something like a counter right so i can do something like this so this is gonna be uh the strength and i think you have to use double quotes right so this is going to be double quotes and here we can use the counter so i can do frame uh a ref count right can you can do that so it didn't really work uh uh-huh so here is the index um so it has to be a reference for whatever reason uh so we don't have a file so let's actually make it file i like the simplicity of reference counting actually it's never used can i just allow that code because it could be dead sometimes just like myself haha self-deprecation uh is never used clone uh i think we're gonna use that so dump what is dump dump is not probably needed whatever okay so uh let me let me see so we have stack one right then i wanna do stack two uh and i'm gonna do it like this i'm gonna clone using the allocator right so you can only clone it by using that allocator then we do stack one pop uh mutable eta and then stack uh one uh push uh push uh mutable eta data type point uh data type pointer okay so this information is useless uh anything else we need to have in here let's try to call this entire thing and we have svg generated and let's take a look at this entire thing okay cool so this doesn't work uh so uh you suppo i think you're supposed to have two in here right i think you're supposed to have two but something went wrong during the cloning process and i wonder what exactly so let's find out uh let's find out uh to the tomb um i wonder what so if i just uh don't do any of this stuff will it work correctly uh i think it does right i think it does work correctly uh huh yeah okay this one is very interesting ah this one is very interesting so basically you have two pointers that point in here right so at this top you pop one out and this is the new top right this is the new top uh and as you push right as you push hmm how is that how's that so so there's a bug in push there's a bug in push [Music] so it's almost like i have to take the top and increment it by by zero by it's kind of unclear how it's it's really unclear how we're supposed to even do that like yeah hmm it's really unclear so the easiest way to work out this kind of stuff would be more sweet but maybe okay so let let's actually try to replicate the situation so we have this one uh right then uh this one and this this one right um uh at the beginning right you have one pointer so here is one uh then you push and you think uh right and you think you point here for a brief moment you have two of them right but then you go back to just one right uh and because of that it doesn't really make any sense to increment it twice or anything then you create another one so brief moment is going to be one but then you're gonna move it out so at the end you're gonna have this thing so you clone this stack right you clone the stack you have two in here right so by popping from the stack you essentially decrement this thing you decrement this thing go back but that effectively means that now there's two pointing in here so pop while decrementing one thing should increment another one right should increment another one which does not make much sense to me uh oh i see so and we have a situation with a single stack right you have a situation with a single stack uh which looks like this right so there's a one uh one and here is the pointer so by popping the element you kind of move down here right you move down here and that makes it two but then you sort of dereference this thing which brings it back to what right so you have to kind of like it's kind of finicky to keep track of all of this kind of stuff right uh and the question is is it even worth it but if we come up with like a proper rules to do all of that maybe it feels like the this kind of stuff should be probably handled on a different level yeah it feels like it should be handled on a different level maybe not so essentially the allocator itself the allocator itself when you free the node when you free the node it should look at the nodes it point to and decrement them as well i think that's what has to happen right so that's essentially what's going on right because that's essentially the operation that we're trying to do in here or also [Music] when you add a new node right when you add a new node uh and that nodes point to something uh we'll have to increment it as well it it feels like it has to be interplay between the uh the type stack and the allocator all the time right it's basically the interplay between them and i'm not sure it's kind of it's kind of painful to be fair it is kind of painful and i ran out of team so mark and sweep would be actually super easy to be fair with the mark and sweep you just have to keep track of the like list of all of these stacks and then you would just iterate through all of them marking which ones are already visited and then you remove everything else so that would be actually way easier you you won't even have to think uh about uh like when to decrement or increment or whether you forgot to do that or not or something like that so um yeah maybe we should try to implement mark and sweep what what do you guys think uh we can try to do that because i think i feel like it's easier for some reason right then messing with like ref counters and whatnot so uh okay for the um so instead of ref counter right let's actually go ahead and remove the ref counter uh so that way uh two to two so we don't have a ref counter so we don't have to print it in here okay so we don't need to do that stuff in here uh we don't need to have that stuff and we have to decrement anything oh and yeah by the way so if we're gonna do mark and sweep when we pop something we don't even have to care about this kind of stuff we can just go ahead and like draft it so uh yeah we can bring back uh-huh so we can do that this is gonna be top then um yeah we don't even have to do any of this stuff don't we so you pop you just you just do that okay so just let it leak uh just let it leak let it leak let it leak let it leak or let it leak memory costs nothing let it leak uh okay so when i clone something we yeah so that essentially means we can just use the uh the default clone uh okay and here that's where we clone all that okay so let me see let me see frame previous data type and stuff like that uh let's have something like visited false i've visited bullying i mean right so visited visited boolean visited is it going to be on the frame or is it going to be like a different data structure that's also a good question this is also a good question and what's interesting is that now if we're gonna do it that way i need an operation that uh like checks whether the frame is already freed or not so that's kind of a problem in here right we want to be able to do that but maybe we can have additional flag that indicates whether something is freed or not right so that way we can easily skip the freed frame if you know what i'm talking about that's actually interesting idea like free right by default it's going to be false right and that way you can quite easily check all of that you know what i think i want to make a small break because my brain is kind of like shutting down so and i already stream for two hours right i'm already streaming for two hours so definitely want to make a small break so um all right so mark and sweep is actually like solve some problems but it introduces another problems is that now i'll have to have a fast operation to check whether the frame is free or not and that will require me introduce like another field in here so maybe i want to still stick with the reference counting idea right so both of the ideas like have their trade-offs and stuff like that but if we can nail down the reference counting i think it's going to be you know relatively convenient to work with so maybe what i'm thinking is that for the reference counter we should get the rid of the free operation right so maybe instead of free operation we have to introduce like something like acquire uh a choir is that how you spell that word did they spell it correctly uh acquire by okay so that's gonna be acquired uh all right self i'm not sure if i'm moving in the right direction by the way so i'm just experimenting uh all right so this is gonna be a size uh this is not implemented and then we're gonna have something like release right so the commutable self index uh is size and this is going to be uh to do so you can acquire something and you can release something and we're not going to have like a ref or anything like that uh so an acquirer will increment the reference counter and releases can decrement the reference counter and if it reaches the uh like minus one or zero or like no why do you say minus one if it reaches zero we're going to basically free to ourselves so when we allocate something i think it will automatically acquire that thing right so it will acquire it um and we'll have to basically quite carefully uh call these two functions right i think that's what needs to happen uh all right so and the question is where should we store the reference counts um we can store them somewhere here maybe all right so maybe the frame itself should store them so it doesn't really matter right so because this is a prototype code we can just throw it somewhere here but it makes it rather inconvenient makes it rather inconvenient [Music] to the two uh it's going to be a rough count because the reason why it's going to be inconvenient by the way is because uh we you have to provide it in here in the in in the initialization right you have to provide it in here initialization but uh if we do it like this somewhere in the tuple uh right it's gonna be a little bit more convenient so um what is more convenient it's kind of difficult to tell right because the user should just stick with this thing so this one is definitely going to be convenient but i don't remember how to access specific fields of the tuple how do you work with tuples in rust uh so tuple let me see so here's the tuple and if i want to access like a very specific field it's a dot 0.1 or something like that okay so this is basically what i want you to see uh okay um so then i do frames uh result uh so let's actually let the compiler do the job like the so the compiler should just tell me what to do uh okay so this is gonna be the zero and then here we're gonna have frames might as well just do something like this uh one because we acquired this thing uh right away uh right and then here we push init and also one uh huh so and when i get this entire thing i also wanna get this uh right uh i'll have to map it by the way right so i'll have to do something like x zero uh and here also have to do something like x uh zero hopefully that will be sufficient enough i'm not sure if it will be sufficient enough let's see uh expected ooh expected uh because of return speed but got just frame which is rather interesting so that means i have to explicitly just do that stuff uh sure uh that is totally fine so and in the frame i got uh these things so this is not a frame anymore it's more of like a frame and a ref count right but i don't really care about the ref count so i'm gonna just simply ignore that thing uh okay does it work it seems to be working okay cool um all right so let's actually implement acquire right so when you try to acquire something uh we do frames index and then i take one and it incremented by one there we go so we just incremented it then if we release something i'm gonna do frames index uh one minus one and if it reaches zero right if uh self frames index one is less or equal than zero i didn't think it can be less than zero so we're just gonna do equal zero uh we are going to free this thing right we're gonna free this thing uh so when we frame the thing this one is quite important so we also have to release uh whatever it's pointing at right so this one is very interesting right we have to do self frame frames index cell frames index 0 then we'll have to take the previous right the previous and if the previous has anything all right uh if let some brief index right if it does even exist we'll have to release it again right so we have to release brief index like so uh so it sort of forms the chain right so it will uh create a chain reaction so i guess the need for this sort of chain reaction created the complication i was dealing with right so you you need to like cascade this kind of like releases and stuff like that um right so and obviously the borrow checker is probably not gonna accept that right so i'm just like outlining the idea um right so let's see if it's going to work and it worked surprisingly like i'm surprised the borrow check is fine with that oh this is because i'm borrowing this thing and i'm releasing it right away right so that kind of makes sense i suppose can i just like have something like i don't even know well i guess that's fine it's kind of a weird code but it's fine i guess i guess that's fine so we have acquire and we have a release cool uh so if i try to run this code now uh it it kind of works by the way it kind of works okay in the stack when i push something onto the stack right it right away acquires that thing right i don't have to do anything it just like acquires that uh and then interestingly enough so it should also increment the top but since we're updating the top it should yeah so this entire thing sort of like we have release and acquire that cancels itself out uh so we don't have to do anything in here in case of a pop this one is really really interesting so i take the frame right i take the frame oh man okay so let me assign it back in here so here is the frame right and essentially i will have to release the current top right so this is the index might as well call it something like top index right so this is the top index right i'm taking uh yeah so the first thing i probably want to do i just want to release this thing uh i'm completely releasing it [Music] but it's kind of dangerous to do so uh so probably not gonna do that i'm taking the frame uh oh man my brain doesn't want to work uh but the problem here is that uh i need to release the top index right i'm releasing the top index is that a dangerous thing to do i feel like it is kind of dangerous thing to do because it will set off the cascade effect right so there's going to be one uh one one right and you have this stop you releasing it right away it sets it to zero which releases that thing which sets it to zero which releases that thing and so on and so forth so it basically cascades so we don't wanna do that all right so it means we don't wanna release it right away first thing we want to do we want to grab the frame right so the current top frame and we want to reassign the top to there right so we have a previous thing i guess the first thing we want to do we want to do either acquire right acquire frame previous if if it exists right that's what we want to do so that's actually pretty cool so this is a cool idea this will not set off the cascade effect right so we have something like this right you have top in here so instead of releasing the top you grab this thing and you acquire it making it turn right then we're gonna move the top to here and we're gonna release the top which will set it to zero which will remove that thing and which will recommend one back here so that will not set off a cascade effect which will remove the entire thing right so you have to do that in a particular and this is why i was kind of scared of reference counting because you see you have to do that in a very particular order and you can set off something that you don't want to set off uh so but if you do that in a correct order maybe it's going to be even easier than implementing mark and sweep see what i'm talking about so yeah and again doing that in rust adds a complication of borrow checker right because now you have to also satisfy the borrow checker i'm not sure like if i will be able to do that so i need to take the frame right here i'm actually um yeah this one is interesting because here i'm boring ater but to acquire the previous frame i need to borrow it again right so that means i have to borrow this entire thing for a brief moment and take the previous value but this thing may not have a previous value right this thing may not have it so let's actually set something like um if let some previous index right so this is something that we want to have right so we take the top index uh we unwrap it obviously obviously and then we take a previous if it does exist we have to acquire it so we have to do an either acquire uh previous index so we acquired that thing uh right so after that i need to do eter release ater release the top index so i'm releasing the top index and then i'm setting the top to the previous one this one is interesting so i have to like do the separation yet again um right which means that it would be better to actually save previous to here like so and then just set it like that i think i did this in a correct order that's right so here no release acquire is required because you do release acquire that cancel each other out so as you can just do that here you take the previous previous exist you acquired that previous to not set off a cascade effect and then you release the top and you assign the top to to that so all right i think i did it i think i actually did it all right so uh let me see so we we need to put a semicolon here uh is it compiling it seems to be compiling actually all right so i essentially just push some stuff onto the stack let's take a look at the svg output all right so here is that but we don't have a reference counter right right because remove the reference counting so let's go back to the reference counting uh this one is going to be something like this and the reference counting uh ref count ref there we go uh so let me see there we go so here are the reference counting right so it is in fact correct we can't see like the tops and stuff like that but that's fine we can just imagine them uh okay so i also i also cloned this stack and again since i brought back the cloning i need to have my own clone operation right i need to have my own clone operation uh and let me quickly do that so this is gonna be momentable self hater mutable frame ater framator and what are we going to do in here so a self top if let some top index equal to that all right um that means what i have to do in here i just need to acquire that top index right and then i can just return self self self top and that is basically it right so yeah you just need to do another acquire in here okay cool but only if it exists uh so anything else so this requires immutable atom uh all right cool so you see we cloned the stack and now we have two things in here that is cool so now if i pop something from the first stack right that means uh now we're gonna have a single pointer in here but two uh reference counts in here because yeah you're gonna have first uh reference count from this node and the second one from the second stack right that makes sense i think i think that makes sense okay so if i uh do that there we go so two moved down and now if i push something to the first original stack uh we have correct reference columns okay that's cool so we have correct reference counting how about that how about that so we just have to do that in the correct order so that's pretty purge uh so we can push more stuff into here right into the first stack into the first stack uh so then can we just go ahead and delete that stack so the easiest way to delete that stack would be to just take stack top uh unwrap it and in the ater uh just to release that top right that kind of makes stack one incorrect right but since we're using indices instead of references the borrower checker is not going to tell us but yeah so essentially what this will do it should remove this entire branch automatically right it should just like remove it and i just want to see if it's going to happen uh okay so i uh forgot to do this thing all right and it kind of worked but this thing still exists right uh okay so this thing still exists and this is because when it reached zero did we actually free it okay we didn't all right so what we forgot to do is to uh add this thing to the list of freed indices right so once the reference count reached zero we have to add it to this thing uh and then uh set of cascade effect but maybe it makes sense to actually do that in here does it really matter i don't think so so uh there we go and as you can see this entire thing was removed right so we removed one thing and removed everything so that's pretty cool hmm so we have a proper memory management uh based on reference counters and stuff like that isn't that cool i think that's pretty cool so it will be interesting to actually have like a more you know like better example um so maybe you do something like a tree of some sort um [Music] i wonder if we can we can do that recursively somehow can we do that regardless just generate like random data types and whatnot uh would be also nice to have a function that can generate a random data type so defend random type right and this thing will just return the data type oh random number generators in rust are like really annoying so the standard library doesn't even have a random number generator right i think i think it doesn't have a random number generator like it's it's a crate it's a separate crate that you have to install okay you think this is gonna stop me uh i'm gonna just copy paste the lcg uh all right so how do you do that i keep forgetting so essentially we have a and c uh all right and we can have like some sort of a global seed uh might as well actually have like a struct rand so we have a and c uh u64 b c u 64. right we can implement um rend method to rend which will accept a mutable self and will return and you think so it would be also nice uh to [Music] to have some sort of a like a and c usually are constants right so uh i'm not sure if i want to make them constant okay let's actually make them so it's gonna be red and a uh i don't know which one to put in here so i'm gonna put this one b is gonna be another one so there's a couple of like good uh numbers in the in wikipedia so maybe we're gonna use them so this is a seat u64 and um yeah so that way we don't have to initialize anything uh all right so and the um result is going to be the following right so we take a rand a uh multiplied by self seed right so this is the current seed plus rand c and we just do mode on m and m so i don't remember let me see and mod is usually so okay so the one that i use in port uh mod is 64 that means you don't need mod at all so we can just do something like this right so and we're gonna do self uh seed equal to that and we're gonna just return self seed all right there we go so we might as well even like one thing that i learned from using this uh lcg thingy and one thing that people in comment section on my youtube channel pointed out is that you don't want to use the low uh 32 bits because they're like not really random uh so you want to use the uh higher 32 bits so the video i'm talking about is this one actually right so um i really recommend to check it out this is where i was using that specific lcg so i'm going to put it in the chat for anyone who's interested and also in the description uh right so this is basically i made the whole language just to generate this thumbnail uh okay anyway so um let me see uh and maybe because of that we want to return 32 and essentially we're going to return something like uh like move it by yeah 32 right so we're just basically removing 32 bits um and that way we can like have a random number generator we can even like check the quality of this random number generator um so you see you don't even need the uh right the the package or anything like that so i think the main uh justification for not having random number generators in the standard library is that to prevent people accidentally using it in like cryptographic cases right so because usually these random opportunities are not cryptographic but we're not doing any cryptography right now so it doesn't really matter i think uh so yeah we just need to like generate some random stuff random stuff uh so let's actually check how this entire thing works right so let's do for e in uh 10 right i'm going to print 11. uh so we have to put something in here so let's do it like this 69 can i just do it uh there we go it's going to be mutable rend rendering cool uh two to the two so this one is c okay so let's set it like this anything else uh so this thing wants a type i think right it wants a type uh all right and i think after that i have to explicitly cast it to usagi too right is it fine it should be fine now uh okay so what is it complaining about i'm not quite sure so there's a bunch of warnings uh multiplication attempt to multiply with overflow but isn't that what i want uh isn't that what i literally want can i just say yeah please overflow so can i just like literally overflow uh overflow abs oh oh you can actually explicitly do that that's actually pretty cool uh overflow multiply uh overflowing okay cool that's actually pretty cool uh all right overflowing multiply what a nice language uh can i have overflowing ad as well why do like at this point why do you even need an infix notation rust if that's what you want your user to type out maybe get rid of the infix notation and just like do all of the operations like this that way you don't even need the traits for like add multiply and stuff like that because you won't have any infix operators right you can simplify your your type system you can simplify your standard library you can simplify your parser right if that's what you want users to do just like get rid of the infects notation uh okay so oh it even okay on top of that it can also returns boolean or something serious um okay so uh all right so can beam [Music] requires call expression requires okay so that's that's what you want okay cool i i generated a bunch of random numbers look at that i have a bunch of random numbers uh okay that's cool [Music] so wrapping molds do i really want wrapping one maybe i do wrap in one you're right i think that's the one i want uh do they return boolean thank god they don't return bullying holy okay and and i have to pretend this is normal right so if i want to be like a good member of the rust community i have to like smile and pretend that this is absolutely normal this is helping everyone this is good right to understand i think i understand that correctly okay right so okay um so cool and so what do we got uh yeah all right so what i want you to have is essentially just this thing uh rend uh so we're gonna accept rand random type all two two to right we're gonna take a mutable rand and we're gonna return the data type and essentially i'm gonna do rand rand uh three and can i just cast this entire thing to like uh to the data type as data type is that a thing i can do uh hopefully uh as expression convert into primitive type um so rust in um number two in num how do you do that you can disable overflow checks in card dot tomml but i don't use cargo how am i supposed to do that how am i supposed to do that if i don't use cargo that's a very good question so there's some traits and some other stuff [Music] i know what i really don't care to the fan uh i just want to get this done right so how more annoying do you want to make generating a bunch of random data for testing make how more annoying do you have to make it this is a very interesting question you just have to make it annoying you just have to uh right so you cannot just like generate quickly no no what if somebody's using that in a cryptographical context you will get a vulnerability no you you can't uh okay so can i just do something like this uh all right think about the children think about the children what if the children will see your code right what if the children will see your random number generator and think that this is a cryptographic quality and will try to use that in their in their like security application or something like that anyway so uh random type is gonna be mutable rand so i just wanna see if i can simply generate this kind of thing right uh all right okay [Music] so stack two non-exhaustive pattern okay so this one is gonna be unreachable right okay so this is everything i wanted to do really like that's it how hard could it be to just generate a bunch of random my god holy and again according to the contract i'm i'm supposed to pretend that this is normal everything's okay it is helping everyone uh okay so um cool um yeah i just want to generate a bunch of random data uh so now we can try to do a recursive generator right that i suppose do the thing so the idea is going to be the following right uh the idea is going to be the following uh generate tree uh we're going to accept the stack right we're gonna accept some sort of like a root stack or something uh it's gonna be stack and it's gonna be mutable uh type stack so in here we're gonna just push like a couple of nodes onto the stack right so four um in zero three uh all right so basically stack push i will also have to pass the uh allocator right so it has to be something like eta mute um what was that uh frame a time right frame atom there we go so i push this thing here and i just want to have a random uh and also you have to you need to have this thing right so you have to you need to have the random number generator and uh the allocator and there you go so here's the rand they have a random type so you you just type a bunch of adventure times oh my god i'm so tired okay so what do we have in here so you just have to do it like that uh cool um where is main so i'm gonna remove the main this is going to be the new main uh generator so here what i want to do i want to split this entire thing like in two right uh i want to split this thing in two essentially um i'm gonna continue generating the tree to [Music] let stack zero stack clone right and i'm gonna clone it in here right so uh something like this then i'm gonna continue execution on the previous stack might as well yeah that's fine so it's gonna be random ater stack and then uh on the stack zero but we also need to keep track of the level right so uh let's introduce level use size and if level is equal to zero we just return uh right so and in here every time we do a call we decrement the level by one right so we can have several levels in here so we start with a specific stack with the default stack right and i just want to generate a tree uh so also need to do something like rand rand seed 69 so there we go and uh i generate three so i provide the random number generator rand then i provide the allocator heater and then i provide this stack right so and how many levels we want to generate let's let's say three right so we're going to generate three levels so that will basically just push some stuff into the stack then it will split the stack and continue pushing and it will just do that recursively and just generate a bunch of stuff okay so this thing oh this one is interesting so i feel like maybe we have to pass this stack stacked by the by the reference or something um so let me let me see um i might as well actually do like that it feels like i have to do it like that uh cannot borrow as mutable it's not declared as mutable okay so can all right so let's take a look at the svg are you guys ready are you guys ready boom so here is the current situation with the stack right so essentially we had a stack uh so basically stack grows upwards right so we pushed a bunch of stuff then we split it and then continue pushing and as you can see yeah there we go so this is the persistent data structure so and at the end of the day we just had four stacks right and they share some of the parts of each other so yeah so and all of the all of the reference counting is actually correct in here as far as you can see we can increment the uh the levels right so let's actually have four levels so we have to be careful because it grows exponentially right so that's essentially what we have in here and maybe we can even split it in three because why not so we can have something like stack one and stack one in here so it's gonna be a little bit more branching uh right so as you can see yeah it just grows exponentially so yeah and as you can see here is the reference counting is working more or less correctly um so that's pretty pal seems to be working so um and i can use this thing i can use this setup i can use this setup for porth finally right because at the beginning of the stream i said that for porth i need uh some sort of like a memory memory management system and data structure which will allow me to just clone the stacks right uh quite easily and quite inexpensively so i don't have to do too much of the memory management and i think this thing suits that goal quite well uh and i'm actually super happy so yeah i really like that does anyone have any questions about what we've done so far [Music] um [Music] so do i need to upload this anywhere because this is like a throwaway program that i don't really plan to do anything with because i'll need to translate this idea to porth at some point i just want you to explore that idea on the stream so all of that is going to be moved to porth um right and then first we're going to have like a fixed arrays and stuff like that um i might actually upload that to gist right so maybe some somebody wants to play with this thing um yeah so i'm going to put it on a gist uh so how am i going to call it persistent stack rs and i'm going to paste this entire thing so i can't see in this mist unfortunately so let's create do i want to create a secret one let's actually create a public one so upload it to pornhub does porn help even support like code or text information um persistent did they make a typo uh where did they make a typo today first is standard i understand and see a type i'm sorry anyway so uh it doesn't really matter uh so here is this thing and i'm gonna put that in description as well right source uh source code all right so that's it for today i guess uh thanks everyone who's watching right now i really appreciate that have a good one and i see you next time uh thank you for all the subscriptions all the donations and stuff like that hope i hope this stream was interesting it was definitely interesting for me uh i never actually seriously used reference counting and i can see that for this specific case it is actually very very useful so yeah okay thanks everyone for watching i'm really tired so i need to go eat something love you you

Channel: Tsoding Daily

Views: 11,804

Keywords:

Id: sAz_E4TZ-eQ

Length: 157min 42sec (9462 seconds)

Published: Mon Nov 22 2021