[r6rs-discuss] Re: [Formal] bytevector aliasing severely impedes optimizations (Sam TH)

From: Bradley Lucier <lucier>
Date: Mon Mar 5 12:42:46 2007

On Mar 5, 2007, at 10:37 AM, r6rs-discuss-request_at_lists.r6rs.org wrote:

> Message: 5
> Date: Mon, 5 Mar 2007 08:36:59 -0500
> From: "Sam TH" <samth_at_ccs.neu.edu>
> Subject: Re: [r6rs-discuss] [Formal] bytevector aliasing severely
> impedes optimizations
> To: r6rs-discuss_at_lists.r6rs.org
> Message-ID:
> <63bb19ae0703050536x528f2957u7213133c8d20a883_at_mail.gmail.com>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
> On 3/3/07, Bradley Lucier <lucier_at_math.purdue.edu> wrote:
>> By having only one type of bytevector that aliases all of 32-bit
>> integers, 64-bit integers, 32-bit IEEE 754 numbers, and 64-bit IEEE
>> 754 numbers, optimization opportunities for compilers are severely
>> degraded. One does not know, for example, whether storing a 64-bit
>> IEEE double into bytevector A changes the value of a 32-bit integer
>> read from bytevector B without actually checking whether A and B are
>> the same objects and whether the range of indices used to access A
>> and B overlap.
>>
>> This very problem has been recognized by recent C standards, which
>> forbid such types of aliasing except by going through (char *). (The
>> proposed R6RS bytevectors would propose a problem for more than
>> Scheme->C compilers, however---it is a library design problem.) It
>> could be said by analogy that the proposed R6RS libraries offer
>> *only* a (char*) (more tamed than in C), which solves one small
>> class of problems (how to allow semi-portable, low-level translation
>> between data types that can be considered sequences of bytes; how to
>> write I/O device drivers; ...) while completely ignoring a much
>> larger and more important class of problems (allowing fast and
>> memory-
>> efficient access to large arrays of homogeneous numerical data).
>
> Is your suggestion that Scheme compilers be allowed to assume that two
> bytevectors do not alias, without either proving this statically or
> checking it dynamically?

No.

> If there is another way to deal with aliasing, I'd be interested to
> hear it.

The C standard says (roughly) that if you access memory by
dereferencing a (double *) then you cannot access the same memory by
dereferencing, e.g., a (int *); you can do anything with a (char *).
This applies to arrays, too.

Thus, you can assume that if you are doing sparse matrix-vector
multiply, and reading an integer vector of indices, and writing to a
64-bit floating-point vectors of values, that saving a floating-point
value into the vector of results won't change the vector of integer
indices.

If, instead of bytevectors, R6RS had homogenous vectors as in SRFI 4,
this could be inferred from the text of the program.

Brad
Received on Mon Mar 05 2007 - 12:42:40 UTC