Discussion:
Memory, objects, and TCollections
(too old to reply)
Jim Leonard
2012-07-22 18:02:36 UTC
Permalink
I'm starting a new hobby project that has a requirement of running in
16-bit DOS. The most elegant way for this project to work with
information internally is a TSortedCollection, but as far as I can
tell, these are limited to using the heap for storage. (They return
pointers to objects, and objects are stored in main RAM on the heap.)
At some point, I will run out of the lower 640K DOS memory to hold all
my objects.

What is the recommended way to get past this? I can't compile to 286
protected mode because I'm working with some pretty hairy inline
assembler (that I CANNOT change) that doesn't work in protected mode.
I could store my objects on an EMS or XMS stream (or even disk if I'm
desperate), but manipulating them (ie. sorting them, insertion/
deletion) could get unacceptably slow. How did people solve
TCollection/Object memory issues in the past?
Marco van de Voort
2012-07-22 21:07:52 UTC
Permalink
Post by Jim Leonard
tell, these are limited to using the heap for storage. (They return
pointers to objects, and objects are stored in main RAM on the heap.)
At some point, I will run out of the lower 640K DOS memory to hold all
my objects.
That points to 16-bit protected mode. But you rule that out also.
Post by Jim Leonard
What is the recommended way to get past this? I can't compile to 286
protected mode because I'm working with some pretty hairy inline
assembler (that I CANNOT change) that doesn't work in protected mode.
I could store my objects on an EMS or XMS stream (or even disk if I'm
desperate), but manipulating them (ie. sorting them, insertion/
deletion) could get unacceptably slow. How did people solve
TCollection/Object memory issues in the past?
By not setting umpteen conflicting borderconditions :-)

Since the real mode TP memory model is fundamentally limited to 1MB, there
is not much you can do easily.

Basically all I can think of is using upper memory blocks (since the limit
is 1MB not 640k) and (data) overlays.

Overlay (swapping in blocks in and out of high mem) is rarely fully
transparent, since simply not everything can't be in addressable memory at
the same time, and this boundery condition must be manually enforced.

One could e.g. stuff very large arrays in EMS, and map the relevant parts
in when needed.

In theory one could also use UMBS as real heap, but that would require
modifying the heapmanager. Maybe there already is such one in SWAG.

In short, there was a reason why people were happy to go from real mode
towards 32-bit and protected mode. This is the reason, memory management
this way is manual (and thus time intensive and errorprone) and often not
very reusable from application to application.
Robert AH Prins
2012-07-23 02:31:55 UTC
Permalink
Post by Marco van de Voort
Post by Jim Leonard
tell, these are limited to using the heap for storage. (They return
pointers to objects, and objects are stored in main RAM on the heap.)
At some point, I will run out of the lower 640K DOS memory to hold all
my objects.
That points to 16-bit protected mode. But you rule that out also.
Post by Jim Leonard
What is the recommended way to get past this? I can't compile to 286
protected mode because I'm working with some pretty hairy inline
assembler (that I CANNOT change) that doesn't work in protected mode.
I could store my objects on an EMS or XMS stream (or even disk if I'm
desperate), but manipulating them (ie. sorting them, insertion/
deletion) could get unacceptably slow. How did people solve
TCollection/Object memory issues in the past?
By not setting umpteen conflicting borderconditions :-)
Since the real mode TP memory model is fundamentally limited to 1MB, there
is not much you can do easily.
Basically all I can think of is using upper memory blocks (since the limit
is 1MB not 640k) and (data) overlays.
Overlay (swapping in blocks in and out of high mem) is rarely fully
transparent, since simply not everything can't be in addressable memory at
the same time, and this boundery condition must be manually enforced.
One could e.g. stuff very large arrays in EMS, and map the relevant parts
in when needed.
In theory one could also use UMBS as real heap, but that would require
modifying the heapmanager. Maybe there already is such one in SWAG.
There is a unit in SWAG that does this, actually, several near identical ones.
I've assembler-ized one of them and used it until I made the switch to 32-bit.

