 Notice. New forum software under development. It's going to miss a few functions and look a bit ugly for a while, but I'm working on it full time now as the old forum was too unstable. Couple days, all good. If you notice any issues, please contact me. |
Forum Index : Microcontroller and PC projects : Dynamic Data Structures
| Author | Message | ||||
elk1984 Senior Member  Joined: 11/07/2020 Location: United KingdomPosts: 227 |
I may have posted on this before (forgive me if I have), this post had me wondering what dynamic data structures have people successfully implemented in MM Basic (short of CSUBS) that allow for efficient memory usage of multi-length elements and allowing add / remove with freeing memory back to the heap. Linked list with NULL delimited strings or that kind of thing? I'm thinking dictionaries and arraylists (in .NET / Java parlance). |
||||
| William Leue Guru  Joined: 03/07/2020 Location: United StatesPosts: 383 |
I have yet to find a way to usefully deallocate memory and return it to the heap for reuse. Besides lacking any syntactic support in MMBasic, it would also require the firmware to have a garbage collector, which I fear it does not. So other than the nuclear option (CLEAR), or crude things like program chaining, there does not appear to be any way to have true dynamic memory management. I am not even sure whether a CSUB could use malloc() and free() and expect the memory to be reusable. Of it is still possible to program stacks, queues, and other useful data structures; you just have to dream up the maximum size you think they will need. -Bill |
||||
| matherp Guru Joined: 11/12/2012 Location: United KingdomPosts: 8592 |
Why do you post incorrect supposition instead of asking a question when you clearly don't know something and haven't read the source code to find out? |
||||
| JohnS Guru Joined: 18/11/2011 Location: United KingdomPosts: 3661 |
I suspect in previous devices (CMM1, micromites etc) there wasn't much need - or RAM! If I wanted such, badly enough, on a CMM2 I think I'd write some wrappers and maybe use PEEK & POKE (there's plenty of RAM), if I wasn't happy just using arrays and some gnarly pointers (array indices). Depends how creative one wants to be and the time available. John |
||||
| William Leue Guru Joined: 03/07/2020 Location: United StatesPosts: 383 |
Sorry, Peter! I should have said that IF garbage collection exists in the firmware, its use does not extend to MMBasic. -Bill |
||||
| matherp Guru Joined: 11/12/2012 Location: United KingdomPosts: 8592 |
MMBasic uses its own heap. You can GetTempMemory which is "garbage collected" at the end of every Basic statement or use GetMemory/FreeMemory which is the internal equivalent of malloc/free. In the case of GetMemory garbage is collected whenever you run a new program. All of these functions are exposed in the CSub header. In MMBasic you can use the ERASE command to delete one or more individual variables or CLEAR to delete them all. In both cases memory is returned for re-use. Not sure what else you think you need |
||||
vegipete Guru Joined: 29/01/2013 Location: CanadaPosts: 1082 |
Hey! Hey! Hey! No fair! "ERASE" isn't in the manual.  Serves me right for not memorizing the output of LIST COMMANDS and LIST FUNCTIONS. Visit Vegipete's *Mite Library for cool programs. |
||||
| matherp Guru Joined: 11/12/2012 Location: United KingdomPosts: 8592 |
It somehow seems to have gone missing in the 5.05.05 manual although it is standard across all versions of MMBasic. It will certainly be in the 5.05.06 manual. |
||||
| William Leue Guru Joined: 03/07/2020 Location: United StatesPosts: 383 |
Ah, so THAT is why I never saw ERASE! Excellent, I will start playing with it right away; it might be the answer to lots of memory allocation issues. -Bill |
||||
| William Leue Guru Joined: 03/07/2020 Location: United StatesPosts: 383 |
Oh, is there an equivalent to the C sizeof() function that will let you know the size in bytes of a variable? I looked through the documentation but didn't see anything. With the ability to dynamically resize a variable using ERASE and DIM, it would be nice to have. -Bill |
||||
| vegipete Guru Joined: 29/01/2013 Location: CanadaPosts: 1082 |
"BOUND" will help a bit. Visit Vegipete's *Mite Library for cool programs. |
||||
| William Leue Guru Joined: 03/07/2020 Location: United StatesPosts: 383 |
Ooh, yes! I always forget about BOUND(). My printed manual is for 5.05.03 and I am waiting for 5.05.06 before I get it printed again. I HATE looking up stuff on the computer; a printed manual is so much faster for me and lets me make notes. Thanks! -Bill |
||||
| MauroXavier Guru Joined: 06/03/2016 Location: BrazilPosts: 303 |
I had used CLEAR and ERASE and itīs a very good practice and I proof it by myself. It accelerated the DEMOX a lot when clearing all the variables in each demo part, and the ERASE is used in my INTO THE DARKNESS and WOLF3D to clear variables in each stage, which proved to give a few more frames. |
||||
| qwerty823 Newbie  Joined: 30/07/2020 Location: United StatesPosts: 30 |
One thing I noticed in the source code is that the variable list is done as an array, so position in the list severely impacts variable lookups. For example: option explicit option default none option base 0 DIM a AS INTEGER #include "const1000.inc" DIM b AS INTEGER timer=0 for a = 0 to 100000 next a print timer timer=0 for b = 0 to 100000 next b print timer The file "const1000.inc" is basically a file with 1000 defined constants in the form: Const const00001=0 Const const00002=0 ... When I run the above code, it prints out: 198.236 10959.405 Because b is at the end of the variable list, it takes roughly 55x as long to run the same loop. (yes, it took almost 10 seconds to count to 100K on a 400Mhz machine). I'm sure asking for the vartbl to be changed to something like a hash table is not likely to happen, but something to keep in mind if you aren't explicitly declaring variables, that the order they are created can have GREAT impact on program speed. Edited 2020-10-19 10:41 by qwerty823 |
||||
panky Guru Joined: 02/10/2012 Location: AustraliaPosts: 1097 |
This just underlines what Geoff and Peter have said numerous times before - if possible ENSURE that all variables, constants etc have different characters in the first 4 positions - if your 1000 constants all had a different and unique first 4 characters, scanning the variable table would be much quicker. Your point about position is valid and important too when you are trying to get the absolute most performance. Doug. Edit: Just goes to show what I know - which is not much at all!!  Ran a couple of tests myself and in the case above, position in the table is 99% of the issue as qwerty823 correctly pointed out. I think to have unique first 4 characters is still good advice in general though. D. Edited 2020-10-19 13:25 by panky ... almost all of the Maximites, the MicromMites, the MM Extremes, the ArmMites, the PicoMite and loving it! |
||||
| qwerty823 Newbie Joined: 30/07/2020 Location: United StatesPosts: 30 |
Not really, since the table would still be something like: a const00001 const00002 const00003 ... const01000 b findvar still has to skip over ALL of those constants to get to the 'b'. If I rename 'b' to something like 'consxx', then it has to do a deeper check on all the constXXXXX variables, since the first 4 chars are the same. Doing this takes about 11135.012 ms vs 10959.405 ms (so slightly more time, but not that much more). Most of the time is spent iterating over the array finding the variable. Granted, this is a fairly contrived example, but even only having 100 vars (which I don't think is quite contrived), ends up taking almost twice as long finding a variable at the end compared to the beginning. |
||||
| matherp Guru Joined: 11/12/2012 Location: United KingdomPosts: 8592 |
I did have a play at using a hash table for variable lookup but like all things there are pros and cons. Would be much faster in the somewhat contrived example above but slower for many simple programs or complex programs where data is held in a limited number of big arrays (games). If any of the C specialists out there wants to have have a go at it I'd be happy to consider it for inclusion. The protocol would be something like: Define a suitable hashing algorithm for say 1024 keys When the program is run get a chunk of MMBasic heap memory for the hash table (assume say 1024 variables) 1. Change findvar so that when a new variable is created it a hash key is created and the location of the variable is stored in the hash table. In the case of a hash conflict don't store it just leave it in the normal VARTABLE 2. Change findvar so that the search first hashes the variable name and checks the hash table. If not found do a sequential search in VARTABLE. If not found go to 1 |
||||
thwill Guru Joined: 16/09/2019 Location: United KingdomPosts: 3848 |
I might have the skill, but I definitely don't have the time  so I offer the following for informational purposes only with no expectation that anyone might do anything about it ... I may well be teaching people how to suck eggs.> 1. Change findvar so that when a new variable is created it a hash key is created and the location of the variable is stored in the hash table. In the case of a hash conflict don't store it just leave it in the normal VARTABLE Why not have each entry in the hash-table mapped to a linked list? Isn't that likely to be a more efficient way of dealing with collisions ? The BBC Micro (yes that old chestnut) was acknowledged as having particularly fast variable lookup compared to its peers, I believe it did the following: 1. Predefined locations for the 24 single letter integer variables a%-z% so they could be looked up as fast as possible. 2. Instead of using a single list the other variables were stored in 24 linked lists indexed by the first letter of the variable name. YMMV. Best wishes, Tom Edited 2020-10-19 19:21 by thwill Game*Mite, CMM2 Welcome Tape, Creaky old text adventures |
||||
| Barbiani Newbie Joined: 18/10/2020 Location: BrazilPosts: 6 |
Or leave the code using vartable arrays, but insert sort and binary search. |
||||
| lizby Guru Joined: 17/05/2016 Location: United StatesPosts: 3017 |
Or with storage as is, create and sort linked list and do binary search. I do like the idea of A-Z stored separately occupying the maximum possible bits for any variable, with access based on variable type. (But this is just so much hot air.) PicoMite, Armmite F4, SensorKits, MMBasic Hardware, Games, etc. on fruitoftheshed |
||||
 Print this page |
