QL Heap

[mk79]

The only internal difference that I can deduce is that there is a while loop using fseek() to figure out the size of a file (doing so in 64 byte blocks)

I must say I find it almost comical that the provided LIBC doesn't provide a better way. Only way I see is

Code: Select all

long src[8];
long ret[8];

src[0] = 0x42;
src[1] = -1;
src[3] = -1;
src[4] = fd;
trap3(src, ret);
// file size now in ret[1]

Is it really worth putting up with this very limited compiler?

before it does the malloc (and it fails on the malloc before it actually reads in the file). So I speculate that QDOS has read in part of the file while fseeking through it and is using part of the heap leaving the file in cache.

File caching is done in the slave blocks, which reside in the "free" memory, not in the heap. What will get allocated in the heap is the channel block, i.e. when opening the file. I'd be VERY surprised if seeking had any impact.

[mk79]

One other question...it seems the QL allocate function (which Martin

Marcel

I'm really sorry about that...don't know why Martin stuck in my head...

Don't worry, most English people call me Marcus for some reason, even after correcting them (i.e. "sorry Marcus")

Digital 'C' SE does have an avail() function that returns how much memory is left but it is unclear to me what that means.

It returns the gap between the topmost heap entry and the base of Basic. Not the biggest hole in the heap

I'm not sure what use I would have for that as I would care more about the largest chunk available. I need to figure out why a failed malloc sometimes causes havoc as you'd think the call would realize there wasn't enough memory and just return NULL. I don't see my code doing anything destructive as it just gives up and returns to the prompt.

avail() will actually abort the EXE if the parameter is != 0, like "avail(1000)" and there is not enough space (but as we've seen, it doesn't consider the holes... better just try to the malloc and see what you get).

You can implement a binary tree heap structure as a static linear array pretty simply

I'm personally very fond of self-balancing AVL trees and use them quite often, but QDOS cannot be changed anyway and even for SMSQ/E it would be a compatibility nightmare to change the heap handling.

[pjw]

<>Here's a basic program I use to debug heap problems, it dumps the heap structure into a file. Maybe it can help you:<>

Nice one! But seriously Marcel, GO TO?
Running this on my system right after boot, I see 600! smallish heap entries for qascade v1s14. Nothing else running comes anywhere close. I presume Qascade is compiled with C68? Ive always suspected, but never knew for sure until now..

[mk79]

<>Here's a basic program I use to debug heap problems, it dumps the heap structure into a file. Maybe it can help you:<>

Nice one! But seriously Marcel, GO TO?

This is quick&dirty debug code, not production quality

Running this on my system right after boot, I see 600! smallish heap entries for qascade v1s14. Nothing else running comes anywhere close. I presume Qascade is compiled with C68? Ive always suspected, but never knew for sure until now..

Yes, qascade is compiled using Q68.

[Derek_Stewart]

Hi Marcus,

I am not sure that Qascade was compiled on a Q68... maybe C68 perhaps.

Would this HEAP problem be associated with Digital C, maybe trying reducing the heap size may help.

[bwinkel67]

I think you're missing a point here - namely what the task of an OS is on the one hand, and how "well-behaving applications" should use that services OTOH.

QDOS has been written under the assumption that jobs would try and use the memory services of the OS in the most cooperative way possible: That is, the way C68 does it. What Digital C seems to do is not very cooperative: The system used (allocating lots of tiny chunks all over the place) there is bound to cause memory fragmentation big time on a multi-tasking system. And, as the unexpanded QL is severely memory-limited, that leads to exhausted heap space very early.

Knowing Digital 'C' SE is inefficient is good info though. It means I'll need to do a better job in my implementation as currently I'm rather lazy in how I use dynamic memory. Since I'm doing a lot of allocates and free I may implement my own internal heap and just do big allocates in the common heap and then deal with it internally. I think I can pretty easily create a heap data structure in a linear array with the occasional resize when it runs out of space and I don't think it would add much overhead. Then I just return address pointers within the larger chunk. Wouldn't slow things down and likely speed things up a trivial amount. The interesting bit is collecting free chunks that are next to each other to create bigger contiguous blocks but I was thinking if I have a back-ptr for each chunk (an extra byte or two at the beginning or end) I can keep track of where each chunk is in my heap and when I free something I can find where my neighbor is, resize it and then reheapify and voila, I have merged two chunks in log(n) time.

In fact I should just grab a 16K chunk and be done with it since I'm trying to simulate a ZX81. That would keep common heap clean and force me to do all my work within that 16K chunk like the ZX81 does. Perhaps an option eventually where one can increase the seize to 32K, etc, depending on given memory. So it's good to understand both the QDOS common heap and how Digital 'C' SE deals with it.

[bwinkel67]

The only internal difference that I can deduce is that there is a while loop using fseek() to figure out the size of a file (doing so in 64 byte blocks)

I must say I find it almost comical that the provided LIBC doesn't provide a better way.

Yeah, it's weird. The only file I/O they provided besides opening, seeking, and closing is delete...why delete?

Only way I see is

Code: Select all

long src[8];
long ret[8];

src[0] = 0x42;
src[1] = -1;
src[3] = -1;
src[4] = fd;
trap3(src, ret);
// file size now in ret[1]

Ha, I had looked at using that trap but somewhere it read I needed a 64 byte buffer (on top of the src and ret arrays) and so it seemed less trivial than what you just wrote so I will give it a go. I'm already using trap3 for getting I/O and this seems just as simple -- thanks!

Is it really worth putting up with this very limited compiler?

I like optimization problems and they can formulate themselves differently in different contexts. Using a limited resource and finding ways around obstacles can be a good intellectual challenge. The idea of implementing my own internal heap structure is getting more appealing (I've taught the various ways they formulate but don't get much use in practical circumstances). It also keeps the mind off of the current news cycle and in the US it ain't good presently. Plus, my server at school crashed a month ago and I can't get in there as the entire A/C unit is being replaced and they don't want anyone in there until completed so I can't work on research which is what summers are for (I do speech recognition, another challenging optimization task wrapped in probability theory).

before it does the malloc (and it fails on the malloc before it actually reads in the file). So I speculate that QDOS has read in part of the file while fseeking through it and is using part of the heap leaving the file in cache.

File caching is done in the slave blocks, which reside in the "free" memory, not in the heap. What will get allocated in the heap is the channel block, i.e. when opening the file. I'd be VERY surprised if seeking had any impact.

Oh, so literally a small chunk of memory is fragmenting the heap for me in that instance...D'oh. I will look to use the trap3 to get file size and allocate memory before opening. I think I'll get the whole thing implemented (still need to add floating point) before I optimize its memory usage into a single 16K chunk with its own internal heap.

Many thanks!

[mk79]

Ha, I had looked at using that trap but somewhere it read I needed a 64 byte buffer (on top of the src and ret arrays) and so it seemed less trivial than what you just wrote so I will give it a go. I'm already using trap3 for getting I/O and this seems just as simple -- thanks!

It's pure theory based on the source code but I'm about 95% certain that it should work Do tell if it did.

I like optimization problems and they can formulate themselves differently in different contexts.

All right, I respect that

(I do speech recognition, another challenging optimization task wrapped in probability theory).

Cool, sounds fun. My work is much more mundane and even though I've had some ideas unfortunately I don't have the time to get into any of the AI stuff.

Cheers, Marcel

[mk79]

Hi Marcus,

Good one

I am not sure that Qascade was compiled on a Q68... maybe C68 perhaps.

lol, right. When I compiled the latest Qascade version Q68 didn't even exist

[bwinkel67]

Ha, I had looked at using that trap but somewhere it read I needed a 64 byte buffer (on top of the src and ret arrays) and so it seemed less trivial than what you just wrote so I will give it a go. I'm already using trap3 for getting I/O and this seems just as simple -- thanks!

It's pure theory based on the source code but I'm about 95% certain that it should work Do tell if it did.l

I did get it to work. I had to use MAXINT instead of -1 for position but got it to seek to the end of the file and it then sets it to filesize. It looks like Digital 'C' SE's fseek() is actually doing the same thing (setting up the same trap3 call) but there is no way to get the register value to get the size. I had actually looked at the 0x47 trap3 which reads in the header and thus needs 64 bytes of buffer space.

I do still need to do two seeks (or two trap3 calls) since I need to seek back to 0...for a while I couldn't figure out why I was getting the right size and not reading in the file :-/