There's also a unit to store data in XMS. It's not in SWAG (IIRC), but you might
find it on Garbo, or rather a mirror of Garbo, as Garbo itself is dead (thanks
to some bean-counters).
Post by Marco van de Voort
In short, there was a reason why people were happy to go from real mode
towards 32-bit and protected mode. This is the reason, memory management
this way is manual (and thus time intensive and errorprone) and often not
very reusable from application to application.
+1

Robert
--
Robert AH Prins
robert(a)prino(d)org
Jim Leonard
2012-07-23 18:33:35 UTC
Permalink
Post by Marco van de Voort
In short, there was a reason why people were happy to go from real mode
towards 32-bit and protected mode.  This is the reason, memory management
this way is manual (and thus time intensive and errorprone) and often not
very reusable from application to application.
+1
I was afraid of this; thanks for all the suggestions. I already have
the ability to store objects in both an EMS and XMS stream, so I guess
I'll have rewrite the object management to use streams when the time
comes (a shame, since TSortedCollection really solves a lot of
problems for me, and stream-based access is going to be an order of
magnitude slower). Oh well!

When the project I'm working on is done, I'll post a short note about
it here.
Marco van de Voort
2012-07-24 16:20:50 UTC
Permalink
Post by Jim Leonard
Post by Marco van de Voort
very reusable from application to application.
+1
I was afraid of this; thanks for all the suggestions. I already have
the ability to store objects in both an EMS and XMS stream, so I guess
I'll have rewrite the object management to use streams when the time
comes (a shame, since TSortedCollection really solves a lot of
problems for me, and stream-based access is going to be an order of
magnitude slower). Oh well!
IMHO the objective should be to kill the legacy, not change good (abstract)
code to legacy ;-) IOW, time to bite the bullet and move into the 32-bit
space? (or be radical and move directly to 64-bit?)
Post by Jim Leonard
When the project I'm working on is done, I'll post a short note about
it here.
Note that most default ordered collections in TP and Delphi (resp. tsorted*,
tstringlist) do not scale very well beyond a few tens of thousands of
entries. The TP ones max out already on 16384 items though.

Inserting an item in larger collections becomes very slow because
it has to move (on average) n/2 items.

So if you want to go to that magnitude, there will be more rethinking
involved.
Jim Leonard
2012-07-26 21:19:48 UTC
Permalink
Post by Marco van de Voort
IMHO the objective should be to kill the legacy, not change good (abstract)
code to legacy ;-) IOW, time to bite the bullet and move into the 32-bit
space? (or be radical and move directly to 64-bit?)
This project must run on 808x systems, so no.
Post by Marco van de Voort
Inserting an item in larger collections becomes very slow because
it has to move (on average) n/2 items.
Right, but it's only moving a 4-byte pointer so it's not that bad. I have the RTL and I peeked at the implementation -- it's just an array of pointers.
Marco van de Voort
2012-07-27 10:46:38 UTC
Permalink
Post by Jim Leonard
This project must run on 808x systems, so no.
Dataintensive apps with those limitations, that is setting yourself up for
disaster, but let's take it as a given.

One of the problems then is that the hardwiring of ems/xms support, while
8086 compatible also adds limitations. You can't rely on it too much and
essentially use mainmem as a paging buffer, because what if it is missing or
very limited in size like on XTs and older 286s?
Post by Jim Leonard
Post by Marco van de Voort
Inserting an item in larger collections becomes very slow because
it has to move (on average) n/2 items.
Right, but it's only moving a 4-byte pointer so it's not that bad. I have the RTL and I peeked at the implementation -- it's just an array of pointers.
That should have been on /ordered/ collections.

If you load unsorted data and insert them into a TP TSorted* or Delphi TStringlist,
since the average item will insert in the middle of the list, there are
sizeof(pointer)* (N/2) bytes to move to make room for them.

So for N items that becomes a sizeof(pointer)*N^2/2 iow O(N^2) operation.

