New GUI for the Atari 8-bit

[fibrewire]

I know that the majority of the RAM upgrades out there do not follow the 130XE standard, as defined by Atari as the "correct/legal" way to bank. The default architecture of the 130XE has the specific advantage of either the CPU or the ANTIC accessing extended RAM, and I'm sure that you could really do some fancy stuff with it... perhaps it's hasty to rule it out completely?

 

DOS 2.5 for Axlon RAMdisk - http://www.atarimagazines.com/v4n10/dos25.html

[flashjazzcat]

I wrote 3 lengthy messages to you regarding your endeavors with the GUI, and deleted them all. I didn't want to add to the clutter of this thread - and you STILL managed to hear my brain grinding away from across the pond!

 

I can't ever ask for a source code listing, but a flow chart of the logic behind the GUI would be awesome to see

 

EDIT: Source to flowchart - http://www.assemblyflowchart.com/

The level of research, discussion and planning is clearly outweighing the amount of coding going on at the moment. It's a wonder the sound of MY brain grinding away doesn't carry across the ocean...

 

I can see the wisdom in producing some structural diagrams... please bear with me.

Edited December 2, 2011 by flashjazzcat

[flashjazzcat]

Amazing that it took so long to get this working, but what with all the distractions and feeling under the weather... it took me two days to track the bug down.

 

 

Doesn't look like much, but this is the self-coalescing heap manager allocating five chunks of memory and then freeing them up in random order. It shows the block being deallocated, then walks the free list. I now have to optimize the allocation routines for "best fit" efficiency. Relocatable blocks are becoming less attractive by the minute, not least because the extra level of indirection would most of the time simply heap extra work on the rendering routines.

Edited December 2, 2011 by flashjazzcat

[ivop]

I have not read this whole thread, but am I right that you are planning on using a garbage collector? If so, I would like to point out that garbage collectors always keep too much memory allocated at a certain point in time, which is generally not a good idea on systems with little memory. To minimize this effect you could run the collector more often, but this might slow down the application in unacceptable places. It's also totally unpredictable when and in what order memory blocks are de-allocated. Proper malloc and free when the application doesn't need the memory anymore is favored instead of garbage collection IMHO.

 

Perhaps there's a time/space trade-off you have already considered and of which I'm not aware, then please ignore my rant (or elaborate )

 

Not meaning to disqualify your efforts BTW, I really like what you are doing.

[flashjazzcat]

I have not read this whole thread, but am I right that you are planning on using a garbage collector? If so, I would like to point out that garbage collectors always keep too much memory allocated at a certain point in time, which is generally not a good idea on systems with little memory. To minimize this effect you could run the collector more often, but this might slow down the application in unacceptable places. It's also totally unpredictable when and in what order memory blocks are de-allocated. Proper malloc and free when the application doesn't need the memory anymore is favored instead of garbage collection IMHO.

 

Perhaps there's a time/space trade-off you have already considered and of which I'm not aware, then please ignore my rant (or elaborate )

 

Happy to elaborate - and the points you raise are most welcome! The way the heap manager has turned out is interesting, and quite simple (which I think is a good thing). Because of the way the free list is managed, coalescing of adjacent free space (during deallocations) is very cheap, so the need for a garbage collection run is completely removed. A more effective garbage collection technique, of course, is actually moving allocated blocks around, but this introduces extra complexity for the application and makes the possibility of indirectly mapping memory accesses onto a virtual 64KB block a more difficult proposition.

 

The original heap manager (which I wrote several months ago) always put the most recently freed block at the head of the linked list, so coalescing of neighbouring free blocks was quite expensive (potentially requiring a complete traversal of the tree from start to finish every time). The decision was then made to only perform coalescing when a memory allocation failed, but the garbage collection run was then so costly (many traversals of the entire tree) that I came up with the current arrangement instead. Without relocatable blocks, I believe that continued refinement of the current self-cleaning method will be the most suitable solution.

 

One concept which interests me greatly is "slab allocation", which recognizes and capitalizes on the fact that a GUI frequently deallocates and reallocates memory for objects of the same type and size in quick succession. By caching memory blocks, we can further improve the performance of the heap manager.

 

Regarding the actual order of deallocation and reallocation of RAM in typical scenarios: I tend to agree that this will be very hard to "profile", and applications which sensibly allocate and free RAM are probably more important to an efficient system than very complex garbage collection methods.

 

Not meaning to disqualify your efforts BTW, I really like what you are doing.

 

Not at all, and thanks. I find the topic of memory management quite intriguing and I'm having a lot of fun designing an effective system using a small amount of code and memory.

Edited December 5, 2011 by flashjazzcat

[ivop]

Ah, I see. By garbage collecting you mean cleaning up after a normal alloc/free cycle. The points I raised relate to a "java vm-style" garbage collector, i.e. the application allocates at will and periodically the garbage collector checks for memory blocks not being referenced anymore and adds them back to the pool. This means that unreferenced memory blocks stay allocated until the gc runs, hence the too much memory allocated point I made above.

 

