Stack allocated variable length arrays

Google Group
1

Here is my rationale not supporting it:

  1. To me, it is always safer to malloc
    if [n] is unknown at compile-time unless…

  2. Unless n is small. Say n <= 1024. Then you can do

val () = assertloc (n <= 1024)
var X = @[type]1024

There is a bit waste but …

  1. If your C compiler supports it, then you can do it in C.
    More precisely, foo in the following code can be implemented
    in C and foo2 can be implemented in ATS.

fun
foo{n:nat}
(
n: int(n)
) : void = let
//
var A = @[type]n
//
in
foo2 (A, n)
end // end of [foo]

2

I wonder, has profiling indicated that malloc is the bottleneck for
these functions?On Fri, Oct 31, 2014 at 10:34:42PM -0500, Barry Schwartz wrote:

gmhwxi gmh...@gmail.com skribis:

I am not against alloca(1024) but I am against (1024*1024) :slight_smile:

My general view is a mathematical one, I suppose. If the size of the
allocation has some natural upper bound, then unless it really is
very, very big, it is ‘small’. For example: an array allocated for
some matrix operation in LAPACK or GSL; one should not normally have
to use Fortran’s ALLOCATE just to do that, without good cause. The
rank of the matrix likely is known; and, even if it is not, the
algorithm is likely to put a sharp limit on the rank.

C99, then, is to me just the copying over to C of a feature Fortran
already had, and which helped make the language much more pleasant to
use than it had been. Admittedly, in C this is less important, on
account of C having a long history of malloc, and not being used as
much for array algorithms.

A typical use of variable size arrays in my C code would be something
like a routine to do basis conversion of a bezier curve, or some other
polynomial operation. I do not know what the degree of the polynomials
will be; the most I have dealt with to date is about 9, but the future
may hold surprises. However, I do know that the degree cannot get very
large before there is no practical use. So the storage is ‘small’,
however much it happens to be.

If OTOH there is no natural limit, such as a general text string –
then, even if one expects it to be small, it is not ‘small’ in the
sense above. It needs a malloc.

–
You received this message because you are subscribed to the Google Groups “ats-lang-users” group.
To unsubscribe from this group and stop receiving emails from it, send an email to ats-lang-user...@googlegroups.com.
To post to this group, send email to ats-lan...@googlegroups.com.
Visit this group at http://groups.google.com/group/ats-lang-users.
To view this discussion on the web visit https://groups.google.com/d/msgid/ats-lang-users/20141101033441.GA25437%40crud.

3

Then would you consider alloca an acceptable solution in your case?On Fri, Oct 31, 2014 at 8:26 PM, Barry Schwartz < chemoe...@chemoelectric.org> wrote:

gmhwxi gmh...@gmail.com skribis:

Here is my rationale not supporting it:

  1. To me, it is always safer to malloc
    if [n] is unknown at compile-time unless…

Well, yeah, but I think I can come up with serious
counterarguments. For instance, people who write libraries should not
be deciding for the library’s user what constitutes a ‘small’ array;
they should simply be providing something to handle the case, if they
are inclined to do so.

What constitutes ‘small’ may also vary within a single
program. Something deeply recursive is completely different from a
non-recursive top-level procedure, for instance.

Finally, there are types of programming where one does not want
ordinary buffer overruns, dangling pointers, mallocs without free,
etc. – basically where a person wants to be helped avoid common
programming errors – but frankly doesn’t care much if the stack in
very remote instances might be exceeded, causing a segfault. I’m
thinking for instance of my Sorts Mill Tools, where my goal in perhaps
using ATS would be to slowly undo the extreme bugginess and
intractability of the C code I inherited from FontForge, but where I
don’t really care if it uses more stack than some person somewhere can
provide. I don’t even care about the buffer overruns and dangling
pointers, except that they represent actual bugs in the algorithms.

–
You received this message because you are subscribed to the Google Groups
“ats-lang-users” group.
To unsubscribe from this group and stop receiving emails from it, send an
email to ats-lang-user...@googlegroups.com.
To post to this group, send email to ats-lan...@googlegroups.com.
Visit this group at http://groups.google.com/group/ats-lang-users.
To view this discussion on the web visit
https://groups.google.com/d/msgid/ats-lang-users/20141101002614.GA13853%40crud
.

4

Now the compiler issues an error message indicating that
an array of undetermined size cannot be stack-allocated. It will
go into the next release.On Friday, October 31, 2014 10:02:14 PM UTC-4, Barry Schwartz wrote:

gmhwxi <gmh...@gmail.com <javascript:>> skribis:

  1. If your C compiler supports it, then you can do it in C.
    More precisely, foo in the following code can be implemented
    in C and foo2 can be implemented in ATS.

fun
foo{n:nat}
(
n: int(n)
) : void = let
//
var A = @[type]n
//
in
foo2 (A, n)
end // end of [foo]

BTW having it in a library, even if I have to write the library
myself, is fine. I don’t care if it is a language feature, although
there should be something better than the assertion failure in the
compiler. A specific explanation of the problem should be possible.

5

What constitutes ‘small’ may also vary within a single
program. Something deeply recursive is completely different from a
non-recursive top-level procedure, for instance.

When I used 1024 as a “small” number, I did have some justification
in my mind.

I think that President Lincoln said once that two things that are equal
should be treated equally. Maybe he didn’t :slight_smile:

In my mind, calling alloca is like making a function call. If we must
tolerate function calls, then alloca should be tolerated as well. Now
the real question is what the average size of a function frame is.
My thought was that having a hundred variables of word-size should
be enough.

So 100 * 8 bytes = 800 bytes. Rounding it up to the next power of 2
gives you 1024.

I am not against alloca(1024) but I am against alloca(1024*1024) :)On Friday, October 31, 2014 8:26:24 PM UTC-4, Barry Schwartz wrote:

gmhwxi <gmh...@gmail.com <javascript:>> skribis:

Here is my rationale not supporting it:

  1. To me, it is always safer to malloc
    if [n] is unknown at compile-time unless…

Well, yeah, but I think I can come up with serious
counterarguments. For instance, people who write libraries should not
be deciding for the library’s user what constitutes a ‘small’ array;
they should simply be providing something to handle the case, if they
are inclined to do so.

What constitutes ‘small’ may also vary within a single
program. Something deeply recursive is completely different from a
non-recursive top-level procedure, for instance.

Finally, there are types of programming where one does not want
ordinary buffer overruns, dangling pointers, mallocs without free,
etc. – basically where a person wants to be helped avoid common
programming errors – but frankly doesn’t care much if the stack in
very remote instances might be exceeded, causing a segfault. I’m
thinking for instance of my Sorts Mill Tools, where my goal in perhaps
using ATS would be to slowly undo the extreme bugginess and
intractability of the C code I inherited from FontForge, but where I
don’t really care if it uses more stack than some person somewhere can
provide. I don’t even care about the buffer overruns and dangling
pointers, except that they represent actual bugs in the algorithms.

6

Mind you, I would have to look it up, but probably the standard
allows C99 variable length arrays to be malloc’d, as long as it is
cleaned up when one leaves the scope

I think that any reasonable implementation of variable-length arrays
would just use malloc unless C99 stipulated that variable-length arrays
be stack-allocated (which is very unlikely).

Option 3 is always available to you.

I would just use malloc instead of variable-length arrays. If C had linear
types, then there would be very little reason for introducing
variable-length
arrays in the first place. New features take time to learn and they usually
slow
down everyone who does not use them. By the way, Linux is slowing down by
about 2% after each new release.