JamesD Posted March 30, 2011 Share Posted March 30, 2011 Thanks Dan - your general approval is important. Not having a "next" pointer in the allocated block header saves two bytes, and I couldn't really figure a use for it, so I guess it's not necessary. Since there's no backtracking involved in a linear sweep through the pool, I reckon a full coalesce will be fast as hell anyway. The big fear with the original (self-cleaning) "free" routine was that you might end up making 60,000 node visits when freeing up only a few hundred objects. The next pointer saves calculating an address but in such a small memory environment you can save a lot of space. A little CPU time is a small price to pay. I suppose you could try both methods to see how they compare for speed/memory when used with real applications. This should be transparent to apps so you should be able to change in the future if you wish. Quote Link to comment Share on other sites More sharing options...
fibrewire Posted March 30, 2011 Share Posted March 30, 2011 FJC, i've looked in other related threads, saw someone had recently created an Eclipse plugin for A8 assembler, even saw something about Xedit and MAC65. Just out of curiosity... What do you use as your development environment? Quote Link to comment Share on other sites More sharing options...
flashjazzcat Posted March 30, 2011 Author Share Posted March 30, 2011 (edited) Yeah: two bytes per object soon mounts up, believe me. I don't mind the odd half-second pause during operation, but I suspected that the self-cleaning free routine could have taken a couple of seconds when closing a window containing several hundred icons. The coalescing routine - admittedly - quit as soon as free blocks either side of the target block had been identified, but it seemed crazy to walk the list three hundred times when releasing three hundred objects when you could just do a single linear scan some time later on. In any case, as you say - the calling mechanism will never change so the machanics can be altered at any time @fibrewire: check this out: The WUDSN plug-in for Eclipse has been around for nearly two years now, IIRC, and I converted to it back when it first came out. I'd never used another IDE (I was up until then coding using XEDIT and MA65 in an emulator), so I've been brought up on WUDSN/Eclipse. Peter is making quite amazing strudes with WUDSN, and although there are a lot of very nice editors out there, I think when you appreciate just how tightly WUDSN integrates with the compiler, you appreciate its immense power. Edited March 30, 2011 by flashjazzcat Quote Link to comment Share on other sites More sharing options...
JamesD Posted March 30, 2011 Share Posted March 30, 2011 BTW, if you want to eventually multi-task and have the ability to kill a task and free it's memory, the memory free/allocated flag works nicely for this. 0 = free, any other value is the number of the task. It would also be handy for debugging in a multi-tasking environment. Quote Link to comment Share on other sites More sharing options...
flashjazzcat Posted March 30, 2011 Author Share Posted March 30, 2011 (edited) BTW, if you want to eventually multi-task and have the ability to kill a task and free it's memory, the memory free/allocated flag works nicely for this. 0 = free, any other value is the number of the task. It would also be handy for debugging in a multi-tasking environment. You must be psychic, 'cause I was thinking about just that earlier today (in one of my foolhardy mental dalliances with the idea of multi-tasking). If we had all the tasks sharing the same 16KB memory banks, then we'd have four spare bits in total (with fourteen bit pointers), which equates to eight task IDs (three bits), plus the free/used bit. Edited March 30, 2011 by flashjazzcat Quote Link to comment Share on other sites More sharing options...
JamesD Posted March 30, 2011 Share Posted March 30, 2011 (edited) Yeah: two bytes per object soon mounts up, believe me. I don't mind the odd half-second pause during operation, but I suspected that the self-cleaning free routine could have taken a couple of seconds when closing a window containing several hundred icons. The coalescing routine - admittedly - quit as soon as free blocks either side of the target block had been identified, but it seemed crazy to walk the list three hundred times when releasing three hundred objects when you could just do a single linear scan some time later on. You shouldn't be doing any walking of the list on free. That's why you keep allocated blocks in the list. Yeah, it's a byte wasted for each block but the payoff in speed on freeing is huge. <edit> at least if I follow what you are saying correctly. You either just mark the block free (simple way)... or mark it free and look to see if the next block is free, if so, add the sizes and update the size of the block. Since pointer to the next block is calculated, you don't need to change a pointer as well. <edit> Paged memory is of coarse more complicated. Edited March 30, 2011 by JamesD Quote Link to comment Share on other sites More sharing options...
flashjazzcat Posted March 30, 2011 Author Share Posted March 30, 2011 Yep: when I freed myself of the concept of walking the list to coalesce free space, it all made sense. But doing linear coalescing (the way I see it) screws up the linked list, since the "next" adjacent block might be much further along in terms of list nodes. Just rebuidling the list on the fly seemed like a nice simple compromise, and (espcecially at the moment), I like simple. Quote Link to comment Share on other sites More sharing options...
JamesD Posted March 30, 2011 Share Posted March 30, 2011 Here are my ideas for a paged memory manager. Each page has a structure containing the size of the largest block of memory on the page. When searching for a block of memory, find the first page with a large enough block, then memory management is about the same except alloc/free routines update the largest block size on that page. It makes finding a page with enough free mem fast at the expense of some overhead on managing the largest block size on a page when you allocate/free it from that page's free/alloc list. Quote Link to comment Share on other sites More sharing options...
JamesD Posted March 30, 2011 Share Posted March 30, 2011 (edited) Yep: when I freed myself of the concept of walking the list to coalesce free space, it all made sense. But doing linear coalescing (the way I see it) screws up the linked list, since the "next" adjacent block might be much further along in terms of list nodes. Just rebuidling the list on the fly seemed like a nice simple compromise, and (espcecially at the moment), I like simple. But if all blocks are on the list you shouldn't have that problem. <edit> If you had pointers you could keep free blocks at the front of the list without messing it up... but traversing reordering the list would be required to merge blocks. Edited March 30, 2011 by JamesD Quote Link to comment Share on other sites More sharing options...
JamesD Posted March 30, 2011 Share Posted March 30, 2011 Here are my ideas for a paged memory manager. Each page has a structure containing the size of the largest block of memory on the page. When searching for a block of memory, find the first page with a large enough block, then memory management is about the same except alloc/free routines update the largest block size on that page. It makes finding a page with enough free mem fast at the expense of some overhead on managing the largest block size on a page when you allocate/free it from that page's free/alloc list. Actually, you could use the same memory manager as normal mem from within each page if you don't hard code where it starts it's linked list. Then use intermediate routines that call it and do the rest of the work. Quote Link to comment Share on other sites More sharing options...
DracIsBack Posted March 30, 2011 Share Posted March 30, 2011 This just gets cooler and cooler. Too bad you weren't around in 1984 making this! :-) Quote Link to comment Share on other sites More sharing options...
+wood_jl Posted March 31, 2011 Share Posted March 31, 2011 And it's better! Yeah, it pretty much kicks the shit out of the Amiga "Boink" demo, too, eh? Quote Link to comment Share on other sites More sharing options...
JamesD Posted March 31, 2011 Share Posted March 31, 2011 (edited) And it's better! Yeah, it pretty much kicks the shit out of the Amiga "Boink" demo, too, eh? The Amiga Boing demo was written late one night at the CES show. I doubt the Atari demo was written so quickly. <edit> BTW, the Amiga version has a shadow where you can still see the background. The Fuji demo overwrites the background. FWIW, the CoCo3 version also uses a shadow that shows the background. Edited March 31, 2011 by JamesD Quote Link to comment Share on other sites More sharing options...
+wood_jl Posted March 31, 2011 Share Posted March 31, 2011 (edited) And it's better! Yeah, it pretty much kicks the shit out of the Amiga "Boink" demo, too, eh? The Amiga Boing demo was written late one night at the CES show. I doubt the Atari demo was written so quickly. <edit> BTW, the Amiga version has a shadow where you can still see the background. The Fuji demo overwrites the background. FWIW, the CoCo3 version also uses a shadow that shows the background. Perhaps, but I'll take the 128 (256?) color scroll on the rotating fuji, over the shadow. edit: If the source of that little anecdote about it being written "late one night at a CES show" is RJ Mical (sp?) then take that with about 10 pounds of salt, as that guy's a well-established bullshitter, and I believe I've read the program was written by him. Ask AtariAge user wgungfu (who is knowledgeable and well-respected here) about RJ Mical's truthfulness. Sound like an excuse for why the demo wasn't better. Edited March 31, 2011 by wood_jl Quote Link to comment Share on other sites More sharing options...
JamesD Posted March 31, 2011 Share Posted March 31, 2011 And it's better! Yeah, it pretty much kicks the shit out of the Amiga "Boink" demo, too, eh? The Amiga Boing demo was written late one night at the CES show. I doubt the Atari demo was written so quickly. <edit> BTW, the Amiga version has a shadow where you can still see the background. The Fuji demo overwrites the background. FWIW, the CoCo3 version also uses a shadow that shows the background. Perhaps, but I'll take the 128 (256?) color scroll on the rotating fuji, over the shadow. Don't you mean Perhaps but Fuji Boing runs on the Atari. Quote Link to comment Share on other sites More sharing options...
JamesD Posted March 31, 2011 Share Posted March 31, 2011 edit: If the source of that little anecdote about it being written "late one night at a CES show" is RJ Mical (sp?) then take that with about 10 pounds of salt, as that guy's a well-established bullshitter, and I believe I've read the program was written by him. Ask AtariAge user wgungfu (who is knowledgeable and well-respected here) about RJ Mical's truthfulness. Sound like an excuse for why the demo wasn't better. I used to have the source code to it and it wasn't very big so it shouldn't have taken too long to write. It's just color cycling for the ball rotation. Quote Link to comment Share on other sites More sharing options...
+MrFish Posted March 31, 2011 Share Posted March 31, 2011 And it's better! Yeah, it pretty much kicks the shit out of the Amiga "Boink" demo, too, eh? The Amiga Boing demo was written late one night at the CES show. I doubt the Atari demo was written so quickly. <edit> BTW, the Amiga version has a shadow where you can still see the background. The Fuji demo overwrites the background. FWIW, the CoCo3 version also uses a shadow that shows the background. The Boink and Super Boink demos have that characteristic. Boink.zip Quote Link to comment Share on other sites More sharing options...
JamesD Posted March 31, 2011 Share Posted March 31, 2011 edit: If the source of that little anecdote about it being written "late one night at a CES show" is RJ Mical (sp?) then take that with about 10 pounds of salt, as that guy's a well-established bullshitter, and I believe I've read the program was written by him. Ask AtariAge user wgungfu (who is knowledgeable and well-respected here) about RJ Mical's truthfulness. Sound like an excuse for why the demo wasn't better. And you would be wrong. Quote Link to comment Share on other sites More sharing options...
JamesD Posted March 31, 2011 Share Posted March 31, 2011 The Boink and Super Boink demos have that characteristic. Boink.zip But can you click on the ball and throw it around with a mouse? Does the ball accelerate as it falls and slow as it rises? (AKA physics) Now the iPhone has an exact replica... you can drag and throw the ball with your finger. Oh to have that speed back then. <sigh> Quote Link to comment Share on other sites More sharing options...
flashjazzcat Posted March 31, 2011 Author Share Posted March 31, 2011 Seems to me the dynamic list rebuild on coalescing run is the simplest to implement. The overhead for having a linked list of allocated blocks might seem small (four bytes instead of two), but it's actually quite large when you factor in the size of a basic object structure on top. Keeping a linked list of free blocks makes allocation fast, and the linear garbage collection routine - which probably won't be executed that often - never requires more than a single visit to each free/allocated header. What would be really nice - of course - is to extend the idea to cover more than one 16KB bank if sufficient memory is available. This is tricky, though, and would require each node pointer to have a bank number as well as a memory pointer. Then, "get_child", for example, would automatically switch in the appropriate bank. You'd need indirection on all accesses to the tree, though, to ensure the right block of memory is switched in when editing objects. It would make the following code unworkable: ldy #widget.x lda (parent),y sta (object),y The reason being that parent and object could be in different extended banks. Complete "virtualisation" would be expensive. For example: ldy #widget.x jsr get_byte_parent jsr store_byte_object The two subroutines would take care of all the bank switching transparently. The alternative is to "load" and "save" objects to a buffer in main memory. So, for example, "get_child_object" would actually copy an object's child into a sort of control block. You could then use the offsets (widget.x, etc) to edit the data, then call "write_object", which would copy the object back into the appropriate bank. Kind of hard to say how this would affect existing code, but it would certainly be simpler from the application point of view. Quote Link to comment Share on other sites More sharing options...
Frankie Posted March 31, 2011 Share Posted March 31, 2011 Ahh! This thread is driving me crazy... Ok, how long do I have to wait so I can just go to sleep and wake up and it will be all done? Quote Link to comment Share on other sites More sharing options...
flashjazzcat Posted March 31, 2011 Author Share Posted March 31, 2011 Six months. Quote Link to comment Share on other sites More sharing options...
pixelmischief Posted March 31, 2011 Share Posted March 31, 2011 This thread makes me feel horribly inadequate. And I'm Irish, for Christ's sake! Quote Link to comment Share on other sites More sharing options...
flashjazzcat Posted March 31, 2011 Author Share Posted March 31, 2011 Believe me, it makes me feel inadequate at times too. The bank-switching necessary on the little Atari is a big coding hurdle. Quote Link to comment Share on other sites More sharing options...
JamesD Posted March 31, 2011 Share Posted March 31, 2011 Seems to me the dynamic list rebuild on coalescing run is the simplest to implement. The overhead for having a linked list of allocated blocks might seem small (four bytes instead of two), How did 3 bytes turn into 4? but it's actually quite large when you factor in the size of a basic object structure on top. Explain basic object structure please. Is this code or data you are referring to? Keeping a linked list of free blocks makes allocation fast, and the linear garbage collection routine - which probably won't be executed that often - never requires more than a single visit to each free/allocated header. Well, it depends on how much free mem is in the system. With a small app that doesn't use a lot of memory you would be correct. If you have an app that is pushing memory limits your garbage collection routine would have to run more often. Especially if the large app allocates and frees different sized blocks often. So... for a very simple text editor things might be quick... but for a full blown word processor, cuts and pastes might be costly. What would be really nice - of course - is to extend the idea to cover more than one 16KB bank if sufficient memory is available. This is tricky, though, and would require each node pointer to have a bank number as well as a memory pointer. Then, "get_child", for example, would automatically switch in the appropriate bank. You'd need indirection on all accesses to the tree, though, to ensure the right block of memory is switched in when editing objects. It would make the following code unworkable: ldy #widget.x lda (parent),y sta (object),y The reason being that parent and object could be in different extended banks. Complete "virtualisation" would be expensive. For example: ldy #widget.x jsr get_byte_parent jsr store_byte_object The two subroutines would take care of all the bank switching transparently. The alternative is to "load" and "save" objects to a buffer in main memory. So, for example, "get_child_object" would actually copy an object's child into a sort of control block. You could then use the offsets (widget.x, etc) to edit the data, then call "write_object", which would copy the object back into the appropriate bank. Kind of hard to say how this would affect existing code, but it would certainly be simpler from the application point of view. When a program allocates a piece of memory, it can split it up however it wants, so you no longer have your bank info to transparently switch banks because a pointer no longer points at the memory block structure. Which is why the app must do the switching. Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.