Xref: utzoo comp.lang.c:13869 comp.lang.c++:1891
Path: utzoo!utgpu!attcan!uunet!pyrdc!pyrnj!rutgers!ucla-cs!admin.cognet.ucla.edu!casey
From: casey@admin.cognet.ucla.edu (Casey Leedom)
Newsgroups: comp.lang.c,comp.lang.c++
Subject: Re: Matrices
Keywords: Matrix Operations
Message-ID: <17601@shemp.CS.UCLA.EDU>
Date: 7 Nov 88 04:55:24 GMT
References: <183@rubmez.UUCP> <985@oswego.Oswego.EDU>
Sender: news@CS.UCLA.EDU
Reply-To: casey@cs.ucla.edu (Casey Leedom)
Organization: UCLA Cognitive Science Program
Lines: 97

[Doug Lea talks about matrix library he and several others are working on.
In particular he says that coming up with a matrix representations that
are flexible and efficient is very difficult.]

  Perhaps Doug or someone else could help us with a problem of a somewhat
similar nature.  We're developing a C++ development environment for
programming the Connection Machine (CM) from Thinking Machines
Incorporated in Massachusetts.

  First off, any CM object always has two parts: the actual storage used
by the object on the CM, and various description information stored on
the front end (FE) machine (the CM is driven by a FE computer which feeds
the CM a stream of CM instructions).  The CM object storage is obvious.
The FE object description is minimally the address of the objects storage
on the CM.

  The CM supports integers of *any* bit length.  We would like to define
a C++ class to support this which doesn't suffer from stupid performance
hits.  Specifically, we'd like to be able to do something like the
following:

	CM_int a(8, 0), b(16, 0), c(32, 0);

where the first numbers are the sizes of the declared objects.  It's easy
to see that we can simply add a length to the address description set,
but this incurs a performance hit.  Most objects are fully defined at
compile time.  In particular, we know that ``a'' (above) is 8 bits long.
The storage to remember this at run time is totally useless.  But this
isn't much of a concern for us.  We're much more concerned with the run
time checking used to determine which particular CM instruction to use
to, say, add two CM_ints.

  Essentially what we're looking for are compile time attributes of
objects.  One obvious way of doing this is to simply invent a bunch of
subclasses.  E.g.:

	CM_int_8 a(0);
	CM_int_16 b(0);
	CM_int_32 c(0);

but this requires that we define all possible CM_int_* subclasses (of
which there are literally thousands possible).  So then we use a CPP
macro to create subclasses, but it starts getting ugly here.

  I'll end this with a concrete example to try to forestall
miscommunication.  The CM implements two signed integer addition
instructions.  One is a three address, single length (the two sources and
the destination are all the same length), the other is three addresses
and three lengths (both sources and the destination may all be different
lengths).

  We could always use the second, but we take a bad performance hit if
we do.  We could always check the lengths of the arguments to "+" at run
time to decide which to use, but this uses up time on the front end (and,
as has already been pointed out above, is almost always already known at
compile time).  We could depend on automatic coersion to larger integer
subclasses and then always use the first CM instruction, but that
eliminates the speed advantage of letting the CM do it's work properly.

  We'd like to be able to implement "+" something like the following:

	inline CM_int operator+(CM_int &a, CM_int &b)
	{
		if (sizeof(a) == sizeof(b))
			return(CM_int(sizeof(a), CM_s_add_1L(...)));
		else
			return(CM_int(max(sizeof(a), sizeof(b),
				CM_s_add_3L(...)));
	}

Where the ``sizeof''s are only used to give you an impression of what we
want (this is actually true of the entire outline above).  Obviously it
would be acceptable to generate stupid code and then let the optimizer
toss null branches, etc.

  The reason I say that Doug's matrix problem has some of the same
problems can be seen in the simple case of matrix multiplication.  E.g.:

	matrix a(M,N), b(N,P);

obviously it's going to be impossible to declare all possible matrix
sizes/shapes.  Therefore, we have to declare the size/shape of each
matrix at object declaration time.  Also, most of the time we know
everything about the size/shape of a matrix at compile time.

  It should be perfectly possible to detect whether ``a*b'' is legal at
compile time for most matrix objects.  While this could easily be done at
run time via descriptors, this suffers both a performance penalty *and*
loses the benefits of strict compile time type checking.  A particular
line of code may well compile correctly, but never be executed till some
critical point of a programs life time causing the program to fail.

  Oh well, I've dribbled on enough here.  We're probably just being
stupid.  Hopefully someone will point out an obvious solution.  Flames
for stupidity welcome.

Casey