BTW some people argue that garbage collection can actually be faster than the usual explicit memory management as it deallocates a lot of blocks at once and not one at the time in between normal code, but this still seems highly theoretical and does not hold up in practice, at least not for java. Haskell might be an exception, although I have not seen hard facts on that either.

Edited December 5, 2011 by ivop

[flashjazzcat]

Ah, I see. By garbage collecting you mean cleaning up after a normal alloc/free cycle. The points I raised relate to a "java vm-style" garbage collector, i.e. the application allocates at will and periodically the garbage collector checks for memory blocks not being referenced anymore and adds them back to the pool. This means that unreferenced memory blocks stay allocated until the gc runs, hence the too much memory allocated point I made above.

 

Absolutely agree. I think the unreferenced block model is a little too risky for a small memory model such as this one.

 

BTW some people argue that garbage collection can actually be faster than the usual explicit memory management as it deallocates a lot of blocks at once and not one at the time in between normal code, but this still seems highly theoretical and does not hold up in practice, at least not for java. Haskell might be an exception, although I have not seen hard facts on that either.

 

I suppose it depends entirely on how fast single block deallocations are actioned. The simple model I've gone for ensures there are no "backward" references in the linked list, so when deallocating a block, one first checks to see if the previous block is free and if it is, the target position is changed to that of the previous block and the size enlarged to cover it and the target block. We then check to see if the next node is also a free block, and if it is, expand the block to cover that one too. Naturally we remove or add free nodes as required, and it all works quite nicely. However, we still had to walk the list from the head until we reached a "next" pointer which was beyond the block we're freeing up. What I propose to do is cache the "previous" node and its next pointer, so that the next free call simply checks to see if the target block is higher up the pool than the cached "previous" node, saved after the previous deallocation. If it is (and - if many deallocations are done in the reverse order they were allocated - it should be), we start at "previous" and walk (usually) just a couple of nodes before we can do all our coalescing checks. This should - in typical circumstances - do away with most of the list walking and still leave us with completely coalesced free blocks at all times, without any garbage collection requirement.

Edited December 5, 2011 by flashjazzcat

[Kylev]

flashjazzcat,

 

Are we dealing with a doubly linked list here? or a single?

[flashjazzcat]

Are we dealing with a doubly linked list here? or a single?

 

Single - saves space. I was doing some notes last night and if there's a seperate "floating" pointer for the head (in this case the lowest free block) and we search for memory from the bottom of the heap upwards, we can avoid fragmenting memory by always using the smaller, recently deallocated blocks first. Coupled with the caching I described earlier, this looks like a nice little system. In addition, when a 16KB block can't satisfy a memory request, it's easy to add an additional bank to the chain.

 

Time to look at the relocatable linking loader now, and posssibly mapping out cartridge banks as a ROM disk.

Edited December 6, 2011 by flashjazzcat

[flashjazzcat]

 

Hmmm... a photo to appeal to hardcore heap manager fans only, I think. This one works well anyway (this part's far too engrossing, actually - one could go on indefinitely adding refinements).

 

I've amended things so that we start off with the following in the bottom of a 16KB bank:

 

heap_head		equ $4000 ; pointer to most recently freed block (0 = no free blocks)
free_count	equ $4002
heap_base		equ $4004

 

Heap_head is initialized to $4004, which contains a free block header (16380 bytes with a next node pointer of 0). Allocated blocks are taken from the bottom up, pushing heap_head upwards through the heap. It's now perfectly possible to allocate every byte in the heap (minus the 2 byte header for each allocated block). If there are no free blocks left (we know this when free_count is 0), heap_head is also 0 (no free blocks left). When blocks are deallocated, heap_head always points to the lowest (first) free block, and thus this is where searches begin when more memory is required. This tends to keep all the allocations at the bottom of the heap, and the bigger free blocks at the top (I could have done it the other way around but it's six and two threes at the end of the day).

 

Now, if a deallocation is happening below heap_head, we merely need to check if it's immediately adjacent to the first free block, and if so, join them together. Thus we avoided list walking and coalesced RAM in one fell swoop. If a deallocation is above heap_head, we walk the list as normal and check for neigbouring free blocks. Of course, since the list doesn't back track, once we reach the target block, coalescing is a simple two-step process. Finally, if heap_head is zero when a deallocation happens, we just mark the block as free and point heap_head to it.

 

Designing code to really thrash the heap manager intriguing in itself, but this one should be pretty fast. Large free spaces are preserved, free blocks are always coalesced, and list walking is minimal. No garbage collection needed.

 

Two final optimisations before I actually put this code into action. Firstly, the allocations should be "best fit", so that large free blocks aren't needlessly broken up for small requests which would be better satisfied by smaller free blocks. Secondly, a "last freed block" pointer should be maintained, which can be checked against the block address when freeing memory. If the target block is above "last freed block" (usually it will be right next to it), we completely avoid any list walking.

