From: rbe@yrloc.ipsa.reuter.COM (Robert Bernecky)
Subject: Re: j 5.1, pc, 386
Reply-To: rbe@yrloc.ipsa.reuter.COM (Robert Bernecky)
Organization: Snake Island Research Inc, Toronto
Date: Sun, 27 Sep 92 18:42:36 GMT

In article <1992Sep26.211848.14906@yrloc.ipsa.reuter.COM> dgil@ipsaint.ipsa.reuter.COM (Gillett, David) writes:
>
>
>     Rob Bernecky has suggested a couple of ways in which J's storage 
      ^^^^^^^^^^^^

Is this a recommendation?


>management could be improved over raw use of the local C compiler's malloc() 
>and free() implementation.
>     Three of his four suggestions do nothing about heap fragmentation. Unless 
>that is addressed, it will normally be the case that total heap space available 
>is greater -- perhaps by an order of magnitude! -- than the size of the largest 
>object which can be created.  It seems to me that either number might be needed 
>by the programmer, so quadWAprime should probably return both values -- which 
>makes it no longer strictly analogous to quadWA.


The response was directed at the "how do I get a Quadwa facility in J?" 
question. As usual in the language design biz, the person who "wants
facility X" usually has another, unasked question about another, unspecified,
problem. In this case, it's heap fragmentation and virtual storage problems.

Without looking closer at how J dereferences pointers to array storage,
I can't say how hard this would be, but here's a potential solution to the
"heap fragmentation problem":

a. Allocate a big mess of store from the heap, using malloc, as suggested
   in a previous posting. Allocate all arrays from this heap. 
   When allocation fails, due to not a big enough hunk of space left in
   the "workspace", defragment the workspace, by moving things downto
   the bottom (or top). Failure to obtain enough space then means
   that your workspace is too small. Whether you reallocate or 
   signal workspace full is a matter of taste.

b. Defragmentation is traditionally done in APL intepreters by performing
   all array references indirectly through a pointer table. The arrays
   contain a descriptor which in turn points back to the pointer table,
   so that when the storage compacter moves an array, its location in
   the pointer table can be updated immediately to reflect the new
   location of the array. In the special case where there is only one
   reference to an array (such as a temp), the pointer/backpointer pair
   can reside on the stack, with no loss in generality.

The cost of this an an extra storage reference while dereferencing 
array pointers, and a fair bit of caution when performing storage
allocation during an operation, since your function arguments may have
moved over the allocation call, due to compaction.
This is a traditional favorite bug in APL systems.


Now, as to the "amount of wasted space" issue:

In most APL interpreters, you want to have AT LEAST 3-4 times the space
required for the largest object you want to manipulate. Sometimes, this
threshold can be reduced, but by and large, it's impractical to do so,
and often results in much headbanging by the application programmer trying
to avoid ws full. Why is this?

Consider a typical dyadic verb, such as membership or indexof:

You need:
a. Space for the left argument.
b. Space for the right argument.
c. Space for the result (Although results can sometimes overlay an
   argument, it is the exception rather than the rule in functional programming
   languages to be able to do so).
d. Space for temps required by the function. In the case of the above,
   you want space for hash tables, upgrade tables, etc., to make the
   thing go fast. These tend to be integer tables about twice the
   size of one argument for the above primitives.

So, a factor of 10 is only about twice the ceiling height in the case here.
That offers room for growth in the application, as well. 

>to allocate ALL available heap memory to the heap manager, and have it dole it 
>out to the rest of the interpreter as necessary.

Not really. I often run applications where I have a good feeling for the
space required by it. Allocation of all heap memory is overkill. By
limiting my storage requirements by stating "This application runs in
a 2 megabyte workspace", I get the advantage of improved performance,
no worry about fragmentation, and leave the remainder of store available to
other tasks in the system.

>     I can see two down sides to this.  One is that, particularly on small 
>systems, heap space (even virtual heap space) tends to be shared out to all 
>processes as requested.  Grabbing all of a system resource like this is not 
>multitasking-friendly.  (You can solve this for some particular target system, 
>but I don't think it can be portable.)

Agreed. Don't do it.


>     The other difficulty is that if every J task requires, from the system's 
>perspective, the maximum possible memory allocation, small-to-medium size J 
>applications risk taking an unwarranted performance hit from the system's 
>memory manager.  (Sure, you can tell people that the fix for their J problems 
>is to get an OS that's smart enough to out-guess programs that allocate memory
>and then don't "really" use it....)

Any virtual storage system worth its salt doesn't allocate hard memory pages
to a task until you "touch" the page in question by referencing it or
storing into it. There is a wee cost involved in page table space, but
this is not excessive today.



>
>     I think that the best that can be done, practically and portably, is
>something like a primitive which takes a size and returns a boolean:  If I
>were to try to create an array of size n, would there be enough storage to do
>that?  A portable implementation could just see if malloc() succeeded, and if
>so then free() the space again; a tuned implementation could conduct its own
>negotiations with the system heap facilities.


Nah. In a real system, there is no guarantee that that approach is race free.
Suppose that another task grabs the store between the time of your
query and the time of the malloc. Since malloc returns a "worked/didn't
work" signal anyway, what's the point?



Robert Bernecky      rbe@yrloc.ipsa.reuter.com  bernecky@itrchq.itrc.on.ca 
Snake Island Research Inc  (416) 368-6944   FAX: (416) 360-4694 
18 Fifth Street, Ward's Island
Toronto, Ontario M5J 2B9 
Canada
Newsgroups:   comp.lang.apl