But as said typically you only start to notice it at hundreds of thousands
of items, and afaik standard TP datatypes are limited to 64k, so 16384 items
max.
Jim Leonard
2012-07-23 18:42:46 UTC
Permalink
Post by Marco van de Voort
Basically all I can think of is using upper memory blocks (since the limit
is 1MB not 640k) and (data) overlays.
You can use overlays for data?
Marco van de Voort
2012-07-25 12:10:12 UTC
Permalink
Post by Jim Leonard
Post by Marco van de Voort
Basically all I can think of is using upper memory blocks (since the limit
is 1MB not 640k) and (data) overlays.
You can use overlays for data?
Same principle. Code overlay is based that some code is only needed at
certain times. One can do the same for data, page data into the EMS
pageframe when needed. This is mostly explicit though. (iow you have the
responsibility to do it at the same time). XMS and EMS arrays are more or
less based on this.
Jim Leonard
2012-07-26 21:21:49 UTC
Permalink
> You can use overlays for data?
Same principle. Code overlay is based that some code is only needed at
certain times. One can do the same for data, page data into the EMS
pageframe when needed. This is mostly explicit though. (iow you have the
responsibility to do it at the same time). XMS and EMS arrays are more or
less based on this.
I thought you meant you could use the Overlay unit for overlaying data as well as code. You're just taking about paging data in and out as needed.

If I need to do this, I'll rewrite the entire data structure to use a stream. Orders of magnitude slower, but still better than paging data in from disk!
Marco van de Voort
2012-07-27 11:13:06 UTC
Permalink
Post by Jim Leonard
Post by Marco van de Voort
Same principle. Code overlay is based that some code is only needed at
certain times. One can do the same for data, page data into the EMS
pageframe when needed. This is mostly explicit though. (iow you have the
responsibility to do it at the same time). XMS and EMS arrays are more or
less based on this.
I thought you meant you could use the Overlay unit for overlaying data as well as code. You're just taking about paging data in and out as needed.
I don't know the overlay unit that well. I spent only the beginnings of my 16-bit time with
TP(6 mostly), moving on to Topspeed Modula2 later. When that ended I came
back to FPC. So I'm not that deep into 16-bit specific TP issues. (including
286 real mode, which I used only once or twice).

I do know that some overlay systems can also swap out global variables
that are in the implementation of units in an overlay. I don't know if TP
can.

I think what I'm refering to is what XMS/EMSarray are in TP. You just store
pointers into the (EMS) pageframe or XMS buffer, and structure your program
so that it makes sure that the appropriate memory is mapped in.

My main adastructure was a "larger than 64k array" (a block>64k allocated and then
walked by manipulating the segment part of the pointer) that held pointers
to the data. (so that I could have more than 16384 elemnents)

The pointers to the data contained the block number of the ems frame to map
in in the segment part.

So accessing such a pointer was something like

blocknr:=seg(myptr);
if blocknr<>currentblocknr then
begin
mapin(blocknr);
currentblocknr:=blocknr;
end;
segmentof(myptr):=segmentemspageframe; // I don't even know how to do this anymore

access(myptr);


However when you do a lot of random access this can be slow in theory. IIRC
I did mergesorts the first time for the bulk of the data, and cached that on
disk, adding only most recent mutations on every run. The mergesort had a
naieve fallback to disk only in case there was not enough memory (the in
memory sorting was faster but required twice the space)

This made sure that the number of blockswaps was in the magnitude of the
64kb/sizeof(data)

But this was all in 486, early pentium times when even older machines were
at least 386's with 4MB. Though a brief while memory became urgent again
because people insisted on running under Windows (3.x and even 95) on
machines that could barely run it, not leaving much memory for applications.

My favorate deployment destination was DV (DesqView) or DV/X.

I maintained that application a while in 16-bit after I moved to 32-bit
because it was for a market (BBSes) that didn't warrant rearchitecting.

And currently I happen to be thinking about making a generics based
tstringlist/tstringcollection type for FPC/Delphi that has proper
insertion behaviour over 4 billion elements :-)

Loading...