[flashjazzcat]

Need some help with MADS' proprietary relocatable binary file format (it supports symbols like the SDX loader, but is DOS-independent and somewhat more flexible). I've already advertised for MADS experts at AtariArea. The Google translated docs are very hard work when it comes to interpreting the headers in the various blocks. Some make sense, others are harder to follow.

 

Heap manager works like a dream, at least. I allocated 32 x 20 byte blocks and then deallocated them again. Because of the optimisations I described above, no list walking occured at all. The order of deallocation - in this instance - didn't make any difference, although normally it would be most efficient to release the blocks in the same order they were allocated.

Edited December 6, 2011 by flashjazzcat

[flashjazzcat]

Heh... I was using the wrong directive to declare external symbols. Using .EXTRN, all the headers line up with what's described in the manual. I should be able to figure this out now. Just goes to show - RTFM, even if it's in Polish (RTFPM).

 

These GUI apps are gonna look rather nice:

 

printf .extrn .proc
open .extrn .proc
.reloc

.public main
.public last

main
jsr printf
jsr open
rts
.ds 64
last

blk update address
blk update public

 

(The above is just a nonsensical test of the compiler directives).

Edited December 7, 2011 by flashjazzcat

[simonl]

Two final optimisations before I actually put this code into action. Firstly, the allocations should be "best fit", so that large free blocks aren't needlessly broken up for small requests which would be better satisfied by smaller free blocks. Secondly, a "last freed block" pointer should be maintained, which can be checked against the block address when freeing memory. If the target block is above "last freed block" (usually it will be right next to it), we completely avoid any list walking.

 

Are you using thinking of using a "buddy block" binary tree for this? If not, may be worth looking at.

 

http://en.wikipedia.org/wiki/Buddy_memory_allocation

 

Cheers,

 

Simon

[flashjazzcat]

Are you using thinking of using a "buddy block" binary tree for this? If not, may be worth looking at.

I looked at it a while back, but considered it too wasteful of bytes for a model this size. I must admit I didn't look into Knuth's modifications. In any case, they were all worth looking at, and believe me I've looked at a lot.

 

It's unlikely that what I've come up with is better than any other possible solution, but it works and I'm reasonably happy to run with it while I'm progressing with other areas of the system.

[LoTonah]

Happy New Year, Flashjazzcat Any progress to report?

[flashjazzcat]

Heh - thanks for the necrobump!

 

MrFish has been working on the icon collection, which is just about complete. He's also working on a resource editor, and I guess bigger font sizes will come next. Nothing exciting to report on the coding front, but as soon as the RC of the VBXE version of The Last Word is released (in a few hours), I'll be picking up where I left off on the GUI (specifically with the masking routines for multi-window redraws).

 

Momentum has really been lost on this project because various distractions - some self-inflicted, others not - but I'm aware that we need to get the ball rolling again ASAP. At least I feel I can look at the existing code with fresh eyes now, and I'm benefitting from a good coding workout on the word processor.

Edited January 13, 2012 by flashjazzcat

[Mclaneinc]

is it done?

 

 

 

 

 

 

 

 

 

 

 

 

 

Stop playing games and get this done

Edited January 13, 2012 by Mclaneinc

[flashjazzcat]

I'm writing the README. It's the best bit.

[Mclaneinc]

I'm writing the README. It's the best bit.

 

Will it be in Chav language so myself and fellow Londeoner Carmel can understand it....

Edited January 13, 2012 by Mclaneinc

[flashjazzcat]

Will it be in Chav language so myself and fellow Londeoner Carmel can understand it....

 

Heh... I'm incapable of emulating such rich vernacular via the written word. However, it's in euro-accessible plain English (although most English-speaking Europeans I've spoken to here have a quite superior command of the language and could show most UK teenagers a clean pair of heels).

 

Just noticed another bug while typing it up... delayed until tea-time.

Edited January 13, 2012 by flashjazzcat

[JamesD]

is it done?

Are we there yet? Are we there yet? Are we there yet? Are we there yet? Are we there yet? Are we there yet?

 

<flashjazzcat> Don't make me turn this car around!

 

Glad to hear you are starting to work on this again.

[Mclaneinc]

Same as all of us, Jon's stuff is top notch so really looking forward to this when its ready..

[flashjazzcat]

Boring efficiency test of fully masked font rendering:

 

 

This is just to show I'm doing something. The menus wouldn't normally be masked out like this, obviously, and the vertical band-shaped mask serves no practical purpose. It will all make sense very soon, however...

[AtariGeezer]

Ahhh, icons in menus?

[flashjazzcat]

Ahhh, icons in menus?

 

Although there's nothing to stop us having icons in menus, that's not what the masking's about. It's to do with overlapping window redraws.