Stack allocated variable length arrays

[Barry Schwartz]

The notation

var X = @[type][n] ()

seems to give me a match error in pats_typerase_dynexp.dats if n is an
unknown value at compile time (a ‘variable’). Is this C99-like
notation not supported? Do I have to use (yuck) alloca?

[gmhwxi]

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 ...

3. 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]

[Barry Schwartz]

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.

[Barry Schwartz]

I wrote:
> 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.

To give you an idea of what sort of code I inherited and what my goals
for ATS would be: before I modified that part of the program, the
FontForge code was storing data in the padding between struct
fields. And this wasn’t even a bug. That’s just the type of code I
deal with and want to fix using a tool like ATS.

[Hongwei Xi]

Then would you consider alloca an acceptable solution in your case?

--
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.

[Barry Schwartz]

Hongwei Xi <gmh...@gmail.com> skribis:

> Then would you consider alloca an acceptable solution in your case?

I suppose if one has to, but AFAIK alloca is not according to any of
the standards, and I am used to having C99 features, which are
standardized. Therefore I would be much more likely to avoid something
that explicitly invokes alloca. The only compilers that do not
support most of C99 are ones I do not care about at all.

It is, after all, nearly 2015, and C99 is the _previous_ standard,
having been published 14 years and 11 months ago, already.

(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. This is what one has to do,
anyway, to implement alloca on a 3B or some other architecture that
has separately located stack frames; see Gwyn’s PD alloca.c in Gnulib
and numerous other GNU packages, which uses malloc this way.)

[gmhwxi]

>>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.

[Barry Schwartz]

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

> 3. 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.

[Barry Schwartz]

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

> 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.

Expect much worse with the continued use of C and the nearly complete
ignorance that such bugs are artifacts of inadequate programming
tools; nearly always we see the invisible programmer insulted,
instead. So bandaid measures are introduced, as if this were
addressing the problem.

For instance, starting with recent GCC versions Gentoo turns on
-fstack-protector by default, which means that people who do not
explicitly override this are building nearly all their software so
that it does shenanigans just to raise and lower the stack. This
‘canary’ stuff is going into Linux kernels these days, too. Gentoo
already enabled various bandaids in the C library in a way that is
more difficult to bypass.

I used to think well of such measures but now think they are mostly
encouraging people to continue using inadequate tools.

(BTW IMO using malloc in place of stack isn’t a terrible thing now
that system mallocs are very fast and provide plenty of space.)

[gmhwxi]

>>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 :)

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) :)

[Barry Schwartz]

gmhwxi <gmh...@gmail.com> skribis:
> I am not against alloca(1024) but I am against (1024*1024) :)

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.

[gmhwxi]

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.

[Shea Levy]

I wonder, has profiling indicated that malloc is the bottleneck for
these functions?

> --
> 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.